# Isomorphism types or structure theory for nonstandard analysis

My question is about nonstandard analysis, and the diverse possibilities for the choice of the nonstandard model R*. Although one hears talk of the nonstandard reals R*, there are of course many non-isomorphic possibilities for R*. My question is, what kind of structure theorems are there for the isomorphism types of these models?

Background. In nonstandard analysis, one considers the real numbers R, together with whatever structure on the reals is deemed relevant, and constructs a nonstandard version R*, which will have infinitesimal and infinite elements useful for many purposes. In addition, there will be a nonstandard version of whatever structure was placed on the original model. The amazing thing is that there is a Transfer Principle, which states that any first order property about the original structure true in the reals, is also true of the nonstandard reals R* with its structure. In ordinary model-theoretic language, the Transfer Principle is just the assertion that the structure (R,...) is an elementary substructure of the nonstandard reals (R*,...). Let us be generous here, and consider as the standard reals the structure with the reals as the underlying set, and having all possible functions and predicates on R, of every finite arity. (I guess it is also common to consider higher type analogues, where one iterates the power set ω many times, or even ORD many times, but let us leave that alone for now.)

The collection I am interested in is the collection of all possible nontrivial elementary extensions of this structure. Any such extension R* will have the useful infinitesimal and infinite elements that motivate nonstandard analysis. It is an exercise in elementary mathematical logic to find such models R* as ultrapowers or as a consequence of the Compactness theorem in model theory.

Since there will be extensions of any desired cardinality above the continuum, there are many non-isomorphic versions of R*. Even when we consider R* of size continuum, the models arising via ultrapowers will presumably exhibit some saturation properties, whereas it seems we could also construct non-saturated examples.

So my question is: what kind of structure theorems are there for the class of all nonstandard models R*? How many isomorphism types are there for models of size continuum? How much or little of the isomorphism type of a structure is determined by the isomorphism type of the ordered field structure of R*, or even by the order structure of R*?

-
I haven't read the book, but it appears that "Super-Real Fields" by Dales & Woodin is really about that very question. –  François G. Dorais Jan 6 '10 at 19:14
Uh, oh. I hope this doesn't put me in the doghouse with Woodin! :-) (He was my advisor 15-20 years ago.) Actually, now I remember Dales giving a number of seminar talks in Berkeley on superreal fields, when he was visiting Woodin at that time. –  Joel David Hamkins Jan 6 '10 at 22:18

Under a not unreasonable assumption about cardinal arithmetic, namely $2^{<c}=c$ (which follows from the continuum hypothesis, or Martin's Axiom, or the cardinal characteristic equation t=c), the number of non-isomorphic possibilities for *R of cardinality c is exactly 2^c. To see this, the first step is to deduce, from $2^{<c} = c$, that there is a family X of 2^c functions from R to R such that any two of them agree at strictly fewer than c places. (Proof: Consider the complete binary tree of height (the initial ordinal of cardinality) c. By assumption, it has only c nodes, so label the nodes by real numbers in a one-to-one fashion. Then each of the 2^c paths through the tree determines a function f:c \to R, and any two of these functions agree only at those ordinals $\alpha\in c$ below the level where the associated paths branch apart. Compose with your favorite bijection R\to c and you get the claimed maps g:R \to R.) Now consider any non-standard model *R of R (where, as in the question, R is viewed as a structure with all possible functions and predicates) of cardinality c, and consider any element z in *R. If we apply to z all the functions *g for g in X, we get what appear to be 2^c elements of *R. But *R was assumed to have cardinality only c, so lots of these elements must coincide. That is, we have some (in fact many) g and g' in X such that *g(z) = *g'(z). We arranged X so that, in R, g and g' agree only on a set A of size $<c$, and now we have (by elementarity) that z is in *A. It follows that the 1-type realized by z, i.e., the set of all subsets B of R such that z is in *B, is completely determined by the following information: A and the collection of subsets B of A such that z is in *B. The number of possibilities for A is $c^{<c} = 2^{<c} = c$ by our cardinal arithmetic assumption, and for each A there are only c possibilities for B and therefore only 2^c possibilities for the type of z. The same goes for the n-types realized by n-tuples of elements of *R; there are only 2^c n-types for any finite n. (Proof for n-types: Either repeat the preceding argument for n-tuples, or use that the structures have pairing functions so you can reduce n-types to 1-types.) Finally, since any *R of size c is isomorphic to one with universe c, its isomorphism type is determined if we know, for each finite tuple (of which there are c), the type that it realizes (of which there are 2^c), so the number of non-isomorphic models is at most (2^c)^c = 2^c.

To get from "at most" to "exactly" it suffices to observe that (1) every non-principal ultrafilter U on the set N of natural numbers produces a *R of the desired sort as an ultrapower, (2) that two such ultrapowers are isomorphic if and only if the ultrafilters producing them are isomorphic (via a permutation of N), and (3) that there are 2^c non-isomorphic ultrafilters on N.

If we drop the assumption that $2^{<c}=c$, then I don't have a complete answer, but here's some partial information. Let \kappa be the first cardinal with 2^\kappa > c; so we're now considering the situation where \kappa < c. For each element z of any *R as above, let m(z) be the smallest cardinal of any set A of reals with z in *A. The argument above generalizes to show that m(z) is never \kappa and that if m(z) is always < \kappa then we get the same number 2^c of possibilities for *R as above. The difficulty is that m(z) might now be strictly larger than \kappa. In this case, the 1-type realized by z would amount to an ultrafilter U on m(z) > \kappa such that its image, under any map m(z) \to \kappa, concentrates on a set of size < \kappa. Furthermore, U could not be regular (i.e., (\omega,m(z))-regular in the sense defined by Keisler long ago). It is (I believe) known that either of these properties of U implies the existence of inner models with large cardinals (but I don't remember how large). If all this is right, then it would not be possible to prove the consistency, relative to only ZFC, of the existence of more than 2^c non-isomorphic *R's.

