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 $\overline{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} - (T)$ of an $L$ -theory $T$ .

Exercise.

Show that if $M \subseteq N$ , $\overline{a} \in M$ and $N ⊨ \forall \overline{x} θ (\overline{x}, \overline{a})$ with $θ$ quantifier-free then $M ⊨ \forall \overline{x} θ (\overline{x}, \overline{a})$ . (Hint: prove $N ⊨ θ (\overline{b})$ holds if and only if $M ⊨ θ (\overline{b})$ holds, for all q.f. $θ$ and all $\overline{b} \in 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 \in 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 \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} ⊨ D_{0} (M)$ .

Exercise.

Let $T$ be an $L$ -theory and $M ⊨ \forall_{1} - (T)$ . Show that $D_{0} (M) \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 ⊨ T$ if and only if $M ⊨ \forall_{1} - (T)$ .

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

\{b \in M: M ⊨ (θ (a) \to θ (b)), for all formulas θ\}

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 \in 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) \in tp (a)$ the set $\{c \in 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 ⊨ \neg R_{i} (ω)$ for all $i$ . Then it turns out that $N ≻ M$ but of course $N ∖ M = \{ω\}$ .