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 an equivalent formula in prenex normal form, and counting the number of changes of quantifiers:

In the theory ZFC, a formula ${\displaystyle A}$ is called:[1][2]

${\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 is both ${\displaystyle \Sigma _{i}}$ and ${\displaystyle \Pi _{i}}$, 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.

Alternatively, Lévy also used ${\displaystyle \Sigma _{i}^{\mathsf {ZFC}}}$ (resp. ${\displaystyle \Pi _{i}^{\mathsf {ZFC}}}$) for formulae that are provably logically equivalent to one of those in ${\displaystyle \Sigma _{i}}$ (resp. ${\displaystyle \Pi _{i}}$), and Pohlers has defined ${\displaystyle \Delta _{1}}$ in particular semantically, in which a formula is "${\displaystyle \Delta _{1}}$ in a structure ${\displaystyle M}$".[3]

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, 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}}$.

Jech p. 184 Devlin p. 29

• Arithmetic hierarchy
• Absoluteness

• 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.