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

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.

• $|M|\leq |N|$ and $M\equiv N$ does not imply that there is an elementary embedding from $M$ to $N$. For example, there are countable non-Archimedean real closed fields, which cannot elementarily embed in $\mathbb{R}$. Jan 9, 2021 at 4:10
• I agree with Alex, the proof of that direction (complete $\implies$ JEP) does not work. Hint: use compactness. The proof of the other direction (JEP $\implies$ complete) is correct. Jan 9, 2021 at 11:20

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?