11,052 Pages

The hierarchies $$\Sigma_n$$ and $$\Pi_n$$, which are called the Levy hierarchy, are defined inductively on $$n$$ in the following way[1]:

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 n_0 \exists n_1 \exists n_2...\exists n_k \psi$$ for some natural numbers $$n_0, n_1, n_2...n_k$$ where $$\psi$$ is $$\Pi_n$$, then $$\phi$$ is $$\Sigma_{n+1}$$
3. If $$\phi$$ is equivalent to $$\forall n_0 \forall n_1 \forall n_2...\forall n_k \psi$$ for some natural numbers $$n_0, n_1, n_2...n_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[2].

## Examples

• $$\exists x(x=x)$$ is a $$\Sigma_1$$ formula.
• Given a free variable $$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 $$\Pi_2$$.
• Work in an arithmetic such as Peano arithmetic. Given a natural number $$n$$, the property "$$n$$ is odd" is $$\Delta_1$$, e.g. the formulae $$\exists k(n=k+k+1)$$ (which is $$\Sigma_1$$) and $$\forall k(k+k\neq n)$$ (which is $$\Pi_1$$) are logically equivalent.

## Sources

1. Levy, Azriel (1965). A hierarchy of formulas in set theory. Mem. Am. Math. Soc. 57. Zbl 0202.30502
2. R. Gostanian The next admissible ordinal (p.173) (accessed 2021-03-03)
Community content is available under CC-BY-SA unless otherwise noted.