A sentence is called existential if it is of the form $\exists x_1 \cdots \exists x_n \varphi(x_1, \cdots, x_n)$, where $\varphi$ is quantifier-free formula.
I wish to show (an exercise):
A theory allows an existential axiomatization iff its models are closed under
extensions.
This an analog of the Los-Tarski theorem (which deals instead with universal axiomatizations).
We define $A \prec_\exists B$ when $A \models \varphi \Rightarrow B \models \varphi$ for every existential $\varphi$.
The exercise comes with the hint to first show (1) and (2):
(1) $T$ allows an existential axiomatization iff $A \models T$ and
$A \prec_\exists B$ imply $B \models T$. (2) $A \prec_\exists B$ iff
$A$ can be embedded in an elementary extension of $B$.
I can prove (2) (I think not hard), and also show why (1) & (2) imply the main result.
For (1) I have:
we only want to show right-to-left (other direction is easy). Define
\begin{equation*}
T_\exists = \{\varphi : T \models \varphi \text{ and $\varphi$ is existential}\} \, .
\end{equation*}
Show: $T_\exists \models T$; suppose $B \models T_\exists$ arbitrary, prove $B \models T$. It is enough to establish the existence of a structure $A$ such that $A \models T$ and $A \sqsubseteq_\exists B$. Consider
\begin{equation*}
T' = T \cup \{\neg\varphi : T \not\models \varphi \text{ and $\varphi$ is existential}\} \, .
\end{equation*}
We use the compactness theorem to show satisfiability. If say $S \models T'$, then $S \models T$ and $S \models \varphi \Rightarrow B \models \varphi$ for every existential $\varphi$, and we are done. So we want that $T \cup \{\neg\varphi_1, \cdots, \neg\varphi_n\}$ is consistent. We know by definition that each $T \cup \{\neg\varphi_i\}$ is satisfiable.
But I don't know how to proceed. My guess is to somehow use the existential nature of the sentences $\varphi_i$… I feel I am not far of! 🙂
Could you provide a hint?
Best Answer
You need to consider a slightly different $T'$. The reason is that $T$ might not be complete: there might be existential sentences $\varphi$ and $\psi$ such that $T\models \varphi\lor \psi$, but $T\not\models \varphi$ and $T\not\models \psi$. According to your definition of $T'$, it would contain $\{\varphi\lor \psi, \lnot \varphi, \lnot \psi\}$, which is clearly inconsistent.
Instead, note that it suffices to look at $T' = T\cup \{\lnot \varphi\mid B\not\models \varphi\text{ and }\varphi\text{ is existential}\}$.
Any finite subset of $T'$ is contained in a theory of the form $T\cup \{\lnot\varphi_1,\dots,\lnot \varphi_n\}$, which is equivalent to $T\cup \{ \bigwedge_{i=1}^n\lnot \varphi_i\}$, equivalently $T\cup \{\lnot \bigvee_{i=1}^n \varphi_i\}$. If this were inconsistent, then we would have $T\models \bigvee_{i=1}^n \varphi_i$. But $\bigvee_{i=1}^n \varphi_i$ is equivalent to an existential formula $\psi$, which is in $T_\exists$, and hence is satisfied by $B$. This contradicts the fact that $B\models \lnot \bigvee_{i=1}^n \varphi_i$.