The Theorem is 3.1.11 and states that for $n>0$ the following are equivalent :

  1. $\phi$ is equivalent both to a $\Sigma^0_{n+1}$ and a $\Pi^0_{n+1}$ sentence.

  2. $\phi$ is equivalent to a Boolean combination of $\Sigma^0_n$ sentences.

The proof is model theoretic (it involves defining a $\Sigma^0_n$-chain of models). In the book it says that this theorem is a model theoretic proof of a theorem about predicate logic. Does this mean that there is a simpler proof that is not model theoretic? What is the alternative proof?

Note : The classes $\Sigma^0_n$ and $\Pi^0_n$ of formulas are defined recursively as follows : $\Sigma^0_0 = \Pi^0_0 = $ the set of all quantifier free formulas and $\phi$ is in $\Sigma^0_{n+1}$ (resp. $\Pi^0_{n+1}$) if $\phi = \exists x_1 \ldots \exists x_n \psi$ (resp. $\phi = \forall x_1 \ldots \forall x_n \psi$), where $\psi$ is in $\Pi^0_n$ (resp. $\Sigma^0_n$).


Your Answer

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

Browse other questions tagged or ask your own question.