The halting problem and Gödel’s first incompleteness theorem are pretty much the same thing, and proofs of both involve self-reference. The proof of my thingy is much simpler and doesn’t involve self-reference, so it seems to be unrelated.
Apparently pointing out that things like the axiom of choice, the GCH, or other statements fall under Godel’s proof and are not self referential is not popular around here.
The theory is that there are statements that are true but undecidable with any sufficiently strong decider. Those statements are proofs of that theory, they (or their negation) are true but undecidable.
You are right, in that those statements do satisfy the conclusion, and I don’t see why you’re being downvoted. The difference between them and the original, self referential, statement is generality. For example:
You: I know that ZF set theory is incomplete because the axiom of choice cannot be proven within it.
Some other guy: Okay then, how about we add the axiom of choice as another axiom, maybe this new system will be complete?
You: Nope, it still can’t prove or disprove the continuum hypothesis.
SUG: So I’ll add that in as another axiom, maybe that will finally patch it?
You: Nope, still doesn’t work because …
SUG: But if I add that as an axiom as well...
Hopefully you can see why this might keep going for quite a while, and given that its quite difficult to prove a statement is undecidable you will run out eventually. There’s nothing you can do to convince him those undecidable statements are symptoms of a general problem rather than just one-time flaws.
Compare to this:
Godel: ZF set theory is not complete, because I have this self-referential construction of an unprovable statement.
SUG: But what if I add your statement as another axiom?
Godel: Then my proof still applies to this new system you created, and I can construct another, similar statement.
SUG: But what if I...
Godel: There’s no point in you trying to continue this, whatever system you create my theorem will always apply.
Apparently pointing out that things like the axiom of choice, the GCH, or other statements fall under Godel’s proof and are not self referential is not popular around here.
Let’s say for now that the proofs that AC and CH being undecidable in ZF—AC don’t have much to do with self-reference. (This seems sort of true to me but my understanding of the forcing technique is very poor.) How does this at all relate to the comments which got downvoted?
Those are statements that fall under what Godel proved, that is they are statements that are unprovable in ZF. So even though his statement doesn’t include self-reference it can still fall under Godel’s proof if his decoder is strong enough to determine what is an integer and what is not an integer. Self-referencing has nothing to do with it at all.
The best response that anyone has given to me about being wrong itself references back to the halting problem which is itself another formulation of Godel’s proof.
The correct response would be to point out that deciding if something is an integer can be accomplished with just addition and the example decoder proceeds in that manner rather than using any form of multiplication to determine what is an integer and what is not. Such a system is decidable but also infinite, so the string given is indeed decidable and given infinite time the decoder will halt (at infinity which isn’t part of the axiomization, which is where the problem lies). However, what throws me is “we can find such pathological inputs for any other encoding system,” which to me implies a stronger system is being thought of which would cause the system to hang for some inputs as it would fall under Godel’s proof.
It is very funny to me that my most downvoted comment isn’t about religion but is about Godel’s proof and no one gave a decent refutation of what I said.
Those are statements that fall under what Godel proved, that is they are statements that are unprovable in ZF. So even though his statement doesn’t include self-reference it can still fall under Godel’s proof if his decoder is strong enough to determine what is an integer and what is not an integer. Self-referencing has nothing to do with it at all.
The existence of specific undecidable statements in ZF or ZF—AC is a different sort of result than what Godel showed. That for example the continuum hypothesis is undecidable in ZFC is interesting because the continuum hypothesis is interesting. However, Godel’s theorems show that any consistent, axiomatizable systemn with all valid proofs recursively enumerable, that is strong enough to model a large chunk of N, must be incomplete. Exhibiting results like Cohen’s results about choice and the continuum hypothesis don’t give you the full result, they just show specific things about the system ZF. Indeed, if one didn’t know Godel’s theorems, and just knew about Cohen’s forcing results, you might be tempted to just throw in AC and GH as additional axioms if you didn’t have them already and then wonder if that system is complete.
It is very funny to me that my most downvoted comment isn’t about religion but is about Godel’s proof and no one gave a decent refutation of what I said.
People here have a very complicated set of attitudes. Even as many don’t want to bother talking about irrational aspects of religion, or engaging in religious individuals who are convinced that their religious view is somehow different from all the other religious views, people who are religious are that way due to a variety of very strong cognitive biases. So there’s some sympathy there. Getting math wrong and then insisting one is correct is just simple arrogance or at least, only Dunning-Kruger. There’s much less sympathy there. And yes, people have tried to explain why you were wrong albeit fairly succinctly.
However, what throws me is “we can find such pathological inputs for any other encoding system,” which to me implies a stronger system is being thought of which would cause the system to hang for some inputs as it would fall under Godel’s proof.
No, it is directly related and is exactly what Godel’s incompleteness theorem says without the self referential part. That is, this covers precisely the idea that if ones system is strong enough to determine the natural numbers then it will have statements that hang. The halting problem and the proof given are proofs that the theorem is true, not that those are the only examples of the theorem.
I really don’t think it is analogous. This result doesn’t exploit any interesting property that the integers have, unlike Godel, it just uses with their size. In addition, this one says ‘certain integers cannot be represented’ whereas Godel says ‘certain statements about integers cannot be proven’.
Godel was working under a philosophical system that assumed that everything could be deconstructed into first order logic. He disagreed and essentially wrote “this statement is false” as a proof that it can not be done. However, he also points out in his proof that there is an infinite number of such statements and that they do not have to be self-referential. Nor was what he was doing exploiting an interesting property of the integers but exploiting an interesting property of the system that creates the integers. This decoder can tell if something is an integer and tell one what integer it is, therefore it is able to evaluate everything needed for Godels proof, therefore it must have not only one but an infinite number of cases for which it hangs.
You’re wrong. You’re arguing from surface similarity rather than detailed internal workings, which is a big no-no in maths. I could have spent about five paragraphs breaking down your argument point by point, but you’ve made my life easy with that final line:
therefore it is able to evaluate everything needed for Godel’s proof, therefore it must have not only one but an infinite number of cases for which it hangs.
This is not the case, there is a simple counter-example. Unary code, in which 0 is 0, 1 is 10, 2 is 110, 3 is 1110, 15 is 1111111111111110, hangs on the string 111111.… and no other. The fact your argument led to this conclusion is a demonstration of how completely wrong it is.
No, it’s completely different. The representation of integers as bit strings doesn’t even have to be computable. There will always be an infinite string of bits of which no prefix represents any integer. This can be derived from König’s Lemma, which says that if a finitely branching tree has paths of all finite lengths, it has an infinite path. Consider the infinite binary tree with the out-edges of each node labelled 0 and 1. Chop off all the descendants of every node that represents an integer and consider the tree that remains. Since there are infinitely many integers, there must be such nodes of arbitrarily large depth. Therefore the tree contains an infinite path.
There are certainly connections. König’s Lemma isn’t constructively true, for example. That is, given a computable description of an infinite tree, the problem of finding an infinite path may not be computable. Imagine walking down the tree node by node—how can you tell whether you have stepped into a merely finite but enormously large subtree and have missed the infinite branch? Obviously, an oracle for the halting problem will solve that problem. I don’t know off-hand, or from thinking about it for five minutes, whether the reverse is the case, i.e. if the halting problem can be encoded as the problem of finding an infinite branch in some computable infinite tree.
Isn’t this what Godel said?
The informal part is kinda sorta reminiscent, but the formal part is too simple to be analogous to Gödel’s theorem.
But is it analogous to the halting problem?
The halting problem and Gödel’s first incompleteness theorem are pretty much the same thing, and proofs of both involve self-reference. The proof of my thingy is much simpler and doesn’t involve self-reference, so it seems to be unrelated.
Apparently pointing out that things like the axiom of choice, the GCH, or other statements fall under Godel’s proof and are not self referential is not popular around here.
How on earth do those at all “fall under Gödel’s proof”? Satisfying the conclusion of a theorem is not a meaningful relation to that theorem.
The theory is that there are statements that are true but undecidable with any sufficiently strong decider. Those statements are proofs of that theory, they (or their negation) are true but undecidable.
You are right, in that those statements do satisfy the conclusion, and I don’t see why you’re being downvoted. The difference between them and the original, self referential, statement is generality. For example:
You: I know that ZF set theory is incomplete because the axiom of choice cannot be proven within it.
Some other guy: Okay then, how about we add the axiom of choice as another axiom, maybe this new system will be complete?
You: Nope, it still can’t prove or disprove the continuum hypothesis.
SUG: So I’ll add that in as another axiom, maybe that will finally patch it?
You: Nope, still doesn’t work because …
SUG: But if I add that as an axiom as well...
Hopefully you can see why this might keep going for quite a while, and given that its quite difficult to prove a statement is undecidable you will run out eventually. There’s nothing you can do to convince him those undecidable statements are symptoms of a general problem rather than just one-time flaws.
Compare to this:
Godel: ZF set theory is not complete, because I have this self-referential construction of an unprovable statement.
SUG: But what if I add your statement as another axiom?
Godel: Then my proof still applies to this new system you created, and I can construct another, similar statement.
SUG: But what if I...
Godel: There’s no point in you trying to continue this, whatever system you create my theorem will always apply.
SUG: Drat! Foiled again!
(Why is some other guy SUG and not SOG? Oversight? Euphony?)
Because I evidently can’t spell :(
Let’s say for now that the proofs that AC and CH being undecidable in ZF—AC don’t have much to do with self-reference. (This seems sort of true to me but my understanding of the forcing technique is very poor.) How does this at all relate to the comments which got downvoted?
Those are statements that fall under what Godel proved, that is they are statements that are unprovable in ZF. So even though his statement doesn’t include self-reference it can still fall under Godel’s proof if his decoder is strong enough to determine what is an integer and what is not an integer. Self-referencing has nothing to do with it at all.
The best response that anyone has given to me about being wrong itself references back to the halting problem which is itself another formulation of Godel’s proof.
The correct response would be to point out that deciding if something is an integer can be accomplished with just addition and the example decoder proceeds in that manner rather than using any form of multiplication to determine what is an integer and what is not. Such a system is decidable but also infinite, so the string given is indeed decidable and given infinite time the decoder will halt (at infinity which isn’t part of the axiomization, which is where the problem lies). However, what throws me is “we can find such pathological inputs for any other encoding system,” which to me implies a stronger system is being thought of which would cause the system to hang for some inputs as it would fall under Godel’s proof.
It is very funny to me that my most downvoted comment isn’t about religion but is about Godel’s proof and no one gave a decent refutation of what I said.
The existence of specific undecidable statements in ZF or ZF—AC is a different sort of result than what Godel showed. That for example the continuum hypothesis is undecidable in ZFC is interesting because the continuum hypothesis is interesting. However, Godel’s theorems show that any consistent, axiomatizable systemn with all valid proofs recursively enumerable, that is strong enough to model a large chunk of N, must be incomplete. Exhibiting results like Cohen’s results about choice and the continuum hypothesis don’t give you the full result, they just show specific things about the system ZF. Indeed, if one didn’t know Godel’s theorems, and just knew about Cohen’s forcing results, you might be tempted to just throw in AC and GH as additional axioms if you didn’t have them already and then wonder if that system is complete.
People here have a very complicated set of attitudes. Even as many don’t want to bother talking about irrational aspects of religion, or engaging in religious individuals who are convinced that their religious view is somehow different from all the other religious views, people who are religious are that way due to a variety of very strong cognitive biases. So there’s some sympathy there. Getting math wrong and then insisting one is correct is just simple arrogance or at least, only Dunning-Kruger. There’s much less sympathy there. And yes, people have tried to explain why you were wrong albeit fairly succinctly.
Possibly.
No, it is directly related and is exactly what Godel’s incompleteness theorem says without the self referential part. That is, this covers precisely the idea that if ones system is strong enough to determine the natural numbers then it will have statements that hang. The halting problem and the proof given are proofs that the theorem is true, not that those are the only examples of the theorem.
I really don’t think it is analogous. This result doesn’t exploit any interesting property that the integers have, unlike Godel, it just uses with their size. In addition, this one says ‘certain integers cannot be represented’ whereas Godel says ‘certain statements about integers cannot be proven’.
Godel was working under a philosophical system that assumed that everything could be deconstructed into first order logic. He disagreed and essentially wrote “this statement is false” as a proof that it can not be done. However, he also points out in his proof that there is an infinite number of such statements and that they do not have to be self-referential. Nor was what he was doing exploiting an interesting property of the integers but exploiting an interesting property of the system that creates the integers. This decoder can tell if something is an integer and tell one what integer it is, therefore it is able to evaluate everything needed for Godels proof, therefore it must have not only one but an infinite number of cases for which it hangs.
You’re wrong. You’re arguing from surface similarity rather than detailed internal workings, which is a big no-no in maths. I could have spent about five paragraphs breaking down your argument point by point, but you’ve made my life easy with that final line:
This is not the case, there is a simple counter-example. Unary code, in which 0 is 0, 1 is 10, 2 is 110, 3 is 1110, 15 is 1111111111111110, hangs on the string 111111.… and no other. The fact your argument led to this conclusion is a demonstration of how completely wrong it is.
I got that part, I tried to explain further in another response. If this is all that is being said then I was wrong.
No, it’s completely different. The representation of integers as bit strings doesn’t even have to be computable. There will always be an infinite string of bits of which no prefix represents any integer. This can be derived from König’s Lemma, which says that if a finitely branching tree has paths of all finite lengths, it has an infinite path. Consider the infinite binary tree with the out-edges of each node labelled 0 and 1. Chop off all the descendants of every node that represents an integer and consider the tree that remains. Since there are infinitely many integers, there must be such nodes of arbitrarily large depth. Therefore the tree contains an infinite path.
Interesting, however it is my understanding that Konig’s lemma is related to the halting problem and the Wiki article agrees with me:
“Any such tree has a path computable from 0′, the canonical Turing complete set that can decide the halting problem.”
There are certainly connections. König’s Lemma isn’t constructively true, for example. That is, given a computable description of an infinite tree, the problem of finding an infinite path may not be computable. Imagine walking down the tree node by node—how can you tell whether you have stepped into a merely finite but enormously large subtree and have missed the infinite branch? Obviously, an oracle for the halting problem will solve that problem. I don’t know off-hand, or from thinking about it for five minutes, whether the reverse is the case, i.e. if the halting problem can be encoded as the problem of finding an infinite branch in some computable infinite tree.