Prove $PA\vdash Con_Q$

Question

So let $PA$ be Peano Arithmetic as usual, and $Q$ be Robinson Arithmetic. I'm trying to show that $PA\vdash Con_Q$, i.e. that from $PA$ we can prove $Q$'s consistency. It is assumed that $PA \nvdash Con_{PA}$ because it is assumed that $PA$ is consistent, and a consistent theory cannot prove its own consistency by Godel's theorems - so how come it can suddenly prove $Q$'s consistency? It is quite close to $PA$, the main difference being $Q$'s lack of induction axiom. Any guidance on how to do this would be appreciated.

Answer 1

This answer drifts away from $Q$ in favor of a stronger result. I think that's ultimately to the good, but it is worth mentioning at the outset. Also, while presumably there's an easier proof of the weaker result, I don't actually know one offhand.

---

First, it needs to be observed that $Q$ is not close at all to $PA$. The omission of the induction axiom (scheme) is a huge deal. For example, $Q$ cannot prove that addition is commutative or that every number is either even or odd; at a more technical level, $Q$ has computable nonstandard models while $PA$ does not (see here).

We get theories closer to $PA$ - and generally better-behaved - by adding some induction. For each $n\in\mathbb{N}$, the theory $I\Sigma_n$ consists of the ordered semiring axioms (which already can prove things $Q$ can't) together with the induction scheme for $\Sigma_n$ formulas; so $$PA=\bigcup_{n\in\mathbb{N}}I\Sigma_n$$ (and in particular $PA$ is not finitely axiomatizable; in fact, no consistent extension of $PA$ in the same language is finitely axiomatizable, but that's an aside). There are other fragments of $PA$ of significant interest, but they are a bit more technical to define.

It turns out that $PA$ is rather close to proving its own consistency:

$(*)\quad$ For each $n$, $PA$ proves the consistency of $I\Sigma_n$.

In fact, $PA$ proves that $PA$ proves the consistency of $I\Sigma_n$ for each $n$. However, $PA$ does not prove "For all $n$, $I\Sigma_n$ is consistent," so this does not yield a contradiction. At this point two comments are worthwhile:

• If this seems weird, note that the same phenomenon happens in a simpler way when we talk about provability and consistency: $PA$ can prove "For each $x$, $PA$ proves that $x$ is not the Godel number of a $PA$-proof of $0=1$" (since - reasoning in $PA$ - either $x$ is indeed not such a number, in which case $PA$ knows that via $\Sigma^0_1$ completeness, or it is in which case $PA$ is inconsistent and hence proves everything). But (hopefully!) $PA$ does not prove "For all $x$, $x$ is not the Godel number of a $PA$-proof of $0=1$" since then $PA$ would prove its own consistency.

• Also, the same thing happens with set theory: for every finite $T\subseteq ZFC$ we have $ZFC\vdash Con(T)$, and indeed $ZFC$ proves that fact (in fact, $PA$ alone proves "$ZFC$ proves the consistency of each of its finite subtheories").

The result $(*)$ - especially in light of its $PA$-provability - subsumes your question and was originally proved by Mostowski if I recall correctly. It is discussed here.

---

And now my answer gets a bit unsatisfying.

The standard proof of $(*)$ is a bit technical; it's treated well in Kaye's Models of Peano arithmetic (which Carl Mummert's answer at the linked question points to as well), but is a bit long to summarize here. Hajek/Pudlak's book Metamathematics of first-order arithmetic is also wonderful (and freely and legally available online!), and treats this result in chapter $1$, section $4$ (starting on page $98$).

Alternatively, if you're familiar with Gentzen's consistency proof, one proof can be summarized fairly snappily: by modifying Gentzen's argument we can show for each $n$ the proof-theoretic ordinal of $I\Sigma_n$ is much less than $\epsilon_0$ (if memory serves, it's an exponential tower of $\omega$s of height $n$ - e.g. the proof-theoretic ordinal of $I\Sigma_3$ is $\omega^{(\omega^\omega)}$). But since $PA$ proves well-foundedness of each such ordinal, we have $PA\vdash Con(I\Sigma_n)$.

Finally, if you're familiar with theories of second-order arithmetic (which is a terrible name, since these are first-order theories, but oh well) then there's a proof which in my opinion is much easier to understand. First, we show that $ACA_0$ is a conservative extension of $PA$; in particular, this means that if $ACA_0$ proves $Con(I\Sigma_n)$ then so does $PA$. Our goal now is to, in $ACA_0$, prove the Soundness theorem and then show that $\mathbb{N}$ is a mdoel of $I\Sigma_n$. This takes some care, but works: what we do is show that if $T$ is any theory and there is a structure $A$ equipped with Skolem functions witnessing the truth of the axioms in $T$, then $T$ must be consistent. Now we just need to show that $ACA_0$ can "construct" a family of Skolem functions for $I\Sigma_n$ holding in $\mathbb{N}$. But this is a straightforward computability argument: such Skolem functions can be found uniformly computably in $\emptyset^{(n)}$.

• What the shift from $PA$ to $ACA_0$ bought us was the ability to talk directly about structures rather than having to reason about proofs alone. Semantic arguments are often considered easier to understand than syntactic arguments - by me, for example, although of course one's own stance may differ.

After understanding any of the arguments above, one should go through the details carefully to see where things break down if we try to use them to show that $PA$ proves "For all $n$, $I\Sigma_n$ is consistent." It's really the same issue in each case, but in somewhat different guises.