The hierarchies \(\Sigma_n\) and \(\Pi_n\), which are called the Levy hierarchy, are defined inductively on \(n\) in the following way[1]:

  1. If \(\phi\) is equivalent to a first order formula in set theory without unbounded quantifiers, then \(\phi\) is \(\Pi_0\) and \(\Sigma_0\)
  2. If \(\phi\) is equivalent to \(\exists n_0 \exists n_1 \exists n_2...\exists n_k \psi\) for some natural numbers \(n_0, n_1, n_2...n_k\) where \(\psi\) is \(\Pi_n\), then \(\phi\) is \(\Sigma_{n+1}\)
  3. If \(\phi\) is equivalent to \(\forall n_0 \forall n_1 \forall n_2...\forall n_k \psi\) for some natural numbers \(n_0, n_1, n_2...n_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 concepts[2].

Examples

  • \(\exists x(x=x)\) is a \(\Sigma_1\) formula.
  • Given a free variable \(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 \(\Pi_2\).
  • Work in an arithmetic such as Peano arithmetic. Given a natural number \(n\), the property "\(n\) is odd" is \(\Delta_1\), e.g. the formulae \(\exists k(n=k+k+1)\) (which is \(\Sigma_1\)) and \(\forall k(k+k\neq n)\) (which is \(\Pi_1\)) are logically equivalent.

Sources

  1. Levy, Azriel (1965). A hierarchy of formulas in set theory. Mem. Am. Math. Soc. 57. Zbl 0202.30502
  2. R. Gostanian The next admissible ordinal (p.173) (accessed 2021-03-03)
Community content is available under CC-BY-SA unless otherwise noted.