Levy hierarchy

The term of Levy hierarchy are in mathematical logic in particular, set theory , a set of hierarchies of formulas and formal languages subsumed. Set theory formulas are classified in a certain sense according to their complexity. Formal languages ​​are arranged in the hierarchy according to the complexity of the formulas that describe them. Applied to these, the Levy hierarchy extends far beyond the arithmetic and analytic hierarchies . The consideration of lower levels of the hierarchy allows statements about the transferability of the validity of statements between models of set theory.

The hierarchy was introduced by Azriel Levy in 1965 .

definition

A formula in the language of set theory (i.e. first-order predicate logic with equality and the two-place relation ) is called -, - or -formula if all occurring quantifications are restricted, i.e. H. for a formula and variables of the form (abbreviated ) or (abbreviated ). Now one defines inductively: A formula is a formula of the form for a formula and a formula is a formula of the form for a formula . Every - or - formula is also a - formula, that is, a formula in which the maximum nesting depth of unlimited quantifiers is. The sets of all such formulas are given . or be the set of all formulas that result as Boolean combinations of - or - formulas. ${\displaystyle \in }$ ${\displaystyle \Delta _{0}}$ ${\displaystyle \Sigma _{0}}$ ${\displaystyle \Pi _{0}}$ ${\displaystyle \phi }$ ${\displaystyle x,y}$ ${\displaystyle \forall x(x\in y\rightarrow \phi )}$ ${\displaystyle \forall x\in y\phi }$ ${\displaystyle \exists x(x\in y\wedge \phi )}$ ${\displaystyle \exists x\in y\phi }$ ${\displaystyle \Sigma _{i+1}}$ ${\displaystyle \exists x\phi }$ ${\displaystyle \Pi _{i}}$ ${\displaystyle \phi }$ ${\displaystyle \Pi _{i+1}}$ ${\displaystyle \forall x\psi }$ ${\displaystyle \Sigma _{i}}$ ${\displaystyle \psi }$ ${\displaystyle \Sigma _{i}}$ ${\displaystyle \Pi _{i}}$ ${\displaystyle \Lambda _{i}}$ ${\displaystyle i}$ ${\displaystyle \Sigma _{i},\Pi _{i},\Lambda _{i}}$ ${\displaystyle {\mathfrak {B}}(\Sigma _{i})}$ ${\displaystyle {\mathfrak {B}}(\Pi _{i})}$ ${\displaystyle \Sigma _{i}}$ ${\displaystyle \Pi _{i}}$

Now be a theory in the language of set theory (such as the Zermelo-Fraenkel set theory ). is then defined as the set of all formulas for which the equivalence to a formula in can be proven, i.e. H. , where the free variables are in. is analogous to and by defined. in the following always contain at least the axioms of classical first-order predicate logic. Every formula in the language of set theory is for an in , since it can be brought into prenex normal form . ${\displaystyle T}$ ${\displaystyle ZF}$ ${\displaystyle \Sigma _{i}^{T}}$ ${\displaystyle \phi }$ ${\displaystyle \Sigma _{i}}$ ${\displaystyle \psi }$ ${\displaystyle T}$ ${\displaystyle T\vdash \forall x_{1}\ldots \forall x_{n}(\phi \leftrightarrow \psi )}$ ${\displaystyle x_{1},\ldots ,x_{n}}$ ${\displaystyle \phi }$ ${\displaystyle \Pi _{i}^{T}}$ ${\displaystyle \Delta _{i}^{T}}$ ${\displaystyle \Sigma _{i}^{T}\cap \Pi _{i}^{T}}$ ${\displaystyle T}$ ${\displaystyle i}$ ${\displaystyle \Sigma _{i}^{T}}$

As classes of formal languages , the subsets of natural numbers (more generally relations are also possible) can be distinguished, which - or - are definable, i.e. H. for which a - or - formula exists such that . From further properties it follows that the sets in sufficiently strong axiom systems can actually be defined in terms of object language , without reference to models or provability (see below). ${\displaystyle X}$ ${\displaystyle \Sigma _{i}}$ ${\displaystyle \Pi _{i}}$ ${\displaystyle \Sigma _{i}}$ ${\displaystyle \Pi _{i}}$ ${\displaystyle \phi (x)}$ ${\displaystyle \forall x\in X(x\in Y\leftrightarrow \phi (x))}$ ${\displaystyle \Sigma _{i},\Pi _{i},\Delta _{i}}$

