7 ms·

Something I've always been curious about: does Gödel's theorem imply an infinity of inconsistent statements, or is the "this statement cannot be proven..." stat

Something I've always been curious about: does Gödel's theorem imply an infinity of inconsistent statements, or is the "this statement cannot be proven..." statement the only one? If it's the latter, then of what practical significance is the singularity? If a system is incomplete only in that regard, couldn't one redefine incompleteness to exclude it, and render the system complete for all practical purposes?

lqet 6y ago
From Wikipedia [0]: > The proof constructs a particular Gödel sentence for the system F, but there are infinitely many statements in the language of the system that share the same properties, such as the conjunction of the Gödel sentence and any logically valid sentence. [0] https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems#First_incompleteness_theorem https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_...
- vannevar 6y ago
  Yes, but the "such as..." example incorporates the original "this statement is not provable" statement, so it seems a bit of a cheat. If you could exclude that statement, it would also by definition exclude any compound versions of it. It seems to me that the issue boils down to, can "this statement is not provable" be leveraged to get to something like 1 + 1 = 3?
  - Corazoor 6y ago
    https://en.m.wikipedia.org/wiki/List_of_statements_independent_of_ZFC https://en.m.wikipedia.org/wiki/List_of_statements_independe... What Gödel did prove was that the above list of statements (and infinitely more) must exist. The special thing about his proof is indeed that it is recursive, i.e. adding another axiom can't fix the problem. But that was only necessary to prove that no formal system can be perfect, ever. Most undecidable problems can indeed be "fixed" by adding another axiom, but if you go beyond the ones of ZFC it becomes less clear which of the two alternatives is the "right" one...
  - jlokier 6y ago
    You can exclude any particular Gödel statement (a specific string of symbols), and as you're suggesting you can even exclude an infinite sequence of derived statements too, found by systematically adding the previous ones as axioms and applying a "Gödelisation" procedure to make another. But "this statement is not provable" isn't a statement in the logic. It's an English language description of a type of statement, one which has certain self-referential characteristics and shows us the incompleteness of the logic. There are an infinite number of statements in the logic which fit that type by having the relevant characteristics, and they aren't all obvious. The self-referential recursion implied in Gödel's construction is designed to make it obvious, but it can be encoded in less and less obvious ways while still containing an encoded image of themselves. You can even get to statements where the self-reference is encrypted (using an actual encryption algorithm)! Only a mathematician with the "secret key", or a clever super-mathematician with amazing brute-forcing skills, would be able to read the statement and confirm that it's true! And so "perceivable truth" is a thing too. Some truths are too complex for an ordinary mind to verify, yet still true. To exclude all self-referential statements in the logic of type "this statement is not provable", you would need a decision procedure to tell you which statements in the logic are those. Unfortunately you can't make such a decision procedure. It's very similar to Turing's halting problem. Just as you can't make a program which will take any input X and tell you if the program encoded as X will eventually terminate, you can't make a procedure which will take any statement S and tell you if it contains a fancy encoding of itself. There's just no way to do it. The fact it can be related to Turing's halting problem, which is about real machines and real algorithms running on them, may give you some idea that the core principle can be grounded in something quite down to earth which affects practical applications.
