# Are there mutually independent undecidable statements?

In a recursively axiomatized theory such as PA, are there undecidable statements that are arithmetically true but mutually independent (i.e., are there two statements A and B that are each undecidable from the axioms and where neither is deducible from the other?)?

• Sure - take $Con(S)$ vs. $Con(T)$ for theories $S,T$ of incomparable consistency strengths. Feb 26 at 21:06
• @NoahSchweber probably useful to give examples of such theories as well
– cody
Feb 26 at 21:13

Here is an easy way to see it.

• Let $$A$$ assert that if PA is inconsistent, the smallest $$k$$ for which $$\Sigma_k$$ induction is inconsistent is a multiple of $$3$$.

• Let $$B$$ make the similar assertion that the smallest such $$k$$ is a multiple of $$5$$.

Both of these statements are true, since PA is actually consistent.

Neither statement is provable, since if $$M$$ is a nonstandard model of true arithmetic, then we can select a nonstandard number $$k$$ that is a multiple neither of $$3$$ nor $$5$$, and consider the theory $$I\Sigma_k$$ inside $$M$$, which is consistent in $$M$$. By the incompleteness theorem, applied in $$M$$, this theory does not prove its own consistency, and so $$M$$ thinks the theory $$I\Sigma_k+\neg\text{Con}(I\Sigma_k)$$ is consistent. We may therefore form the corresponding Henkin theory inside $$M$$, which gives rise to a model $$N$$, interpretable by this theory in $$M$$, which looks upon it as a model of $$I\Sigma_k+\neg\text{Con}(I\Sigma_k)$$. Externally, we can see that this theory includes PA, since every standard instance of induction will be included in $$I\Sigma_k$$ as $$k$$ is nonstandard. Since $$I\Sigma_k$$ proves the consistency of $$\Sigma_{k-1}$$ induction, the first failure of consistency occurs exactly at $$k$$ in $$N$$, and so both $$A$$ and $$B$$ are false in $$N$$ by the choice of $$k$$.

The same argument shows that we can make either $$A$$ or $$B$$ true and the other false, simply with a suitable choice of nonstandard $$k$$ in $$M$$. So neither is deducible from the other. All four combinations occur.

A similar argument is possible whenever you have a definition $$\phi$$ of a number, such that it is consistent with PA that any particular number could be the number defined by $$\phi$$.

For example, take $$\phi(x)$$ to hold when "$$x$$ is the last number appearing on the universal algorithm, or $$0$$ is there is no such number.

Now we can let $$A$$ assert that the number is a multiple of $$3$$, and $$B$$ that it is a multiple of $$5$$. Since we can make this number whatever we want, we get all four combinations again in models of PA, fulfilling your desired independence.

Indeed, we can get a scheme of infinitely many such mutually independent statements, and this appears as theorem 19 in the universal algorithm paper.

Theorem 19. There are infinitely many mutually independent $$\pi^0_1$$ sentences $$\eta_0$$, $$\eta_1$$, $$\eta_2$$, and so on. Any desired true/false pattern for these sentences is consistent with PA.

(This theorem goes back to Mostowski 1960, but the universal algorithm makes it very easy.)

The statement $$\eta_k$$ is the assertion "the number $$k$$ does not appear on the universal algorithm sequence." Since the model can be extended so as to place exactly any given numbers on the universal sequence, these statements fulfill an extremely strong form of independence, namely, they all start out true in the standard model, and in any model of PA, which of them remain true can be made false in an end-extension of the model in accordance with any desired finite pattern. In particular, not only are they mutually independent, but they remain so in any model in which they remain true.

There is a similar phenomenon with Orey sentences (necessarily of higher complexity) that enable one to drop the "remaining true" part, as in theorem 21 of the paper.

• Excellent answer! After "This theory is true in the corresponding Henkin model $N$", there is a tacit switch back from working in the nonstandard model $M$ to working in the real $\mathbb N$. Should I edit to include the point where the switch is made?
– C7X
Feb 27 at 1:32
• @C7X Thanks so much! About your remark, the Henkin model is constructed inside $M$ and only makes sense there, since $k$ is nonstandard. So there is no going back to $\mathbb{N}$ that I see, except to note that $N$ is a model of PA, since the true PA is included in $I\Sigma_k$. Or perhaps I've misunderstood you? Feb 27 at 3:08
• Yes, the part where it is remarked that $N$ is a model of PA is the part which I saw as going back to $\mathbb N$. If I understand correctly, this remark cannot be true in $M$, since the theory $M$ thinks is PA is a proper superset of $I\Sigma_k$, so instead the remark must be in $\mathbb N$. The rest of the paragraph is about $A$ and $B$ being false in $N$, which I also took as argumentation taking place in the real $\mathbb N$, to give an answer to the question.
– C7X
Feb 27 at 4:24
• Ah, I suppose. In my view, this is just arguing in the metatheory, the same as the whole argument. We construct a model $N$ inside $M$, but then make observations about it, thereby having shown that there are models realizing all four possibilities for the statements A and B. I'll edit to clarify. Feb 27 at 12:12
• I have now edited. Feb 27 at 12:18