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? – Henning Makholm Jun 20 '17 at 14:56
• @HenningMakholm Yep! – Alex Kruckman Jun 20 '17 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)? – W. Rether Jun 23 '17 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. – Alex Kruckman Jun 23 '17 at 17:38

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 ? – Max Jun 20 '17 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 Jun 20 '17 at 20:02
• Here it is: math.stackexchange.com/q/2330298/413 – JDH Jun 20 '17 at 22:15

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.

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).) – Noah Schweber Jun 21 '17 at 14:52