roywiggins 6y ago
if P is (this statement cannot be proved), then you can't prove A && P for any provable A, either. There's an infinite number of statements that can be proven (1=1, 2=2, 3=3... for starters) so there's an infinite number of statements that can't be proven. There are less trivial classes of statements that can't be proven. For instance, there's an infinite number of statements like "bit N of Chaitin's constant is 1" that cannot be proven (only a finite number of those statements are provable). https://en.wikipedia.org/wiki/Chaitin%27s_constant#Incompleteness_theorem_for_halting_probabilities https://en.wikipedia.org/wiki/Chaitin%27s_constant#Incomplet...
Shoop 6y ago
I think this partially answers your question: One thing people try to do to "fix" the incompleteness is to just add the Godel sentence as an axiom of the mathematical system. However, each time you do this, you can create yet another new Godel sentence for the new system with the new axiom. Since it's a diagonalization argument, no amount of adding of new axioms can permanently "fix" the system and make it complete -- there will always be new Godel sentence that is true but not provable.
cyphar 6y ago
Others have explained why you can't wave away inconsistency (principle of explosion) nor incompleteness (adding new axioms just creates a new axiomatic system with its own Godel sentences). However you might also find it interesting what incompletenesses exist in our own mathematical system (ZFC) -- the most well-known example is the Continuum Hypothesis[1]: > There is no set whose cardinality is strictly between that of the integers and the real numbers. Or to put it another way, there exists no intermediate type of infinity between countable infinities (the set of integers) and uncountable infinities (the set of real numbers). The CH is independent of ZFC -- both CH and its negation can be included as new axioms to ZFC and both versions are logically consistent if and only if ZFC is -- meaning that being able to prove the CH is an incompleteness in ZFC. [1]: https://en.wikipedia.org/wiki/Continuum_hypothesis https://en.wikipedia.org/wiki/Continuum_hypothesis
- tshaddox 6y ago
  I thought that independent (undecidable) statements are totally different than the Gödel sentences which demonstrate incompleteness. The latter is a statement which is true in the axiomatic system but which cannot be proven using the axiomatic system. The former is just a statement that essentially has no truth value in the axiomatic system.
  - deleted 6y ago
    [deleted]
  - a1369209993 6y ago
    Something being true in a axiomatic system is the same thing as it being provable; that's what "true" means. While a Godel statement for X can be interpreted as "X does not prove this statement", that interpretation inherently relies on the semantic implied by X. The Godel construction is systematic way of generating independent statements without needing to know anything specific about the axiomatic system.
    - tshaddox 6y ago
      Ah yes, you're right, and my lazy wording in the former comment is inaccurate. A Gödel sentence is just a statement written in the syntax of whatever formal system we're dealing with: generally, it's a statement that there exists no natural number which satisfies a particular property. The formal system cannot prove or disprove that statement. As you said, we tend to call the statement "true" because we know that the formal system itself was designed with the intention to describe natural numbers and arithmetic, and the statement was designed intentionally to refer indirectly to itself and claim its own unprovability. Since the statement is formally unprovable, we interpret it as being true. I had forgotten that Gödel actually showed that there are other interpretations of the formal system in which the Gödel statement is false.
