Elementary Amalgamation Theorem

From ProofWiki
Jump to navigation Jump to search


Let $\mathcal{M}$ and $\mathcal{N}$ be $\mathcal{L}$-structures.

Let $B$ be a subset of the universe of $\mathcal{M}$ such that there is a partial elementary embedding $f:B\to \mathcal{N}$.

There is an elementary extension $\mathcal{A}$ of $\mathcal{M}$ and an elementary embedding $g:\mathcal{N}\to \mathcal{A}$ such that $g(f(b)) = b$ for all $b\in B$.

$\array{ &&\mathcal{A}&&\\ &\preceq&&\nwarrow \exists g &&\!\!\!\!\!\!\!\!\!\!\!\!\!:gf=\mathrm{id}_B\\ \mathcal{M}&&&&\!\!\!\!\!\!\!\!\mathcal{N}\\ &\supseteq&&\nearrow f\\ &&B&&\\ }$


The proof is essentially a straightforward application of the Compactness Theorem on the collection of sentences with parameters true in each of $\mathcal{M}$ and $\mathcal{N}$, but it requires some tedious set-up in handling symbols of the language involved to make sure that we get the map $g$ with the properties we want in the end.

  • First, we will define some new languages by adding constants for all of the elements in the structures involved. This well help us construct the claimed $\mathcal{A}$. This first part of the proof is essentially just setting the stage for our argument, there is little to verify.

Let $C_\mathcal{M} = \{c_m : m\in \mathcal{M}\}$ be set of new constant symbols (not appearing in $\mathcal{L}$) corresponding to each element of the universe of $\mathcal{M}$.

Similarly, let $C'_\mathcal{N} = \{c_n : n\in\mathcal{N}\}$ be new constant symbols (not appearing in $\mathcal{L}$ or $C_\mathcal{M}$) corresponding to elements of the universe of $\mathcal{N}$.

It will be beneficial to use the same constant symbols for both the elements of $B$ and their images in $f(B) \subseteq \mathcal{N}$, so we will define:

$C_\mathcal{N} = (C'_\mathcal{N} - \{c_{f(b)}: b\in B\})\cup \{c_b : b\in B\}$

Let $\mathcal{L}_\mathcal{M}$ be the language obtained from $\mathcal{L}$ by adding the constant symbols in $C_\mathcal{M}$

Let $\mathcal{L}_\mathcal{N}$ be that obtained from $\mathcal{L}$ by adding the constants in $C_\mathcal{N}$.

Note that $\mathcal{L}_\mathcal{M}$ and $\mathcal{L}_\mathcal{M}$ share the constant symbols $c_b$ for $b\in B$, and those constant symbols which already appear in $\mathcal{L}$, but all of their other constant symbols are distinct.

We will view $\mathcal{M}$ as an $\mathcal{L}_\mathcal{M}$-structure by interpreting each constant $c_m$ as $m$.

Similarly, we will view $\mathcal{N}$ as an $\mathcal{L}_\mathcal{N}$-structure by interpreting each $c_n$ for $n\in \mathcal{N} - f(B)$ as $n$, and each $c_b$ for $b \in B$ as $f(b)$.

Let $\mathcal{L}_\mathcal{MN}$ be the language obtained from $\mathcal{L}$ by adding the constant symbols in $C_\mathcal{M} \cup C_\mathcal{N}$

Let $\mathrm{eldiag}(\mathcal{M})$ be the set of $\mathcal{L}_\mathcal{M}$-sentences which are satisfied by $\mathcal{M}$.

Similarly, let $\mathrm{eldiag}(\mathcal{N})$ be the set of $\mathcal{L}_\mathcal{N}$-sentences which are satisfied by $\mathcal{N}$.

(We are using this notation since these are essentially elementary diagrams, the only difference is that we have made some more specific decisions about the constants involved.)

Let $T$ be the $\mathcal{L}_\mathcal{MN}$-theory $\mathrm{eldiag}(\mathcal{M})\cup\mathrm{eldiag}(\mathcal{N})$.

  • Now that we have all of these definitions, we will show that $T$ is satisfiable. This will give us a model which we can use to obtain the one claimed by the theorem. It will suffice to show that all finite subsets of $T$ are satisfiable, since we may then apply the Compactness Theorem.

Let $\Delta$ be a finite subset of $T$.

$\Delta$ is then a finite subset of $\mathrm{eldiag}(\mathcal{M})$, together with finitely many $\mathcal{L}_\mathcal{N}$-sentences from $\mathrm{eldiag}(\mathcal{N})$ whose conjunction we will write as $\phi(\bar c_b, \bar c_n)$, where $\phi(\bar x, \bar y)$ is an $\mathcal{L}$-formula, $\bar b$ is a ordered tuple from $B$, and $\bar n$ is a tuple of mutually distinct elements from $\mathcal{N}$ not containing elements of $f(B)$.
Suppose $\Delta$ has no model.
In particular, every $\mathcal{L}_\mathcal{MN}$-model of $\mathrm{eldiag}(\mathcal{M})$ must fail to be model of $\Delta$.
So we have $\mathrm{eldiag}(\mathcal{M})\models \neg \phi(\bar c_b, \bar c_n)$.
But, since the constants in $\bar c_n$ are distinct from all of the constants corresponding to elements of $B$ and $\mathcal{M}$ in general, it doesn't matter how a $\mathcal{L}_\mathcal{MN}$-model of $\mathrm{eldiag}(\mathcal{M})$ interprets $\bar c_n$:
$\mathrm{eldiag}(\mathcal{M})\models \forall \bar y \neg \phi(\bar c_b, \bar y)$.
Since $\mathcal{M}\models \mathrm{eldiag}(\mathcal{M})$, we obtain:
$\mathcal{M}\models \forall \bar y \neg \phi(\bar c_b, \bar y)$, and hence
$\mathcal{M}\models \forall \bar y \neg \phi(\bar b, \bar y)$ since $\mathcal{M}$ interprets each $c_b$ as $b$.
Since $f$ is partial elementary on $B$, we get:
$\mathcal{N}\models \forall \bar y \neg \phi(f(\bar b), \bar y)$.
But, this contradicts the choice of $\phi(\bar c_b, \bar c_n)$ as being a conjunction of sentences in $\mathrm{eldiag}(\mathcal{N})$, since $\mathcal{N}$ interprets each $c_b$ as its corresponding element $f(b)$.
Thus, $\Delta$ has a model.

Hence, by the Compactness Theorem, $T$ is satisfiable.

Now, let $\mathcal{A}^*$ be a model of $T$, and let $\mathcal{A}$ be the $\mathcal{L}$-structure obtained by removing all of the interpretations of constants in $C_\mathcal{M} \cup C_\mathcal{N}$ from $\mathcal{A}^*$.

Since $\mathcal{A}^* \models \mathrm{eldiag}(\mathcal{M})$, we can, after possibly creating an isomorphic copy of $\mathcal{A}^*$ with new distinct elements, and replacing each element $a$ of the universe of $\mathcal{A}^*$ such that $c_{m}^{\mathcal{A}^*} = a$ with the element $m\in \mathcal{M}$, view $\mathcal{A}$ as an elementary extension of $\mathcal{M}$ such that $c_{m}^{\mathcal{A}} = m \in \mathcal{A}$.

Define $g : \mathcal{N}\to \mathcal{A}$ by $g(n) = c_{n}^{\mathcal{A}^*}$, where $c_n$ is the constant symbol in $C_\mathcal{N}$ which $\mathcal{N}$ interprets as $n$.

Since $\mathcal{A}^* \models \mathrm{eldiag}(\mathcal{N})$, we have that $g$ is elementary.

Let $b\in B$.

Recall that $\mathcal{N}$ interprets $c_b$ as $f(b)$, and since $b\in B\subseteq \mathcal{M}$, we have $c_b^{\mathcal{A}^*} = b$.
Thus, $g(f(b)) = c_{b}^{\mathcal{A}^*}$ = b.

So, $\mathcal{A}$ and $g$ are as claimed by the theorem.