# Example of non-isomorphic structures which are elementarily equivalent

I just started learning model theory on my own, and I was wondering if there are any interesting examples of two structures of a language L which are not isomorphic, but are elementarily equivalent (this means that any L-sentence satisfied by one of them is satisfied by the second).

I am using the notaion of David Marker's book "Model theory: an introduction".

-

Let me make a couple of comments on Pete's answer--this is my first time here and I don't see how to leave comments.

2) Any two dense linear orders without endpoints are elementarily equivalent. In particular $(Q,<)$ and $(R,<)$ are elementarily equivalent. So there is no first order way of expressing the completeness of the reals.

3) Any two algebraically closed fields of the same characteristic are elementarily equivalent. So the algebraic numbers is elementarily equivalent to the complex numbers. This means you can prove first order things about the algebraic numbers using complex analysis or the complex numbers using Galois Theory or countability.

4) Similarly the reals field is elementarily equivalent to the real algebraic numbers or to the field of real Puiseux series. One can for example use the Puiseux series to prove asymptotic properties of semialgebraic functions.

Finally, Pete's comment 5) about infinite models of the theory of finite fields being elementarily equivalent isn't quite right. This is only true if the relative algebraic closure of the prime fields are isomorphic. For example,

a) take an ultrapower of finite fields $F_p$ where the ultrafilter containing {2,4,8,...} then the resulting model has characteristic 2, while if the ultrafilter contains the set of primes, then the ultraproduct has characteristic 0.

b) if the ultrapower contains the set of primes congruent to 1 mod 4, in the ultraproduct -1 is a square, while if the ultraproduct contains the set of primes congruent to 3 mod 4 then in the ultraproduct -1 is not a square..

-
Are there important examples of 3) where the result about algebraic numbers can't (as far as is known) be proved by purely algebraic methods (or the result about complex numbers can't be proved directly by complex methods)? Also, hi again! – Akhil Mathew Aug 6 '10 at 2:24
Dave, to leave comments one needs to amass 50 rep points here. – Robin Chapman Aug 6 '10 at 6:49
Thanks very much for your answer. You're right, of course -- I was being too hasty. – Pete L. Clark Aug 6 '10 at 9:28
Hi Akhil!--I don't know a good example for algebraically closed fields. I seem to recall there is a theorem in Buium's "Differential Algebra and Diophantine Geometry" where he proves a result by working over the algebraic numbers and using countability. I know of more interesting applications over the reals. – Dave Marker Aug 6 '10 at 18:49
Hm, interesting--thanks. What would be an example over the reals? – Akhil Mathew Aug 7 '10 at 0:58

Laws, yes[1]: if there weren't such examples, there wouldn't be a subject called model theory and therefore Marker's book would not exist.

There are, however, not very many explicit examples which can be given, with proof, right after the definition of elementary equivalence, a pedagogical problem that I encounered recently when I taught a short summer course on model theory. When I first gave the definition, all I was able to come up with was the following argument: for any language $L$, the class of $L$-structures is a proper class [any nonempty set can be made into the "universe", or underlying set of, an $L$-structure] whereas since there are at most $2^{\max|L|,\aleph_0}$ different theories in the language $L$, the $L$-structures up to elementary equivalence must form a set.

But if you just want examples without proof, sure, here goes:

1) In the empty language, two sets are elementarily equivalent iff they are both infinite or both finite of the same cardinality.

2) Any two dense linear orders without endpoints are elementarily equivalent. [The same holds for DLOs with endpoints, but the two classes of structures are not elementarily equivalent to each other.]

3) Any two algebraically closed fields of the same characteristic are elementarily equivalent.

4) Any two real-closed fields are elementarily equivalent.

