Show that a class of structures is existentially axiomatisable iff it is closed under taking superstructures

240 Views Asked by At

A sentence is called existential if it's of the form $\exists x_1 \cdots \exists x_n \varphi(x_1, \cdots, x_n)$, where $\varphi$ is quantifier-free formula.

I'm trying to prove a lemma left as an exercise in my lecture notes that says

Let $C$ be an axiomatizable class. Then the following conditions are equivalent: (i) $C$ is $\exists$-axiomatizable; (ii) If $A \in C$ and $A \leq B$ then $B \in C$.

One direction is simple - if $C$ is $\exists$-axiomatizable then it follows easily by the fact that if $A \models \varphi(a_1, \cdots , a_n)$ for an existential formula $\varphi(v_1, \cdots , v_n)$, then $B \models \varphi(a_1, \cdots , a_n)$.

I'm really not sure how to go about proving the other direction.

I've proved the equivalent version for universal axiomatisation - i.e. that $C$ is $\forall$-axiomatizable iff $B \in C$ and $A \leq B$ then $A \leq C.$ To do that, I showed that Th$(C) \cup $Th$_∃(A)$ is finitely satisfiable (where $A\models$ Th$_\forall$(C) - i.e. $A$ is a model of the universal sentences in the theory of $C$) where Th$_∃(A)$ are the existential sentences of the theory of $A$. It followed from that, and some other results I have, that Th$(C)\cup$Diag$(A)$ was satisfiable, from which it followed there is a model $B$ of Th$(C)$ such that $A \leq B$, which meant by the assumption that $A\in C$ and hence (since $A\models$ Th$_\forall$(C)) that $C$ was universally axiomatisable.

I'm really unsure how I'd go about taking a similar approach for the existential case - I haven't proved any similar results like the one that took me from Th$(C)\cup$Diag$(A)$ being satisfiable to there being a $B$ like I have here, and even if I did I'm not sure how I'd apply a similar kind of result - since in this case I have to start with a smaller model $A$ instead of a bigger one.

Any advice or suggestions you could offer would be much appreciated.

1

There are 1 best solutions below

0
On

The following general lemma is useful for proving axiomatizability by sentences of a particular form.

Separation Lemma: Let $\Delta$ be a class of sentences which contains $\bot$ and is closed under $\vee$ (up to logical equivalence). Suppose $T$ is a theory such that for any $M\models T$ and $N\not\models T$, there is some $\varphi\in \Delta$ such that $M\models \varphi$ and $N\not\models \varphi$. Then $T$ is axiomatizable by $\Delta$-sentences.

Proof: Fix some $N\not\models T$. For every model $M\models T$, there is some $\varphi_M\in \Delta$ such that $M\models \varphi_M$ and $N\not\models \varphi_M$. Thus $T\cup \{\lnot\varphi_M\mid M\models T\}$ is inconsistent. By compactness, there are finitely many $M_1,\dots,M_k$ such that $T\cup \{\lnot \varphi_{M_1},\dots,\lnot\varphi_{M_k}\}$ is inconsistent. So $T\models \bigvee_{i=1}^k\varphi_{M_i}$. By our assumption on $\Delta$, this disjunction is equivalent to a sentence in $\Delta$, which we call $\psi_N$. Note that $N\not\models \psi_N$.

Now $T' = \{\psi_N\mid N\not\models T\}$ is a $\Delta$-axiomatization of $T$. Indeed, $T\models \psi_N$ for all $\psi_N\in T'$, so every model of $T$ is a model of $T'$. And if $N$ is not a model of $T$, then $N\not\models \psi_N$, so $N$ is not a model of $T'$. $\square$

Rephrasing: To prove that $T$ is $\Delta$-axiomatizable, it suffices to show that if $M\models T$ and every $\Delta$-sentence true in $M$ is also true in $N$, then $N\models T$.

Now let's take $\Delta$ to be the class of existential sentences and assume that the class of models of $T$ is closed under superstructure. Let $M\models T$ and assume that every existential sentence true in $M$ is true in $N$. We would like to show that $N\models T$.

Since the class of models of $T$ is closed under superstructure and elementary equivalence, it suffices to embed $M$ in a model $N'$ elementarily equivalent to $N$. So we look at $\text{Th}(N)\cup \text{Diag}(M)$. By compactness, this is consistent just in case $\text{Th}(N)\cup \{\theta(a_1,\dots,a_n)\}$ is consistent whenever $\theta$ is a conjunction of atomic and negated atomic formulas and $M\models \theta(a_1,\dots,a_n)$. But then $M\models \exists x_1,\dots,x_n \theta(x_1,\dots,x_n)$, so also $N\models \exists x_1,\dots,x_n \theta(x_1,\dots,x_n)$, and interpreting the constants $a_i$ as witnesses in $N$, we have $N\models \text{Th}(N)\cup \{\theta(a_1,\dots,a_n)\}$.