Lévy hierarchy


In set theory and mathematical logic, the Lévy hierarchy, introduced by Azriel Lévy in 1965, is a hierarchy of formulas in the formal language of the Zermelo–Fraenkel set theory, which is typically called just the language of set theory. This is analogous to the arithmetical hierarchy which provides the classifications but for sentences of the language of arithmetic.

Definitions

In the language of set theory, atomic formulas are of the form x = y or x ∈ y, standing for equality and respectively set membership predicates.
The first level of the Levy hierarchy is defined as containing only formulas with no unbounded quantifiers, and is denoted by. The next levels are given by finding an equivalent formula in Prenex normal form, and counting the number of changes of quantifiers:
In the theory ZFC, a formula is called:
if is equivalent to in ZFC, where is
if is equivalent to in ZFC, where is
If a formula is both and, it is called. As a formula might have several different equivalent formulas in Prenex normal form, it might belong to several different levels of the hierarchy. In this case, the lowest possible level is the level of the formula.
The Lévy hierarchy is sometimes defined for other theories S. In this case and by themselves refer only to formulas that start with a sequence of quantifiers with at most i−1 alternations, and and refer to formulas equivalent to and formulas in the theory S. So strictly speaking the levels and of the Lévy hierarchy for ZFC defined above should be denoted by and .

Examples

Σ0=Π0=Δ0 formulas and concepts

Σ3-formulas and concepts

Jech p. 184
Devlin p. 29