John Baez and I have been conducting a conversation about nonstandard models of Peano arithmetic (PA). This page serves as an annotated table of contents, bibliography, and general repository for supporting material.
Posts 1–10 are available as pdf files, formatted for small and medium screens.
John has also written an annotated table of contents.
There’s a companion series of posts, Topics in Nonstandard Arithmetic.
A Conversation between me and John Baez
Non-standard Models of Arithmetic 1: John kicks off the series by asking about recursively saturated models, and I say a bit about n-types and the overspill lemma. I mention the arithmetical hierarchy.
Non-standard Models of Arithmetic 2: John mention some references, and sets a goal: to understand Enayat’s paper “Standard Models of Arithmetic”. He describes his dream: to show that “the” standard model is a much more nebulous notion than many seem to believe. He says a bit about the overspill lemma, and Joel David Hamkins gives a quick overview of saturation.
Non-standard Models of Arithmetic 3: A few remarks on the ultrafinitists Alexander Yessenin-Volpin and Edward Nelson; also my grad-school friend who used to argue that 7 might be nonstandard.
Non-standard Models of Arithmetic 4: Some back-and-forth on Enayat’s term “standard model” (or “ZF-standard model”) for the omega of a model of ZF. Philosophy starts to rear its head.
Non-standard Models of Arithmetic 5: Hamlet and Polonius talk math, and I hold forth on my philosophies of mathematics.
Non-standard Models of Arithmetic 6: John weighs in with why he finds “the standard model of Peano arithmetic” a problematic phrase. The Busy Beaver function is mentioned.
Non-standard Models of Arithmetic 7: We start on Enayat’s paper in earnest. Some throat-clearing about Axiom SM, standard models of ZF, inaccessible cardinals, and absoluteness. “As above, so below”: how ZF makes its “gravitational field” felt in PA.
Non-standard Models of Arithmetic 8: A bit about the Paris-Harrington and Goodstein theorems. In preparation, the equivalence (of sorts) between PA and ZF¬∞. The universe Vω of hereditarily finite sets and its correspondence with 
Nonstandard Arithmetic: A Long Comment Thread: Quite sometime after posts 7 and 8 went live, Bruce Smith and John Baez added a lot of comments; it became hard to follow in that format, so I converted it to a separate webpage. I added this post to point at that webpage, and the post acquired further comments.
Non-standard Models of Arithmetic 9: I sketch the proof of the Paris-Harrington theorem.
Non-Standard Models of Arithmetic 10: Ordinal analysis, the function growth hierarchies, and some fragments of PA. Some questions that neither of us knows how to answer.
Non-standard Models of Arithmetic 11: Back to Enayat’s paper: his definition of PAT for a recursive extension T of ZF. This uses the translation of formulas of PA into formulas of ZF, 
Non-standard Models of Arithmetic 12: The strength of PAT for various T‘s. PAZF is equivalent to PAZFC+GCH, but PAZFI is strictly stronger than PAZF. (ZFI = ZF + “there exists an inaccessible cardinal”.)
Non-standard Models of Arithmetic 13: Enayat’s “natural” axiomatization of PAT, and his proof that this works. A digression into Tarski’s theorem on the undefinability of truth, and how to work around it. For example, while truth is not definable, we can define truth for statements with at most a fixed number of quantifiers.
Non-standard Models of Arithmetic 14: The previous post showed that PAT implies ΦT, where ΦT is Enayat’s “natural” axiomatization of PAT. Here we show the converse. We also interpret ΦT as saying, “Trust T”.
Non-standard Models of Arithmetic 15: We start to look at Truth (aka Satisfaction). Tarski gave a definition of Truth, and showed that Truth is undefinable. Less enigmatically put, there is no formula True(x) in the language of Peano arithmetic (L(PA)) that holds exactly for the Gödel numbers of true sentences of Peano arithmetic. On the other hand, Truth for Peano arithmetic can be formalized in the language of set theory (L(ZF)), and there are other work-arounds. We give an analogy with the Cantor diagonal argument.
Non-standard Models of Arithmetic 16: We look at the nitty-gritty of Trued(x), the formula in L(PA) that expresses truth in PA for formulas with parse-tree depth at most d. We see how the quantifiers “bleed through”, and why this prevents us from combining the whole series of Trued(x)’s into a single formula True(x). We also look at the variant SatΣn(x,y).
Non-standard Models of Arithmetic 17: More about how Trued evades Tarski’s undefinability theorem. The difference between Trued and SatΣn, and how it doesn’t matter for us. How Trued captures Truth for models of arithmetic: PA ⊢ Trued(⌜φ⌝) ↔ φ, for any φ of parse-tree depth at most d. Sketch of why this holds.
Non-standard Models of Arithmetic 18: The heart of Enayat’s paper: characterizing countable nonstandard T-standard models of PA (Prop. 6, Thm. 7, Cor. 8). Refresher on types. Meaning of ‘recursively saturated’. Standard meaning of ‘nonstandard’; standard and nonstandard meanings of ‘standard’.
Non-standard Models of Arithmetic 19: We marvel a bit over Enayat’s Prop. 6, and especially Cor. 8. The triple-decker sandwich, aka three-layer cake: ωU⊂U⊂V. More about why the omegas of standard models of ZF are standard. Refresher on ΦT. The smug confidence of a ZF-standard model. Thesis topics for grad students.
Non-standard Models of Arithmetic 20: We start to develop the proof of Enayat’s Prop. 6. We get as far as a related result: any nonstandard model of PA is recursively d-saturated. (‘Recursively d-saturated’ is our user-friendly version of the professional-grade concept: recursively Σn-saturated.) We also meet my imaginary cousin Trudy.
Non-standard Models of Arithmetic 21: Bruce Smith joins the conversation, with questions about the proof of the Paris-Harrington theorem. Preliminaries. The basic setup: PA-model N, set of diagonal indiscernibles B, and M the downward closure of B in N. The need for a transfer principle between M and N that is weaker than elementary equivalence.
Non-standard Models of Arithmetic 22: Three parts to showing that M is a model of PA: (1) M is closed under plus and times. (2) M satisfies all the axioms other than the induction axioms. (3) M satisfies the induction axioms. We do part (2), using downward persistence for ∀1 formulas, and downward persistence of Π1 formulas for an initial segment. In preparation for parts (1) and (3), we go over the definition of diagonal indiscernibles. Terminology: the barrier, the parameters.
Nonstandard Models of Arithmetic 23: Proof that M is a initial substructure, i.e., an initial segment of N closed under successor, plus, and times, and hence a structure for L(PA). (Aka ‘supercut’ or ‘multiplicative cut’.) Two general results about functions that are Δ0 definable with all parameters less than the barrier.
Nonstandard Models of Arithmetic 24: Indicators: what they indicate, some examples, two theorems about indicators for PA, and the role they play in the proof of the Paris-Harrington theorem.
Nonstandard Models of Arithmetic 25: I resume the discussion of Enayat’s paper, but without John. I begin with a recap: n-types, saturation, and recursive saturation.
Nonstandard Models of Arithmetic 26: I finish the recap: ΦT, and the proof of Enayat’s Prop. 6.
Nonstandard Models of Arithmetic 27: I start Enayat’s Theorem 7. Preview of the proof. Part 1: using the Arithmetized Completeness Theorem.
Nonstandard Models of Arithmetic 28: A digression: an apparent contradiction between the last post’s proof and the Tarski Undefinability Theorem, resolved.
Nonstandard Models of Arithmetic 29: Enayat’s Theorem 7, parts 2 and 3.
Nonstandard Models of Arithmetic 30: Enayat’s Theorem 7, part 4: back-and-forth.
Nonstandard Models of Arithmetic 31: Enayat concluded.
Topics in Nonstandard Arithmetic, companion posts
Topics in Nonstandard Arithmetic 1: Table Setting: Introduction and throat-clearing. The “Platonic style”.
Topics in Nonstandard Arithmetic 2: The Arithmetic Hierarchy (Part 1): The ∀n/∃n classification of formulas in model theory, and the related Σn/Πn/Δn hierarchies of recursion theory and Peano Arithmetic. Some motivation (uniform convergence), and the definitions.
Topics in Nonstandard Arithmetic 3: The Arithmetic Hierarchy (Part 2): Σ1(PA) statements are positively decidable. The Σ1-completeness of PA. Con(PA): Π1 but not Σ1(PA). Prepending quantifiers; prepending bounded quantifiers. General model theory: absoluteness, persistence upwards and downwards. ∀1 axiomatizability. Unions of chains: the Chang-Łoś-Suzko theorem.
Topics in Nonstandard Arithmetic 4: Truth (Part 1): Tarski’s Undefinability Theorem and his Definition of Truth. Four loopholes. First loophole: Trued. “Buried” and explicit quantifiers, and “bleeding through”. Addendum: proof of the Undefinability Theorem.
Topics in Nonstandard Arithmetic 5: Truth (Part 2): Formalizing Truth in ZF for set-based structures. Parse trees, instantiation trees, and the truth evaluation function. Why this doesn’t work for V itself.
Topics in Nonstandard Arithmetic 6: The Axioms: Two sets of axioms for PA. The Least Number Principle (LNP) as an alternative to the Induction Scheme. PA–, the axioms for a discretely ordered semiring.
Topics in Nonstandard Arithmetic 7: Truth (Part 3): SatΣn, the “professional-grade” version of Trued. It all comes down to SatΔ0. Similarities and differences to the ZF version for set-based structures.
Topics in Nonstandard Arithmetic 8: Extensions and Substructures: Definitions of various kinds of extensions/substructures: elementary, Σn– and Δ0-elementary, cofinal, and end/initial. End extensions are Δ0-elementary. Moles and the Roman Empire. A grab bag of results: the MacDowell-Specker Theorem, the Mole Disguise Lemma, Gaifman’s Splitting Theorem, and Friedman’s Theorem.
Topics in Nonstandard Arithmetic 9: Tricks with Quantifiers: Exchanging quantifiers (∃∀⇒∀∃). Skolem functions. Turnstile jumping. Cofinal extensions. Collection. “Finite” sequences. The MRDP Theorem. Examples of use: the Mole Disguise Lemma, the existence of proper elementary cofinal extensions, and Gaifman’s Splitting Theorem.
Topics in Nonstandard Arithmetic 10: Truth (Part 4): The Arithmetized Completeness Theorem (ACT). Sketch of Henkin’s proof of the usual Completeness Theorem, how to formalize this in PA, and how this gives a notion of satisfaction extending to usual notion into the realm of “nonstandard formulas”. How it’s used to construct end-extensions.
Bovykin, Andrey. Brief introduction to unprovability.
Enayat, Ali. Standard Models of Arithmetic. Festschrift volume for Christian Bennet, Gothenburg, Sweden, September 2014.
Gaifman, Haim and Constantine Dimitracopoulous. Fragments of Peano’s Arithmetic and the MRDP theorem. Monographie de L’Enseignement Mathematique 30. pp. 187-206, 1982.
Goodstein, R.L. On the restricted ordinal theorem. The Journal of Symbolic Logic, vol.9 no.2, pp. 33–41, June 1944.
Hájek and Pudlák. Metamathematics of First-Order Arithmetic. Perspectives in Mathematical Logic, Springer-Verlag, 1993.
Hodges, Wilfrid. A Shorter Model Theory. Cambridge University Press, 1997.
Katz, Matthew and Jan Reimann. An Introduction to Ramsey Theory: Fast Functions, Infinity, and Metamathematics. Student Mathematical Library, American Mathematical Society, 2018. (See also the errata.)
Kaye, Richard. Models of Peano Arithmetic. Oxford Logic Guides, Oxford University Press, 1991.
Kaye, Richard and Tin Lok Wong. On Interpretations of Arithmetic and Set Theory. Notre Dame Journal of Formal Logic, 2007.
Kirby, Laurie and Jeff Paris. Accessible Independence Results for Peano Arithmetic. Bull. London Math. Soc. vol.14, pp.285–293, 1982,
Kossak & Schmerl. The Structure of Models of Peano Arithmetic. Oxford Logic Guides, Oxford University Press, 2006.
Paris, Jeff. A Mathematical Incompleteness in Peano Arithmetic. In Handbook of Mathematical Logic, ed. Jon Barwise, Studies in Logic and the Foundations of Mathematics, Elsevier, 1977. [The Paris-Harrington Theorem.]
Wong, Tin Lok. Model Theory of Arithmetic. Notes for a course at the University of Vienna, 2014.
Wong, Tin Lok. Logic and Foundation of Mathematics I: the consistency of arithmetic. Notes for a course at the National University of Singapore, 2018/19.
Diagonal Argument 