Lévy hierarchy

In set theory and mathematical logic, the Lévy hierarchy, introduced by Azriel Lévy in 1965, is a hierarchy of formulas in the formal language of the Zermelo–Fraenkel set theory, which is typically called just the language of set theory. This is analogous to the arithmetical hierarchy which provides the classifications but for sentences of the language of arithmetic.

Definitions

In the language of set theory, atomic formulas are of the form x = y or x ∈ y, standing for equality and respectively set membership predicates.

The first level of the Levy hierarchy is defined as containing only formulas with no unbounded quantifiers, and is denoted by $\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 $A$ is called:^[1]

$\Sigma _{i+1}$ if $A$ is equivalent to $\exists x_{1}...\exists x_{n}B$ in ZFC, where $B$ is $\Pi _{i}$

$\Pi _{i+1}$ if $A$ is equivalent to $\forall x_{1}...\forall x_{n}B$ in ZFC, where $B$ is $\Sigma _{i}$

If a formula is both $\Sigma _{i}$ and $\Pi _{i}$ , it is called $\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.

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

Examples

Σ₀=Π₀=Δ₀ formulas and concepts

x = {y, z}
x ⊆ y
x is a transitive set
x is an ordinal, x is a limit ordinal, x is a successor ordinal
x is a finite ordinal
The first countable ordinal ω.
f is a function. The range and domain of a function. The value of a function on a set.
The product of two sets.
The union of a set.

Δ₁-formulas and concepts

x is a well-founded relation on y
x is finite
Ordinal addition and multiplication and exponentiation
The rank of a set
The transitive closure of a set

Σ₁-formulas and concepts

x is countable
|X|≤|Y|, |X|=|Y|
x is constructible

Π₁-formulas and concepts

x is a cardinal
x is a regular cardinal
x is a limit cardinal
x is an inaccessible cardinal.
x is the powerset of y

Δ₂-formulas and concepts

κ is γ-supercompact

Σ₂-formulas and concepts

the Continuum Hypothesis
there exists an inaccessible cardinal
there exists a measurable cardinal
κ is an n-huge cardinal

Π₂-formulas and concepts

The axiom of constructibility: V = L

Δ₃-formulas and concepts

Properties

Jech p. 184 Devlin p. 29

References

1 2 Walicki, Michal (2012). Mathematical Logic, p. 225. World Scientific Publishing Co. Pte. Ltd. ISBN 9789814343862

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" (PDF). Annals of Pure and Applied Logic. 140: 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. 57. Zbl 0202.30502.

This article is issued from Wikipedia - version of the 4/20/2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Lévy hierarchy

Definitions

Examples

Σ0=Π0=Δ0 formulas and concepts

Δ1-formulas and concepts

Σ1-formulas and concepts

Π1-formulas and concepts

Δ2-formulas and concepts

Σ2-formulas and concepts

Π2-formulas and concepts

Δ3-formulas and concepts

Σ3-formulas and concepts

Π3-formulas and concepts

Σ4-formulas and concepts