# What exactly is Levy hierarchy?

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

-
What does KP abbreviate? – Berci Feb 21 '13 at 12:40
@Berci Kripke-Platek set theory – user61182 Feb 21 '13 at 12:41

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).
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.