FOM: non-standard models, completeness, compactness
Stephen G Simpson
simpson at math.psu.edu
Sat Dec 6 12:50:01 EST 1997
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
More information about the FOM
mailing list