Here's the example from Enderton's "A Mathematical Introduction to Logic", p152
(Begin example)
Consider the structure
$\mathfrak N = (\mathbb N; 0, S, < +, \cdot)$
We claim that there is a countable structure $\mathfrak M_0$, elementarily equivalent to $\mathfrak N$ (so that $\mathfrak M_0$ and $\mathfrak N$ satisfy exactly the same sentences) but not isomorphic to $\mathfrak N$.
Proof: We will construct $\mathfrak M_0$ by using the compactnss theorem. Expand the language by adding a new constant symbol $c$. Let
$\Sigma = \{0 \lt c, S0 \lt c, SS0 \lt c,…\}$
We claim that $\Sigma \cup Th \mathfrak N$ has a model. For consider a finite subset. That finite subset is true in
$\mathfrak N_k = (\mathbb N; 0, S, < +, \cdot, k)$
(where $k = c^{\mathfrak N_k}$) for some large $k$. So by the compactness theorem $\Sigma \cup Th \mathfrak N$ has a model.
By the Lowenheim-Skolem theorem, $\Sigma \cup Th \mathfrak N$ has a countable model
$\mathfrak M = (|\mathfrak M|; 0^{\mathfrak M}, S^{\mathfrak M}, <^{\mathfrak M} +^{\mathfrak M}, \cdot^{\mathfrak M}, c^{\mathfrak M})$.
Let $\mathfrak M_0$ be the restriction of $\mathfrak M$ to the original language:
$\mathfrak M_0 = (|\mathfrak M|; 0^{\mathfrak M}, S^{\mathfrak M}, <^{\mathfrak M} +^{\mathfrak M}, \cdot^{\mathfrak M})$.
Since $\mathfrak M_0$ is a model of $Th \mathfrak N$, we have $\mathfrak M_0 \equiv \mathfrak N$:
$\vDash_\mathfrak N \sigma \implies \sigma \in Th \mathfrak N \implies \vDash_\mathfrak {M_0} \sigma$
$\nvDash_\mathfrak N \neg\sigma \implies \sigma \in Th \mathfrak N \implies \vDash_\mathfrak {M_0} \neg \sigma \implies \nvDash_\mathfrak {M_0} \sigma. $
We leave it to the reader to verify that $\mathfrak M_0$ is not isomorphic to $\mathfrak N$. ($|\mathfrak M_0|$ contains the "infinite" number $c^{\mathfrak M}$.)
(End of example)
My first question is that there seems to be a wff that is satisfiable in $\mathfrak M_0$, but not in $\mathfrak N$, and so the two stuctures aren't elementarily equivalent:
$\exists y \forall x (x \lt y)$
Namely, in |$\mathfrak M_0$| there is the infinite number that is greater than all other numbers.
Assuming I am wrong with my counter-example, my second question is how would you prove that the two structures aren't isomorphic?
Best Answer
You claim that $\exists y . \forall x . x < y$ is satisfied in $\mathfrak{M}_0$ but not in $\mathfrak{N}$. But this is not true.
In particular, we have $c < Sc$. Our new vocubulary contains not only the "standard" natural numbers plus $c$, but also many other terms like $Sc$, $c \cdot c$, and more. One can also show that $\exists! y (c = Sy)$, so "$c - 1$" (which isn't technically a term) exists as well.
Forcing a single nonstandard number to be in a model thus forces many others to be in the model as well.
To prove the two aren't isomorphic, simply consider the fact that the only homomorphism $\mathfrak{N} \to \mathfrak{M}_0$ sends $n$ to $(S^{\mathfrak{M}_0})^n(0^{\mathfrak{M}_0})$. Then it's easy to see that $c^{\mathfrak{M}_0}$ is not in the range of this homomorphism.