2
$\begingroup$

I am solving exercises in Model Theory: An Introduction from David Marker. So far I didn't get anywhere with the second part of the following exercise:


Exercise 4.5.13 Let $\Delta$ be a set of $L$-formulas closed under $\wedge, \vee, \neg$ and let $M$ be an $L$-structure. Let $S_n^\Delta ( T ) = \{ \Sigma \subset \Delta \, | \, \Sigma = \Sigma ( v_1 , \ldots , v_n), \, \Sigma \cup T \mbox{ is satisfiable, and } \phi \in \Sigma \mbox{ or } \neg\phi \in \Sigma \mbox{ for all } \phi \in \Delta \}$.

a) Show that for all $p \in S_n^\Delta ( T )$ there is $q \in S_n ( T )$ with $p \subseteq q$.

b) Suppose that for each $n$ and each $p \in S_n^\Delta ( T )$ there is a unique $a \in S_n ( T )$ with $p \subseteq q$. Show that for every $L$-formula $\phi ( \vec v )$ there is $\psi ( \vec v ) \in \Delta$ such that $T \models \phi ( \vec v ) \leftrightarrow \psi ( \vec v )$. In particular, if every quantifier-free type has a unique extension to a complete type, then $T$ has quantifier elimination.


First of all, I fail to see why this $L$-structure $M$ is given? It is not used anywhere in the exercise, so I will assume it is a typo and we can just omit it.

Part a) seems easy, assuming my argument is correct: any $p \in S_n^\Delta ( T )$ is in particular a partial $n$-type, and we know any partial $n$-type can be extended into a complete $n$-type. Is this correct?

Now for part b) I was thinking about doing an induction on the formula complexity of $\phi$. Is this a reasonable approach? For $\phi (\vec v )$ atomic I cannot prove the result. Once we will have shown it for atomic formulas, the $\wedge$ and $\neg$ cases will immediately follow by induction and the assumption that $\Delta$ is closed under those operations. I tried to prove the $\exists$ case but did not succeed either.

$\endgroup$
1
$\begingroup$

After some false starts I found a nice proof. Assume that $\varphi$ is not equivalent to a $\Delta$ formula. Let $p$ be a maximal $\Delta$-type such that for all $\psi \in p$, $\psi\wedge \varphi$ is not a $\Delta$-formula. $p$ is a complete $\Delta$-type since if $\psi\wedge \varphi$ and $\neg \psi\wedge \varphi$ are both $\Delta$ then $\varphi$ is $\Delta$.

Note that $p\cup \{\varphi\}$ is consistent since $\psi\wedge \varphi$ is not $\Delta$ so it cannot be inconsistent. ($\Delta$ must contain an inconsistent formula.)

Now by assumption $p$ has only one extension to a maximal type so $p\cup\{\neg \varphi\}$ is inconsistent. Then there is $\psi \in p$ such that $T\vdash \psi \rightarrow \varphi$ This means that $T\vdash \psi\wedge \varphi \leftrightarrow \psi$ and so $\psi\wedge \varphi$ a $\Delta$-formula, a contradiction.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Why is $p \cup \{ \phi \}$ consistent? I don't understand your argument. $\endgroup$ – McDonald Peter Aug 26 '14 at 2:04
  • $\begingroup$ Also, in the definition of $p$, shouldn't you require something a little bit stronger, namely that for all $\psi \in p$, the formula $\psi \wedge\phi$ is not $T$-equivalent to a $\Delta$-formula? (This because we want to reach the contradiction.) $\endgroup$ – McDonald Peter Aug 26 '14 at 2:20
  • $\begingroup$ Take some conjuction of formulas from $p$ call it $\psi$. If $\psi\wedge\varphi$ is inconsistent then it is $\Delta$. $\endgroup$ – Rene Schipperus Aug 26 '14 at 2:22
  • $\begingroup$ yeah I mean equivalent of course. $\endgroup$ – Rene Schipperus Aug 26 '14 at 2:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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