Nonstandard Models of Arithmetic

There seems to be a murky abyss lurking at the bottom of mathematics. While in many ways we cannot hope to reach solid ground, mathematicians have built impressive ladders that let us explore the depths of this abyss and marvel at the limits and at the power of mathematical reasoning at the same time.

This is a quote from Matthew Katz and Jan Reimann’s book An Introduction to Ramsey Theory: Fast Functions, Infinity, and Metamathematics. I’ve been been talking to my old friend Michael Weiss about nonstandard models of Peano arithmetic on his blog. We just got into a bit of Ramsey theory. But you might like the whole series of conversations, which are precisely about this murky abyss.

Here it is so far:

Part 1: I say I’m trying to understand ‘recursively saturated’ models of Peano arithmetic, and Michael dumps a lot of information on me. The posts get easier to read after this one!

Part 2: I explain my dream: to show that the concept of ‘standard model’ of Peano arithmetic is more nebulous than many seem to think. We agree to go through Ali Enayat’s paper Standard models of arithmetic.

Part 3: We talk about the concept of ‘standard model’, and the ideas of some ultrafinitists: Alexander Yessenin-Volpin and Edward Nelson.

Part 4: Michael mentions “the theory of true arithmetic”, and I ask what that means. We decide that a short dive into the philosophy of mathematics may be required.

Part 5: Michael explains his philosophies of mathematics, and how they affect his attitude toward the natural numbers and the universe of sets.

Part 6: After explaining my distaste for the Punch-and-Judy approach to the philosophy of mathematics (of which Michael is thankfully not guilty), I point out a strange fact: our views on the infinite cast shadows on our study of the natural numbers. For example: large cardinal axioms help us name larger finite numbers.

Part 7: We discuss Enayat’s concept of “a T-standard model of PA”, where T is some axiom system for set theory. I describe my crazy thought: maybe your standard natural numbers are nonstandard for me. We conclude with a brief digression into Hermetic philosophy: “as above, so below”.

Part 8: We discuss the tight relation between PA and ZFC with the axiom of infinity replaced by its negation. We then chat about Ramsey theory as a warmup for the Paris–Harrington Theorem.

Part 9: Michael sketches the proof of the Paris–Harrington Theorem, which says that a certain rather simple theorem about combinatorics can be stated in PA, and proved in ZFC, but not proved in PA. The proof he sketches builds a nonstandard model in which this theorem does not hold!

Part 10: Michael and I talk about “ordinal analysis”: a way of assigning ordinals to theories of arithmetic, that measures how strong they are.

Part 11: Michael begins explaining Enayat’s paper Standard models of arithmetic. I pull him into explaining “Craig’s trick” and “Rosser’s trick”, two famous tricks in mathematical logic.

6 Responses to Nonstandard Models of Arithmetic

  1. Toby Bartels says:

    I like that argument that 7 may be nonstandard, since it takes 7 symbols to write a proof that 7 exists, and that's too long to be acceptable, since every nonstandard number n has a proof of length n that it exists. I argue that 7 definitely does exist, but only because it’s feasible (meaning that it exists in the world of ultrafinitism, unlike 2^100). I know that 7 exists, because here is the proof: SSSSSS1. Yeah, I know, that took 7 symbols, but this isn't some circular argument that 7 exists because that proof exists because 7 exists; 7 exists because the proof exists because it's right there in front of me! But that only works because 7 is feasible; you can't argue like that with 2^100. (Since we're working in PA, rather than in some ultrafinitist system, we can prove that 2^100 exists in some other way, then prove that the proof of length 2^100 exists as well. But we can't start with the proof of length 2^100, whereas we can start work the proof of length 7, because 7 is feasible.)

    • Ahh, but then 7 might be non-standard for my golden retriever!

      This reminds me of the passage in Kasner and Newman’s Mathematics and the Imagination, where they introduce the googolplex:

      The name “googol” was invented by a child…At the same time that he suggested “googol” he gave a name for a still larger number: “Googolplex”…. It was first suggested that a googolplex should be 1, followed by writing zeros until you got tired…. but different people get tired at different times and it would never do to have Carnera a better mathematician than Dr. Einstein, simply because he had more endurance.

      (Primo Carnera was a heavy-weight champion boxer.)

      • Toby Bartels says:

        True. I notice that while the original definition of a googolplex may have been imprecise, it's still definitely less than the standardized definition (1 googolplex = 10^(1 googol), where 1 googol = 10^100).

  2. Ishi Crew says:

    I am commenting partly to ‘bookmark’ this page. When I see the name Yessenin-Volpin (and also Edward Nelson) i put this in my ‘curiosities’ section–the armadillo of math. .

    arXiv has papers on Russian mathematical history involving Volpin
    (I think Y-V’s assistant Catherine Hennix has some very weird music on youtube; Nelson had his own ‘stochastic mechanics’ theory which looked equivalent to Bohmian mechanics to me). Doron Zeilberger (of Rutgers) is another ultrafinitist with an amusing web site (eg ‘pi is not a number’; and he cites a paper by a German physicist who claimed to have a local hidden variable theory of QM—Zeilberger said he didn’t endorse the theory. ).

    Seems about right that the Paris-Harrington theorem does not hold in some NSA models. You might get that from Lowenheim-Skolem theorem. (There is the related Goodstein’s theorem, implemented as the ‘hydra game’ in computer graphics).

    There is a small ‘cottage industry’ –mostly non-academics, though some academics—devoted to disproving Godel’s theorem, Cantor’s diagonal argument, etc. (Even Nelson tried to prove Peano arithmetic was inconsistant as have a few other mathematical logicians.)

    • Seems about right that the Paris-Harrington theorem does not hold in some NSA models.

      (One should say, the Paris-Harrington principle does not hold… The Paris-Harrington theorem is the fact that the PH principle isn’t provable in Peano arithmetic.)

      In fact, one of the original proofs by Paris and Harrington consisted of constructing an NSA in which the Paris-Harrington principle doesn’t hold. However, you don’t get that model anywhere nearly so easily as by invoking the Löwenheim-Skolem theorem—the argument requires intricate combinatorics plus ingenious logic. See Part 9 of the series in diagonalargument.com for a quick sketch, and the book by Katz & Reimann for more details.

  3. John Baez says:

    More episodes:

    Part 10: Michael and I talk about “ordinal analysis”: a way of assigning ordinals to theories of arithmetic, that measures how strong they are.

    Part 11: Michael begins explaining Enayat’s paper Standard models of arithmetic. I pull him into explaining “Craig’s trick” and “Rosser’s trick”, two famous tricks in mathematical logic.

You can use Markdown or HTML in your comments. You can also use LaTeX, like this: $latex E = m c^2 $. The word 'latex' comes right after the first dollar sign, with a space after it.

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.