Similar hierarchies can also be created by allowing additional formulas at the level - for example those that contain terms for certain sets such as power sets - and continuing the definition using the closing properties accordingly. ${\displaystyle \Delta _{0}}$

Examples of definability

Here are some examples of the level of the Levy hierarchy at which important set theoretical properties can be defined (assuming ZF).

Δ ₀ -definable

• ${\displaystyle x\subseteq y}$
• Transitivity
• ${\displaystyle x\in \mathbf {On} }$, d. H. is an ordinal number ${\displaystyle x}$
• ${\displaystyle x\in \mathbb {N} }$
• ${\displaystyle x=\mathbb {N} }$
• ${\displaystyle x\cup y=z}$
• ${\displaystyle x\cap y=z}$
• ${\displaystyle x\times y=z}$
• ${\displaystyle x=n}$ for every natural number ${\displaystyle n}$

Δ ₁ -definable

• Addition, multiplication and exponentiation on the natural numbers and more generally on the ordinal numbers
• ${\displaystyle <}$is a well-ordering on ${\displaystyle x}$
• The set of all hereditary finite sets
• ${\displaystyle x}$is the ordinal number and the level in the constructible hierarchy ${\displaystyle y}$ ${\displaystyle L_{x}}$

Σ ₁ - definable

• Finiteness
• Countability
• Equality

Π ₁ - definable

• ${\displaystyle x={\mathcal {P}}(y)}$, d. H. is the power set of . ${\displaystyle x}$ ${\displaystyle y}$
• ${\displaystyle x\in \mathbf {Cn} }$, d. H. is a cardinal number . ${\displaystyle x}$
• Regularity of a cardinal number
• Limes cardinal numbers
• Strong inaccessibility of a cardinal number
• ${\displaystyle x}$is the ordinal number and the level in the Von Neumann hierarchy ${\displaystyle y}$ ${\displaystyle V_{x}}$

Δ ₂ -definable

• Continuum hypothesis
• ${\displaystyle y}$is a - super compact cardinal number ${\displaystyle x}$

Σ ₂ -definable

• There is a strongly unreachable cardinal number
• There is a measurable cardinal number

Π ₂ -definable

• Constructibility axiom ${\displaystyle V=L}$
• Decision problem in the Dependence Logic
• ${\displaystyle x}$ is a super compact cardinal number

Σ ₃ -definable

• There is a super compact cardinal number

Closing properties

If contains the axioms of ZF without the axiom of infinity and without the axiom of substitution , then for is already for and every variable also and for also . This follows from the fact that a block of existential or universal quantifiers can be replaced by a single existential or universal quantifier, whereby the variable used for quantification is then understood as a tuple and operations on tuples can be expressed in. Therefore, quantifier blocks are sometimes already allowed in the definition of the Levy hierarchy. ${\displaystyle T}$ ${\displaystyle i>0}$ ${\displaystyle \varphi \in \Sigma _{i}^{T}}$ ${\displaystyle x}$ ${\displaystyle \exists x\varphi \in \Sigma _{i}^{T}}$ ${\displaystyle \varphi \in \Pi _{i}^{T}}$ ${\displaystyle \forall x\varphi \in \Pi _{i}^{T}}$ ${\displaystyle \Delta _{0}}$

${\displaystyle \Sigma _{i}^{T}}$, , , And are closed under conjunction and disjunction . , and are also closed under negation. The negations of formulas are even formulas and vice versa. If ZF contains without the axiom of infinity, then for each of these five stages are also closed with limited quantification. The idea is the following: is equivalent to , and is for a formula which is in the same level as equivalent to , and then as a function of is understood, the replacement axiom is used for the proof of the latter equivalence. One proceeds in the same way with a restricted existential quantifier and ultimately obtains the closure inductively. The closure under limited quantification results from the use of the substitution axiom and the definability of calculable functions by means of arithmetic for the closure of -, -, -, - and -definable languages ​​under the formation of an original with regard to a recursive function ${\displaystyle \Pi _{i}^{T}}$ ${\displaystyle \Delta _{i}^{T}}$ ${\displaystyle \Lambda _{i}^{T}}$ ${\displaystyle {\mathfrak {B}}(\Sigma _{i})^{T}}$ ${\displaystyle \Delta _{i}^{T}}$ ${\displaystyle \Lambda _{i}^{T}}$ ${\displaystyle {\mathfrak {B}}(\Sigma _{i})^{T}}$ ${\displaystyle \Sigma _{i}^{T}}$ ${\displaystyle \Pi _{i}^{T}}$ ${\displaystyle T}$ ${\displaystyle i}$ ${\displaystyle \forall x\in y\forall z\varphi }$ ${\displaystyle \forall z\forall x\in y\varphi }$ ${\displaystyle \forall x\in y\exists z\varphi }$ ${\displaystyle \varphi ^{\prime }}$ ${\displaystyle \varphi }$ ${\displaystyle \exists z\forall x\in y\varphi ^{\prime }}$ ${\displaystyle z}$ ${\displaystyle x}$ ${\displaystyle i>0}$ ${\displaystyle \Sigma _{i}}$ ${\displaystyle \Pi _{i}}$ ${\displaystyle \Delta _{i}}$ ${\displaystyle \Lambda _{i}}$ ${\displaystyle {\mathfrak {B}}(\Sigma _{i})}$

