Homomorphisms - Model Theory - Cambridge III notes

2 Homomorphisms

Definition 2.1 (Homomorphism). Let $M, N$ be $L$ -structures. A function $h : M \to N$ is an $L$ -homomorphism if:

(i) For an $n$ -ary function symbol $f$ , and $a_{1}, \dots, a_{n} \in M$ we have
$h (f^{M} (a_{1}, \dots, a_{n})) = f^{N} (h (a_{1}), \dots, h (a_{n})) .$
(ii) For an $n$ -ary relation symbol $R$ , and $a_{1}, \dots, a_{n} \in M$ we have
$(a_{1}, \dots, a_{n}) \in R^{m} iff (h (a_{1}), \dots, h (a_{n})) \in R^{N} .$
(iii) For any constant symbol $c$ , $h (c^{M}) = c^{N}$ .

We write $h : M \to N$ if $h$ is an $L$ -homomorphism.

If $h$ is also injective then this is called an $L$ -embedding.

If $h$ is also bijective then this is called an $L$ -isomorphism.

Theorem 2.2. Assuming that:

$h : M \to N$ is an $L$ -isomorphism
$φ (x_{1}, \dots, x_{n})$ an $L$ -formula
$a_{1}, \dots, a_{n} \in M$

Then

M ⊨ φ (a_{1}, \dots, a_{n}) iff N ⊨ φ (h (a_{1}), \dots, h (a_{n})) .

Proof. Let $\bar{a} = (a_{1}, \dots, a_{n})$ .

Step 1: Terms. Proof by induction on term complexity. For the base case:

For $t$ a constant, we have $h (t^{M}) = h (c^{M}) = c^{N} = t^{N}$ .
For $t$ a variable: $h (t^{M} (x_{i})) = h (a_{i}) = t^{N} (h (a_{i}))$ .

For the inductive step: Let $f$ be an $m$ -ary function symbol. Assume that the claim holds for $t_{1}, \dots, t_{m}$ whose free variables are amongst $x_{1}, \dots, x_{n}$ .

Suppose $t = f (t_{1}, \dots, t_{m})$ . Given $a_{1}, \dots, a_{n} \in M$ , we have

\begin{array}{l} h (t^{M} (a_{1}, \dots, a_{n})) & = h (f^{M} (t_{1}^{M} (a_{1}, \dots, a_{n}), \dots, t_{m}^{M} (a_{1}, \dots, a_{n}))) \\ = f^{N} (h (t_{1}^{M} (\bar{a})), \dots, h (t_{m}^{M} (\bar{a}))) & (f^{N} is an L - isomorphism) \\ = f^{N} (t_{1}^{N} (h_{1} (\bar{a})), \dots, t_{m}^{N} (h (\bar{a}))) & (inductive step) \\ = t^{N} (h (\bar{a})) \end{array}

Step 2: Formulas. Base case: atomic formulas. Suppose $φ$ is $t_{1} = t_{2}$ . Then:

\begin{array}{l} M ⊨ φ (\bar{a}) & iff t_{1}^{M} (\bar{a}) = t_{2}^{M} (\bar{a}) \\ iff h (t_{1}^{M} (\bar{a})) = h (t_{2}^{M} (\bar{a})) & by bijectivity \\ iff t_{1}^{N} (h (\bar{a})) = t_{2}^{N} (h (\bar{a})) & using step 1 \\ iff N ⊨ φ (\bar{a}) \end{array}

Case where $φ$ is $R (t_{1}, \dots, t_{m})$ left as an exercise.

Inductive step: Assume statement holds for $φ$ and $ψ$ .

$φ \land ψ$ , $\neg φ$ left as an exercise.
$\forall x_{n} φ (x_{1}, \dots, x_{n - 1}, x_{n})$ (then $\exists$ will follow since it can be expressed using $\forall$ ).

Let $a_{1}, \dots, a_{n - 1} \in M$ . Then
$\begin{array}{l} M ⊨ \forall x_{n} φ (a_{1}, \dots, a_{n - 1}, x_{n}) & iff for all b \in M, M ⊨ φ (a_{1}, \dots, a_{n - 1}, b) \\ iff for all b \in M, N ⊨ φ (h (a_{1}), \dots, h (a_{n - 1}), h (b)) \\ iff for all c \in N, N ⊨ φ (h (a_{1}), \dots, h (a_{n - 1}), c) \\ iff N ⊨ \forall x_{n} φ (h (a_{1}), \dots, h (a_{n - 1}), x_{n}) □ \end{array}$

Notation. Write $N ≅ M$ if there is an $L$ -isomorphism between them.

Corollary 2.3. If $M ≅ N$ , then $M \equiv N$ .

Remark. So far we have two equivalence relations on $L$ -structures: $\equiv$ and $≅$ .

Corollary 2.4. $h : M \to N$ is an $L$ -embedding if and only if the conclusion of Theorem 2.2 holds for all quantifier free formulas $φ (x_{1}, \dots, x_{n})$ .

Proof.

$\Rightarrow$ Clear from proof of Theorem 2.2.
$\Leftarrow$ Exercise (see Example Sheet 1). □

Definition 2.5 (Elementary embedding). An $L$ -homomorphism $h : M \to N$ is an elementary $L$ -embedding if for any $L$ -formula $φ (\bar{x})$ and any $\bar{a} \in M$ (with $| \bar{x} | = | \bar{a} |$ ) we have

M ⊨ φ (\bar{a}) iff N ⊨ φ (h (\bar{a})) .

Note. $L$ -isomorphisms are elementary $L$ -embeddings.

Definition 2.6 (Substructure). Let $M$ and $N$ be $L$ -structures with $M \subseteq N$ . Let $h : M ↪ N$ be the inclusion map. Then we say that $M$ is a substructure (respectively elementary substructure) of $N$ , written $M \subseteq N$ (respectively $M ≼ N$ ) if $h$ is an $L$ -embedding (respectively elementary $L$ -embedding).

We may also say $N$ is an extension (respectively elementary extension) of $M$ .

Remark.

The notion of substructure generalises subgroups, subrings, induced subgraphs.
Elementary substructure is stronger (more particular to model theory).
If $M ≼ N$ then $M \equiv N$ and $M \subseteq N$ .

Example 2.7. Let $M = (2 ℤ, <)$ and $N = (ℤ, <)$ . Then $M \equiv N$ and $M \subseteq N$ but $M ⁄ ≼ N$ .

Why? Consider $0, 2 \in M$ , $φ (x_{1}, x_{2}) = \exists y (x_{1} < y < x_{2})$ . Then $M ⁄ ⊨ φ (0, 2)$ , but $N ⊨ φ (0, 2)$ .

Theorem 2.8 (Tarski-Vaught Test). Assuming that:

$h : M \to N$ is an $L$ -embedding

Then the following are equivalent:

(i) $h$ is an elementary $L$ -embedding
(ii) For every first order formula $φ (y, x_{1}, \dots, x_{n})$ and every $a_{1}, \dots, a_{n} \in M$ , if there exists $y \in N$ such that $N ⊨ φ (y, h (a_{1}), \dots, h (a_{n}))$ then there exists $y \in M$ such that $N ⊨ φ (h (y), h (a_{1}), \dots, h (a_{n}))$ .

Proof. Example Sheet 1. □