Homomorphisms - Model Theory - Cambridge III notes

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}$

Proof.

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

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$ .

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}))$ .

2 Homomorphisms