Friday, 18 March 2011

The Completeness of PA with the $\omega$-rule

Although it's a well-known fact that the theory obtained by "closing $PA$ under the $\omega$-rule" is complete, I cannot find an immediately available online source, so here is a proof. (Something like this is in a proof theory textbook, like Takeuti, but almost all my books are a thousand miles away.)

The language $L_A$ is the first-order language of arithmetic with $=, 0, S, +$ and $\times$. Assume a Hilbert-style linear deductive system, with Modus Ponens; By "$\phi$ is an axiom of $PA$" I mean "either $\phi$ is a logical axiom or $\phi$ is one of usual axioms for $S, +$ and $\times$, or $\phi$ is an instance of induction". But we shall allow infinitely long derivations, indexed by ordinals. We define the system $PA^{\omega}$ as follows: a (possibly infinite) sequence $(\theta_0, ..., \theta_{\alpha})$ of formulas is an derivation in $\omega$-logic from $PA$ iff, for each $\beta \leq \alpha$:
(i) either $\theta_{\beta}$ is an axiom of $PA$;
(ii) or there are $\gamma, \delta < \beta$, such that $\theta_{\delta}$ has the form $\theta_{\gamma} \rightarrow \theta_{\beta}$;
(iii) or $\theta_{\beta}$ has the form $\forall x \psi(x)$ for some formula $\psi(x)$ with exactly $x$ free, and there is an injection $f : \omega \rightarrow \beta$ such that $\theta_{f(n)} = \psi(n)$, for all $n \in \omega$.
Here $\alpha, \beta, \gamma$ and $\delta$ are ordinals; derivations may be infinite; the second condition (ii) expresses a single application of Modus Ponens; the third condition (iii) expresses a single application of the $\omega$-rule - roughly, the derivation has a subsequence which is an $\omega$-sequence of the form $\psi(0), \psi(1), ...$, and the "conclusion" formula has the form $\forall x \psi(x)$.

Say that $\phi$ is a theorem of $PA$ in $\omega$-logic just when there is an $\omega$-derivation of the form $(\dots, \phi)$ from $PA$. Let $PA^{\omega}$ be the set of theorems of $PA$ in $\omega$-logic. We aim to prove that: $PA^{\omega}$ is the same as true arithmetic; that is,
Theorem. $PA^{\omega} = Th(\mathbb{N})$.
Lemma 1. If, for all $n \in \omega, \phi(n) \in PA^{\omega} $, then $\forall x \phi(x) \in PA^{\omega}$. (I.e., $PA^{\omega}$ is closed under the $\omega$-rule.)
[Proof: Assume that, for all $n \in \omega, \phi(n) \in PA^{\omega}$. So, for each $\phi(n)$, there is an $\omega$-derivation; next, take all these $\omega$-derivations (of $\phi(0), \phi(1)$, etc.) and paste them together; place the formula $\forall x \phi(x)$ at the end. This is an $\omega$-derivation of $\forall x \phi(x)$. So, $\forall x \phi(x) \in PA^{\omega}$.]

Lemma 2. If $\phi \in PA^{\omega}$, then $\mathbb{N} \models \phi$. (I.e., $PA^{\omega}$ is sound.)
[Proof: Each axiom of $PA$ is true in $\mathbb{N}$. Modus ponens is sound for $\mathbb{N}$. The $\omega$-rule is sound for $\mathbb{N}$. Hence, in any given $\omega$-derivation from $PA$, every formula is true in $\mathbb{N}$. So, all $\omega$-theorems of $PA$ are true in $\mathbb{N}$.]

Lemma 3. For all sentences $\phi$, either $\phi \in PA^{\omega}$ or $\neg \phi \in PA^{\omega}$. (I.e., $PA^{\omega}$ is complete.)
[Proof. This is by induction on the complexity of $\phi$. $PA$ is itself negation-complete for atomic sentences. If $\phi$ is of the form $\neg \theta$ and either $\theta \in PA^{\omega}$ or $\neg \theta \in PA^{\omega}$, then either $\neg \neg \theta \in PA^{\omega}$ or $\neg \theta \in PA^{\omega}$; and so, either $\phi \in PA^{\omega}$ or $\neg \phi \in PA^{\omega}$. And similarly with conjunctions.
For quantified formulas, suppose $\phi$ has the form $\forall x \psi$. As induction hypothesis, suppose that, for all $n \in \omega$, either $\psi(n) \in PA^{\omega}$ or $\neg \psi(n) \in PA^{\omega}$. Consider two cases.
Case 1. Suppose that, for all $n \in \omega$, $\psi(n) \in PA^{\omega}$. Then, $\forall x \psi \in PA^{\omega}$, by lemma 1. So, either $\phi \in PA^{\omega}$ or $\neg \phi \in PA^{\omega}$, as required.
Case 2. Suppose that, for some $n \in \omega$, $\psi(n) \notin PA^{\omega}$. So, by induction hypothesis, $\neg \psi(n) \in PA^{\omega}$. So, $\exists x \neg \psi \in PA^{\omega}$. So, $\neg \phi \in PA^{\omega}$. So, either $\phi \in PA^{\omega}$ or $\neg \phi \in PA^{\omega}$, as required.]

Lemmas 2 and 3 say that $PA^{\omega}$ is sound and complete. Hence, all of its models are elementarily equivalent. Since $\mathbb{N}$ is a model of $PA^{\omega}$, all of its models are elementarily equivalent to $\mathbb{N}$. So, $PA^{\omega} = Th(\mathbb{N})$. In fact, the only properties of $PA$ we actually needed to use are that its axioms are true in $\mathbb{N}$ and that it is negation-complete for atomic sentences. These properties both hold for Robinson arithmetic $Q$. So, we get that $Q^{\omega} = Th(\mathbb{N})$.


  1. Göran Sundholm7 August 2013 17:08

    Dear Jeffrey,
    "cannot find an immedaitely available on line source" ...
    In Torkel Franzén, 'Transfinite Progressions: A Second look at ompleteness', Bulletin of Symbolic Logic 10:3 (2004), pp. 367-389, at p. 376 ff there is an elegant proof of Shoenfield's completeness theorem for the RECURSIVE - in fact Kalmár elementary - omega-rule, which a fortiori shows that arithmetic with the unrestricted omega-rule is complete.

  2. Great, many thanks, Göran. Yes, you're right. Actually, I think Torkel showed me this by email, way back!
    To be honest, I didn't look too hard online, though; and probably some proof-theorist has some online lecture notes for it.