Are there mutually independent undecidable statements?

Question

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?)?

Answer 1

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.

• Joel David Hamkins, "The modal logic of arithmetic potentialism and the universal algorithm", arxiv:1801.04599.

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.