1
$\begingroup$

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.

$\endgroup$
2
  • 4
    $\begingroup$ $|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}$. $\endgroup$ Jan 9 '21 at 4:10
  • 1
    $\begingroup$ 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. $\endgroup$ Jan 9 '21 at 11:20
2
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.