# Exercise 4.5.13 in Marker

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.

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.
• Why is $p \cup \{ \phi \}$ consistent? I don't understand your argument. – McDonald Peter Aug 26 '14 at 2:04
• 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.) – McDonald Peter Aug 26 '14 at 2:20
• Take some conjuction of formulas from $p$ call it $\psi$. If $\psi\wedge\varphi$ is inconsistent then it is $\Delta$. – Rene Schipperus Aug 26 '14 at 2:22