# $\exists^\infty$-elimination and model companion.

In the book Ziegler, Tent: A course in model theory it states

Exercise 5.5.7. Let $$T_1$$ and $$T_2$$ be two model complete theories in disjoint languages $$L_1$$ and $$L_2$$. Assume that both theories eliminate $$\exists^\infty$$ . Then $$T_1\cup T_2$$ has a model companion.

I want to prove this statement. Sine $$T_1\cup T_2$$ also eliminates $$\exists^\infty$$ (i.e. in all models realisation sets have either a finite upper bound or are infinite) my strategy was to use the previous exercise

Exercise 5.5.6. Assume that T eliminates the quantifier $$\exists^\infty$$. Then for every formula $$\varphi(x_1 , . . . , x_n , \overline{y})$$ there is a formula $$\theta(\overline{y})$$ such that in all models $$\mathfrak{M}$$ of $$T$$ a tuple $$\overline{b}$$ satisfies $$\theta(\overline{y})$$ if and only if $$\mathfrak{M}$$ has an elementary extension $$\mathfrak{M}'$$ with elements $$a_1 , . . . , a_n\in M'\setminus M$$ such that $$\mathfrak{M}\vDash\varphi(a_1,...,a_n)$$.

I define the theory

$$(T_1\cup T_2)^*:=\{\theta\;|\;$$there exists a $$L_1\cup L_2$$-formula $$\varphi(x_1,..x_n)$$, that is satisfiable in all models $$\mathfrak{M}\vDash T_1\cup T_2$$ such that $$\mathfrak{M}\vDash\theta\Leftrightarrow$$ there exists an elementary extension $$\mathfrak{M}'$$ with elements $$a_1 , . . . , a_n\in M'\setminus M$$ such that $$\mathfrak{M}\vDash\varphi(a_1,...,a_n)\}$$

To me it seemed to be right choice for the model companion of $$T_1\cup T_2$$ until I tried to prove that $$(T_1\cup T_2)^*$$ is model complete (without success). Does this choice make sense?

Since $$T_1$$ and $$T_2$$ are model complete, they are $$\forall\exists$$-axiomatizable, and $$T_1\cup T_2$$ is also $$\forall\exists$$-axiomatizable. So to show the model companion exists, you need to axiomatize the existentially closed models of $$T_1\cup T_2$$.

So suppose $$M\subseteq M'$$, both models of $$T_1\cup T_2$$. We want to write down a sufficient condition for $$M$$ to be existentially closed in $$M'$$. Let $$\psi(x)$$ be a quantifier-free formula with parameters from $$M$$ such that $$M'\models \exists x\, \psi(x)$$. You want to observe the following things:

1. It suffices to assume that $$\psi(x)$$ is a conjunction of atomic and negated atomic $$(L_1\cup L_2)$$-formulas.

2. So if $$L_1$$ and $$L_2$$ are relational, $$\psi(x)$$ is actually a conjunction $$\varphi_1(x)\land \varphi_2(x)$$, where $$\varphi_1$$ is an $$L_1$$-formula and $$\varphi_2$$ is an $$L_2$$-formula. If the languages aren't relational, there's an issue that $$\psi$$ could mention terms formed using function symbols from both $$L_1$$ and $$L_2$$. Then you have to think about replacing $$\psi$$ with another formula obtained by "unnesting" all terms. It might be better to work out the details in the relational case first and then come back to this complication.

3. It suffices to assume that there is a witness $$M'\models \psi(a')$$ such that each element of $$a'$$ is in $$M'\setminus M$$ and the elements of $$a'$$ are all distinct.

This leads us to the following axiomatization: Let $$\varphi_1(x,y)$$ be a quantifier-free $$L_1$$-formula, and let $$\varphi_2(x,z)$$ be a quantifier-free $$L_2$$-formula (here $$x$$, $$y$$, $$z$$ are tuples of variables). Let $$\theta_1(y)$$ and $$\theta_2(z)$$ be the formulas provided by Exercise 5.5.6. for $$\varphi_1$$ and $$\varphi_2$$, respectively. Let $$\theta'_1(y)$$ be the conjunction of $$\theta_1(y)$$ and inequations $$y_i\neq y_j$$ for $$i\neq j$$, and similarly for $$\theta'_2(z)$$. Then look at the following sentence: $$\forall y\, \forall z\, ((\theta'_1(y)\land \theta'_2(z))\rightarrow \exists x\, (\varphi_1(x,y)\land \varphi_2(x,z))).$$

The model companion of $$T_1\cup T_2$$ is axiomatized by $$T_1\cup T_2$$ together with all sentences of the above form. The discussion above can be viewed as an extended hint that every model of this theory is an existentially closed model of $$T_1\cup T_2$$. You also need to show the converse: that every existentially closed model of $$T_1\cup T_2$$ satisfies these extra axioms. Explicitly, given $$\varphi_1(x,y)$$ and $$\varphi_2(x,z)$$, if $$M\models \theta_1'(b)\land \theta_2'(c)$$, then you can embed $$M$$ in a model $$M'$$ of $$T_1\cup T_2$$ such that $$M'\models \varphi_1(a',b)\land \varphi_2(a',c)$$ for some $$a'\in M'$$, and use the fact that $$M$$ is existentially closed to find a witness in $$M$$.

Aside: The statement of the exercise is a result from Peter Winkler's 1975 PhD thesis. It's a nice coincidence that you posted this problem now. Minh Tran, Erik Walsberg, and I are working on a project that we call "Interpolative Fusions" which at its heart is a generalization of this result of Winkler's. We just posted the first paper from this project to the arXiv this week: https://arxiv.org/abs/1811.06108