Note that this notion of ‘completeness’ is not the one used in Gödel’s incompleteness theorems.
Um, yes it is, I think. The incompleteness theorems tell you that there are statements that are true (semantically valid) but unprovable, and hence they provide a counterexample to “If X |=Y then X |- Y”, i.e. the proof system is not complete.
EDIT: To all respondents: sorry, I was unclear. Yes, I do realise that FOL is complete, but the same notion of completeness generalises to different proof systems. The incompleteness theorems show that the proof system for Peano arithmetic is incomplete, in precisely this way
The incompleteness theorems tell you that there are statements that are true (semantically valid) but unprovable, and hence they provide a counterexample to “If X |=Y then X |- Y”, i.e. the proof system is not complete.
This is not correct. In first-order logic, there are no counterexamples to “If X |=Y then X |- Y”—this is (equivalent to) Gödel’s completeness theorem. Gödel’s incompleteness theorem says that every first-order theory with an effectively enumerable set of axioms, and which includes arithmetic, contains some propositions which have neither a proof nor a disproof. One typically goes on to say that the undecidable proposition that the proof constructs is true in the “usual model” of the natural numbers, but that is verging on philosophy. At any rate, the truth of the proposition is asserted for only one particular model of the axioms of arithmetic, not all possible models. By the completeness theorem, an undecidable proposition must be true in some models and false in others.
I think you’re confusing syntax and semantics yourself here. An undecidable proposition has no proof, that does not mean it is not semantically valid. So the second theorem shows that for a consistent theory T, the statement ConT that T is consistent is not provable, but it is true in all models.
So the second theorem shows that for a consistent theory T, the statement ConT that T is consistent is not provable, but it is true in all models.
No, it isn’t. When T includes arithmetic, ConT is not provable in T (provided that T is consistent, the usual background assumption). Therefore by the completeness theorem, there are models of T in which ConT is false.
ConT can be informally read as “T is consistent”, and by assumption the latter statement is true, but that is not the same as ConT itself being true in any model other than the unique one we think we are talking about when we talk about the natural numbers.
Okay, I think this is still because I’m thinking about the second-order logic result. I just went and looked up the FOL stuff, and the incompleteness theorem does give some weird results in FOL! You’re quite right, you do get models in which ConT is false.
First-order logic is complete. There are no counterexamples. Since the Godel sentence of a theory is not provable from the axioms of a theory, it follows (from completeness) that the Godel sentence must be false in some “non-standard” models of the axioms.
You can read the first incompleteness theorem as saying that there’s no way to come up with a finitely expressible set of axioms that can prove all the truths of arithmetic. This is not in conflict with the completeness theorem. The completeness theorem tells us that if there were some finite (or recursively enumerable) set of axioms of arithmetic such that the inference to any truth of arithmetic from those axioms was semantically valid, then all truths of arithmetic can be proven from that set of axioms. The incompleteness theorem tells us that the antecedent of this conditional is false; it doesn’t deny the truth of the conditional itself.
Right, I think the confusion was that I tend to think of the incompleteness theorems as being about second-order Peano arithmetic, but it does give a somewhat different result for first-order.
No, not quite. The distinction is subtle, but I’ll try to lay it out.
there are statements that are true (semantically valid) but unprovable, and hence they provide a counterexample to “If X |=Y then X |- Y”
This is not the case. The problem is with the ‘and hence’: ‘X ⊨ Y’ should not be read as ‘Y is true in X’ but rather ‘Y is true in every model of X’. There are statements which are true in the standard model of Peano arithmetic which are not entailed by it—that is, ‘Y is true in the standard model of Peano arithmetic’ is not the same as ‘PA ⊨ Y’. So this is not a counterexample.
Rather, the notion of ‘complete’ in the incompleteness theorem is that a model is complete if for every statement, either the statement or its negation is entailed by the model (and hence provable by semantic completeness). Gödel’s incompleteness theorem shows that no theory T containing PA is complete in this sense; that is, there statements S which are true in T but not entailed by it (and so not provable). This is because there are models of T in which S is not true: that is, systems in which every statement in T holds, but S does not. (These systems have some additional structure beyond that required by T.)
Wikipedia may do a better job of explaining this than I can at the moment.
I did mean “semantically valid” to be “true in all models”, I was just thinking about second-order Peano arithmetic not first-order ;) I think it’s more natural precisely because then it exactly does show incompleteness.
I’ll attempt to clarify a little, if that’s alright. Given a particular well-behaved theory T, Gödel’s (first!) incompleteness theorem exhibits a statement G that is neither provable nor disprovable in T—that is, neither G nor ¬G is syntactically entailed by T. It follows by the completeness theorem that there are models of T in which G is true, and models of T in which ¬G is true.
Now G is often interpreted as meaning “G is not provable in T”, which is obviously true. However, this interpretation is an artifact of the way we’ve carefully constructed G, using a system of relations on Gödel numbers designed to carefully reflect the provability relations on statements in the language of T. But these Gödel numbers are elements of whatever model of T we’re using, and our assumption that the relations used in the construction of G have anything to do with provability in T only apply if the Gödel numbers are from the usual, non-crazy model N of the natural numbers. There are unusual, very-much-crazy models of the natural numbers which are not N, however, and if we’re using one of those then our relations are unintuitive and wacky and have nothing at all to do with provability in T, and in these G can be true or false as it pleases. So when we say “G is true”, we actually mean “G is true if we’re using the standard model of the natural numbers, which may or may not even be a valid model of T in the first place”.
The simplest way to explain the difference, is that Gödel’s completeness theorem applies to first order logic, whereas Gödel’s incompleteness theorem applies to second order logic.
Um, yes it is, I think. The incompleteness theorems tell you that there are statements that are true (semantically valid) but unprovable, and hence they provide a counterexample to “If X |=Y then X |- Y”, i.e. the proof system is not complete.
EDIT: To all respondents: sorry, I was unclear. Yes, I do realise that FOL is complete, but the same notion of completeness generalises to different proof systems. The incompleteness theorems show that the proof system for Peano arithmetic is incomplete, in precisely this way
This is not correct. In first-order logic, there are no counterexamples to “If X |=Y then X |- Y”—this is (equivalent to) Gödel’s completeness theorem. Gödel’s incompleteness theorem says that every first-order theory with an effectively enumerable set of axioms, and which includes arithmetic, contains some propositions which have neither a proof nor a disproof. One typically goes on to say that the undecidable proposition that the proof constructs is true in the “usual model” of the natural numbers, but that is verging on philosophy. At any rate, the truth of the proposition is asserted for only one particular model of the axioms of arithmetic, not all possible models. By the completeness theorem, an undecidable proposition must be true in some models and false in others.
I think you’re confusing syntax and semantics yourself here. An undecidable proposition has no proof, that does not mean it is not semantically valid. So the second theorem shows that for a consistent theory T, the statement ConT that T is consistent is not provable, but it is true in all models.
No, it isn’t. When T includes arithmetic, ConT is not provable in T (provided that T is consistent, the usual background assumption). Therefore by the completeness theorem, there are models of T in which ConT is false.
ConT can be informally read as “T is consistent”, and by assumption the latter statement is true, but that is not the same as ConT itself being true in any model other than the unique one we think we are talking about when we talk about the natural numbers.
Okay, I think this is still because I’m thinking about the second-order logic result. I just went and looked up the FOL stuff, and the incompleteness theorem does give some weird results in FOL! You’re quite right, you do get models in which ConT is false.
I think my point still stands for SOL, though.
First-order logic is complete. There are no counterexamples. Since the Godel sentence of a theory is not provable from the axioms of a theory, it follows (from completeness) that the Godel sentence must be false in some “non-standard” models of the axioms.
You can read the first incompleteness theorem as saying that there’s no way to come up with a finitely expressible set of axioms that can prove all the truths of arithmetic. This is not in conflict with the completeness theorem. The completeness theorem tells us that if there were some finite (or recursively enumerable) set of axioms of arithmetic such that the inference to any truth of arithmetic from those axioms was semantically valid, then all truths of arithmetic can be proven from that set of axioms. The incompleteness theorem tells us that the antecedent of this conditional is false; it doesn’t deny the truth of the conditional itself.
Right, I think the confusion was that I tend to think of the incompleteness theorems as being about second-order Peano arithmetic, but it does give a somewhat different result for first-order.
No, not quite. The distinction is subtle, but I’ll try to lay it out.
This is not the case. The problem is with the ‘and hence’: ‘X ⊨ Y’ should not be read as ‘Y is true in X’ but rather ‘Y is true in every model of X’. There are statements which are true in the standard model of Peano arithmetic which are not entailed by it—that is, ‘Y is true in the standard model of Peano arithmetic’ is not the same as ‘PA ⊨ Y’. So this is not a counterexample.
Rather, the notion of ‘complete’ in the incompleteness theorem is that a model is complete if for every statement, either the statement or its negation is entailed by the model (and hence provable by semantic completeness). Gödel’s incompleteness theorem shows that no theory T containing PA is complete in this sense; that is, there statements S which are true in T but not entailed by it (and so not provable). This is because there are models of T in which S is not true: that is, systems in which every statement in T holds, but S does not. (These systems have some additional structure beyond that required by T.)
Wikipedia may do a better job of explaining this than I can at the moment.
I did mean “semantically valid” to be “true in all models”, I was just thinking about second-order Peano arithmetic not first-order ;) I think it’s more natural precisely because then it exactly does show incompleteness.
I’ll attempt to clarify a little, if that’s alright. Given a particular well-behaved theory T, Gödel’s (first!) incompleteness theorem exhibits a statement G that is neither provable nor disprovable in T—that is, neither G nor ¬G is syntactically entailed by T. It follows by the completeness theorem that there are models of T in which G is true, and models of T in which ¬G is true.
Now G is often interpreted as meaning “G is not provable in T”, which is obviously true. However, this interpretation is an artifact of the way we’ve carefully constructed G, using a system of relations on Gödel numbers designed to carefully reflect the provability relations on statements in the language of T. But these Gödel numbers are elements of whatever model of T we’re using, and our assumption that the relations used in the construction of G have anything to do with provability in T only apply if the Gödel numbers are from the usual, non-crazy model N of the natural numbers. There are unusual, very-much-crazy models of the natural numbers which are not N, however, and if we’re using one of those then our relations are unintuitive and wacky and have nothing at all to do with provability in T, and in these G can be true or false as it pleases. So when we say “G is true”, we actually mean “G is true if we’re using the standard model of the natural numbers, which may or may not even be a valid model of T in the first place”.
The simplest way to explain the difference, is that Gödel’s completeness theorem applies to first order logic, whereas Gödel’s incompleteness theorem applies to second order logic.
Right.