# Incompleteness theorem

Correct me if I am wrong at any point!

Godel's incompleteness theorem allows us to express "PA is consistent" in the language of Peano arithmetic, and shows that this is not provable in PA. Let's call this sentence $P$.

Godel's completeness theorem tells us that $P$ does not hold in every model of PA; it also tells us that is holds in some models of PA, since otherwise PA would prove $\neg P$ and so PA would be inconsistent.

However, we have a "standard model" of PA, i.e. $\mathbb{N}$, which we can prove things about using ZFC or second-order arithmetic. So my question is, does $P$, thought of as a statement about natural numbers, hold in $\mathbb{N}$? Or have I misunderstood a subtlety (or not-so-subtlety) somewhere?

• Yes, the standard model satisfies $P$. Feb 4, 2015 at 16:10
• @AndresCaicedo: Hmm is that the actual question? $P$ is not provable in PA, and so a proof of $P$ for $\mathbb{N}$ must invoke something beyond the PA axioms applied to $\mathbb{N}$. Feb 4, 2015 at 16:24
• @user21820 it was the question. I'd be interested to see a proof, though. Feb 4, 2015 at 16:31
• You can see the proof in George Tourlakis, Lectures in Logic and Set Theory. Volume 1 : Mathematical Logic (2003), page 205-315. Feb 4, 2015 at 16:51
• A non-technical (i.e crappy) "proof" that $\mathbb{N}\models P$ is to observe that the provability predicate used in the definition of $P$, accurately models provability, when you are working in $\mathbb{N}$. So the statement $P$, which says, roughly "I am not provable" is true (in $\mathbb{N}$), beacuse the first incompleteness theorem holds, and, hence, $\neg(PA \vdash P)$ is true, yet, this is precisely the content of $P$. (All this, assuming $PA$ is consistent). Feb 4, 2015 at 18:11

Converting and expanding from my comment so that the question is marked as answered.

Godel shows that any sufficiently strong (but not too strong) axiomatization of arithmetic is incomplete, meaning for every such axiomatization there is a sentence in its language that the axiomatization neither proves or refutes (proves the negation of). PA is an axiomatization that is sufficiently strong, and hence is incomplete.

In your third paragraph you say

Godel's completeness theorem tells us that P does not hold in every model of PA; it also tells us that is holds in some models of PA, since otherwise PA would prove ¬P and so PA would be inconsistent.

This is not quite correct. The completeness theorem does imply that there are models of PA that are also models of $$P$$ as well as there being other models that model $$\neg P$$, however it is not for the reason you give: PA + $$P$$ and $$PA + \neg P$$ are both consistent (assuming PA was consistent to start with). If one of them was inconsistent, then PA proves the "other" sentence.

Now to your question. You ask whether $$\mathbb{N}$$, the standard model of arithmetic, is a model for either $$P$$ or $$\neg P$$. It must be a model for exactly one of these sentences by the definition of truth. The sentence that Godel's construction produces is true in the standard model. This is because the sentence $$P$$ (more or less) says that there is no proof of $$P$$ from the axioms of PA. More precisely, it says that there is no number that codes a list of numbers each of which encodes a sentence in the language of arithmetic that constitute a proof of P from the axioms in PA.

Now, we know, because of the first incompleteness theorem, that there really is no proof of $$P$$ from PA, which means that there really is no encoding of such a proof by a natural number. This means that each natural number really fails to encode such a proof, but then, by the definition of truth in a model, $$\mathbb{N}$$ is a model of the sentence "there is no number that codes a proof of $$P$$ from PA". But this is exactly the sentence $$P$$, so $$\mathbb{N}$$ models $$P$$.

• One constant source of confusion is that "PA is consistent" cannot be expressed by PA, as PA cannot make statements about statements. In PA we can define a numerical encoding of PA, denoted [PA], and we can define, in PA, a sentence Con [PA]. And Con [PA] is NOT the same thing as the statement, external to PA, that PA is consistent. If PA is consistent then so is PA+($\neg$ Con[PA]). Dec 6, 2020 at 22:09
• @DanielWainfleet Indeed, the Godel sentence is really the claim that there is no number that has a certain number-theoretic property. If we set up our encoding well, then that number theoretic property reflects properties about formal proofs. Dec 8, 2020 at 0:10