Nonstandard Models of Arithmetic: The Series

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 \mathbb{N}. A bit about Ramsey’s theorem (needed for Paris-Harrington). Finally, we touch on the different ways theories can be “equivalent”, thanks to a comment by Jeffrey Ketland.

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, \varphi\mapsto \varphi^\mathbb{N}. Craig’s trick and Rosser’s trick.

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: ωUUV. 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.


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 Σnnn 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.


Bibliography

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.