Levy hierarchy

The hierarchies \(\Sigma_n\) and \(\Pi_n\) of set theoretic formulae, which are called the Levy hierarchy, are defined inductively on \(n\) in the following wayLevy, Azriel (1965). A hierarchy of formulas in set theory. Mem. Am. Math. Soc. 57. Zbl 0202.30502:
# If \(\phi\) is equivalent to a first order formula in set theory without unbounded quantifiers, then \(\phi\) is \(\Pi_0\) and \(\Sigma_0\).
# If \(\phi\) is equivalent to \(\exists x_0 \exists x_1 \exists x_2...\exists x_k \psi\) for some distinct variable symbols \(x_0, x_1, x_2, \ldots, x_k\) where \(\psi\) is \(\Pi_n\), then \(\phi\) is \(\Sigma_{n+1}\).
# If \(\phi\) is equivalent to \(\forall x_0 \forall x_1 \forall x_2...\forall x_k \psi\) for some distinct variable symbols \(x_0, x_1, x_2, \ldots, x_k\) where \(\psi\) is \(\Sigma_n\), then \(\phi\) is \(\Pi_{n+1}\)
Readers should be careful not to confound Levy hierarchy with arithmetic hierarchy, which is also denoted by \(\Sigma_n\) and \(\Pi_n\).
If a formula is both \(\Sigma_n\) and \(\Pi_n\), it can also be called \(\Delta_n\). Note that \(\Sigma_0\), \(\Pi_0\), and \(\Delta_0\) are all equivalent, and are expressive enough to express many basic set-theoretic conceptsR. Gostanian The next admissible ordinal (p.173) (accessed 2021-03-03).
==Examples==
*Given a variable symbol \(x\), \(\exists x(x=x)\) is a \(\Sigma_1\) formula.
*Given distinct variable symbols \(x,y\), \(\exists(x\in y)(x=x)\) is a \(\Sigma_0\) formula.
*Given a formula \(\chi(x_0,x_1,x_2,x_3,x_4,x_5)\) with exactly six free variables, \(\forall x_0\forall x_1\exists x_2\exists x_3\exists x_4\forall(x_5\in x_2)\chi(x_0,x_1,x_2,x_3,x_4,x_5)\) is a \(\Pi_2\) formula.
==Sources==
ja:レヴィ階層
Category:Set theory