Franklin's Notes


Examples of elementarily equivalent models

This note is devoted to exploring several interesting and surprising examples of pairs of models which are nonisomorphic but elementarily equivalent . Philosophically, these are models that "look different from the outside but the same from the inside", or models which are indistinguishable by a first-order language but which nonetheless have distinct structures.

Chang and Kiesler give a couple of cool examples:

Exercise 1. (Chang and Kiesler 1.3.20) Show that the following pairs of models $\mathfrak{A},\mathfrak{B}$ are elementarily equivalent:
1. $\mathfrak{A}=\langle A\rangle, ~ \mathfrak{B}=\langle B\rangle$ where $A,B$ are any two infinite sets
2. $\mathfrak{A}=\langle A,\leq\rangle, ~ \mathfrak{B}=\langle B,\leq\rangle$ where $A,B$ are sets densely ordered by $\leq$ with no endpoints
3. $\mathfrak{A}=\langle \omega,\leq\rangle, ~ \mathfrak{B}=\langle \omega+\omega^d+\omega,\leq\rangle$, where $\omega+\omega^d+\omega$ is the order type of the natural numbers followed by a copy of the integers
4. $\mathfrak{A}=\langle \omega^\omega,\leq\rangle, ~ \mathfrak{B}=\langle \omega_1,\leq\rangle$
5. $\mathfrak{A}=\langle S_\omega(X),\subset\rangle, ~ \mathfrak{B}=\langle S_\omega(Y),\subset\rangle$ where $X,Y$ are infinite sets and $S_\omega(X),S_\omega(Y)$ are the sets of finite subsets of $X,Y$ respectively

These equivalences can be shown using the technique described in the note on generated submodels . For instance, to show equivalence $(1)$, we may note that for any sequence of elements chosen from $A$ and $B$ to become new constant symbols, we may simply choose arbitrary elements from the opposite model to be the corresponding constant symbols - there is no additional imposed structure to restrict our choices. For $(2)$, choices of corresponding constant symbols are nonarbitrary, but the density of the order allows us to always choose candidates for constants that preserve the ordering. The situation with $(3)$ is a bit trickier, but equivalence can be proven here using an Ehrenfeucht-Fraisse Game .

model-theory

first-order-logic

nonstandard-model

back to home page