The question is as in the title. In the edit history you can find my attempt to formalise the question, but that was a failure, for reasons stated clearly in the comments. Thus, my question is just:

Are omega-consistent extensions of PA always consistent with each other?

  • $\begingroup$ @EmilJeřábek you might be right (that it's not research level). I'm trying to resolve a discussion with a colleague, but this is not my field. $\endgroup$
    – N. Virgo
    Apr 20 '17 at 7:58
  • $\begingroup$ @EmilJeřábek thanks. The question in the title is really what I wanted to ask; the question body was just a failed attempt to state that question more formally. I've edited the question; your second comment would now make a good answer, optionally with some more detail so that someone outside the field can understand it. (I assume that "all true sentences" means "all true sentences of the form $\forall x: P(x)$" in this context, is that correct?) $\endgroup$
    – N. Virgo
    Apr 21 '17 at 3:00

$\def\pa{\mathrm{PA}}\def\N{\mathbb N}\DeclareMathOperator\Th{Th}\def\pri{\mathrm{Pr}_1}\def\code#1{\ulcorner#1\urcorner}$The answer is no: in fact, there are sentences $A$ such that $\pa+A$ and $\pa+\neg A$ are both $\omega$-consistent, while together they are visibly inconsistent.

One way to see this is to use the bounded arithmetic complexity of $\omega$-consistency: the set $$\{A: \text{$\pa+A$ is $\omega$-inconsistent}\}$$ is $\Sigma_3$ (“there exists a formula $B(x)$ such that for all $n\in\N$ there exists a PA-proof of $A\to B(n)\land\exists x\,\neg B(x)$”), hence the set $$S=\{A: \text{$\pa+A$ is $\omega$-consistent}\}$$ is $\Pi_3$. Also, if $\N\models A$, then $\pa+A$ is $\omega$-consistent; that is, $S\supseteq\Th(\N)$. However, these two sets cannot be equal, as $\Th(\N)$ is not $\Pi_3$ (in fact, it is not arithmetically definable at all). Thus, $S\supsetneq\Th(\N)$, i.e., there exists a sentence $A$ such that $\pa+A$ is $\omega$-consistent, but $\N\models\neg A$. The latter means that $\pa+\neg A$ is also $\omega$-consistent, QED. The argument actually shows that one can find a $\Sigma_3$-sentence $A$ with this property. (This is best possible: if $A$ is $\Sigma_2$, only one of $\pa+A$ and $\pa+\neg A$ is $\omega$-consistent.)

Another way to prove this is to mimick the proof of Gödel’s incompleteness theorem. Let $\pri(x)$ be the $\Sigma_3$ formula naturally expressing the predicate “the sentence $x$ is provable from $\pa$ using one application of the $\omega$-rule”. By formalizating in $\pa$ the easy arguments that (1) unnested applications of the $\omega$-rule can be collapsed to one, and (2) all true $\Sigma_3$ sentences are provable by one application of the $\omega$-rule, we obtain that $\pri$ satisfies the Hilbert–Bernays–Löb derivability conditions:

  1. $\pa\vdash_1 A\implies\pa\vdash_1\pri(\code A)$,

  2. $\pa\vdash\pri(\code{A\to B})\to(\pri(\code A)\to\pri(\code B))$,

  3. $\pa\vdash\pri(\code A)\to\pri(\code{\pri(\code A)})$,

where $\vdash_1$ denotes provability using one application of $\omega$-rule. Thus, by the standard proof of the second incompleteness theorem, $$\pa\nvdash_1\neg\pri(\code\bot).$$ That is, if $A=\pri(\code\bot)$ is the sentence asserting the $\omega$-inconsistency of $\pa$, then $\neg A$ is not provable from $\pa$ using one application of $\omega$-rule, or in other words, $\pa+A$ is $\omega$-consistent. On the other hand, $\neg A$ is true, hence $\pa+\neg A$ is also $\omega$-consistent.

  • $\begingroup$ Using a Rosser-style argument, the metatheory can be considerably weakened: specifically, $I\Sigma_2^-$ proves that for any recursively axiomatized $\omega$-consistent extension $T$ of $Q$, there is a $\Sigma_3$ sentence such that $T+A$ and $T+\neg A$ are $\omega$-consistent. $\endgroup$ Apr 22 '17 at 15:11

Another proof (due to G. Kreisel, [1]) :

Using diagonal lemma construct a sentence $K$ such that $$PA\vdash K \leftrightarrow \neg \omega -con(PA+K) ~~~~~~(I)$$ As it was noticed in the Emil's proof, omega-inconsistency is a $\Sigma_3$ property, so $K$ is a $\Sigma_3$ sentence. $K$ is false in the standard model (because if it was true, then by $(I)$ , $PA+K$ should be omega-inconsistent which is impossible, because $\mathbb{N}\vDash PA+K$). So $\mathbb{N}\vDash \neg K$ and (again by $(I)$), $\mathbb{N}\vDash \omega -con(PA+K)$, therefore $PA+K$ is omega-consistent. But $PA+\neg K$ is also omega-consistent because $\mathbb{N}\vDash \neg K$.


[1] "Necessary and sufficient conditions for undecidabillity of the Gödel sentence and its truth", Peter Clark, David DeVidi, and Michael Hallett (eds), Vintage Enthusiasms: Essays in Honour of John Bell, University of Western Ontario


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.