# Non-isomorphic structures of the same cardinality which are elementary equivalent

We usually give examples (es. ultrapowers) of elementary equivalent structures which are not isomorphic because they have different cardinalities?

Can someone help me to find an example of two such structures which have the same cardinality?

Can some constructions with ultra products help? (E.g. involving hypotheses about their cardinality, taking regular ultrafilters and similar).

This question is actually much easier without ultraproducts. It's easy to understand the complete theory of an ultraproduct, but it's much much harder to understand its isomorphism type.

On the other hand, any complete theory which is not $\aleph_0$-categorical has two countable models which are elementarily equivalent but non-isomorphic. And any theory which is not uncountably categorical has two models of any uncountable cardinality you like which are elementarily equivalent but non-isomorphic. Since $\aleph_0$-categoricity and uncountable categoricity are very special properties, this means that you can pick just about any theory you like and come up with examples.

Here are some explicit examples:

1. The structures $(\mathbb{Q},+), (\mathbb{Q}^2,+), \dots, (\mathbb{Q}^n,+),\dots$ are all countable and elementarily equivalent (the theory of divisible abelian groups - or equivalently $\mathbb{Q}$-vector spaces - is complete), but non-isomorphic (they have different dimensions).

2. For all $n\geq 0$, let $K_n$ be the algebraic closure of the field $\mathbb{Q}(x_1,\dots,x_n)$. These fields are all countable and elementarily equivalent (the theory of algebraically closed fields of characteristic $0$ is complete), but they are non-isomorphic (they have different transcendence degree).

3. JDH's answer can be expanded to show that for any linear order $I$, the structure $\langle \mathbb{Z}\times I,<\rangle$ (which consists of copies of $\mathbb{Z}$ indexed by the elements of $I$ and ordered accordingly) is elementarily equivalent to $\mathbb{Z}$. Since $\mathbb{Z}\times I$ and $\mathbb{Z}\times J$ are non-isomorphic whenever $I$ and $J$ are non-isomorphic, and there are continuum-many countable linear orders up to isomorphism, this construction produces continuum-many elementarily equivalent but non-isomorphic countable models of $\mathrm{Th}(\mathbb{Z})$. In fact, there are $2^\kappa$-many linear orders of size $\kappa$ up to isomorphism, so we get $2^\kappa$-many non-isomorphic models of $\mathrm{Th}(\mathbb{Z})$ of size $\kappa$.

4. Consider the language with a single unary predicate $P$. The theory $T$ which says that infinitely many elements satisfy $P$ and infinitely many elements satisfy $\lnot P$ is complete. $T$ only has one countable model up to isomorphism, but it has $3$ models of size $\aleph_1$, 5 models of size $\aleph_2$, etc.

5. $\mathrm{Th}(\mathbb{Q},<,(n)_{n\in \mathbb{N}})$ has exactly $3$ countable models up to isomorphism. There are also examples of complete theories with exactly $k$ countable models up to isomorphism for all natural numbers $k\geq 3$. But curiously, Vaught's "never two" theorem tells us that no complete theory has exactly $2$ countable models up to isomorphism. You might be interested in reading about Vaught's conjecture, on the same linked Wikipedia page...

You can get lots more examples by playing around with realizing and omitting types. For example, a variant of Asaf's answer is to start with $\mathbb{N}$ and realize the type of a non-standard element in a countable elementary extension.

• For (2) that would be the theory of algebraically closed fields of characteristic zero, right? Commented Jun 20, 2017 at 14:56
• @HenningMakholm Yep! Commented Jun 20, 2017 at 14:57
• About the beginning of your -very useful!- answer, you say something about categoricity (second paragraph). Your statements are clear to me if you assume the theory to be complete. Why are they true in general (also only a reference is welcome)? Commented Jun 23, 2017 at 16:00
• I meant to say complete theory, I'll edit. It's not true in general - for example, ACF is not uncountably categorical, but all of its completions are, so it doesn't have any two elementarily equivalent but non-isomorphic models of the same uncountable cardinality. Commented Jun 23, 2017 at 17:38
• Thanks so much! BTW are also (Q,+) and (R,+) elementary equivalent ? Commented Feb 21 at 21:49

Take any ultrapower of $\Bbb N$. Well, that's not the right cardinality as $\Bbb N$ itself, but now pick any non-standard element and consider the elementary submodel it generates. That would be a countable model of $\sf PA$ which is elementarily equivalent to $\Bbb N$ itself (both elementarily embed into the ultrapower), but they are not isomorphic, clearly.

Consider the integer order $\langle\mathbb{Z},<\rangle$ and the order $\mathbb{Z}+\mathbb{Z}$. These are not isomorphic, but they are elementarily equivalent, because the theory of an endless discrete order is complete.

• How do you show its completeness ? Commented Jun 20, 2017 at 19:59
• One can show this with an elimination of quantifiers-type argument. Ask as a separate question and I'm sure that someone will answer.
– JDH
Commented Jun 20, 2017 at 20:02
• Here it is: math.stackexchange.com/q/2330298/413
– JDH
Commented Jun 20, 2017 at 22:15

The theory of dense linear orders is complete - so consider the linear orders $((0, 2), <)$ versus $((0, 1)\cup ([1, 2)\cap \mathbb{Q}), <)$. The latter has a countable nontrivial interval while the former doesn't.

(Note that this works in any cardinality $\kappa$ - let $L$ be a $\kappa$-dense linear order of cardinality $\kappa$, and consider $L$ vs. $L+\mathbb{Q}$.)

You mention ultrapowers; it's worth noting that the Henkinization proof of compactness is much better behaved in this context - if I have a structure $M$ and a type not realized in $M$, Henkinization builds me a structure containing $M$ and realizing that type with the same cardinality as $M$. So, e.g. if every element of $M$ is definable this builds a nonisomorphic but elementarily equivalent $M'$ with the same cardinality as $M$.

For example, this gives another proof that there is a countable nonstandard model of $Th(\mathbb{N})$ without having to use ultraproducts + Lowenheim-Skolem.

The countable ultrapower of $\mathbb R$ actually does not increase the cardinality so $\mathbb{R}^{\mathbb N}/\mathcal{F}$ where $\mathcal{F}$ is a free ultrafilter on $\mathbb N$ is an example of an elementary extension that does not increase cardinality.

• +1. For the OP, two comments: (1) Of course, the choice of index set and ultrafilter affects the cardinality - e.g. $\mathbb{R}^\mathbb{R}/\mathcal{U}$, where $\mathcal{U}$ is an ultrafilter not containing any countable sets, will have cardinality greater than that of $\mathbb{R}$. (2) To show that $\mathbb{R}^\mathbb{N}/\mathcal{F}\not\cong\mathbb{R}$ think about e.g. the equivalence class of the sequence $\langle 1, 2, 3, 4 , ...\rangle$. (I'm assuming that we're viewing $\mathbb{R}$ as a structure capable of defining "$<$" - otherwise, they may be isomorphic (e.g. over the empty language).) Commented Jun 21, 2017 at 14:52