Consistent Theories – Exploring Inconsistencies in Provability

incompletenesslogicnonstandard-modelsprovability

In this question, it is asked whether there is a theory $T$ such that $T$ is consistent but $T+\mathrm{Con}(T)$ is inconsistent. The answer is yes: for instance, $T=\mathsf{PA}+\neg\mathrm{Con}(\mathsf{PA})$ is consistent, and yet it proves $\neg\mathrm{Con}(T)$. Thus, $T+\mathrm{Con}(T)$ proves both $\mathrm{Con}(T)$ and $\neg\mathrm{Con}(T)$, and is thus inconsistent.

I am interested in the "iterated" version of this phenomenon. For instance, can we find examples of theories $T$ such that $T$ is consistent and $T+\mathrm{Con}(T)$ is consistent, but $T+\mathrm{Con}(T+\mathrm{Con}(T))$ is inconsistent?

Best Answer

Yes, this can happen.

First, some simplifying notation. For $T$ an "appropriate" theory, let $T'=T+Con(T)$. Note that $T''=T+Con(T)+Con(T+Con(T))$ is actually equivalent to the seemingly-simpler $T+Con(T+Con(T))$ since from $Con(T+Con(T))$ we can deduce $Con(T)$. So you're asking for an example of a theory $T$ such that $T$ and $T'$ are consistent but $T''$ is not consistent.

I claim that the most natural candidate example does the job, namely the theory $T=\mathsf{PA}+\neg Con(\mathsf{PA}')$. We know (under mild assumptions of course!) by Godel that $T$ is consistent; indeed, $T$ is a subtheory of $\mathsf{PA}+\neg Con(\mathsf{PA})$. Meanwhile, it's clear that $T''$ is inconsistent, since $T$ contains $\neg Con(\mathsf{PA}')$ but $T''$ contains $Con(\mathsf{PA}')$. So we just need to show that $T'$ is consistent.

Suppose $T'$ were not consistent. Then $T\vdash\neg Con(T)$. Recalling that $T=\mathsf{PA}+\neg Con(\mathsf{PA}')$ and using the deduction theorem, this gives $$\mathsf{PA}\vdash\neg Con(\mathsf{PA}')\rightarrow \neg Con(T).$$ In contrapositive, and expanding some notation, this is $$\mathsf{PA}\vdash Con[\mathsf{PA}+\neg Con(\mathsf{PA}')]\rightarrow Con[\mathsf{PA}+Con(\mathsf{PA})].$$

So what? Well, note that $\mathsf{PA}\vdash Con(\mathsf{PA})\rightarrow Con(\mathsf{PA}+\neg Con(\mathsf{PA}))$ by internalizing the proof of the second incompleteness theorem. By earlier observations, this means that we can in fact simplify the above line to $$\mathsf{PA}\vdash Con(\mathsf{PA})\rightarrow Con[\mathsf{PA}+Con(\mathsf{PA})].$$ This in turn gives $$\mathsf{PA}'\vdash Con(\mathsf{PA})\rightarrow Con(\mathsf{PA}'),$$ which - since $\mathsf{PA}'\vdash Con(\mathsf{PA})$ - means that $\mathsf{PA}'$ is inconsistent.

(Of course this uses some mild assumptions on the "goodness" of $\mathsf{PA}$; if we replace $\mathsf{PA}$ with $\mathsf{I\Sigma_1}$ throughout the above, though, we get an analogous argument that goes through in $\mathsf{PA}$ alone or indeed much less.)

Related Question