Absoluteness

A formula of set theory in the free variables is called absolute upwards for a class if it holds, where the relativization of on denotes. Analogously, it is called downwards absolute if applies. A formula is called absolute if it is absolute upwards and downwards. ${\displaystyle \varphi }$ ${\displaystyle n}$ ${\displaystyle x_{1},\ldots ,x_{n}}$ ${\displaystyle M}$ ${\displaystyle \forall x_{1},\ldots ,x_{n}\in M(\varphi ^{M}(x_{1},\ldots ,x_{n})\rightarrow \varphi (x_{1},\ldots ,x_{n}))}$ ${\displaystyle \varphi ^{M}}$ ${\displaystyle \varphi }$ ${\displaystyle M}$ ${\displaystyle \forall x_{1},\ldots ,x_{n}\in M(\varphi (x_{1},\ldots ,x_{n})\rightarrow \varphi ^{M}(x_{1},\ldots ,x_{n}))}$

For every transitive class , every formula is absolute. It follows that every formula is absolute for every transitive class upwards and every formula downwards is absolute. ${\displaystyle M}$ ${\displaystyle \Delta _{0}}$ ${\displaystyle \Sigma _{1}}$ ${\displaystyle \Pi _{1}}$

Let be the transitive closure of , i.e. H. the minimum transitive amount that contains. If an uncountable cardinal number, then every formula is absolute for the set . ${\displaystyle TC(x)}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle \kappa }$ ${\displaystyle {\mathfrak {B}}(\Sigma _{1})}$ ${\displaystyle \left\{x\mid |TC(x)|<\kappa \right\}}$

Definability of truth, separation and completeness

The validity of formulas with a given interpretation of free variables - represented by coding as natural numbers - can be expressed by a formula: Consider the transitive closure of the set of values ​​of the free variables. For the truth of every partial formula of a given formula it is sufficient to consider the relativization to . The relation can now be defined with a formula so that if and only if the formula encoded by is valid under the interpretation of the free variables. is -definable, since it results as a minimal amount with certain closing properties. In fact, even ZF without the axiom of infinity is sufficient to give a definition of the validity of formulas, since it is sufficient to restrict the consideration to the finite set of partial formulas of the given formulas. ${\displaystyle \Delta _{0}}$ ${\displaystyle \Pi _{1}}$ ${\displaystyle T}$ ${\displaystyle T}$ ${\displaystyle \Pi _{1}}$ ${\displaystyle R\subseteq \mathbb {N} \times T^{*}}$ ${\displaystyle (n,x)\in R}$ ${\displaystyle n}$ ${\displaystyle \Delta _{0}}$ ${\displaystyle \phi }$ ${\displaystyle x}$ ${\displaystyle R}$ ${\displaystyle \Pi _{1}}$ ${\displaystyle \Pi _{1}}$ ${\displaystyle \Delta _{0}}$

