Existence of direct limit in model theory

Question

In Lemma 12.2 on p. 158 in Jech's Set Theory, the author gives a proof of the existence of and uniqueness a direct limit.

Lemma 12.2. If $\left\{\mathfrak{A}_{i}, e_{i, j}: i, j \in D\right\}$ is a directed system of models, there exists a model $\mathfrak{A}$, unique up to isomorphism, and elementary embeddings $e_{i}$ : $\mathfrak{A}_{i} \rightarrow \mathfrak{A}$ such that $\mathfrak{A}=\bigcup_{i \in D} e_{i}\left(\mathfrak{A}_{i}\right)$ and that $e_{i}=e_{j} \circ e_{i, j}$ for all $i<j$. The model $\mathfrak{A}$ is called the direct limit of $\left\{\mathfrak{A}_{i}, e_{i, j}\right\}_{i, j \in D}$.

Proof. Consider the set $S$ of all pairs $(i, a)$ such that $i \in D$ and $a \in A_{i}$, and define an equivalence relation on $S$ by $$ (i, a) \equiv(j, b) \leftrightarrow \exists k\left(i \leq k, j \leq k \text { and } e_{i, k}(a)=e_{j, k}(b)\right) $$ Let $A=S / \equiv$ be the set of all equivalence classes, and let $e_{i}(a)=[(i, a)]$ for all $i \in D$ and $a \in A_{i}$. The rest is routine. $\square$

I honestly don't understand how it helps prove the statement, not to mention how "the rest is routine." I would appreciate any help in understanding it.

Answer 1

I'm assuming you're working in 1-sorted logic, but the proof for multi-sorted logic is perfectly analogous.

We begin by noting that $A = \bigcup\limits_{i \in I} e_i(A_i)$ and that for all $i \leq k$, we have $e_i = e_k \circ e_{i, k}$. Finally, we note that each $e_i$ is injective.

We now only assume we have been given some such $A$ and some such $\{e_i\}_{i \in D}$ without assuming any other details of the $A$.

Thm. For all $i, j$ and $w \in A_i$, $x \in A_j$, we have $e_i(w) = e_j(x)$ if and only if there exists $k \geq i, j$ such that $e_{i, k}(w) = e_{j, k}(x)$.

Proof: suppose we have $e_{i, k}(w) = e_{j, k}(x)$ for some $k$. Then clearly, we have $e_i(w) = e_k(e_{i, k}(w)) = e_k(e_{j, k}(x)) = e_j(x)$.

Conversely, suppose that $e_i(w) = e_j(x)$. Take some $k \geq i, j$. Then $e_k(e_{i, k}(w)) = e_i(w) = e_j(x) = e_k(e_{j, k}(x))$. Since $e_k$ is injective, $e_{i, k}(w) = e_{j,k}(x)$.

We then have

Thm. For all $n \geq 1$, for all $y_1, \ldots, y_n \in A$, there exists some $k$ and some $x_1, \ldots, x_n$ such that $e_k(x_m) = y_m$ for $m = 1, \ldots, n$.

Proof: induction on $n$. The base case $n = 1$ is immediate. For $n = m + 1$, use the fact that we have a directed system and use the above. $\square$

Next, we require

Thm. Suppose $n \geq 1$, $i, j \in D$, $w_1, \ldots, w_n \in A_i$, and $x_1, \ldots x_n \in A_j$. Further suppose that $e_i(w_m) = e_j(x_m)$ for $m = 1, \ldots, n$. Then there exists some $k \geq i, j$ such that $e_{i, k}(w_m) = e_{j, k}(x_m)$ for $m = 1, \ldots, n$.

Proof: induction on $n$. The base case $n = 1$ is again immediate. For the inductive step, again use the fact that we have a directed system and use the equality criterion above. $\square$

Once we have these two, we now proceed to

Dfn. Given an $n$-ary function symbol $f$, define $f_A : A^n \to A$ by $f_A(e_i(x_1), \ldots, e_i(x_n)) = e_i(f_i(x_1, \ldots, x_n))$. Then $f_A$ is well-defined.

