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?

  • $\begingroup$ What is $\models_n$? I mean, I know what $\models$ is, but I don't quite understand what the subscript is doing there. $\endgroup$ – Nagase Nov 12 '14 at 19:57
  • 1
    $\begingroup$ 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. $\endgroup$ – 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$.


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.