Example of non-isomorphic structures which are elementarily equivalent

Solution 1:

First, I'm glad you are reading my book! :)

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,\ldots\}$ 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 \bmod 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..

Solution 2:

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!"

Solution 3:

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.

Solution 4:

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!

Solution 5:

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.