FOM: answer to Neil's question about nonstandard models of arithmetic

[Stephen G Simpson]

Neil Tennant writes:
 > Is there any proof of existence of non-standard models for full arithmetic
 > that uses methods and assumptions too weak to prove either completeness
 > (on sets of sentences) or compactness?

Basically, no.  The existence of a nonstandard model M of arithmetic
implies the existence of an omega-model of weak K"onig's lemma, namely
the Scott system of M.  And the G"odel completeness and compactness
theorems hold in any such omega-model; in fact, they are equivalent to
weak K"onig's lemma, in the sense of reverse mathematics.  All of this
is provable in weak systems, e.g. RCA_0.  Some of this is sensitive to
exactly how you formulate the definition of "model"; there is a
difficulty with satisfaction predicates.  Details are in sections II.8
and IV.3 of my forthcoming book "Subsystems of Second Order
Arithmetic".  Actually, instead of RCA_0, RCA_0^star is enough; see

    Stephen G. Simpson and Rick Smith, Factorization of polynomials
    and Sigma^0_1 induction, Annals of Pure and Applied Logic, 31,
    1986, pp. 289-306.

However, this is not quite an airtight answer to Neil's question,
because the existence of a nonstandard model of arithmetic does not
literally imply weak K"onig's lemma.  It only implies the existence of
an omega-model of weak K"onig's lemma, as noted above.  Nevertheless,
I would be willing to (somewhat loosely) summarize the precise results
above as follows: The existence of nonstandard models of arithmetic is
equivalent to the G"odel completeness and compactness theorems.

-- Steve