# Prove this proposition concerning a theory with ∀∃-axiomatization

Setting

A theory $\pmb{T}$ has a $\forall\exists$-axiomatization if it can be axiomatized by sentences of the form $$\forall v_1\ldots \forall v_n \exists w_1 \ldots \exists w_n ~~ \phi(\bar{v},\bar{w})$$ where $\phi$ is a quantifier free $\mathcal{L}$-formula.

Furthermore, suppose whenever $(\mathcal{M}_i : i \in \mathbb{I})$ is a chain of models of $\pmb{T}$, then $$\mathcal{M} = \bigcup \mathcal{M}_i \models \pmb{T}.$$ Let $\Gamma = \{ \phi : \phi \text{ is a$\forall\exists$-sentence and$\pmb{T} \models \phi$}\}$. Let $\mathcal{M} \models \Gamma$.

Finally, suppose there is $\mathcal{N} \models \pmb{T}$ such that if $\psi$ is an $\exists\forall$-sentence and $\mathcal{M} \models \psi$, then $\mathcal{N} \models \psi$.

Now I would like to show that there is $\mathcal{N}' \supseteq \mathcal{M}$ with $\mathcal{N}' \equiv \mathcal{N}$.

Problem

1. First, I am not sure if the assumption is that $\mathcal{M} \subseteq \mathcal{N}'$? I am guessing since you can always create an extension, then $\mathcal{N}'$ is assumed to exist?

2. Suppose my presumption is correct so that $\mathcal{N}'$ exist, but as an extension of $\mathcal{M}$, it does not need to satisfy the same sentences correct? So why is it true that $\mathcal{N}' \equiv \mathcal{N}$?

3. Finally, if I am reading the proposition totally wrong, and instead I just have to show/construct some $\mathcal{N}'$ so that $\mathcal{N}' \equiv \mathcal{N}$, how would I go about doing such a construction?

• Isn't your "furthermore" redundant? A theory axiomatized by $\forall\exists$ sentences is necessarily closed under unions of chains, isn't it? – bof Feb 14 '15 at 3:03
• By "there exists $\mathcal M\subseteq\mathcal N'$" you must mean "there exists $\mathcal N'\supseteq\mathcal M$", right? – bof Feb 14 '15 at 3:06
• I don't see how the theory $\pmb{T}$ has anything to do with your question. It seems you are simply asking, if $\mathcal M$ and $\mathcal N$ are two models such that every $\forall\exists$ sentence which holds in $\mathcal M$ also holds in $\mathcal N$, does it follow that some extension of $\mathcal M$ is elementarily equivalent to $\mathcal N$? Is that right? I don't think you need $\forall\exists$ sentences for that; I believe it's enough if every existential sentence that holds in $\mathcal M$ also holds in $\mathcal N$. – bof Feb 14 '15 at 3:19
• @bof I changed the direction of inclusion and their arguments as you suggested. My problem is that if $\mathcal{N}'$ extends $\mathcal{M}$, then wouldn't it be possible that $\mathcal{N}'$ contain elements that may not satisfy the $\forall$ quantifier in some $\forall\exists$-sentence? – chibro2 Feb 14 '15 at 3:26

Please excuse my barbaric notation and terminology; it has been years since I sat in a logic class. I will sketch a proof of the fact that, if $\mathcal M,\mathcal N$ are models such that every existential sentence which holds in $\mathcal M$ also holds in $\mathcal N$, then there is a model $\mathcal N'$ such that $\mathcal M$ is isomorphic to a submodel of $\mathcal N'$ and $\mathcal N$ is isomorphic to an elementary submodel of $\mathcal N'$.

Let $U$ be the first-order theory of $\mathcal N$ in an expanded language which has a constant symbol for each element of $\mathcal N$. Thus any model of $U$ (more precisely, its reduct to the original language) will contain an isomorphic copy of $\mathcal N$ as an elementary submodel.

Let $Q$ be the quantifier-free theory of $\mathcal M$ in an expanded language which has a constant symbol for each element of $\mathcal M$. Thus any model of $Q$ will contain a submodel isomorphic to $\mathcal M$.

Since any model $\mathcal N'$ of $U\cup Q$ will do what we want, all we have left to show is that $U\cup Q$ is consistent. By the compactness theorem, it will suffice to show that $U\cup Q'$ is consistent for each finite set $Q'\subseteq Q$. This follows from the hypothesis that every existential sentence which holds in $\mathcal M$ also holds in $\mathcal N$. [*]

P.S. By virtue of the Keisler-Shelah theorem (elementarily equivalent models have isomorphic ultrapowers) the statement can be strengthened to read: if every existential sentence which holds in $\mathcal M$ also holds in $\mathcal N$, then $\mathcal M$ is isomorphic to a submodel of an ultrapower of $\mathcal N$.

[*] Consider a finite set $Q'\subseteq Q$. By forming a conjunction, we may assume that $Q'$ consists of a single quantifier sentence $\varphi(c_1,\dots,c_n)$, where $c_1,\dots,c_n$ are constants in the expanded language for $\mathcal M$. Since $\varphi(c_1,\dots,c_n)$ holds in $\mathcal M$, so does the existential semtemce $\exists x_1,\dots,x_n)\varphi(x_1,\dots,x_n)$ of the original language. Hence the sentence $\exists x_1,\dots,x_n)\varphi(x_1,\dots,x_n)$ also holds in $\mathcal N$. Therefore, the constants $c_,\dots,c_n$ can be assigned values in $\mathcal N$ so as to satisfy $\varphi(c_1,\dots,c_n)$, showing that $U\cup Q'$ is consistent.

• could you elaborate on the signficance that $Q$ has to be quantifier free? Especially in relation to the sentence "This follows from the hypothesis that every existential sentence which holds in $\mathcal{M}$ also holds in $\mathcal{N}$"? The hypothesis states that if $\mathcal{M}$ satisfies a quantified sentence, then $\mathcal{N}$ also satisfies it. But $Q$ has no quantified sentences although $U$ does. So can't there be quantified sentences in $U$ that cannot be satisfied by $\mathcal{M}$? – chibro2 Feb 14 '15 at 16:02
• Furthermore, how do you know the quantifier-free sentences in $Q$ and $U$ using the expanded langauge will also be satisfiable? – chibro2 Feb 14 '15 at 16:21
• Finally, if I wanted to prove $\mathcal{N}' \equiv \mathcal{N}$, should I use the original language $\mathcal{L}$ or the extended language containing constants from $\mathcal{M}$ and $\mathcal{N}$? – chibro2 Feb 14 '15 at 17:23
• I added some explanation to my answer. – bof Feb 14 '15 at 22:41
• thank you for answering my question. I asked a continuation of the question above. And I am wondering if you'd like to take a look? math.stackexchange.com/questions/1149697/… – chibro2 Feb 15 '15 at 23:05