FOM: non-standard models, completeness, compactness

[Stephen G Simpson]

Neil's question was as follows:
 > Now here is a foundational question for logicians on this list: 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?

I mentioned some technical results that bear on this, and I tried to
summarize them in a non-technical way.  Afterward, I realized that I
had overlooked Neil's restriction to full arithmetic.  Also, Neil
questioned my summary on other grounds.  I need to say more, so let me
start over.

Technical definitions and results:

  1. RCA_0 is the subsystem of second order arithmetic with Sigma^0_1
  induction and Delta^0_1 comprehension.  It has the same consistency
  strength and is conservative over primitive recursive arithmetic
  (PRA) for Pi^0_2 sentences, hence much weaker than first order Peano
  arithmetic (PA).

  Reference: numerous papers on reverse mathematics.

  2. RCA_0^star is the subsystem of second order arithmetic with
  exponentiation, Sigma^0_0 induction, and Delta^0_1 comprehension.
  It is weaker than RCA_0.  It has the same consistency strength and
  is conservative over elementary function arithmetic (EFA) for Pi^0_2
  sentences.

  Reference:
    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.

  3. Within RCA_0 or RCA_0^star, if S is a set of first order
  sentences in a countable language, a weak model of S is defined to
  be a countable domain A (i.e. a subset of N) together with a truth
  valuation for all A-substitution instances of subformulas of
  sentences of S, such that all of the sentences of S are evaluated as
  true.  A model of S is defined in the same way except that the
  valuation extends to all first order sentences in the language of S.

  Reference: section II.8 of my forthcoming book "Subsystems of Second
  Order Arithmetic".

  4. Consistency means consistency with respect to the usual axioms
  and rules of first order logic.  The Soundness Theorem says that if
  S has a model then S is consistent.  The Strong Soundness Theorem
  says that if S has a weak model then S is consistent.  Both of these
  are provable in RCA_0 and in fact in RCA_0^star.  The proof of the
  Strong Soundness Theorem in RCA_0 and RCA_0^star uses cut
  elimination.

  5. WKL_0 is the subsystem of second order arithmetic consisting of
  RCA_0 plus weak K"onig's lemma.  WKL_0^star is defined analogously.
  These systems have the same consistency strength and are
  conservative for Pi^1_1 sentences over RCA_0 and RCA_0^star
  respectively.  See chapter IX of my book, and the Simpson-Smith
  paper.

  6. The Completeness Theorem says that if S is consistent then S has
  a model.  The Compactness Theorem says that if every finite subset
  of S has a (weak) model, then S has a model.  

  7. The Completeness and Compactness Theorem are provable in WKL_0
  and indeed in WKL_0^star.  Indeed, they are equivalent to weak
  K"onig's lemma over RCA_0^star.  See section IV.3 of my book.

  Context: Chapter IV of my book contains many results asserting that
  various mathematical theorems, including many well-known theorems in
  analysis and algebra, are equivalent to weak K"onig's lemma over
  RCA_0.  This is part of reverse mathematics.  See also my paper on
  Hilbert's program, at www.math.psu.edu/simpson/Foundations.html.

  8. By G"odel's incompleteness theorem, the consistency of PA is not
  provable in WKL_0.  Hence the existence of a (weak) model of PA is
  not provable in WKL_0.

  9. ACA_0 is the subsystem of second order arithmetic with
  arithmetical induction and arithmetical comprehension.  It has the
  same consistency strength and is conservative over PA for all first
  order sentences.  It includes WKL_0 but is much stronger than WKL_0.

  10. It is provable in RCA_0^star that there exists a full truth
  valuation for the standard structure of arithmetic N,+,* if and only
  if there exists an omega-model of ACA_0.  It follows that, in
  RCA_0^star, there exists a model of full arithmetic if and only if
  there exists an omega-model of ACA_0.  The existence of such a model
  does not imply the truth of ACA_0 or even of weak K"onig's lemma.

  11. It is provable in RCA_0^star that if there exists an omega-model
  of weak K"onig's lemma, then any consistent recursive set of
  sentences has a model.

  12. WKL_0^star proves the existence of a nonstandard model of any
  consistent fragment of PA (e.g. EFA if EFA is consistent), or of any
  theory in the language of PA that is consistent with PA.  RCA_0^star
  proves that the Scott system of any such model is a weak omega-model
  of weak K"onig's lemma.

  13. WKL_0^star proves the existence of a weak omega-model of weak
  K"onig's lemma.  On the other hand, by G"odel's incompleteness
  theorem, neither WKL_0 nor WKL_0^star proves its own consistency.
  (Recall that the Strong Soundness Theorem has a truth valuation as
  part of the hypothesis.)

Non-technical statement of conclusions relevant to Neil's question:

  1. The existence of a (standard or nonstandard) model of full
  arithmetic implies the existence of an omega-model of, and hence
  consistency of, WKL_0; WKL_0 proves the completeness and compactness
  theorems.

  2. The existence of a (standard or nonstandard) model of full
  arithmetic does not imply the completeness and compactness theorems,
  but it does imply the completeness and compactness theorems for
  recursive sets of sentences.

  3. The completeness and compactness theorems do not imply the
  existence of a (standard or nonstandard) model of full arithmetic.

  4. The completeness and compactness theorems imply that if full
  arithmetic is consistent, then there exists a nonstandard model of
  full arithmetic.

-- Steve