Skip to main content
1 of 5
Joel David Hamkins
  • 236.3k
  • 44
  • 777
  • 1.4k

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 in $M$. This theory is true in the corresponding Henkin model $N$, which is a model of PA since $k$ is nonstandard, but 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.

Joel David Hamkins
  • 236.3k
  • 44
  • 777
  • 1.4k