5) Any two infinite models of the theory of finite fields are elementarily equivalent. (Nope! See Dave Marker's answer.)

In each case, such structures exist of every infinite cardinality, so the class of isomorphism classes of such structures is a proper class, not a set.

[1]: "M-O-O-N, that spells model theory!"

-
+1 for referencing The Stand! (and for the good list of examples). – Jason DeVito Aug 4 '10 at 21:33

Take any complete theory $T$ that has two models of of different cardinalities. Then the models are elementary equivalent (they both model $T$) but they cannot be isomorphic because isomorphisms preserve cardinality.

By the Lowenheim-Skolem theorem, every theory with infinite models has models of different cardinalities, so really any complete theory with infinite models will work for $T$.

Personal note: Whenever I teach students about cardinality, I always point out this sort of application. Because cardinality is preserved by bijections, showing two objects (groups, rings, models, etc) have different cardinalities is an easy way to show they are not isomorphic. I find this a very compelling reason to care about cardinality outside of set theory.

-
Outside of set theory, there are only a handful of cardinalities that arise in practice: finite, countable, continuum, and Huge (pathological). It's very hard to confuse structures whose cardinalities on this scale are different. Do you know an example of normal mathematical objects that one might suspect are isomorphic (if given a minute to think about it), but are distinguished by having different infinite cardinalities? – T.. Aug 5 '10 at 3:41
Yes, it's a very coarse method. There are a few other cardinalities that come up, like the powerset of the reals. You may not like these examples, but I think they are not completely trivial: (1) there are Lebesgue measurable sets that are not Borel (2) the complex numbers are not isomorphic to the algebraic closure of the rational numbers. These are easy to prove with just a cardinality computation. Of course there are other ways to prove them, too. I'm just saying cardinality is one way that's relatively elementary. – Carl Mummert Aug 5 '10 at 4:20
alg.closure(Q) is nonisomorphic to C for the more basic reason that algclosure(Q inside C) is different from C, i.e., transcendental numbers exist. Clearly that's necessary for their nonisomorphism, and it's sufficient because it means C contains elements not in the alg.closure of the subfield generated by 1. Cardinality would distinguish C from an even larger (Huge) algebraically closed field but I don't think such a thing ever comes up without knowing its cardinality by definition, as in "the alg.closed field of char. 0 on a set X of indeterminates". – T.. Aug 5 '10 at 5:39
@Carl: in the second paragraph, I think the phrase "with infinite models" needs to appear somewhere. Anyway, yes, Lowenheim-Skolem is good for producing examples of e.e. nonisomorphic structures. But one has to get through a bit of introductory material to get there (e.g. the OP may not have gotten that far in Marker's book). – Pete L. Clark Aug 5 '10 at 5:43
Certainly "they have different cardinality" is extremely psychologically satisfying as a nonisomorphism proof --- it's hard to think of a more basic invariant that, when it works, distinguishes two objects. My point is just that caring about infinite cardinalities beyond the very crude scale I described, is not likely (as far as I know) to ever make a difference when dealing with ordinary mathematical objects, whose position on that scale is usually very easily tracked. – T.. Aug 5 '10 at 5:45

There are a real numbers worth of countable models of Peano arithmetic, all elementarily equivalent to the usual model, but all pairwise nonisomorphic.

Every nonstandard example (nonstandard means not isomorphic to the usual model) is characterized by the fact that it contains "infinitely large" numbers. That is, each model M has a canonical copy of N = usual naturals inside. However, each nonstandard model M has an element p (in fact, countably many such elements) which the model things is bigger than everything in its copy of N.

They are created by standard compactness arguments paired with the downward Lowenheim-Skolem theorem.

Let PA denote the axioms for Peano Arithmetic and set T = Th(N), the theory of N (i.e., the set of all first order statements which are true in the usual interpretation.

Finally, add a constant c to the language and let phi_n be the statement c > n, or more appropriately, c > SSSS.....S(0), where S is the successor function of PA and there are n S's in the expression.

Now, consider the set of axioms PA union T union phi_n for every n. By a standard compactness argument, this set of axioms is consistent, and so by the Godel completeness theorem, there is a model M of all the axioms simultaneously. By downward Lowenheim-Skolem, we can assume M is countable.

Now, ask yourself, what can c be? Well, since M satisfies phi_n for every n, we must have c > n for each "usual" natural number in M, i.e., c is infinite!

What's really cool is that by playing around with different kinds of phi_n, one can find models that have elements which are divisible by NO "standard" prime number. One can also find models that have elements which are simultaneously divisible by EVERY "standard" prime number!

-
@Nik: The argument I gave above just shows that there is more than one model of $PA$. The argument to get $|\mathbb{R}|$ many different models is the following: Let $\psi_p$ be the statement "$c$ is divisible by $p$." For each subset $X$ of the primes, using a compactness argument, one shows $PA\cup \{\psi_p:p\in X\} \cup \{\neg \psi_q: q\notin X\}$ is consistent, so has a model. In this model, $c$ is divisible precisely by primes in $X$. (continued) – Jason DeVito Dec 13 '12 at 2:50
It follows that for each subset of the primes, there is a countable model of $PA$ with an element divisible by precisely these primes. Since any countable model only has countably many elements, each model "uses up" at most countably many subsets of the primes. If there were $\kappa < |\mathbb{R}|$ countable models of $PA$, we would use up at most $\kappa \cdot \aleph_0 = \kappa<|\mathbb{R}|$ subsets of the primes, so there must be $\geq |\mathbb{R}|$ countable models of $PA$. (continued) – Jason DeVito Dec 13 '12 at 2:53
To get the reverse inequality, note that since your model is countable, you can assume wlog the underlying set is $\mathbb{N}$ and the sucessor function $S:\mathbb{N}\rightarrow \mathbb{N}$ is something weird. There are only $|\mathbb{N}|^{\mathbb{N}|} \leq (2^{|\mathbb{N}|})^{|\mathbb{N}|} = 2^{|\mathbb{N}|} = |\mathbb{R}|$ such functions, so there must be $\leq |\mathbb{R}|$ countable models of $PA$. – Jason DeVito Dec 13 '12 at 2:56
$2^\omega$ is in bijective correspondence with $\mathbb{R}$ regardless of whether or not $CH$ (or even $GCH$) or even $AC$ holds (though I used $AC$ all over the place in other areas). As far as the elementarily equivalent part is concerned, I left this out in my argument in the comments, but you don't just take $PA$ and the $\psi$ sentences, but also the whole theory of $\mathbb{N}$. – Jason DeVito Dec 13 '12 at 4:19
@Isaac: Glad I could retroactively help ;-). I'm somewhat tempted to edit the answer to a) fix typos b) actually tex it and c) add the argument for the number of models of $PA$, but I think I'll pass unless someone asks for it. – Jason DeVito Feb 18 '13 at 18:21

Take a look at the Wikipedia article on Real closed fields. Briefly, they are fields that are first-order equivalent to the field of the real numbers. An example is the field of real numbers that are roots of polynomials with rational coefficients. That's pretty much all I know about them, though.

-