# nLab Lévy hierarchy

foundations

## Foundational axioms

foundational axiom

# The Lévy hierarchy

## Idea

In logic, model theory, and set theory, the Lévy hierarchy is a stratification of formulas?, definable sets, and (definable) classes according to the complexity of the unbounded quantifiers.

## Definition

###### Definition

We define classes of formulas $\Sigma_n$, $\Pi_n$, and $\Delta_n$ by induction on $n$.

• A formula is $\Sigma_0$ iff it is $\Pi_0$ iff it is $\Delta_0$, by definition if it is equivalent to a formula all of whose quantifiers are bounded, i.e. of the form $\forall x\in A$ or $\exists x\in A$.

• A formula is $\Sigma_{n+1}$ if it is equivalent to one of the form $\exists \vec{x}. \phi$, where $\vec{x}$ is a list of variables and $\phi$ is $\Pi_n$.

• A formula is $\Pi_{n+1}$ if it is equivalent to one of the form $\forall \vec{x}. \phi$, where $\vec{x}$ is a list of variables and $\phi$ is $\Sigma_n$.

• A formula is $\Delta_n$ if it is both $\Sigma_n$ and $\Pi_n$.

A class is given one of these labels if it can be defined by a formula which has that label.

###### Remark

The notation “$\Sigma$” and “$\Pi$” can be explained by the fact that the existential quantifier is related to a dependent sum, while the universal quantifier is related to the dependent product.

###### Remark

These definitions are most useful in classical mathematics, in which every formula is equivalent to one all of whose unbounded quantifiers are in the front, that is, a formula in prenex normal form?, so that every formula belongs to some $\Sigma_n$ or $\Pi_n$.

Revised on September 25, 2012 05:35:38 by Mike Shulman (192.16.204.218)