Contents

Lévy hierarchy

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 ${\displaystyle \Delta _{0}=\Sigma _{0}=\Pi _{0}}$.^[1] 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:^[2]p. 184

A formula ${\displaystyle A}$ is called:^[1][3]

• ${\displaystyle \Sigma _{i+1}}$if${\displaystyle A}$ is equivalent to ${\displaystyle \exists x_{1}...\exists x_{n}B}$ in ZFC, where ${\displaystyle B}$is${\displaystyle \Pi _{i}}$
• ${\displaystyle \Pi _{i+1}}$if${\displaystyle A}$ is equivalent to ${\displaystyle \forall x_{1}...\forall x_{n}B}$ in ZFC, where ${\displaystyle B}$is${\displaystyle \Sigma _{i}}$
• If a formula has both a ${\displaystyle \Sigma _{i}}$ form and a ${\displaystyle \Pi _{i}}$ form, it is called ${\displaystyle \Delta _{i}}$.

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.^{[citation needed]}

Lévy's original notation was ${\displaystyle \Sigma _{i}^{\mathsf {ZFC}}}$ (resp. ${\displaystyle \Pi _{i}^{\mathsf {ZFC}}}$) due to the provable logical equivalence,^[4] strictly speaking the above levels should be referred to as ${\displaystyle \Sigma _{i}^{\mathsf {ZFC}}}$ (resp. ${\displaystyle \Pi _{i}^{\mathsf {ZFC}}}$) to specify the theory in which the equivalence is carried out, however it is usually clear from context.^{[5]pp. 441–442} Pohlers has defined ${\displaystyle \Delta _{1}}$ in particular semantically, in which a formula is "${\displaystyle \Delta _{1}}$ in a structure ${\displaystyle M}$".^[6]

The Lévy hierarchy is sometimes defined for other theories S. In this case ${\displaystyle \Sigma _{i}}$ and ${\displaystyle \Pi _{i}}$ by themselves refer only to formulas that start with a sequence of quantifiers with at most i−1 alternations,^{[citation needed]} and ${\displaystyle \Sigma _{i}^{S}}$ and ${\displaystyle \Pi _{i}^{S}}$ refer to formulas equivalent to ${\displaystyle \Sigma _{i}}$ and ${\displaystyle \Pi _{i}}$ formulas in the language of the theory S. So strictly speaking the levels ${\displaystyle \Sigma _{i}}$ and ${\displaystyle \Pi _{i}}$ of the Lévy hierarchy for ZFC defined above should be denoted by ${\displaystyle \Sigma _{i}^{ZFC}}$ and ${\displaystyle \Pi _{i}^{ZFC}}$.

Examples[edit]

Σ₀=Π₀=Δ₀ formulas and concepts[edit]

• x = {y, z}^[7]p. 14
• x ⊆ y ^[8]
• x is a transitive set^[8]
• x is an ordinal, x is a limit ordinal, x is a successor ordinal^[8]
• x is a finite ordinal^[8]
• The first countable ordinal ω ^[8]
• x is an ordered pair. The first entry of the ordered pair xisa. The second entry of the ordered pair xisb ^[7]p. 14
• f is a function. x is the domain/range of the function f. y is the value of fonx ^[7]p. 14
• The Cartesian product of two sets.
• x is the union of y ^[8]
• x is a member of the αth level of Godel's L^[9]
• R is a relation with domain/range/field a ^[7]p. 14

Δ₁-formulas and concepts[edit]

