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 a similar classification 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 set membership predicates, respectively. The first level of the Lévy hierarchy is defined as containing only formulas with no unbounded quantifiers and is denoted by. The next levels are given by finding a formula in prenex normal form which is provably equivalent over ZFC, and counting the number of changes of quantifiers: p. 184 A formula A 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. Lévy's original notation was (resp. ) due to the provable logical equivalence, strictly speaking the above levels should be referred to as (resp. ) to specify the theory in which the equivalence is carried out, however it is usually clear from context. pp. 441–442 Pohlers has defined \Delta_1 in particular semantically, in which a formula is "\Delta_1 in a structure M". The Lévy hierarchy is sometimes defined for other theories S. In this case \Sigma_i and \Pi_i by themselves refer only to formulas that start with a sequence of quantifiers with at most i−1 alternations, and \Sigma_i^S and \Pi_i^S refer to formulas equivalent to \Sigma_i and \Pi_i formulas in the language of the theory S. So strictly speaking the levels \Sigma_i and \Pi_i of the Lévy hierarchy for ZFC defined above should be denoted by and \Pi^{ZFC}_i.

Examples

Σ0=Π0=Δ0 formulas and concepts

Δ1-formulas and concepts

Σ1-formulas and concepts

Π1-formulas and concepts

Δ2-formulas and concepts

Σ2-formulas and concepts

Π2-formulas and concepts

Δ3-formulas and concepts

Σ3-formulas and concepts

Π3-formulas and concepts

Σ4-formulas and concepts

Properties

Let n\geq 1. The Lévy hierarchy has the following properties: p. 184 Devlin p. 29

Citations