nLab
Lévy hierarchy

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 Σ n\Sigma_n, Π n\Pi_n, and Δ n\Delta_n by induction on nn.

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

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

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

  • A formula is Δ n\Delta_n if it is both Σ n\Sigma_n and Π n\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 Σ n\Sigma_n or Π n\Pi_n.

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