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 at 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.



  3. Amazing post and this article tell me how to solve math question with W rule and how to explain his solving method thanks for share it booking software .

  4. Hallo, mijn naam is Jaclyn Tibben. Ik woon in Amsterdam, Nederland en heb mijn studie gevolgd aan de University of Technology Amsterdam. Ik ben technisch ingenieur bij de helpdesk Paypal

  5. Your blog is very informative and interesting to read, finally, I found exactly what I searching for. There are lots of users of Macfee antivirus in the world because of its features and easy interface. If you want to explore more interesting facts about Mcafee antivirus or want to resolve your technical issues then must visit Mcafee ondersteuningsnummer.

  6. Hi, Thank you for sharing such a good and valuable information,It is very important for me. Gmail is the worldwide used email service but sometimes user faces some problems in it. If you want to get some information about the Gmail then you can visit Gmail suomi yhteystiedot.

  7. hi I read your blog which is really great.Please visit on this site.Bellen mcafee

  8. Geprekan yang berada di Jalan Gajahmada ini tidak kalah populer dari Ayam Geprek Pak Mus loh. Jadi Opsi menu yang berada di Super Geprek Gajahmada lumayan banyak, dan sebagian besar geprekan di sini nikmat gaes. Beberapa menu unggulan Super Geprek Gajahmada ada Lele geprek, ayam geprek, bebek geprek, udang geprek, tempe geprek, iga geprek, empal geprek, telur geprek, dan kecuali menu geprekan Super Geprek Gajahmada menyuguhkan beragam sajian yang sedap. Untuk sambal dari Super Geprek Gajahmada tak perlu disangsikan kembali, karena rasanya itu manteb sekali!