diegof79 6y ago
It implies an infinity of inconsistent statements. I'm not a mathematician, but the way I understand it is to do an analogy with the halting problem: for any programming language that is powerful enough you can build a program where you don't know if it's going to halt or not. About avoiding singularities, the GEB book (Godel,Escher,Bach) mentions at the beginning: mathematicians like Russel tried to avoid paradoxes by moving them out of the system, but Godel shown that it doesn't work if you want a complete and consistent system (complete and consistent are technical terms, Wikipedia does a good explanation: https://en.wikipedia.org/wiki/Kurt_Gödel#Incompleteness_theorem https://en.wikipedia.org/wiki/Kurt_Gödel#Incompleteness_theo...). Also related to your question: https://en.wikipedia.org/wiki/Chaitin%27s_constant https://en.wikipedia.org/wiki/Chaitin%27s_constant Sorry if I don't get the technical terms right, hopefully someone else in HN can explain this better.
- qppo 6y ago
  I think the question is a bit more specific in the context of the halting problem We know by contradiction that we cannot write a program that determines if any program halts, if the program being checked also contains the program that determines if itself halts. Is this the only class of program that cannot be determined to halt?
  - Kranar 6y ago
    It's a tough question to answer because it highly depends on interpretation, after all what does it mean for a program to check whether it itself halts, what does it mean for a program to be self referential? There are many sneaky and indirect ways to make a program self referential. All undecidable languages that are recognizable in some sense contain a self referential program sneaking within it. This is because the halting problem is complete for its complexity class and hence any undecidable but recognizable language is Turing reducible to the halting problem. However for undecidable and unrecognizable languages, there are proofs of undecidability that are independent of diagonalization and instead use other proof techniques that in a very strong sense are entirely independent of self-reference. Of course this isn't a formal answer mostly because the idea of a self referential program is not a formal concept but there are techniques such as reverse mathematics [1] that can be used to determine a minimal set of axioms needed to prove a theorem along with proof techniques that depend on the Low basis theorem [2] that are able to prove that some languages are undecidable and unrecognizable that do not in any way depend on diagonalization, which is the proof technique that is associated with self referential programs. [1] https://en.wikipedia.org/wiki/Reverse_mathematics https://en.wikipedia.org/wiki/Reverse_mathematics [2] https://en.wikipedia.org/wiki/Low_basis_theorem https://en.wikipedia.org/wiki/Low_basis_theorem
redvenom 6y ago
Excellent question. It implies an infinite number of statements. For if T is such an incomplete theory and X is a statement true in some models of T and false in others, then T+X is also a theory that satisfies the same requirements as T in Godel's theorem. Therefore there is another statement Y that is true in some models of T+X and false in other models of T+X. But any model of T+X is a model of T so Y is true in some models of T and false in others. And it goes on...
ProfHewitt 6y ago
There are an infinitely many propositions that cannot be proved or disproved in foundational theories of Computer Science. However, foundational theories exclude the [Gödel 1831] proposition *I'mUnprovable* because including it would make the theories inconsistent for reasons mentioned elsewhere in this discussion.

lqet 6y ago

From Wikipedia [0]: > The proof constructs a particular Gödel sentence for the system F, but there are infinitely many statements in the language of the system that share the same properties, such as the conjunction of the Gödel sentence and any logically valid sentence. [0] https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems#First_incompleteness_theorem https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_...

vannevar 6y ago
Yes, but the "such as..." example incorporates the original "this statement is not provable" statement, so it seems a bit of a cheat. If you could exclude that statement, it would also by definition exclude any compound versions of it. It seems to me that the issue boils down to, can "this statement is not provable" be leveraged to get to something like 1 + 1 = 3?
- Corazoor 6y ago
  https://en.m.wikipedia.org/wiki/List_of_statements_independent_of_ZFC https://en.m.wikipedia.org/wiki/List_of_statements_independe... What Gödel did prove was that the above list of statements (and infinitely more) must exist. The special thing about his proof is indeed that it is recursive, i.e. adding another axiom can't fix the problem. But that was only necessary to prove that no formal system can be perfect, ever. Most undecidable problems can indeed be "fixed" by adding another axiom, but if you go beyond the ones of ZFC it becomes less clear which of the two alternatives is the "right" one...
- jlokier 6y ago
  You can exclude any particular Gödel statement (a specific string of symbols), and as you're suggesting you can even exclude an infinite sequence of derived statements too, found by systematically adding the previous ones as axioms and applying a "Gödelisation" procedure to make another. But "this statement is not provable" isn't a statement in the logic. It's an English language description of a type of statement, one which has certain self-referential characteristics and shows us the incompleteness of the logic. There are an infinite number of statements in the logic which fit that type by having the relevant characteristics, and they aren't all obvious. The self-referential recursion implied in Gödel's construction is designed to make it obvious, but it can be encoded in less and less obvious ways while still containing an encoded image of themselves. You can even get to statements where the self-reference is encrypted (using an actual encryption algorithm)! Only a mathematician with the "secret key", or a clever super-mathematician with amazing brute-forcing skills, would be able to read the statement and confirm that it's true! And so "perceivable truth" is a thing too. Some truths are too complex for an ordinary mind to verify, yet still true. To exclude all self-referential statements in the logic of type "this statement is not provable", you would need a decision procedure to tell you which statements in the logic are those. Unfortunately you can't make such a decision procedure. It's very similar to Turing's halting problem. Just as you can't make a program which will take any input X and tell you if the program encoded as X will eventually terminate, you can't make a procedure which will take any statement S and tell you if it contains a fancy encoding of itself. There's just no way to do it. The fact it can be related to Turing's halting problem, which is about real machines and real algorithms running on them, may give you some idea that the core principle can be grounded in something quite down to earth which affects practical applications.

roywiggins 6y ago

if P is (this statement cannot be proved), then you can't prove A && P for any provable A, either. There's an infinite number of statements that can be proven (1=1, 2=2, 3=3... for starters) so there's an infinite number of statements that can't be proven. There are less trivial classes of statements that can't be proven. For instance, there's an infinite number of statements like "bit N of Chaitin's constant is 1" that cannot be proven (only a finite number of those statements are provable). https://en.wikipedia.org/wiki/Chaitin%27s_constant#Incompleteness_theorem_for_halting_probabilities https://en.wikipedia.org/wiki/Chaitin%27s_constant#Incomplet...

Shoop 6y ago

I think this partially answers your question: One thing people try to do to "fix" the incompleteness is to just add the Godel sentence as an axiom of the mathematical system. However, each time you do this, you can create yet another new Godel sentence for the new system with the new axiom. Since it's a diagonalization argument, no amount of adding of new axioms can permanently "fix" the system and make it complete -- there will always be new Godel sentence that is true but not provable.

cyphar 6y ago

Others have explained why you can't wave away inconsistency (principle of explosion) nor incompleteness (adding new axioms just creates a new axiomatic system with its own Godel sentences). However you might also find it interesting what incompletenesses exist in our own mathematical system (ZFC) -- the most well-known example is the Continuum Hypothesis[1]: > There is no set whose cardinality is strictly between that of the integers and the real numbers. Or to put it another way, there exists no intermediate type of infinity between countable infinities (the set of integers) and uncountable infinities (the set of real numbers). The CH is independent of ZFC -- both CH and its negation can be included as new axioms to ZFC and both versions are logically consistent if and only if ZFC is -- meaning that being able to prove the CH is an incompleteness in ZFC. [1]: https://en.wikipedia.org/wiki/Continuum_hypothesis https://en.wikipedia.org/wiki/Continuum_hypothesis

tshaddox 6y ago
I thought that independent (undecidable) statements are totally different than the Gödel sentences which demonstrate incompleteness. The latter is a statement which is true in the axiomatic system but which cannot be proven using the axiomatic system. The former is just a statement that essentially has no truth value in the axiomatic system.
- deleted 6y ago
  [deleted]
- a1369209993 6y ago
  Something being true in a axiomatic system is the same thing as it being provable; that's what "true" means. While a Godel statement for X can be interpreted as "X does not prove this statement", that interpretation inherently relies on the semantic implied by X. The Godel construction is systematic way of generating independent statements without needing to know anything specific about the axiomatic system.
  - tshaddox 6y ago
    Ah yes, you're right, and my lazy wording in the former comment is inaccurate. A Gödel sentence is just a statement written in the syntax of whatever formal system we're dealing with: generally, it's a statement that there exists no natural number which satisfies a particular property. The formal system cannot prove or disprove that statement. As you said, we tend to call the statement "true" because we know that the formal system itself was designed with the intention to describe natural numbers and arithmetic, and the statement was designed intentionally to refer indirectly to itself and claim its own unprovability. Since the statement is formally unprovable, we interpret it as being true. I had forgotten that Gödel actually showed that there are other interpretations of the formal system in which the Gödel statement is false.

diegof79 6y ago

It implies an infinity of inconsistent statements. I'm not a mathematician, but the way I understand it is to do an analogy with the halting problem: for any programming language that is powerful enough you can build a program where you don't know if it's going to halt or not. About avoiding singularities, the GEB book (Godel,Escher,Bach) mentions at the beginning: mathematicians like Russel tried to avoid paradoxes by moving them out of the system, but Godel shown that it doesn't work if you want a complete and consistent system (complete and consistent are technical terms, Wikipedia does a good explanation: https://en.wikipedia.org/wiki/Kurt_Gödel#Incompleteness_theorem https://en.wikipedia.org/wiki/Kurt_Gödel#Incompleteness_theo...). Also related to your question: https://en.wikipedia.org/wiki/Chaitin%27s_constant https://en.wikipedia.org/wiki/Chaitin%27s_constant Sorry if I don't get the technical terms right, hopefully someone else in HN can explain this better.

qppo 6y ago
I think the question is a bit more specific in the context of the halting problem We know by contradiction that we cannot write a program that determines if any program halts, if the program being checked also contains the program that determines if itself halts. Is this the only class of program that cannot be determined to halt?
- Kranar 6y ago
  It's a tough question to answer because it highly depends on interpretation, after all what does it mean for a program to check whether it itself halts, what does it mean for a program to be self referential? There are many sneaky and indirect ways to make a program self referential. All undecidable languages that are recognizable in some sense contain a self referential program sneaking within it. This is because the halting problem is complete for its complexity class and hence any undecidable but recognizable language is Turing reducible to the halting problem. However for undecidable and unrecognizable languages, there are proofs of undecidability that are independent of diagonalization and instead use other proof techniques that in a very strong sense are entirely independent of self-reference. Of course this isn't a formal answer mostly because the idea of a self referential program is not a formal concept but there are techniques such as reverse mathematics [1] that can be used to determine a minimal set of axioms needed to prove a theorem along with proof techniques that depend on the Low basis theorem [2] that are able to prove that some languages are undecidable and unrecognizable that do not in any way depend on diagonalization, which is the proof technique that is associated with self referential programs. [1] https://en.wikipedia.org/wiki/Reverse_mathematics https://en.wikipedia.org/wiki/Reverse_mathematics [2] https://en.wikipedia.org/wiki/Low_basis_theorem https://en.wikipedia.org/wiki/Low_basis_theorem

redvenom 6y ago

Excellent question. It implies an infinite number of statements. For if T is such an incomplete theory and X is a statement true in some models of T and false in others, then T+X is also a theory that satisfies the same requirements as T in Godel's theorem. Therefore there is another statement Y that is true in some models of T+X and false in other models of T+X. But any model of T+X is a model of T so Y is true in some models of T and false in others. And it goes on...

ProfHewitt 6y ago

There are an infinitely many propositions that cannot be proved or disproved in foundational theories of Computer Science. However, foundational theories exclude the [Gödel 1831] proposition *I'mUnprovable* because including it would make the theories inconsistent for reasons mentioned elsewhere in this discussion.