Lévy hierarchy#Definitions

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 $\backslash Delta\_0=\backslash Sigma\_0=\backslash Pi\_0$.Walicki, Michal (2012). Mathematical Logic, p. 225. World Scientific Publishing Co. Pte. Ltd. {{isbn|9789814343862}} The next levels are given by finding a formula in prenex normal form which is provably equivalent over ZFC, and counting the number of changes of quantifiers:T. Jech, 'Set Theory: The Third Millennium Edition, revised and expanded'. Springer Monographs in Mathematics (2006). ISBN 3-540-44085-2.^p. 184

A formula $A$ is called:J. Baeten, [https://ir.cwi.nl/pub/12723/12723D.pdf Filters and ultrafilters over definable subsets over admissible ordinals] (1986). p.10

• $\backslash Sigma\_\{i+1\}$ if $A$ is equivalent to $\backslash exists\; x\_1\; ...\; \backslash exists\; x\_n\; B$ in ZFC, where $B$ is $\backslash Pi\_i$
• $\backslash Pi\_\{i+1\}$ if $A$ is equivalent to $\backslash forall\; x\_1\; ...\; \backslash forall\; x\_n\; B$ in ZFC, where $B$ is $\backslash Sigma\_i$
• If a formula has both a $\backslash Sigma\_i$ form and a $\backslash Pi\_i$ form, it is called $\backslash 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.{{citation needed|date=July 2023}}

Lévy's original notation was $\backslash Sigma\_i^\backslash mathsf\{ZFC\}$ (resp. $\backslash Pi\_i^\backslash mathsf\{ZFC\}$) due to the provable logical equivalence,A. Lévy, 'A hierarchy of formulas in set theory' (1965), second edition strictly speaking the above levels should be referred to as $\backslash Sigma\_i^\backslash mathsf\{ZFC\}$ (resp. $\backslash Pi\_i^\backslash mathsf\{ZFC\}$) to specify the theory in which the equivalence is carried out, however it is usually clear from context.K. Hauser, "Indescribable cardinals and elementary embeddings". Journal of Symbolic Logic vol. 56, iss. 2 (1991), pp.439--457.^{pp. 441–442} Pohlers has defined $\backslash Delta\_1$ in particular semantically, in which a formula is "$\backslash Delta\_1$ in a structure $M$".W. Pohlers, Proof Theory: The First Step into Impredicativity (2009) (p.245)

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

• x = {y, z}Jon Barwise, Admissible Sets and Structures. Perspectives in Mathematical Logic (1975)^p. 14
• x ⊆ y D. Monk 2011, [https://web.archive.org/web/20111206123643/http://euclid.colorado.edu/~monkd/m6730/gradsets14.pdf Graduate Set Theory] (pp.168--170). Archived 2011-12-06
• 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 infinite ordinal ω
• x is an ordered pair. The first entry of the ordered pair x is a. The second entry of the ordered pair x is b ^p. 14
• f is a function. x is the domain/range of the function f. y is the value of f on x ^p. 14
• The Cartesian product of two sets.
• x is the union of y
• x is a member of the αth level of Godel's LW. A. R. Weiss, [https://www.math.toronto.edu/weiss/Set_Theory.pdf An Introduction to Set Theory] (chapter 13). Accessed 2022-12-01
• R is a relation with domain/range/field a ^p. 14
• X is Hausdorff.

• x is a well-founded relation on y K. J. Williams, [https://arxiv.org/pdf/1709.03955.pdf Minimum models of second-order set theories] (2019, p.4). Accessed 2022 July 25.
• x is finite ^p.15
• Ordinal addition and multiplication and exponentiation F. R. Drake, Set Theory: An Introduction to Large Cardinals (p.83). Accessed 1 July 2022.
• The rank (with respect to Gödel's constructible universe) of a set ^p. 61
• The transitive closure of a set.
• The specifiability relation Sp(A) for a set A. F. R. Drake, Set Theory: An Introduction to Large Cardinals (p.127). Accessed 4 October 2024.

• x is countable.
• |X|≤|Y|, |X|=|Y|.
• x is constructible.
• g is the restriction of the function f to a ^p. 23
• g is the image of f on a ^p. 23
• b is the successor ordinal of a ^p. 23
• rank(x) ^p. 29
• The Mostowski collapse of $(x,\backslash in)$ ^p. 29

• 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

• κ is γ-supercompact

• the continuum hypothesis
• there exists an inaccessible cardinal
• there exists a measurable cardinal
• κ is an n-huge cardinal

• The axiom of choiceAzriel Lévy, "On the logical complexity of several axioms of set theory" (1971). Appearing in Axiomatic Set Theory: Proceedings of Symposia in Pure Mathematics, vol. 13 part 1, pp.219--230
• The generalized continuum hypothesis
• The axiom of constructibility: V = L

• there exists a supercompact cardinal

• κ is an extendible cardinal

• there exists an extendible cardinal

Let $n\backslash geq\; 1$. The Lévy hierarchy has the following properties:^p. 184

• If $\backslash phi$ is $\backslash Sigma\_n$, then $\backslash lnot\backslash phi$ is $\backslash Pi\_n$.
• If $\backslash phi$ is $\backslash Pi\_n$, then $\backslash lnot\backslash phi$ is $\backslash Sigma\_n$.
• If $\backslash phi$ and $\backslash psi$ are $\backslash Sigma\_n$, then $\backslash exists\; x\backslash phi$, $\backslash phi\backslash land\backslash psi$, $\backslash phi\backslash lor\backslash psi$, $\backslash exists(x\backslash in\; z)\backslash phi$, and $\backslash forall(x\backslash in\; z)\backslash phi$ are all $\backslash Sigma\_n$.
• If $\backslash phi$ and $\backslash psi$ are $\backslash Pi\_n$, then $\backslash forall\; x\backslash phi$, $\backslash phi\backslash land\backslash psi$, $\backslash phi\backslash lor\backslash psi$, $\backslash exists(x\backslash in\; z)\backslash phi$, and $\backslash forall(x\backslash in\; z)\backslash phi$ are all $\backslash Pi\_n$.
• If $\backslash phi$ is $\backslash Sigma\_n$ and $\backslash psi$ is $\backslash Pi\_n$, then $\backslash phi\backslash implies\backslash psi$ is $\backslash Pi\_n$.
• If $\backslash phi$ is $\backslash Pi\_n$ and $\backslash psi$ is $\backslash Sigma\_n$, then $\backslash phi\backslash implies\backslash psi$ is $\backslash Sigma\_n$.

Devlin p. 29

• Arithmetic hierarchy
• Absoluteness

• {{cite book | last=Devlin | first=Keith J. | authorlink=Keith Devlin | title=Constructibility | url=https://archive.org/details/constructibility00devl_407 | url-access=limited | zbl=0542.03029 | series=Perspectives in Mathematical Logic | location= Berlin | publisher=Springer-Verlag | year=1984 | pages=[https://archive.org/details/constructibility00devl_407/page/n40 27]–30 }}
• {{cite book | last1=Jech | first1=Thomas | author1-link=Thomas Jech | title=Set Theory | edition=Third Millennium | publisher=Springer-Verlag | location=Berlin, New York | series=Springer Monographs in Mathematics | isbn=978-3-540-44085-7 | year=2003 | zbl=1007.03002 | page=183 }}
• {{cite journal | first=Akihiro | last=Kanamori | authorlink=Akihiro Kanamori | title=Levy and set theory | journal=Annals of Pure and Applied Logic | volume=140 | year=2006 | issue=1–3 | pages=233–252 | zbl=1089.03004 | doi=10.1016/j.apal.2005.09.009 | doi-access=free }}
• {{cite book | last=Levy | first=Azriel | authorlink=Azriel Lévy | title=A hierarchy of formulas in set theory | zbl=0202.30502 | series=Mem. Am. Math. Soc. | volume=57 | year=1965 }}

{{Reflist}}

{{DEFAULTSORT:Levy hierarchy}}

Category:Mathematical logic

Category:Set theory

Category:Mathematical logic hierarchies