Lévy hierarchy
Introduction 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. 184A formula  is called:*  if  is equivalent to  in ZFC, where  is *  if  is equivalent to  in ZFC, where  is * If a formula has both a  form and a  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  (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  in particular semantically, in which a formula is " in a structure ".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}p. 14* x ⊆ y * ''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 countable 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 Godel's L* ''R'' is a relation with domain/range/field ''a'' p. 14===Δ1-formulas and concepts===* ''x'' is a well-founded relation on ''y'' * ''x'' is finite p.15* Ordinal addition and multiplication and exponentiation * The rank (with respect to Gödel's constructible universe) of a set p. 61* The transitive closure of a set.===Σ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* rank(''x'') p. 29* 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''===Δ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 choice* The generalized continuum hypothesis* The axiom of constructibility: ''V'' = ''L''===Δ3-formulas and concepts======Σ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===