Levy hierarchy

View full site to see MathJax equation

The hierarchies \(\Sigma_n\) and \(\Pi_n\) of set theoretic formulae, which are called the Levy hierarchy, are defined inductively on \(n\) in the following way:

1. If \(\phi\) is equivalent to a first order formula in set theory without unbounded quantifiers, then \(\phi\) is \(\Pi_0\) and \(\Sigma_0\).
2. If \(\phi\) is equivalent to \(\exists x_0 \exists x_1 \exists x_2...\exists x_k \psi\) for some distinct variable symbols \(x_0, x_1, x_2, \ldots, x_k\) where \(\psi\) is \(\Pi_n\), then \(\phi\) is \(\Sigma_{n+1}\).
3. If \(\phi\) is equivalent to \(\forall x_0 \forall x_1 \forall x_2...\forall x_k \psi\) for some distinct variable symbols \(x_0, x_1, x_2, \ldots, x_k\) where \(\psi\) is \(\Sigma_n\), then \(\phi\) is \(\Pi_{n+1}\)

Readers should be careful not to confound Levy hierarchy with arithmetic hierarchy, which is also denoted by \(\Sigma_n\) and \(\Pi_n\).

If a formula is both \(\Sigma_n\) and \(\Pi_n\), it can also be called \(\Delta_n\). Note that \(\Sigma_0\), \(\Pi_0\), and \(\Delta_0\) are all equivalent, and are expressive enough to express many basic set-theoretic concepts.

Examples

• Given a variable symbol \(x\), \(\exists x(x=x)\) is a \(\Sigma_1\) formula.
• Given distinct variable symbols \(x,y\), \(\exists(x\in y)(x=x)\) is a \(\Sigma_0\) formula.
• Given a formula \(\chi(x_0,x_1,x_2,x_3,x_4,x_5)\) with exactly six free variables, \(\forall x_0\forall x_1\exists x_2\exists x_3\exists x_4\forall(x_5\in x_2)\chi(x_0,x_1,x_2,x_3,x_4,x_5)\) is a \(\Pi_2\) formula.