Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer

up vote 7 down vote accepted

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.")

share|improve this answer
    
Thanks, Andreas - this is just what I was hoping for. –  Scott McKuen Jul 26 '10 at 15:00
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.