Completion of Peano arithmetic

Question

Godel proved that Peano arithmetic is incomplete and Ryll-Nardzewski proved that there is no finite complete extension of it. I wonder if there is any specific set of sentences (infinitely many) to make Peano arithmetic complete.

Answer 1

This is really just an addendum to Bram28's answer, but it's a bit too long for a comment:

---

First, re: the specific question you ask, Bram28 correctly points out that true arithmetic $\mathsf{TA}$ is a complete theory extending $\mathsf{PA}$. This is simply a particular instance of a more general phenomenon: for any structure $\mathfrak{A}$ the theory $Th(\mathfrak{A})$ is trivially complete, so to find a complete theory extending a given theory $T$ it's enough to find any model of $T$. In this case, the most natural choice of model is the standard model of arithmetic $\mathbb{N}$, and the resulting theory is $\mathsf{TA}$.

Of course there are nonstandard models of $\mathsf{PA}$, including ones very different from $\mathbb{N}$ (e.g. per the second incompleteness theorem there is an $M\models\mathsf{PA}+\neg Con(\mathsf{PA})$). We could use such a model in place of $\mathbb{N}$ here if we wanted. However, $\mathbb{N}$ is - unsurprisingly - the most natural model of $\mathsf{PA}$, so why not use it?

(Incidentally, as in your previous question basic model-theoretic questions about $\mathsf{PA}$ become conceptually much simpler once we forget the details of $\mathsf{PA}$ and just think about it as some first-order theory.)

---

That addresses your question as specifically posed. However, there is also an interesting computability-theoretic aspect. Specifically, the theory $\mathsf{TA}$ is rather complicated, in the precise sense that not only is it more complicated than the halting problem but it is more complicated than any finite iterate of the halting problem. Can we do better? Say that a Turing degree d is a PA degree iff d computes a complete consistent theory extending $\mathsf{PA}$. Per the first incompleteness theorem the degree ${\bf 0}$ is not a PA degree. Meanwhile, $deg(\mathsf{TA})$ - more commonly denoted "${\bf 0^{(\omega)}}$" - is trivially a $\mathsf{PA}$ degree. How complicated do PA degrees have to be?

It turns out that there are PA degrees which are vastly simpler than ${\bf 0^{(\omega)}}$. By a greedy algorithm it's easy to construct a ${\bf 0'}$-computable consistent completion of $\mathsf{PA}$:

Fix a computable enumeration $(\varphi_i)_{i\in\mathbb{N}}$ of the sentences of arithmetic, and recursively let $\psi_i=\varphi_i$ if $\mathsf{PA}\cup\{\psi_j:j<i\}\cup\{\varphi_i\}$ is consistent and let $\psi_i=\neg\varphi$ otherwise. Since checking consistency is ${\bf 0'}$-computable, the resulting theory is ${\bf 0'}$-computable.

This is just Bram28's second example with a "complexity calculation" thrown on because computability theory builds character.

However, we can do even better than that! The low basis theorem says that there is a PA degree whose Turing jump is just ${\bf 0'}$ itself (this is obviously as small as possible). Note that it's not at all obvious that noncomputable low degrees even exist at all! There are other basis theorems as well, e.g. the hyperimmune-free basis theorem, but the low basis theorem is by far the most important.

It turns out that PA degrees play a central role in computability theory. This is because of the perhaps-surprising robustness of the definition. The following are equivalent, for a degree d:

• d is a PA degree.

• For every computably axiomatizable theory $T$, d computes a complete consistent extension of $T$.

• For every computably axiomatizable theory $T$, d computes (the atomic diagram of) a model of $T$.

• For every computable infinite binary tree $A\subseteq 2^{<\omega}$, d computes an infinite path through $A$.

And there are a number of other equivalent characterizations besides. This robustness is a consequence of the computational power of $\mathsf{PA}$, specifically the fact that $\mathsf{PA}$ is $\Sigma_1$-complete (consequently we can replace $\mathsf{PA}$ here with much weaker theories, but $\mathsf{PA}$ has historical value).

If you're interested in this topic, a couple of good sources are this survey paper of Diamondstone/Dzhafarov/Soare and this book draft of Cenzer/Remmel. These texts are structured around $\Pi^0_1$ classes but this is basically the same topic: a $\Pi^0_1$ class is a set of paths through a computable binary tree, and PA degrees are exactly those degrees which compute a member of every $\Pi^0_1$ class.

Answer 2

How about just al the true statements of arithmetic?

Or, if you're worried about what 'true' means: take the set of statements that are logical consequences of PA. Then go through all the statements that can be expressed in the language of arithmetic one by one (there are enumerably many of those so there is some enumeration of them, and so follow any one such enumeration). If any sentence that you encounter is not in the set that you have so far, nor its negation, then add it to the ever-growing set, and expand the set to its closure with regard to logical consequence. In the limit, that should get you a complete set that is an extension of PA.