Proof Verification: $T$ is complete if and only if $\text{Mod}(T)$ satisfies the joint embedding property

Question

This answer has an example exercise to show a relationship between the joint embedding property of the category of models of a given theory and the completeness of that theory, paraphrased in the section below with links to definitions.

I tried to prove it. I'm pretty sure my proof attempt works but I'm not totally certain.

• Does the proof attempt work?
• Is there a more elegant way to prove this?
• Am I assuming any nontrivial results improperly (e.g. without naming the theorem when it would be idiomatic to name it)?

---

A theory $T$ is complete if and only if its category of models with arrows given by elementary embeddings $\text{Mod}(T)$ satisfies the joint embedding property.

---

Suppose that $T$ is complete.

For any pair of objects $x$ and $y$ in $\text{Mod}(T)$, $x$ and $y$ are elementarily equivalent because they satisfy the same sentences due to the completeness of $T$. Suppose without loss of generality that $|x| \le |y|$, then there exists an elementary embedding $f : x \to y$. The cardinals are totally ordered and every object has an identity arrow going to itself, therefore both $x$ and $y$ have arrows going to $\max(x, y)$, the larger of the two by cardinality, or $x$ if they have the same cardinality. Since $x$ and $y$ were chosen arbitrarily, $\text{Mod}(T)$ has the joint embedding property.

Suppose $T$ satisfies the joint embedding property.

For any objects $x$ and $y$ in $\text{Mod}(T)$, there exists an object $z$ so that there exist arrows $f : x \to z$ and $g : y \to z$. By definition of $\text{Mod}(T)$, if an arrow exists between two objects, then they satisfy the same sentences. Therefore, $x$ satisfies the same sentences as $z$ and $y$ satisfies the same sentences as $z$. Therefore, $x$ satisfies the same sentences as $y$. Since $x$ and $y$ were chosen arbitrarily, this means that all models satisfy the same sentences. Thus, $T$ is complete.

Answer 1

As others have pointed out in the comments, your proof of the implication "complete$\implies$ JEP" is not quite right. In particular, the claim that $|M|\leqslant |N|$ implies the existence of an elementary embedding $M\to N$ is not true in general. Alex gives a nice example of this, but here is perhaps a simpler one:

Let $\mathcal{L}=\{P_1,P_2\}$ consist of two unary predicate symbols, and let $T$ assert that $P_1\cap P_2=\emptyset$, that each $P_i$ is infinite, and that every element belongs to one of the $P_i$. Then $T$ is $\aleph_0$-categorical (why?), and is hence in particular complete. However, consider a model $M$ of $T$ where $|P_1^M|=\aleph_1$ and $|P_2^M|=\aleph_1$, and a model $N$ of $T$ where $|P_1^N|=\aleph_0$ and $|P_2^N|=\aleph_2$. Then $|M|=\aleph_1<\aleph_2=|N|$, but there is no elementary embedding $M\to N$, since such an embedding would induce an injection $P_1^M\to P_1^N$.

There is a relevant notion you might find interesting, of a "prime model" of a complete theory, the defining property of which is that they elementarily embed into every other model. You can read about these in, eg, chapter 4 of Marker.

---

Here's an alternative proof. Let $\mathcal{L}'=\mathcal{L}\cup\{c_a\}_{a\in M}\cup\{d_b\}_{b\in N}$, where the $c_a$ and $d_b$ are constant symbols corresponding to the elements of $M$ and $N$, respectively. We can naturally consider $M$ as an $\mathcal{L}\cup\{c_a\}_{a\in M}$-structure, by realizing each $c_a$ as $a$; let $T_M$ be the set of all $\mathcal{L}\cup\{c_a\}_{a\in M}$ sentences satisfied by $M$. (This is known as the "elementary diagram" of $M$.)

Similarly, let $T_N$ be the elementary diagram of $N$ in the language $\mathcal{L}\cup \{d_b\}_{b\in N}$, and let $T'=T\cup T_M\cup T_N$. Can you use completeness of $T$ to show that $T'$ is finitely satisfiable?

Since $M\models T\cup T_M$, it suffices to show that $T_N$ is finitely satisfiable in $M$. By taking conjunctions, we therefore just need to to show that $\psi(d_{b_1},\dots,d_{b_n})$ is satisfiable in $M$ for any $\mathcal{L}$-formula $\psi(\overline{w})$ with $\psi(\overline{d})\in T_N$. By construction, we know $$N\models\psi(d_{b_1},\dots,d_{b_n}),$$ and so in particular $N\models\exists w_1,\dots,w_m\ \psi(w_1,\dots,w_n)$. Moreover, the sentence $\exists \overline{w}\ \psi(\overline{w})$ is an $\mathcal{L}$-sentence (ie, it contains no symbols outside $\mathcal{L}$). Since $T$ is complete, this means we must have $\exists \overline{w}\ \psi(\overline{w})\in T$, and hence $M\models\exists\overline{w}\ \psi(\overline{w})$. Interpreting the $d_{b_i}$ as witnesses of this sentence in $M$ then gives the desired result.

Thus $T'$ is finitely consistent, and so – by compactness – there exists an $\mathcal{L}'$-structure $O$ modeling $T'$. Now, consider the functions $f:M\to O$ and $g:N\to O$ given by $f(a)=c_a^O$ and $g(b)=d_b^O$. Can you show that this map is an elementary $\mathcal{L}$-embedding?