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 .Walicki, Michal (2012). Mathematical Logic, p. 225. World Scientific Publishing Co. Pte. Ltd. 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:T. Jech, 'Set Theory: The Third Millennium Edition, revised and expanded'. Springer Monographs in Mathematics (2006). ISBN 3-540-44085-2.p. 184
A formula is called:J. Baeten, Filters and ultrafilters over definable subsets over admissible ordinals (1986). p.10
if is equivalent to in ZFC, where is if is equivalent to in ZFC, where is If a formula is both and form, 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.
Lévy's original notation was (respectively ) due to the provable logical equivalence,A. Lévy, 'A hierarchy of formulas in set theory' (1965), second edition strictly speaking the above levels should be referred to as (respectively ) to specify the theory in which the equivalence is carried out, however it is usually clear from context.K. Hauser, "Indescribable cardinals and elementary embeddings". Journal of Symbolic Logic vol. 56, iss. 2 (1991), pp.439--457.pp. 441–442 Pohlers has defined in particular semantically, in which a formula is " in a structure ".W. Pohlers, Proof Theory: The First Step into Impredicativity (2009) (p.245)
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 language of 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 x = {y, z}Jon Barwise, Admissible Sets and Structures. Perspectives in Mathematical Logic (1975)p. 14 x ⊆ y D. Monk 2011, Graduate Set Theory (pp.168--170). Archived 2011-12-06 x is a transitive set x is an ordinal, x is a limit ordinal, x is a successor ordinal x is a finite ordinal The first infinite ordinal ω x is an ordered pair. The first entry of the ordered pair x is a. The second entry of the ordered pair x is b p. 14 f is a function. x is the domain/range of the function f. y is the value of f on x p. 14 The Cartesian product of two sets. x is the union of y x is a member of the αth level of Gödel's LW. A. R. Weiss, An Introduction to Set Theory (chapter 13). Accessed 2022-12-01 R is a relation with domain/range/field a p. 14 X is Hausdorff.
Δ1-formulas and concepts
x is a well-founded relation on y K. J. Williams, Minimum models of second-order set theories (2019, p.4). Accessed 2022 July 25. x is finite p.15 Ordinal addition and multiplication and exponentiation F. R. Drake, Set Theory: An Introduction to Large Cardinals (p.83). Accessed 1 July 2022. x has rank α Akihiro Kanamori, The Higher Infinite: Large Cardinals in Set Theory from Their Beginnings (p.5). Springer (2009) The rank (with respect to Gödel's constructible universe) of a set p. 61 The transitive closure of a set. The specifiability relation Sp(A) for a set A. F. R. Drake, Set Theory: An Introduction to Large Cardinals (p.127). Accessed 4 October 2024.
Σ1-formulas and concepts
x is countable. |X|≤|Y|, |X|=|Y|. x is constructible. g is the restriction of the function f to a p. 23 g is the image of f on a p. 23 b is the successor ordinal of a p. 23 The Mostowski collapse of p. 29
Π1-formulas and concepts
x is a cardinal x is a regular cardinal x is a limit cardinal x is an inaccessible cardinal. x is the powerset of y x is
Δ2-formulas and concepts
κ is γ-supercompact
Σ2-formulas and concepts
the continuum hypothesis there exists an inaccessible cardinal there exists a measurable cardinal κ is an n-huge cardinal
Π2-formulas and concepts The axiom of choiceAzriel Lévy, "On the logical complexity of several axioms of set theory" (1971). Appearing in Axiomatic Set Theory: Proceedings of Symposia in Pure Mathematics, vol. 13 part 1, pp.219--230 The generalized continuum hypothesis The axiom of constructibility: V = L
Δ3-formulas and concepts
κ is an measurable cardinal
Σ3-formulas and concepts
there exists a supercompact cardinal
Π3-formulas and concepts
κ is an extendible cardinal
Σ4-formulas and concepts
there exists an extendible cardinal
Properties Let . The Lévy hierarchy has the following properties:p. 184 If is , then is . If is , then is . If and are , then , , , , and are all . If and are , then , , , , and are all . If is and is , then is . If is and is , then is .
Devlin p. 29
See also Arithmetic hierarchy Absoluteness
References
Citations