# Formula Complexity of $\models_n$

I want to show $\models_0$ is $\Sigma_1$, and $\forall n \geq 1, \models_n$ is $\Sigma_n$.

So for the base case, $\models_0 \ulcorner \phi \urcorner$ is true iff $\ulcorner \phi \urcorner \in Formulas$, $\ulcorner \phi \urcorner \in \Delta_0$ and $\exists M (M$ is transitive and $(M , \in ) \models \phi$). So, I have to show that those three conditions can be expressed as $\Sigma_1$ formulas. I think the first two be expressed as $\Delta_0$ under any reasonable coding, correct? And I'm having trouble with expressing the last condition, particularly with expressing $(M , \in ) \models \phi$ as $\Delta_0$ or $\Sigma_1$.

Once we have the base case, the inductive step follows pretty easily since $\models_n \ulcorner \exists x\phi \urcorner$ is true iff $\ulcorner \phi \urcorner \in Formulas$, $\ulcorner \phi \urcorner \in \Pi_{n-1}$ and $\exists a \neg \models_{n-1} \neg \phi(a)$. That the first two are expressible as $\Sigma_n$ would again follow from a reasonable coding procedure and the last is $\Sigma_n$ since we are just prefixing an $\exists$ and a $\neg$ to a $\Sigma_{n-1}$ formula.

Any general advice for approaching formula complexity problems would also be appreciated. Sometimes what we are trying to express as a formula can get fairly ugly formula-wise. It seems like the only strategy here is to memorize at which formula complexity a lot of the fundamental notions are and then to try to reduce the problem at hand to those fundamental notions, right?

• What is $\models_n$? I mean, I know what $\models$ is, but I don't quite understand what the subscript is doing there. – Nagase Nov 12 '14 at 19:57
• The definitions are basically what I wrote in the first sentences of the first two main paragraphs. They are introduced on page 186 of Jech's Set Theory. – Taro Nov 12 '14 at 20:01

I highly recommend Chapter I.9 of Devlin's "Constructibility", where many of the subtleties of this are worked out. It takes about 6 pages to show that "$$\varphi$$ is a formula" is $$\Delta_1$$; see Lemma 9.4. For each fixed (meta-mathematical) natural number $$n\geq 1$$, the sentence "$$\varphi$$ is $$\Sigma_n$$" is also $$\Delta_1$$, and is sketched in Lemma 9.13. Satisfiability for sets $$M$$ is definitely the most involved part; this is completed in Lemma 9.10 and shown to be $$\Delta_1$$. I think Jech was expecting students to just take these three facts for granted, as he never specifies a fixed definition of $$Form$$.