[FOM] Order type of denumerable nonstandard models

[A.P. Hazen]

    The proof that denumerable non-standard models of arithmetic-- either
of true First Order arithmetic or of such axiomatized systems as PA-- is
omega+(omega*+omega).eta (that is: the order type of the genuine naturals,
followed by infinitely many blocks, the blocks ordered like the rationals
and the non-standard numbers in each block being ordered like the integers)
is very simple: a good thing to teach to undergraduates as an elementary
sample of what model theory is about.
    The proof is given in Boolos & Jeffrey, "Computability and Logic,"
chapter 17.  Chapter 29 (only in the third, 1989, edition) gives a clear
exposition of a proof of Tennenbaum's theorem, that the OPERATIONS (as
opposed to the ORDER RELATION) of a non-standard model cannot be recursive
sets.  (The two proofs are both in chapter 25 of the re-organized fourth,
2002, edition, by Boolos, Burgess, and Jeffrey.)
    No source, however, is given for the first, "positive," result.
    (It MUST have been original with Henkin: Henkin's paper giving it was
in the JSL, and Church would surely have had him put in a reference if it
had been published by anyone else in the 300 year history of symblic logic!)

--
Allen Hazen
Philosophy Department
University of Melbourne