Finally, Joel asked about a structure theory for such *R's. Quite generally, without constraining the cardinality of *R to be only c, one can describe such models as direct limits of ultrapowers of R with respect to ultrafilters on R. The embeddings involved in such a direct system are the elementary embeddings given by Rudin-Keisler order relations between the ultrafilters. (For the large cardinal folks here: This is just like what happens in the "ultrapowers" with respect to extenders, except that here we don't have any well-foundedness.) And this last paragraph has nothing particularly to do with R; the analog holds for elementary extensions of any structure of the form (S, all predicates and functions on S) for any set S.

-
Andreas, Welcome to MO! I am very glad to see you here, and thank you very much for your thorough answer. –  Joel David Hamkins Jun 17 '10 at 12:08
Andreas, I noticed that you may have multiple MO identities (see mathoverflow.net/users/6428). The moderators can merge these. I'll flag this post to bring the issue to their attention. –  Joel David Hamkins Jun 18 '10 at 12:59
Thanks Joel! ... –  Scott Morrison Jun 18 '10 at 15:56

I think that the nonstandard models of R* will be fairly wild by most reasonable metrics, since the theory is unstable (the universe is linearly ordered). For instance, I don't think that arbitrary models will be determined up to isomorphism by well-founded trees of countable submodels (as they are in classifiable'' theories).

EDIT: I'm not sure how many nonisomorphic models there are of cardinality c (the size of the continuum), but there are 2^{2^c} distinct nonisomorphic nonstandard models of theory of R* of size 2^c. A crude counting argument shows that this is the maximum number of nonisomorphic models of size 2^c that any theory with a language of cardinality 2^c could possibly have, which can be considered as evidence that the class of models of the theory of R* is wild.''

(This result follows from the proof of Theorem VIII.3.2 of Shelah's Classification Theory, one of his many-models'' arguments about unclassifiable theories. In fact, an argument from the second chapter of my thesis applied to this theory shows that you can even build a collection of 2^{2^c} models of size 2^c which are pairwise bi-embeddable but pairwise nonisomorphic.)

It's a good question whether or not you can have two models of this theory which are order-isomorphic but nonisomorphic -- there must be somebody studying o-minimal structures with an answer to this.

-
Thanks for the answer! I'd love to hear about how the size of the language affects the situation with stability... –  Joel David Hamkins Jan 6 '10 at 1:16
Isn't your crude bound off by a power set? After all, the language here has size 2^c, not c. By my crude calculations, then, a model is determined up to isomorphism by a list of 2^c many subsets of a set of size c. But this gives 2^{2^c} not 2^{2^omega}. ( c = continuum = 2^omega ) Does this problem affect the rest of your answer? –  Joel David Hamkins Jan 6 '10 at 14:06
@Joel: You're right, I was thinking that the size of the language was only c, not 2^c, which does affect my answer (which I just edited). A lot of things seem to break down when you start thinking about structures that are smaller than their language (e.g. Lowenheim-Skolem won't work to produce such models). –  John Goodrick Jan 6 '10 at 19:23

Let me offer one counterpoint to John's excellent answer.

Under the Continuum Hypothesis, the ultrapower version of R* will be saturated in any countable language. That is, it will realize all finitely realizable countable types with countably many parameters. Thus, by the usual back-and-forth construction, if we take the reduct to any countable part of the language, such as the ordered field structure and more, then under CH there will be only one saturated model of size continuum.

I'm not sure if John's construction can produce saturated models, but if so, then under CH this observation will answer his question at the end about whether one can have non-isomorphic R*'s that are isomorphic orders or even as ordered fields.

-

The following was useful in a recent paper on asymptotic cones with Kramer, Shelah and Tent. How many ultraproducts $\prod_{\mathcal{U}} \mathbb{N}$ exist up to isomorphism, where $\mathcal{U}$ is a non-principal ultrafilter over $\mathbb{N}$? If $CH$ holds, then obviously just one ... if $CH$ fails, then $2^{2^{\aleph_{0}}}$.

In the case when $CH$ fails, the ultraproducts are already nonisomorphic as linearly ordered sets. The proof uses the techniques of Chapter VI of Shelah's book "Classification Theory and the Number of Non-isomorphic Models".

-

See Robinson's book Non-Standard Analysis (North-Holland 1966)...
Section 3.1 has some remarks about the order type of the non-standard natural numbers.

-
In the case of countable nonstandard models of arithmetic, the order type is clearly omega+ZQ, since there will be a Z chain around each nonstandard integer, and the Z blocks will be densely ordered, hence Q many of them. Does he classify the order-type arising for the N of R*? I guess it has order type omega+Zt for some dense order type t, which looks closely related to R. –  Joel David Hamkins Jan 6 '10 at 16:34
This is his Theorem 3.1.6 ... the order type is omega + (omega* + omega) theta , where theta is a dense order type without first or last element. –  Gerald Edgar Jan 7 '10 at 16:45