This is an exercise sheet in model theory and discusses
the idea of an embedding of a structure $M$ into another
structure $N$. One of the highlights is a *preservation
theorem* that says exactly when $M$ has an embedding into
some $L$-structure satisfying a given $L$-theory $T$.

Fix a first-order language $L$. Unless otherwise stated, $M$, $N$ will be understood to be $L$-structures. I will use here the notation $\stackrel{\_}{a}$ for an undetermined finite number of parameters or variables ${a}_{0},{a}_{1},\dots $. You will also need to know the definitions of: what it means for a structure $M$ to be a substructure of another structure $N$ (written $M\subseteq N$); what it means for $f:M\to N$ to be an embedding, and an elementary embedding; quantifier-free (q.f.) formulas; and the ${\forall}_{1}$ consequences ${\forall}_{1}-\left(T\right)$ of an $L$-theory $T$.

Exercise.

Show that if $M\subseteq N$, $\stackrel{\_}{a}\in M$ and $N\models \forall \stackrel{\_}{x}\u200a\theta (\stackrel{\_}{x},\stackrel{\_}{a})$ with $\theta $ quantifier-free then $M\models \forall \stackrel{\_}{x}\u200a\theta (\stackrel{\_}{x},\stackrel{\_}{a})$. (Hint: prove $N\models \theta \left(\stackrel{\_}{b}\right)$ holds if and only if $M\models \theta \left(\stackrel{\_}{b}\right)$ holds, for all q.f. $\theta $ and all $\stackrel{\_}{b}\in M$, by using induction on the complexity of $\theta $.)

Exercise.

Let $M$ be an $L$-structure, let ${L}_{M}$ be the language obtained by adding a new constant $a$ to $L$ for each $a\in M$ and regard $M$ as a ${L}_{M}$ structure in the natural way. Let ${D}_{0}\left(M\right)$ be the set of q.f. ${L}_{M}$ sentences that are true in $M$. Prove that, for any $L$-structure $N$, there is an embedding $f:M\to N$ if and only if $N$ has an expansion ${N}_{0}=(N,\dots ,{a}^{N},\dots {)}_{a\in M}$ to ${L}_{M}$ such that ${N}_{0}\models {D}_{0}\left(M\right)$.

Exercise.

Let $T$ be an $L$-theory and $M\models {\forall}_{1}-\left(T\right)$. Show that ${D}_{0}\left(M\right)\cup T$ has a model. (Use the Compactness Theorem. You may find the ∀-Introduction rule helpful.)

Exercise.

Deduce that, for all $L$-structures $M$ and all $L$-theories $T$, there is some $L$-structure $N\supseteq M$ with $N\models T$ if and only if $M\models {\forall}_{1}-\left(T\right)$.

Exercise.

It is an easy observation that if
$f:M\to M$ is an embedding of $M$
properly into itself then $M$ is infinite.
Prove that if $f:M\to M$ is an
*elementary* embedding of $M$ properly into itself
and $a\in M$ is not in the image of $f$, then the set
of elements of $M$ having the same first-order properties
as $a$, i.e. the set

is infinite.

The following is a variation of the last.

Exercise.

Let $M$ be an $L$-structure and $N\succ M$ a proper elementary extension. Then for each $a\in N\setminus M$ the type of $a$, $\mathrm{tp}\left(a\right)=\left\{\theta \left(x\right):N\models \theta \left(a\right)\right\}$ consisting of all formulas $\theta \left(x\right)$ true in $N$ at $a$ has the property that for each $\theta \left(x\right)\in \mathrm{tp}\left(a\right)$ the set $\left\{c\in M:M\models \theta \left(c\right)\right\}$ is infinite. It follows that $M$ must be infinite to have a proper elementary extension.

If $N\succ M$ is a proper elementary extension it need not be the case that $N\setminus M$ is infinite. For example, let $L$ have ${\aleph}_{0}$ unary relations ${R}_{i}$ and let $M$ be the $L$-structure consisting of domain $\mathbb{N}$ and $M\models {R}_{i}\left(j\right)$ iff $i=j$. Let $N={\mathbb{N}}^{\left\{\omega \right\}}$ be an extension where $N\models \neg {R}_{i}\left(\omega \right)$ for all $i$. Then it turns out that $N\succ M$ but of course $N\setminus M=\left\{\omega \right\}$.