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

Question

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).

Thank you in advance.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.