3
$\begingroup$

This is a problem (2.5.12) from Marker's Model Theory: An Introduction of showing that a model has only elementary submodels as its submodels if and only if for every formula is equivalent to some universal ($\Pi_1$) formula.

The "if" part is easy. I'm trying to show the "only if" part by induction. I try to show the induction step for a formula that starts with $\exists$ by finding the witness syntactically, but in vain. How can I do this?

$\endgroup$
2
  • $\begingroup$ I always confuse these, but by the "only if" part you mean assuming that it has only elementary submodels? $\endgroup$
    – Asaf Karagila
    Oct 23, 2014 at 18:29
  • $\begingroup$ Yes! (more keystrokes) $\endgroup$
    – Pteromys
    Oct 23, 2014 at 18:30

1 Answer 1

3
$\begingroup$

Exercise 2.5.12 is actually a little different than what you've written. First, it's formula-by-formula, and second, it just says that truth of $\phi$ goes down to substructures, but not conversely.

For those who don't have a copy of Marker on hand, the text of the problem is:

Show that the following are equivalent:

i) There is a universal formula $\psi(\overline{v})$ such that $T\models \forall\overline{v}\,(\varphi(\overline{v})\leftrightarrow \psi(\overline{v}))$.

ii) If $M$ and $N$ are models of $T$ with $M\subset N$, $\overline{a}\in M$, and $N\models \varphi(\overline{a})$, then $M\models \varphi(\overline{a})$.

I'll give a Hint: Adapt the proof of Theorem 2.3.9: instead of taking $\Gamma$ to be all universal sentences which are consequences of $T$, take it to be all universal formulas which are consequences of $\varphi(\overline{v})$ mod $T$. Show that if $\overline{a}\in M\models T$ and $M\models \Gamma(\overline{a})$, then $M\models \varphi(\overline{a})$. Then by compactness, some finite subset of $\Gamma(\overline{v})$ implies $\varphi(\overline{v})$ mod $T$, and the conjunction of this finite subset will be a universal formula equivalent to $\varphi$.

But the statement you've asked about in the question ($T$ is model complete [if you don't know this term, see Def 3.1.13 in Marker] iff every formula is equivalent mod $T$ to a universal formula) follows easily from the exercise. In fact, this is Exercise 3.4.12 in Marker (except with "existential" instead of "universal"...but see below).

How? Well, if $T$ is model complete, then condition ii) above holds for all formulas, and hence every formula is equivalent to a universal formula.

Note that if every formula is equivalent to a universal formula, then for any formula $\varphi$, $\lnot\varphi$ is equivalent to a universal formula $\psi$, so $\varphi \equiv \lnot(\lnot\varphi) \equiv \lnot\psi$, and hence every formula is also equivalent to an existential formula.

Now for the converse, we have that every formula is equivalent to both a universal formula and an existential formula. Since truth of universal formulas goes down and truth of existential formulas goes up, this shows $T$ is model complete.

$\endgroup$

You must log in to answer this question.

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