In fact, even the truth of formulas is definable (the one unlimited universal quantifier simply has to be extracted from the coding). It follows that the validity of formulas is -definable (since the truth of is equivalent to the falsehood of is) and inductively for each the truth of formulas is -definable and that of -formulas -definable. With Tarski's theorem of indefinability , it follows that the Levy hierarchy is actually a hierarchy: If ZF includes without the axiom of infinity and if the fragment of is consistent, then and , otherwise the hierarchy would be stationary, it would be the truth of -formulae then -definierbar what the Undefinierbarkeitssatz contrary, since the amount of -formulae is closed under negation and sufficiently powerful with the included arithmetic, so the Diagonallemma applies. These real inclusion relationships therefore also apply to the corresponding hierarchy of formal languages. The respective definability of the truth also only allows the - or -definability of a formal language to be understood as object-language properties. In ZF (with the axiom of infinity) the separation can even be proven, since the consistency of every fragment from ZF in ZF can be proven. This follows using the truth definition for formulas from the reflection principle as it was published by Levy 1960 and which, assuming the other axioms, is equivalent to the replacement axiom together with the infinity axiom. ${\displaystyle \Pi _{1}}$ ${\displaystyle \Pi _{1}}$ ${\displaystyle \Sigma _{1}}$ ${\displaystyle \Sigma _{1}}$ ${\displaystyle \phi }$ ${\displaystyle \neg \phi }$ ${\displaystyle n>0}$ ${\displaystyle \Pi _{n}}$ ${\displaystyle \Pi _{n}}$ ${\displaystyle \Sigma _{n}}$ ${\displaystyle \Sigma _{n}}$ ${\displaystyle T}$ ${\displaystyle \Delta _{n}}$ ${\displaystyle T}$ ${\displaystyle \Sigma _{n}^{T}\subsetneq \Delta _{n+1}^{T}\subsetneq \Sigma _{n+1}^{T}}$ ${\displaystyle \Pi _{n}^{T}\subsetneq \Delta _{n+1}^{T}\subsetneq \Pi _{n+1}^{T}}$ ${\displaystyle n}$ ${\displaystyle \Delta _{n}}$ ${\displaystyle \Delta _{n}}$ ${\displaystyle \Delta _{n}}$ ${\displaystyle \Pi _{n}}$ ${\displaystyle \Sigma _{n}}$ ${\displaystyle \Delta _{n}}$ ${\displaystyle \Sigma _{n}}$

It can be shown that for . ${\displaystyle {\mathfrak {B}}(\Sigma _{i})^{ZF}\subsetneq \Lambda _{i}^{ZF}}$ ${\displaystyle i>0}$

A - or quantity of natural numbers is called - or -complete if for any other - or quantity by a computable function to be reduced is so true. Obviously, the sets of codes of true - or - sentences for their respective class are complete, must simply be chosen in such a way that an appropriate substitution is made. Due to the closeness of calculable archetypes, complete sets are not definable and vice versa. ${\displaystyle \Pi _{n}}$ ${\displaystyle \Sigma _{n}}$ ${\displaystyle C}$ ${\displaystyle \Pi _{n}}$ ${\displaystyle \Sigma _{n}}$ ${\displaystyle \Pi _{n}}$ ${\displaystyle \Sigma _{n}}$ ${\displaystyle A\subseteq \mathbb {N} }$ ${\displaystyle f\colon \mathbb {N} \to \mathbb {N} }$ ${\displaystyle C}$ ${\displaystyle x\in A\Leftrightarrow f(x)\in C}$ ${\displaystyle \Pi _{n}}$ ${\displaystyle \Sigma _{n}}$ ${\displaystyle f}$ ${\displaystyle \Pi _{n}}$ ${\displaystyle \Sigma _{n}}$

Relation to arithmetic

ZF is assumed in this section. From the definability of natural numbers and the arithmetic operations it follows that every formula in first-order arithmetic can already be expressed as a formula. The sentence ${\displaystyle \Delta _{1}}$ ${\displaystyle \Delta _{1}}$ ${\displaystyle \Sigma _{2}^{0}}$

${\displaystyle \exists x\forall y2\cdot y=x}$

in the sentence ${\displaystyle \Pi _{1}}$

${\displaystyle \forall \mathbb {N} \left(\mathbb {N} {\text{ ist die Menge der nat. Zahlen }}\right)\rightarrow \exists x\in \mathbb {N} \forall y\in \mathbb {N} 2\cdot y=x}$

translate, a sentence is obtained accordingly through negations. The definable languages therefore already contain all languages, i.e. the entire arithmetic hierarchy . In can even translate any formulas of arithmetic of any level , in particular the entire analytical hierarchy is included. The sentence ${\displaystyle \Sigma _{1}}$ ${\displaystyle \Delta _{1}}$ ${\displaystyle \Sigma _{i}^{0}}$ ${\displaystyle \Delta _{2}}$ ${\displaystyle \Sigma _{j}^{i}}$ ${\displaystyle \Sigma _{1}^{1}}$

${\displaystyle \exists X\forall y2\cdot y\in X}$

in the -Satz ( is an amount which here for containing) ${\displaystyle \Pi _{2}}$ ${\displaystyle V}$ ${\displaystyle {\mathcal {P}}^{n}(\mathbb {N} )}$ ${\displaystyle n\in \mathbb {N} }$

