[Math] Simple examples of non-isomorphic but elementarily equivalent structures.

model-theory

An uncountable example is obtained by considering dense linear orders without endpoints. Any two dense linear orders without endpoints are elemenatarily equivalent. But $\langle\mathbb{R},<\rangle$ and $\langle\mathbb{I},<\rangle$ with the usual order, $\mathbb{I}$ the set of irrational numbers, are non-isomorphic as the first is complete while the latter is not.
There is no such countable example as the theory of dense linear orders without endpoints is $\aleph_0$-categorical.

I am interested in countable and finite examples of elementarily equivalent but non-isomorphic first-order structures.

Best Answer

You're not going to find any finite examples. For any finite structure $A$, every model of $\text{Th}(A)$ is isomorphic to $A$.

But there are many many countable examples. In fact, if $T$ is any complete theory which is not $\aleph_0$-categorical, then (by definition) it has countable models which are elementarily equivalent but not isomorphic.

Here are some concrete examples:

  • Let $L$ consist of countably many constant symbols $\{c_i\mid i\in\mathbb{N}\}$, and let $T$ be the theory asserting that $c_i\neq c_j$ for all $i\neq j$. This is a complete theory, and it has countably many nonisomorphic countable models, determined by how many elements are in the structure which are not named by constants. The choices are $0, 1, 2, \dots, \aleph_0$.
  • Similarly, the theory of algebraically closed fields of characteristic $0$ is complete. The fields $\overline{\mathbb{Q}}$, $\overline{\mathbb{Q}(t_0)}$, $\overline{\mathbb{Q}(t_0,t_1)}$, $\dots$, $\overline{\mathbb{Q}(t_0,t_1,t_2,\dots)}$ are all countable and elementarily equivalent but nonisomorphic.
  • Any two discrete linear orders without endpoints are elementarily equivalent (this can be proven using EF games). Any model of this theory looks like $L \times \mathbb{Z}$, ordered lexicographically, where $L$ is some linear order. Anytime $L$ is finite or countable, this model is countable, but nonisomorphic orders $L$ give nonisomorphic models $M_L$.
  • Consider the structure $\langle \mathbb{Q},<,\{c_q\}_{q\in\mathbb{Q}}\rangle$. This is $\langle\mathbb{Q},<\rangle$ with every element named by a constant. Its complete theory is the theory of dense linear orders in which the constants pick out a copy of $\mathbb{Q}$. This theory has continuum-many nonisomorphic countable models, since you're free to choose which countable collection of the continuum-many cuts in $\mathbb{Q}$ to fill.
Related Question