10
$\begingroup$

Background

I am working through a particular result in a paper of Cherlin, Shelah, and Shi, and am satisfied that it follows from basic model theory material - but I'm stuck on one point in the background material.

In Hodges' "A Shorter Model Theory", Lemma 7.2.5 on page 191 seems to have an unused assumption. He considers, for a $\forall_2$ $L$-theory $T$, an existential formula $\phi$ and the set of all universal formulas implied (under $T$) by $\phi$. He calls this set the resultant of $\phi$:

$Res_\phi(x) =$ {universal $\psi(x)$ | $T \vdash \forall x (\phi(x) \rightarrow \psi(x))$}

Then he shows that an arbitrary $L$-structure $A$ and element $a$ satisfy $Res_\phi(a)$ iff there is some extension $B$ of $A$ with $B \models T$ and $B \models \phi(a)$.

Key Issue

I can't tell where Hodges is using the assumption that $T$ is $\forall_2$. The given proof (below) looks like it goes through without that assumption:

$\Rightarrow$ Suppose some extension $B$ of $A$ satisfies $\phi(a)$ and $T$. Then $B$ satisfies $Res_\phi(a)$. Any universal formula satisfied in $B$ must be satisfied in the substructure $A$, also. Since $Res_\phi(x)$ contains only universal formulas, $B \models Res_\phi(a) \implies A \models Res_\phi(a)$.

$\Leftarrow$: Suppose $A$ satisfies $Res_\phi(a)$. If there is no extension $B$ of $A$ that satisfies $\phi(a)$ and $T$, then add to the language a constant $c$ representing $a$, and consider (in the language $L_c$) $Diag(A) \cup \{\phi(c)\} \cup T$. By assumption, this set of sentences has no model, so by compactness

$$ T \vdash \phi(c) \rightarrow \neg \sigma(c,d^A) $$

for some $d^A$ in $A$ and some quantifier-free formula $\sigma$. Since $c$ and $d^A$ do not appear in $T$, we can replace them with universally quantified variables:

$$ T \vdash \forall x [ \phi(x) \rightarrow \forall y \neg \sigma(x,y) ] $$

Thus, $\forall y(\neg \sigma(x,y)) \in Res_\phi(x)$ so $A \models \forall y (\neg \sigma(a,y))$. But we got $\sigma$ by considering the $L_c$-diagram of $A$, so $A \models \exists y \sigma(a,y)$. Contradiction.

I don't see anywhere that the $\forall_2$ assumption on T comes in. Perhaps this assumption is just for context in the rest of the neighboring material?

$\endgroup$

1 Answer 1

8
$\begingroup$

The result doesn't need the assumption that $T$ is an $\forall_2$-theory, nor does it need that the formula $\phi(x)$ is existential. The relevant general result is that a structure $A$ has an extension satisfying a theory $T$ (in the same vocabulary) if and only if $A$ satisfies all the universal sentences that are provable from $T$. To get the result quoted in the question, minus the unnecessary hypotheses, apply this general result not to the given $T$ but to $T$ plus $\phi(c)$, where $c$ is a new constant symbol interpreted as $a$. (Actually, there is an even more general version of the result; see the "Model Extension Theorem" in Section 5.2 of Shoenfield's "Mathematical Logic" or Lemma 3.5.10(i) of Hinman's "Fundamentals of Mathematical Logic.")

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .