The Completeness of PA with the ω-rule

Although it's a well-known fact that the theory obtained by "closing PA under the ω-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 LA is the first-order language of arithmetic with =,0,S,+ and ×. Assume a Hilbert-style linear deductive system, with Modus Ponens; By "ϕ is an axiom of PA" I mean "either ϕ is a logical axiom or ϕ is one of usual axioms for S,+ and ×, or ϕ is an instance of induction". But we shall allow infinitely long derivations, indexed by ordinals. We define the system PAω as follows: a (possibly infinite) sequence (θ0,...,θα) of formulas is an derivation in ω-logic from PA iff, for each βα:
(i) either θβ is an axiom of PA;
(ii) or there are γ,δ<β, such that θδ has the form θγθβ;
(iii) or θβ has the form xψ(x) for some formula ψ(x) with exactly x free, and there is an injection f:ωβ such that θf(n)=ψ(n), for all nω.
Here α,β,γ and δ 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 ω-rule - roughly, the derivation has a subsequence which is an ω-sequence of the form ψ(0),ψ(1),..., and the "conclusion" formula has the form xψ(x).

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

Lemma 2. If ϕPAω, then Nϕ. (I.e., PAω is sound.)
[Proof: Each axiom of PA is true in N. Modus ponens is sound for N. The ω-rule is sound for N. Hence, in any given ω-derivation from PA, every formula is true in N. So, all ω-theorems of PA are true in N.]

Lemma 3. For all sentences ϕ, either ϕPAω or ¬ϕPAω. (I.e., PAω is complete.)
[Proof. This is by induction on the complexity of ϕ. PA is itself negation-complete for atomic sentences. If ϕ is of the form ¬θ and either θPAω or ¬θPAω, then either ¬¬θPAω or ¬θPAω; and so, either ϕPAω or ¬ϕPAω. And similarly with conjunctions.
For quantified formulas, suppose ϕ has the form xψ. As induction hypothesis, suppose that, for all nω, either ψ(n)PAω or ¬ψ(n)PAω. Consider two cases.
Case 1. Suppose that, for all nω, ψ(n)PAω. Then, xψPAω, by lemma 1. So, either ϕPAω or ¬ϕPAω, as required.
Case 2. Suppose that, for some nω, ψ(n)PAω. So, by induction hypothesis, ¬ψ(n)PAω. So, x¬ψPAω. So, ¬ϕPAω. So, either ϕPAω or ¬ϕPAω, as required.]

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

Comments

  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.

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

    Cheers,

    Jeff

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

    ReplyDelete
  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

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

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

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

    ReplyDelete
  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. https://resepmakanan-sehat.com/ Untuk sambal dari Super Geprek Gajahmada tak perlu disangsikan kembali, karena rasanya itu manteb sekali!

    ReplyDelete

Post a Comment