Incompleteness theorem

257 Views Asked by At

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?

1

There are 1 best solutions below

2
On BEST ANSWER

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$.