Is there a statement independent from PA and does not increase the consistency strength?

Question

There are many known independence results of $\mathsf{PA}$, for example, Goodstein theorem, Paris-Harrington theorem, and the reflection principle. But these examples imply the consistency of $\mathsf{PA}$.

I guess not all independent statements of $\mathsf{PA}$ imply the consistency of $\mathsf{PA}$. I have tried to find such examples, but I can't even prove the existence of such a proposition. I would appreciate your help.

Answer 1

You can attack this kind of question by thinking about the Lindenbaum-Tarski algebra for PA. This can be viewed as a partial order $\preceq$ on the set of all sentences in the language of arithmetic, where we have $\phi \preceq \psi$ if and only if $PA + \psi \vdash \phi$. (It is possible to use the opposite order, but I prefer to have stronger sentences be higher in the order than weaker sentences).

One fact about this order is that, when we use PA or other sufficiently strong theories, the order is dense: if $\phi \prec \psi$ then there is a sentence $\theta$ with $\phi \prec \theta \prec \psi$. One way to construct $\theta$ is to begin with a sentence $\chi$ which is independent of $\text{PA} + \phi + \lnot \psi$ and then let $\theta = \psi \lor (\phi \land \chi)$.

So, to answer the question, if we let $\phi$ be a sentence provable in PA, and we let $\psi$ be Con(PA), then we have $\phi \prec \psi$, and so by density there is a sentence $\theta$ strictly between them. This sentence $\theta$ is not provable in PA, because it is strictly above $\phi$, but it does not imply Con(PA), because it is strictly below Con(PA).

It is much more challenging to find "natural" examples of sentences independent of PA that are implied by, but do not imply, Con(PA). The general construction shows there are at least some sentences with that property, though. The example constructed as above is essentially $$\text{Con}(\text{PA}) \lor \text{Con}(\text{PA} + \lnot\text{Con}(\text{PA}))$$ where $\text{Con}(\cdot)$ is the Gödel/Rosser consistency sentence.

Answer 2

Here's a proof that there exists such a sentence (although as Carl observes, this doesn't give an example of such a sentence). We'll assume $PA$ is consistent throughout.

Suppose towards a contradiction that for every $\varphi$ which is independent of $PA$, either $\varphi$ or $\neg\varphi$ proves $Con(PA)$. Note that since $PA$ is consistent, this means that for any $\varphi$ which is independent of $PA$, exactly one of $\varphi$ and $\neg\varphi$ implies $Con(PA)$ (if both $\varphi$ and $\neg\varphi$ implied $Con(PA)$, then $PA\vdash Con(PA)$, so $PA$ is inconsistent).

But this lets us construct a computable consistent completion of $PA$, as follows. Enumerate the sentences of arithmetic as $\{\psi_i: i\in\mathbb{N}\}$, and define a sequence of sentences $\varphi_i$ $(i\in\mathbb{N})$ as follows:

• Suppose we've defined $\varphi_j$ for all $j<i$. Let $\theta_i=\bigwedge_{j<i}\varphi_j$ be the conjunction of all the $\varphi$s so far. By induction, we'll have four cases, exactly one of which holds: either $PA+\theta_i$ proves $\psi_i$, or $PA+\theta_i$ proves $\neg\psi_i$, or $PA+\theta_i+\psi_i$ proves $Con(PA)$, or $PA+\theta_i+\neg\psi_i$ proves $Con(PA)$.

• By searching through all possible proofs from $PA+\theta_i$, we may determine effectively which of these four cases holds. We now define $\varphi_i$ as follows. If case $1$ or $4$ holds, $\varphi_i=\psi_i$; if case $2$ or $3$ holds, $\varphi_i=\neg\psi_i$.

It's now not hard to check that $PA\cup\{\varphi_i: i\in\mathbb{N}\}$ is a computable consistent completion of $PA$ - contradicting Godel's theorem.

Answer 3

The Rosser sentence $\rho$ is an example.

The Rosser sentence $\rho$ for a theory T (containing some weak arithmetic) is the assertion that for every proof of $\rho$ in $T$, there is a shorter proof of $\neg\rho$, that is, a proof with a smaller Gödel code. (One can use the fixed-point lemma to handle the apparent self-reference.)

If $T$ is consistent, then $\rho$ is independent of $T$, by the following well-known argument. If $T\vdash\rho$, then $T$ would not also prove $\neg\rho$, but it would have to, in light of what $\rho$ expresses. So $T\not\vdash\rho$. Similarly, if $T\vdash\neg\rho$, then $T$ would have to prove that there is a shorter proof of $\rho$, which it cannot because it is consistent.

Thus, we've proved $\text{Con}(T)\to\text{Con}(T+\rho)\wedge\text{Con}(T+\neg\rho)$, in a very weak theory. Thus, $T+\rho$ and $T+\neg\rho$ are equiconsistent with $T$. So $\rho$ is a sentence that is indepdnent of $T$, without increasing consistency strength.

In particular, the Rosser sentence $\rho$ is strictly weaker than $\text{Con}(T)$.