${\displaystyle \forall V\ \forall \mathbb {N} \left(\mathbb {N} {\text{ ist die Menge der nat. Zahlen }}\wedge V{\text{ transitiv }}\wedge \mathbb {N} \in V\wedge \forall P\left(\exists M\in V\ \forall S\in P\ S\subseteq M\right)\rightarrow P\in V\right)\rightarrow \exists X\in V\ X\subseteq \mathbb {N} \wedge \forall y\in X\ 2\cdot y\in X}$

translate accordingly. The relationship also results from the following more general observation: If one extends the Levy hierarchy by allowing restricted quantification over all subsets ( etc.) as a restricted quantification , the resulting hierarchy coincides from the level with the Levy hierarchy. ${\displaystyle \Sigma _{2}}$ ${\displaystyle \forall x\subseteq y}$ ${\displaystyle \Delta _{2}}$

The Levy hierarchy can also be viewed in a concrete model of set theory. The set of all hereditary finite sets forms a model of ZF without the axiom of infinity. The -definable subsets of the natural numbers in this model , in the sense that a -formula exists, so that are precisely the recursively enumerable sets , the -definable subsets coincide with the recursive sets . More generally, the Levy hierarchy for this model is precisely the arithmetic hierarchy ( apart from the level depending on the definition) from which it forms an abstraction in this sense. ${\displaystyle HF}$ ${\displaystyle \Sigma _{1}}$ ${\displaystyle X}$ ${\displaystyle \Sigma _{1}}$ ${\displaystyle \varphi (x)}$ ${\displaystyle n\in X\Leftrightarrow HF\vDash \varphi (x)}$ ${\displaystyle \Delta _{1}}$ ${\displaystyle 0}$

literature

• Azriel Levy : A hierarchy of formulas in set theory . In: Memoirs of the American Mathematical Society . tape 57 . American Mathematical Society , 1965, ISSN  0065-9266 .
• Solomon Feferman : A Hierarchy of Formulas in Set Theory by Azriel Lévy . Review by: Solomon Feferman. In: Journal of Symbolic Logic . tape 33 , no. 3 . Association for Symbolic Logic , p. 473-474 , JSTOR : 2270349 .
• Jouko Väänänen: Dependence Logic . A New Approach to Independence Friendly Logic. Cambridge University Press , 2007, ISBN 0-521-87659-1 , pp. 137 ff .
• Keith Devlin : Constructibility . Springer , Berlin 1984, ISBN 3-540-13258-9 , pp. 27-31 ( online ).
• Frank R. Drake: Set Theory . An Introduction to Large Cardinals. North Holland, Amsterdam 1974, ISBN 0-7204-2200-0 , pp. 75-106 .

Web links

• Lévy hierarchy , entry in the nLab . (English)

Individual evidence

1. ^ Jon Barwise , Admissible Sets and Structures: An Approach to Definability Theory . Springer Science + Business Media , Berlin 1975, ISBN 3-540-07451-1 , pp. 10 ( online ).
2. ↑ ^{a b c} Devlin, p. 27.
3. ^ Väänänen, p. 140.
4. ↑ Marios Koulakis: Large cardinals and elementary embeddings of V. (PDF; 558 kB) Retrieved on March 25, 2013 . 
5. ↑ ^{a b} Richard Kaye, Tin Lok Wong: On Interpretations of Arithmetic and Set Theory . In: Notre Dame Journal of Formal Logic . tape 48 , no. 4 , 2007, p. 505 , doi : 10.1305 / ndjfl / 1193667707 .
6. ↑ Devlin, p. 29.
7. ↑ ^{a b c d} Väänänen, p. 151.
8. ↑ ^{a b c} Akihiro Kanamori : The Higher Infinite . Large Cardinals in Set Theory from Their Beginnings. 2nd Edition. Springer , 2009, ISBN 978-3-540-88867-3 , pp. 302 , doi : 10.1007 / 978-3-540-88867-3 .
9. ^ Väänänen, p. 140.
10. ^ Väänänen, p. 138.
11. ↑ Drake, p. 104.
12. ↑ Joan Bagaria: A gentle introduction to the theory of large cardinals. (PDF; 459 kB) 2011, p. 45 , accessed on March 22, 2013 . 
13. ↑ Azriel Levy : Axiom schemes of strong infinity in axiomatic set theory . In: Pacific Journal of Mathematics . tape 10 , no. 1 , 1960, p. 223-238 ( online ).
14. ↑ Levy, 1965, p. 68.
15. ↑ Barwise, p. 47.