Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Wikipedia lacks information on Levy hierarchy, so what exactly is Levy hierarchy? This will tell me what $\Delta_0$ means in KP set theory.

share|improve this question
    
What does KP abbreviate? –  Berci Feb 21 '13 at 12:40
1  
@Berci Kripke-Platek set theory –  user61182 Feb 21 '13 at 12:41

1 Answer 1

A formula in the language of set theory is called $\Delta_0$ (or $\Sigma_0$ or $\Pi_0$) if all of the quantifiers appearing in it are bounded, that is if they are all of the form $\forall x\in y$ or $\exists x\in y$. A formula is called $\Sigma_{n+1}$ if it is of the form $\exists x_1\dots\exists x_k\colon\varphi$, where $\varphi$ is $\Pi_n$. A formula is called $\Pi_{n+1}$ if it is of the form $\forall x_1\dots\forall x_k\colon \varphi$, where $\varphi$ is $\Sigma_n$.

This classification is quite rigid: the formulas appearing have a very specific form, with all of the unbounded quantifiers outside. If you are given some theory $T$, you can do a similar and slightly more useful classification based on $T$-provable equivalence. That is to say, a formula is called $\Sigma_n^T$ if it is $T$-provably equivalent to a $\Sigma_n$ formula (and similarly for $\Pi_n^T$). A formula is called $\Delta_n^T$ if it is both $\Sigma_n^T$ and $\Pi_n^T$ (note that there is no such thing as a $\Delta_n$ formula).

Both of these hierarchies are called the Lévy hierarchy.

It is also quite common (as Asaf points out in the comments) to replace the $\Sigma_n$ and $\Pi_n$ of the basic hierarchy with $\Sigma_n^\emptyset$ and $\Pi_n^\emptyset$, in effect modding out by logical equivalence.

share|improve this answer
1  
It is often better to require logical equivalence (over the empty theory) when defining the hierarchy. This way the classes are closed under conjunction and disjunction. –  Asaf Karagila Jun 25 '13 at 7:22

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.