4

Lindenbaum's Lemma says that every consistent theory has a complete consistent extension. Can this be extended to omega-consistent theories? Does every omega-consistent theory have a complete omega-consistent extension?

Does the following argument sustain the conclusion that every omega-consistent theory does indeed have a complete omega-consistent extension?

"Let T be omega-consistent. Then T has a consistent complete extension T'. Suppose T' is not omega-consistent. Then there are in T' sentences F0, F1, ... for every n, and also the sentence ~allx Fx. Let T" be the theory that comes from T' by deleting every such ~allx xFx and replacing it with allx xFx. Then T" is a complete omega-consistent extension of T."

Keith
  • 133
  • Isn't it true that $\omega$-consistent theories are true in $\Bbb N$? In which case, trivially, yes. (I might be wrong, though, so take this with a grain of salt.) – Asaf Karagila Nov 18 '16 at 11:44
  • 1
    @Asaf Karagila: the result is that a theory is true in the standard model if and only if it is consistent in $\omega$-logic (with the infinitary $\omega$ rule). This is stronger than being just $\omega$ consistent. There is some info in https://en.wikipedia.org/wiki/%CE%A9-consistent_theory#.CF.89-logic – Carl Mummert Nov 20 '16 at 04:16
  • @Carl: Thank you for the correction! – Asaf Karagila Nov 20 '16 at 05:24
  • Many thanks @Asaf and Carl. I've edited my question to make it clearer what I need help with. I'd really appreciate your advice. – Keith Nov 21 '16 at 10:47

1 Answers1

2

Perhaps surprisingly, the answer is no!


First, we prove the following weaker result:

Lemma: the only complete $\omega$-consistent theory containing "enough arithmetic" (Robinson's arithmetic $\mathsf{R}$ is enough) is $T=Th(\mathbb{N})$.

Proof.$\quad$Let $T$ be a complete $\omega$-consistent theory containing $\mathsf{R}$. We'll prove by induction on $k$ that for each $k$, $T$ proves every true $\Pi_k$ sentence and every $\Sigma_k$ sentence.

The base case $k=1$ follows by $\Sigma_1$-completeness of $\mathsf{R}$: our theory $T$ proves every true $\Sigma_1$ sentence, and therefore in order to be complete and $\omega$-consistent it must also prove every $\Pi_1$ sentence.

Next, we suppose the result holds for $k$ and show that it also holds for $k+1$:

  • Fix a $\Sigma_k$-formula $\psi(x)$ and suppose the $\Pi_{k+1}$ sentence $\forall x\psi(x)$ is true; we want to show that $T\vdash \forall x\psi(x)$. Suppose otherwise. Then by completeness, $T\vdash\exists x\neg\psi(x)$. But since $\forall x\psi(x)$ is true, by the induction hypothesis we have $T\vdash\psi(\underline{n})$ for each $n$. And this contradicts $\omega$-consistency.

  • Fix a $\Pi_k$-formula $\psi(x)$ and suppose the $\Sigma_{k+1}$ sentence $\exists x\psi(x)$ is true; we want to show that $T\vdash\exists x\psi(x)$. Since $\exists x\psi(x)$ is true, let $n$ be such that $\psi(\underline{n})$ is true. The sentence $\psi(\underline{n})$ is $\Pi_k$ and true, hence by induction we have $T\vdash\psi(\underline{n})$ and so $T\vdash\exists x\psi(x)$ by existential generalization.

This finishes the proof. $\quad\Box$

As an aside, note that only the first bulletpoint used $\omega$-consistency. More generally, if $S$ is a theory proving all true $\Pi_k$ sentences, then $S$ also proves all true $\Sigma_{k+1}$ sentences. This is an interesting asymmetry in the arithmetic hierarchy between the "$\Pi$" and "$\Sigma$" sides.


We now argue as follows:

Corollary: there is an $\omega$-consistent theory containing "enough arithmetic" which has no $\omega$-consistent completion.

Proof.$\quad$ Suppose otherwise. Then we have that for every sentence $\varphi$, exactly one of the following holds:

  • $\varphi$ is true, or

  • $\mathsf{R}+\varphi$ is $\omega$-inconsistent.

Clearly we can't have them both hold; conversely, if they both failed we would get a complete $\omega$-consistent theory containing a false sentence, contradicting the lemma.

But this means that $Th(\mathbb{N})$ can be computed from $\{\varphi:\neg\omega Con(\mathsf{R}+\varphi)\}$. But this can't be: the latter is $\Pi_3$-definable while the former isn't even arithmetic.

Noah Schweber
  • 245,398