• x is a well-founded relationony ^[10]
• x is finite ^[4]p.15
• Ordinal addition and multiplication and exponentiation ^[11]
• The rank (with respect to Gödel's constructible universe) of a set ^[7]p. 61
• The transitive closure of a set.

Σ₁-formulas and concepts[edit]

• xiscountable.
• |X|≤|Y|, |X|=|Y|.
• x is constructible.
• g is the restriction of the function ftoa ^[7]p. 23
• g is the image of fona ^[7]p. 23
• b is the successor ordinal of a ^[7]p. 23
• rank(x) ^[7]p. 29
• The Mostowski collapseof${\displaystyle (x,\in )}$ ^[7]p. 29

Π₁-formulas and concepts[edit]

• x is a cardinal
• x is a regular cardinal
• x is a limit cardinal
• x is an inaccessible cardinal.
• x is the powersetofy

Δ₂-formulas and concepts[edit]

• κisγ-supercompact

Σ₂-formulas and concepts[edit]

• the continuum hypothesis
• there exists an inaccessible cardinal
• there exists a measurable cardinal
• κ is an n-huge cardinal

Π₂-formulas and concepts[edit]

• The axiom of choice^[12]
• The generalized continuum hypothesis^[12]
• The axiom of constructibility: V = L^[12]

Δ₃-formulas and concepts[edit]

Σ₃-formulas and concepts[edit]

• there exists a supercompact cardinal

Π₃-formulas and concepts[edit]

• κ is an extendible cardinal

Σ₄-formulas and concepts[edit]

• there exists an extendible cardinal

Properties[edit]

Let ${\displaystyle n\geq 1}$. The Lévy hierarchy has the following properties:^[2]p. 184

• If${\displaystyle \phi }$is${\displaystyle \Sigma _{n}}$, then ${\displaystyle \lnot \phi }$is${\displaystyle \Pi _{n}}$.
• If${\displaystyle \phi }$is${\displaystyle \Pi _{n}}$, then ${\displaystyle \lnot \phi }$is${\displaystyle \Sigma _{n}}$.
• If${\displaystyle \phi }$ and ${\displaystyle \psi }$ are ${\displaystyle \Sigma _{n}}$, then ${\displaystyle \exists x\phi }$, ${\displaystyle \phi \land \psi }$, ${\displaystyle \phi \lor \psi }$, ${\displaystyle \exists (x\in z)\phi }$, and ${\displaystyle \forall (x\in z)\phi }$ are all ${\displaystyle \Sigma _{n}}$.
• If${\displaystyle \phi }$ and ${\displaystyle \psi }$ are ${\displaystyle \Pi _{n}}$, then ${\displaystyle \forall x\phi }$, ${\displaystyle \phi \land \psi }$, ${\displaystyle \phi \lor \psi }$, ${\displaystyle \exists (x\in z)\phi }$, and ${\displaystyle \forall (x\in z)\phi }$ are all ${\displaystyle \Pi _{n}}$.
• If${\displaystyle \phi }$is${\displaystyle \Sigma _{n}}$ and ${\displaystyle \psi }$is${\displaystyle \Pi _{n}}$, then ${\displaystyle \phi \implies \psi }$is${\displaystyle \Pi _{n}}$.
• If${\displaystyle \phi }$is${\displaystyle \Pi _{n}}$ and ${\displaystyle \psi }$is${\displaystyle \Sigma _{n}}$, then ${\displaystyle \phi \implies \psi }$is${\displaystyle \Sigma _{n}}$.

Devlin p. 29

See also[edit]

• Arithmetic hierarchy
• Absoluteness

References[edit]

• Devlin, Keith J. (1984). Constructibility. Perspectives in Mathematical Logic. Berlin: Springer-Verlag. pp. 27–30. Zbl 0542.03029.
• Jech, Thomas (2003). Set Theory. Springer Monographs in Mathematics (Third Millennium ed.). Berlin, New York: Springer-Verlag. p. 183. ISBN 978-3-540-44085-7. Zbl 1007.03002.
• Kanamori, Akihiro (2006). "Levy and set theory". Annals of Pure and Applied Logic. 140 (1–3): 233–252. doi:10.1016/j.apal.2005.09.009. Zbl 1089.03004.
• Levy, Azriel (1965). A hierarchy of formulas in set theory. Mem. Am. Math. Soc. Vol. 57. Zbl 0202.30502.

Citations[edit]