FOM: 7:Undefinability/Nonstandard Models

[Harvey Friedman]

This is the seventh in a series of positive self contained postings to fom
covering a wide range of topics in f.o.m. Previous ones are:

1:Foundational Completeness   11/3/97, 10:13AM, 10:26AM.
2:Axioms  11/6/97.
3:Simplicity  11/14/97 10:10AM.
4:Simplicity  11/14/97  4:25PM
5:Constructions  11/15/97  5:24PM
6:Undefinability/Nonstandard Models   11/16/97  12:04AM

Let me remind you that a complete archiving of fom, message by message, is
available at http://www.math.psu.edu/simpson/fom/index.html

I want to clarify some matters from 6:Undefinability/Nonstandard Models
regarding proper elementary extensions of (V(w+1),epsilon). If we just want
to show that "there exists a proper elementary extension M of
(V(w+1),epsilon)" cannot be proved in ZF, one can avoid my consideration of
finitely additive nonatomic probability measures on V(w+1) altogether and
instead use the totally standard argument that derives a nontrivial
ultrafilter on all subsets of w. The argument goes like this: just fix a
nonstandard integer n, and given any subset A of omega, ask whether or not
n lies in the nonstandard version of A. Then combine this with the well
known result that the existence of a nontrivial ultrafilter on all subsets
of w is not provable in ZF. I am grateful to Steve for pointing this out.

However, the matter of the set theoretic definability of proper elementary
extensions of (V(w+1),epsilon) is much more delicate. I carelessly wrote in
6:

 > Now proper elementary extensions of (V(w+1),epsilon) are necessarily
 > pathological. To see this, first observe that from a proper elementary
 > extension M of (V(w+1),epsilon), one can easily construct a finitely
 > additive nonatomic probability measure on V(w+1); i.e., where singetons get
 > measure 0. To see this, let n be a nonstandard integer in M, and let E be a
 > subset of V(w). Look at the nonstandard fraction of elements of E in V(n)
 > compared to the elements of V(n). Define the measure to be the real part of
 > this nonstandard fraction.

But this construction relies on the choice of the nonstandard integer n in
M! So this does NOT establish, e.g., that there is no provably definable
proper elementary extension of (V(w+1),epsilon) in ZFC.

In fact, using so called special models of power beth_omega, one can prove
the existence of a definable proper elementary extension of
(V(w+1),epsilon) within ZFC, up to isomorphism, contrary to what I said. In
particular, the construction builds a definable family of proper elementary
extensions of V(w+1,epsilon), any two of which are isomorphic by an
isomorphism that is the identity on V(w+1).

Several questions remain:

1. Can one construct an individual proper elementary extension of V(w+1)
definably within ZFC?
2. Can one construct a proper elementary extension of V(w+1) of power c
definably within ZFC up to isomorphism? Or at least with at most c
nonstandard integers?
3. What about defining a nonstandard integer within some definable proper
elementary extension up to isomorphism?

I don't see how to answer 1. However, I can answer 2. The answer is no.
Here is the formal result:

THEOREM 1. There is no formula A(x) in the language of ZFC such that the
following is provable in ZFC. A has solutions, all of which are proper
elementary extensions of V(w+1) with at most c integers, where any two
solutions are isomorphic.

To prove this, note that if otherwise, there would be, provably in ZFC, a
definable set of power at most c of nontrivial ultrafilters on all subsets
of w. However, we know that this cannot be. Note that we don't need to add
"which is the identity on V(w+1)" at the end.

All right, I have to admit that this idea that maybe the nonstandard
universe could be unique in some reasonable sense is still alive because of
such results as the existence of a definable proper elementary extension of
V(w+1) provably within ZFC, up to isormorphism (although we don't know the
answer to problem 1 above). But then also one wants an example of an
infinitesimal. The following says that we can't do this.

THEOREM 2. There is no formula A(x,y) of ZFC such that the following is
provable in ZFC. A defines a funciton F such that
	a) dom(F) is a nonempty set of proper elementary extensions of V(w+1);
	b) for all M in dom(F), F(M) is a nonstandard integer in M;
	c) for all M and M' in dom(F), there is an isomorphism from
(M,F(M)) onto (M',F(M')) which is the identity on V(w+1).

The proof is that one would get a provably definable ultrafilter on all
subsets of w in ZFC.

For the sake of completeness of this series of positive postings, I note
here a conservative extension result (approx. 1967) that I stated at the
end of my posting Replies/NonstandardAnalysis, 1PM 11/12/97:

>Add a predicate St(x) for "x is standard" to the language of Peano
>Arithmetic (PA). Consider the following axioms:

>1. Usual equational axioms and axioms for successor.
>2. Induction for all formulas with respect to the Standard integers only.
>3. Induction for all formulas that don't mention St with respect to all
>integers.
>4. The successor of every standard integer is standard.
>5. There exists a nonstandard integer.

>THEOREM. Every sentence without St that is provable is already provable in PA.

>PS: Now that my interest in conservative extension results of this kind
>has been rekindled, maybe Rick and some others on FOM can state some other
>>conservative extension results.

NOTE: See how old subjects get a fresh look when looked at through the
lense of f.o.m. I got on this because of assertions that I disagreed with
about the f.o.m. nature of nonstandard analysis - i.e., the(?)
infinitesimals, examples(?) of infinitesimals, etcetera. And the
conservative extension result is another example, in which old subjects get
a fresh look when looked at through the lense of f.o.m. Such conservative
extension results will be the subject of a future postive posting. Also
note the level of interaction between model theory and set theory.