Godel 17

The truth of the Godel sentence

The proof of Godel’s incompleteness theorem just sketched is proof-theoretic (also called syntactic) in that it shows that if certain proofs exist (a proof of P(G(P)) or its negation) then they can be manipulated to produce a proof of a contradiction. This makes no appeal to whether P(G(P)) is “true”, only to whether it is provable. Truth is a model-theoretic, or semantic, concept, and is not equivalent to provability except in special cases.

By analyzing the situation of the above proof in more detail, it is possible to obtain a conclusion about the truth of P(G(P)) in the standard model (\mathbb{N}) of natural numbers. As just seen, q(n,G(P)) is provable for each natural number n, and is thus true in the model (\mathbb{N}). Therefore, within this model,

P(G(P)) = \forall y\, q(y,G(P))

holds. This is what the statement “P(G(P)) is true” usually refers to — the sentence is true in the intended model. It is not true in every model, however: If it were, then by Godel’s completeness theorem it would be provable, which we have just seen is not the case.

— Wikipedia on Proof sketch for Godel’s first incompleteness theorem

2013.11.14 Thursday ACHK