bryjnar comments on Proofs, Implications, and Models - Less Wrong

58 Post author: Eliezer_Yudkowsky 30 October 2012 01:02PM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Comments (209)

You are viewing a single comment's thread. Show more comments above.

Comment author: Bakkot 29 October 2012 12:48:35PM 4 points [-]

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.

Comment author: bryjnar 29 October 2012 11:24:47PM 2 points [-]

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.