# Embeddings of L-structures

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 $a _$ for an undetermined finite number of parameters or variables $a 0 , a 1 , …$. 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 ⊆ N$); what it means for $f : M → N$ to be an embedding, and an elementary embedding; quantifier-free (q.f.) formulas; and the $∀ 1$ consequences $∀ 1 - ( T )$ of an $L$-theory $T$.

Exercise.

Show that if $M ⊆ N$, $a _ ∈ M$ and $N ⊨ ∀ x _ θ ( x _ , a _ )$ with $θ$ quantifier-free then $M ⊨ ∀ x _ θ ( x _ , a _ )$. (Hint: prove $N ⊨ θ ( b _ )$ holds if and only if $M ⊨ θ ( b _ )$ holds, for all q.f. $θ$ and all $b _ ∈ M$, by using induction on the complexity of $θ$.)

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 ∈ M$ and regard $M$ as a $L M$ structure in the natural way. Let $D 0 ( M )$ 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 → N$ if and only if $N$ has an expansion $N 0 = ( N , … , a N , … ) a ∈ M$ to $L M$ such that $N 0 ⊨ D 0 ( M )$.

Exercise.

Let $T$ be an $L$-theory and $M ⊨ ∀ 1 - ( T )$. Show that $D 0 ( M ) ∪ 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 ⊇ M$ with $N ⊨ T$ if and only if $M ⊨ ∀ 1 - ( T )$.

Exercise.

It is an easy observation that if $f : M → M$ is an embedding of $M$ properly into itself then $M$ is infinite. Prove that if $f : M → M$ is an elementary embedding of $M$ properly into itself and $a ∈ 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 ≻ M$ a proper elementary extension. Then for each $a ∈ N ∖ M$ the type of $a$, $tp ( a ) = θ ( x ) N ⊨ θ ( a )$ consisting of all formulas $θ ( x )$ true in $N$ at $a$ has the property that for each $θ ( x ) ∈ tp ( a )$ the set $c ∈ M M ⊨ θ ( c )$ is infinite. It follows that $M$ must be infinite to have a proper elementary extension.

If $N ≻ M$ is a proper elementary extension it need not be the case that $N ∖ M$ is infinite. For example, let $L$ have $ℵ 0$ unary relations $R i$ and let $M$ be the $L$-structure consisting of domain $ℕ$ and $M ⊨ R i ( j )$ iff $i = j$. Let $N = ℕ ω$ be an extension where $N ⊨ ¬ R i ( ω )$ for all $i$. Then it turns out that $N ≻ M$ but of course $N ∖ M = ω$.