Proof: For all $y_1, \ldots, y_n \in A$, we can find $i$ and $w_1, \ldots, w_n$ such that $y_m = e_i(w_m)$ for $m = 1, \ldots, n$. Suppose we also found $j$ and $x_1, \ldots, x_n$ such that $y_m = e_j(x_m)$ for $m = 1, \ldots, n$. Then take $k \geq i, j$ such that $e_{i, k}(w_m) = e_{j, k}(x_m)$ for $m = 1, \ldots, n$. Then we see that

$\begin{equation} \begin{split} e_j(f_j(x_1, \ldots, x_n)) &= e_k(e_{j, k}(f_j(x_1, \ldots, x_n))) \\ &= e_k(f_k(e_{j, k}(x_1), \ldots, e_{j, k}(x_n))) \\ &= e_k(f_k(e_{i, k}(w_1), \ldots, e_{i, k}(w_n))) \\ &= e_k(e_{i, k}(f_i(w_1, \ldots, w_n))) \\ &= e_i(f_i(w_1, \ldots, w_n)) \end{split} \end{equation}$

which proves well-definedness. $\square$

We now define the predicates:

Dfn. Given an $n$-ary predicate symbol $P$, define $P_A \subseteq A^n$ by $(e_i(w_1), \ldots, e_i(w_n)) \in P$ if and only if $(w_1, \ldots, w_n) \in P_i$. Then $P_A$ is well-defined.

Proof: exactly the same as proving that $f_A$ is well-defined. $\square$

Then $A$ together with the functions and predicates defined above is a structure. We now prove

Thm. Each $e_i$ is an elementary embedding.

Proof: we assumed injectivity long ago. The function symbol and predicate symbol parts follow from the above definitions of $f_A$ and $P_A$. So we see $e_i$ is an embedding.

We then proceed via a straightforward induction on formulas to prove that $e_i$ is an elementary embedding. We could also use a modified version of the Tarski-Vaught test. The only nontrivial inductive step is the one with the quantifiers as usual; this step follows from the fact that all the $e_{i, j}$s are elementary embeddings. $\square$

$\square$

In order to prove uniqueness, I claim the following:

Thm. Let $V$ be a model, and suppose we have elementary embeddings $v_i : \mathfrak{A}_i \to V$ such that $v_i = v_k \circ e_{i, k}$ whenever $i \leq k$. Then there is a unique elementary embedding $v : \mathfrak{A} \to V$ such that for all $i$, $v_i = v \circ e_i$.

In other words, $\mathfrak{A}$ is actually the directed colimit (aka the direct limit) of the directed system in the category of models and embeddings as claimed.

Proof: we can simply directly define $v(e_i(w)) = v_i(w)$ and verify that this map is well-defined and an elementary embedding. $\square$

Corollary: $\mathfrak{A}$, together with the $e_i$, is unique up to unique isomorphism.

Proof:

Note that we defined the model structure $\mathfrak{A}$ on $A$ in the only possible way for each $e_i$ to be an elementary embedding.

So suppose we had another model $\mathfrak{B}$ with elementary embeddings $b_i : \frak A_i \to B$ such that for all $i \leq k$, $b_i = b_k \circ e_{i, k}$ and such that $\mathfrak{B} = \bigcup\limits_{i \in D} \mathfrak{A}_i$.

Then note that the condition $B = \bigcup\limits_{i \in I} e_i(A_i)$ holds. And note that for all $i \leq k$, we have $b_i = b_k \circ e_{i, k}$. And note that each $b_i$ is injective. Therefore, all of the above theorems which have been proved about $\mathfrak{A}$ and the $e_i$ also hold about $\mathfrak{B}$ and the $b_i$.

So in particular, we see that $(\mathfrak{B}, \{b_i\}_{i \in D})$ is also the directed colimit of $(\{\mathfrak{A}_i\}_{i \in D}, \{e_{i, k}\}_{i \leq k, i})$. Therefore, by the uniqueness of colimits, there is a unique isomorphism $f : \mathfrak{B} \to \mathfrak{A}$ such that for all $i$, $f \circ b_i = e_i$. $\square$