Lévy hierarchy

The Lévy hierarchy classifies formulas of set theory by their alternations of unbounded quantifiers, ignoring bounded quantifiers of the forms $\forall x\in y$ and $\exists x\in y$.

In ZF, $\omega$ is the least nonzero limit ordinal. Ordinality is expressed by a bounded formula in set theory asserting transitivity and strict total membership order, with well-foundedness supplied by the Axiom of foundation. Put $L(x)=\mathrm{Ord}(x)\wedge x\ne \varnothing \wedge \forall y\in x\exists z\in x(y\in z)$. Then $x=\omega$ is equivalent over ZF to $L(x)\wedge \forall y\in x\neg L(y)$, again bounded. Therefore nested transitive models of ZF have the same $\omega$.

A first-order formula is Delta-one modulo ZF if that theory proves it equivalent both to a Sigma-one formula in set theory and to a Pi-one formula in set theory, with the same free variables. Equivalently its assertion and negation each have existential-bounded definitions over ZF. A witness gives upward absoluteness for the first definition; the universal form gives downward absoluteness. Thus the formula has Delta-one absoluteness between nested transitive models of ZF.

A first-order formula is ${\Delta }_1$ modulo ZFC if that theory proves it equivalent, with the same free variables, both to a Sigma-one formula in set theory and to a universal unbounded quantifier block with a bounded formula in set theory as matrix. The theory used for provable equivalence matters: modulo ZF is a stronger requirement.

A syntactically ${\Pi }_1$ first-order formula has an unbounded universal quantifier block followed by a bounded formula in set theory. Universal quantification makes it downward absolute between transitive models. A Pi-one formula modulo ZF may have another syntax but has such an equivalent provable in ZF.

A first-order formula is syntactically ${\Sigma }_1$ when it is an unbounded existential quantifier block followed by a bounded formula in set theory. Equivalence provable in a specified theory gives the corresponding modulo-theory notion. Existential witnesses show upward absoluteness between transitive models containing the parameters.

A first-order formula is ${\Pi }_1^{\mathrm{ZF}}$ if ZF proves it equivalent, with the same free variables, to a universal unbounded quantifier block followed by a bounded formula in set theory. Bounded quantifiers do not increase its level in the Lévy hierarchy. Such properties are downward absolute between appropriate transitive models of ZF.

An infinite cardinal number $\kappa$ is a regular cardinal if every function from an ordinal $\delta <\kappa$ into $\kappa$ has bounded range. Write this as $\forall f\forall \delta \in \kappa (\mathrm{Map}(f,\delta ,\kappa )\Rightarrow \exists \beta \in \kappa \forall \xi \in \delta f(\xi )<\beta )$. The graph predicates are bounded formulas in set theory, and cardinalhood is Pi-one definable, so adding infinite cardinalhood yields a Pi-one formula modulo ZF.

An ordinal $\kappa$ is a cardinal number precisely when no smaller ordinal has a bijection onto it. Ordinalhood and the graph predicate for a bijection are bounded formulas in set theory, so $\mathrm{Ord}(\kappa )\wedge \forall f\forall \alpha \in \kappa \neg \mathrm{Bij}(f,\alpha ,\kappa )$ is a Pi-one formula modulo ZF. This does not assert that every set can be assigned an ordinal cardinal without the axiom of choice.

A formula is ${\Delta }_1^{\mathrm{ZF}}$ when ZF proves it equivalent both to a ${\Sigma }_1$ formula and to a ${\Pi }_1$ formula. Such formulas are absolute between suitable transitive models of finite fragments of ZF.