0
$\begingroup$

I don't quite understand the meaning of, and the difference between elementary equivalence and isomorphism of logical models in the context of first-order logic. Please help me understand it by elucidating the following example.

The following assertion was made by a competent logician without further explanation:

$(\mathbb{N},<)\equiv(\mathbb{N}+\mathbb{Z},<)$, as can be proved e.g. via quantifier elimination, but, clearly, $(\mathbb{N},<)\not\cong(\mathbb{N}+\mathbb{Z},<)$.

The notation $\mathbb{N}+\mathbb{Z}$ means an ordered set that is order isomorphic to the ordered set $\mathbb{N}$ followed by the ordered set $\mathbb{Z}$, the symbol $\equiv$ means elementary equivalence, and the notation $\cong$ means isomorphism.

  1. What does $(\mathbb{N},<)\equiv(\mathbb{N}+\mathbb{Z},<)$ mean? What steps can I take to verify that this claim holds?

  2. What does $(\mathbb{N},<)\not\cong(\mathbb{N}+\mathbb{Z},<)$ mean? How can I verify that it holds?

$\endgroup$
3
$\begingroup$

Elementary equivalence means that if $\phi$ is any sentence (in the language under consideration, i.e. $\{<\}$) then $$ (\mathbb N,<) \models \phi \iff (\mathbb N + \mathbb Z,<) \models \phi. $$ Proving this is typically not trivial; in this case, because $(\mathbb N, <)$ is a substructure[1] of $(\mathbb N+\mathbb Z,<)$, you can use the relatively usable Tarski-Vaught test.

Isomorphism is stronger than elementary equivalence: what this means, basically, is that the structures are the same except for the 'names' of the elements of the underlying set. Two structures $(A,<_A)$ and $(B,<_B)$ are isomorphic if there is a bijection $f: A \to B$ such that for all $a,a' \in A$ we have $$ a <_A a' \iff f(a) <_B f(a'). $$ In fact, many algebraic notions of isomorphic reduce to this notion. If you know any group theory, then consider the language $(\circ, (-)^{-1},e)$ of group theory; then two groups $G,H$ are isomorphic if and only if there is a bijective function $f: G \to H$ such that $f(a \circ b) = f(a) \circ f(b)$, and $f(a^{-1}) = f(a)^{-1}$, and $f(e) = e$.

You can see that your two structures are not isomorphic by assuming (towards a contradiction) that an isomorphism $f: \mathbb N \to \mathbb N + \mathbb Z$ exists, and proving by induction that $f(n) = n$, showing that $f$ is not a bijection.

[1] This means in this case that $\mathbb N \subseteq \mathbb N + \mathbb Z$ in such a way that for $n,m \in \mathbb N$ we have $n <_{\mathbb N} m \iff n <_{\mathbb N + \mathbb Z} m$.

$\endgroup$
  • $\begingroup$ Thanks for your reply. Referring to your first paragraph: I am having difficulty proving elementary equivalence using the Tarski-Vaught test. Would you mind fleshing out the details? $\endgroup$ – Evan Aad Feb 8 '17 at 11:18
  • 1
    $\begingroup$ @EvanAad, you have to show that if $\exists x\phi(x, n_1,\ldots, n_k)$ holds in the larger structure, with the $n_i$ from the smaller structure, then in particular you can choose $x$ to be from the smaller structure, too; instead of picking something from the copy of $\mathbb Z$ you can always pick a "sufficiently large natural". Now fill in the details/make this formal. $\endgroup$ – Mees de Vries Feb 8 '17 at 11:23
  • $\begingroup$ Thanks. I understand what needs to be proved. What I don't understand is the details. I figure it requires structural induction on $\phi$. I am able to prove the basis step as well as the case when $\phi = \psi\vee\eta$ for some formulas $\psi$ and $\eta$. But I get stuck when the formula is of the form $\phi = \neg\psi$ or $\phi=\forall y,\psi$. $\endgroup$ – Evan Aad Feb 8 '17 at 11:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.