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 (ZFC), 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 Δ 0 = Σ 0 = Π 0 {\displaystyle \Delta _{0}=\Sigma _{0}=\Pi _{0}} . The next levels are given by finding a formula in prenex normal form that is provably equivalent over ZFC, and counting the number of alternations of quantifiers:p. 184 A formula A {\displaystyle A} is called:
Σ i + 1 {\displaystyle \Sigma _{i+1}} if A {\displaystyle A} is equivalent to ∃ x 1 . . . ∃ x n B {\displaystyle \exists x_{1}...\exists x_{n}B} in ZFC, where B {\displaystyle B} is Π i {\displaystyle \Pi _{i}}
Π i + 1 {\displaystyle \Pi _{i+1}} if A {\displaystyle A} is equivalent to ∀ x 1 . . . ∀ x n B {\displaystyle \forall x_{1}...\forall x_{n}B} in ZFC, where B {\displaystyle B} is Σ i {\displaystyle \Sigma _{i}}
… excerpt ends here. Continue reading the full article.
