FOM: 6:Undefinability/Nonstandard Models

[Harvey Friedman]

This is the sixth 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

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

This posting was inspired by some disagreements over foundational aspects
of nonstandard analysis that appeared on the fom.

In the normal setup for nonstandard analysis, one starts with the reals R,
together with a convenient collection of relations on R which are each
given a name. One then takes a proper elementary extension of this
structure, R*, and works with R and R* and various interactions between
them. Often one simply takes a name for absolutely all relations on R.

More generally, given any structure M, with an arbitrary number of named
relations on dom(M), one can take a proper elementary extension. Assuming M
is infinite, the size of this proper elementary extension can be taken to
the greater of the cardinality of dom(M) and the number of relations used.

This construction is of course grossly nonconstructive, and raises a number
of definability issues. We consider the more rudimentary case where we
start with N = the set of all natural numbers.

As long as we use at most finitely many relations on N, no interesting
definability issues arise. However, constructivity issues do arise, as well
as algebraic and model theoretic and issues. If very simple structure is
placed on N, then one can constructively create proper elementary
extensions. For example, (N,+) has lots of effectively given proper
elementary extensions. E.g., add variable x, and consider all qx + n, where
either q is a strictly positive rational number and n is an integer, or q =
0 and n is in N. As another example, consider (R,+,x) = the ordered field
of real numbers. Again we can add a variable x, form the ordered field R[x]
of rational functions with real coefficients, and take its real closure. Or
equivlently, take germs of algebraic functions at infinity. Of course, it
is not clear what constructivity means in this context, but one can instead
start with an effectively given real closed field such as the real
algebraic numbers and perform the same construction.

PROBLEM: Give some necessary and/or sufficient conditions on a structure
for there to be "good" proper elementary extensions. Or on a (complete)
theory so that every model has a "good" proper elementary extension.

In the case of model complete theories, by definition one need only get a
"good" proper extension - it is automatically elementary. If the structure
is o-minimal, as in the two examples above, then there is no problem
getting a "good" proper elementary extension - i.e., the germs at infinity.
I'm sure that the applied model theorists know of other situations.

As a protoype of some relevant questions, consider the following. Let T be
a theory in a finite language. Investigate the following conditions on T
and their relationships:

1. Let M be a countable model of T. Then M has an (elementary) extension
satisfying T which is recursive in M.
2. There is a recursive operator which sends any countable model of T to an
(elementary) extension which is a model of T.
3. It is provable in ZF that every model of T has an (elementary) extension
which is a model of T.
4. In ZFC, there is a definable way to pass from any model of T to an
(elementary) extension which is a model of T.
5. Various model theoretic conditions on T.

Now let us consider (N,+,x). This is well known to be bad from a model
theoretic point of view, and so one expects some real badness in the proper
elementary extensions. This is of course well known. E.g., although (N,+,x)
is obviously recursively presentable, no proper elementary extension is. In
fact, it is well known that in any nonstandard model of Peano Arithmetic
with domain N, even the + must not be recursive.

For such reasons, it is completely embedded in everyone's brain that there
is no "algebraic" construction of a nonstandard model of PA. But is the
above "no recursive presentation" theorem the best way to say this?

In the usual nonstandard analysis setup, one has an elementary extension of
N with every relation of several variables individually named. Let us call
these the full elementary extensions of N.

There are some alternative equivalent formulations which uses only a finite
relational type. We can consider the relational structure
(N,+,x,S(N),epsilon), which is the standard model of "2nd order
arithemtic." Or (N,S(NxN),relational application). Or alternatively, we can
just consider (V(w+1),epsilon). If we use the cumulative hierarchy for
arithmetic, then we take (V(w),epsilon). And we take elementary extensions.
We will use the (V(w+1),epsilon) formulation.

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.

In the 70's I proved that the existence of such a probability measure on
V(w+1) cannot be proved in ZF. Furthermore, there is no definition that
provably, in ZFC, defines such a probabiliy measure. I don't know if this
is due to me; these same results were already known, and are easier, for
ultrafilters - i.e., 0,1-valued measures. I also did this for measures on
V(w+2); i.e., on all sets of reals.

Note that for the undefinability result, we only needed the isomorphism
type of M. So we can summarize as follows:

THEOREM. The existence of a proper elementary extension of (V(w+1),epsilon)
is independent of ZF. There is no formula of set theory which, provably in
ZFC, has solutions, all of which are pairwise isomorphic elementary
extensions of (V(w+1),epsilon).

QUESTION: It is clear how to pass from a nontrivial ultrafilter on V(w+1)
to a proper elementary extension of (V(w+1),epsilon). However, how do you
pass from a finitely additive nonatomic probability measure on V(w+1) to a
proper elementary extension of (V(w+1),epsilon)? Also, I don't know if
anyone has proved that you can't pass from a finitely additive nonatomic
probability measure on V(w+1) to a nontrivial ultrafilter on V(w+1).

We can weaken the concept of a proper elementary extension of
(V(w+1),epsilon). Note that they must be models of PA in which every
element of V(w+1) is the intersection with V(w+1) of a definable set. Call
this a full model of PA.

QUESTION: What is the set theoretic (definability) status of full models of
PA? We conjecture that this is weak enough so that we can construct one
explicitly in ZF.

There are many other issues, but aren't you tired of reading this?

NOTE: Apparently there is an area one might call "extending models" which
cuts across various brands of model theory with set theoretic definability,
and recursion theoretic aspects. This only scratches the surface, and I
expect to return to this more systematically.