Lévy hierarchy

The term of the Levy hierarchy a set of hierarchies of formulas and formal languages ​​are in mathematical logic, especially set theory, subsumed. Formulas of set theory are being sorted in a certain sense, according to their complexity. Formal languages ​​are classified according to the complexity of the formulas describing them in the hierarchy. When applied to such ranges the Levy hierarchy far beyond the arithmetical and the analytical hierarchy. The observation of low levels of the hierarchy allows statements about the transferability of the validity of statements between models of set theory.

The hierarchy was introduced in 1965 by Azriel Levy.

Definition

A formula in the language of set theory ( that is, the first-order predicate logic with equality and binary relation ) is called -, - or - formula if all occurring quantifications are limited, that is for a formula and variables of the form are ( written shortly ) or (short). Now we define inductively: A formula is a formula of the form for a formula and a formula is a formula of the form for a formula. Any - or formula is a formula, ie a formula in which is the maximum nesting unrestricted quantifiers. The amounts of all such formulas are called. or be the set of all formulas that are as Boolean combinations of - give or formulas.

Let now a theory in the language of set theory ( Zermelo -Fraenkel about the set theory ). is then defined as the set of formulas that can be the equivalent of a formula to prove, i.e., the free variables may be in the. is the same and given by. contained in the following always at least the axioms of classical first-order logic. Each formula in the language of set theory is a in, as they can be brought in Pränexnormalform.

As classes of formal languages ​​can be the subsets of the natural numbers ( more generally relations are possible ) differ, the - and - are defined, that is, for a - or - formula exists, so true. For further properties it follows that the quantities actually be object- language, define in sufficiently strong axiom systems without reference to models or provability (see below).

Similar hierarchies can be formed also by on the stage, additional formulas are permitted - such as those that contain terms for certain quantities such as power sets - and the definition of the closure properties will be continued accordingly.

Examples of definability

Here are some examples which can be at what stage of the Levy hierarchy identify important set-theoretic properties (ZF required).

Δ0 - definable

• Transitivity
• , Ie is an ordinal
• For every natural number

Δ1 - definable

• Addition, multiplication and exponentiation on the natural numbers and general ordinals
• Is a well-ordering on
• The set of all hereditarily finite sets
• Is ordinal, and the level in the hierarchy constructible

Σ1 - definable

• Finiteness
• Countability
• Equal thickness

Π1 - definable

• , H d is the power set of.
• , I.e., is a cardinal number.
• Regularity of a cardinal number
• Limes cardinal numbers
• Strong inaccessibility of a cardinal number
• Is ordinal, and the level in the hierarchy of Neumann

Δ2 - definable

• Continuum hypothesis
• Is a super - compact cardinal number

Σ2 - definable

• There exists a strongly inaccessible cardinal number
• There exists a measurable cardinal

Π2 - definable

• Konstruierbarkeitsaxiom
• Decision problem in Dependence Logic
• Is a super-compact cardinal number

Σ3 - definable

• There is a super compact cardinal number

Closure properties

Contains the axioms of ZF without the axiom of infinity and without the substitution axiom, then for already and for each variable and also for also. This follows from the fact that a block of existential or universal quantifiers by a single existence or universal quantifier can be replaced, where the variable over which is quantified, is then regarded as a tuple and can be expressed in operations on tuples. Sometimes Quantorenblöcke are therefore also approved in the definition of the Levy hierarchy.

Absoluteness

A formula of set theory in the free variables is called upward absolute for a class if and only if, the relativization of to call. Similarly, it is called down completely if the following applies. A formula is called absolute if it is up and down absolutely.

For every transitive class each formula is absolute. It follows that every formula for every transitive class upwards absolute and each formula is downward absolute.

Be the transitive closure of, ie the minimal transitive set that contains. Is an uncountable cardinal, then every formula is absolute for the crowd.

Definability of truth, separation and completeness

The validity of formulas with a given interpretation of free variables - represented by a 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 each subformula of a given formula, it suffices to consider the correlation on. It can now be a formula defining the relation, so that if and when that is valid under the interpretation of free variables by coded formula. is - definable, since it results in a minimal amount with certain closure properties. In fact, even ZF without the axiom of infinity is sufficient to specify a definition of validity of formulas, since it is sufficient to restrict the consideration to the finite set of subformulas of the given formula.

In fact, even the truth of formulas - definable (there just have the unrestricted universal quantifier can be extracted from the encoding ). It follows that the validity of formulas - definable (since the truth of is equivalent to the falsehood of ), and inductively, for each the truth of formulas - definable and of formulas - definable. It follows with the Undefinierbarkeitssatz of Tarski, that there is indeed a hierarchy in the Levy hierarchy: Includes ZF without the axiom of infinity and the fragment of consistent, so true and, otherwise, the hierarchy for stationary then it would be the truth of formulas then - definable, what the Undefinierbarkeitssatz contrary, since the amount of formulas is closed under negation and with the included arithmetic sufficiently powerful so that the Diagonallemma applies. This genuine inclusion relations are therefore also valid for the corresponding hierarchy of formal languages ​​. The respective definability of truth also allows only that - interpreted or - definability of a formal language as object language properties. In ZF ( with the axiom of infinity ), the separation can even prove because the consistency of each fragment of ZF is provable in ZF. This follows by using the definition of truth for formulas of the reflection principle, as it was published by Levy in 1960 and that is assuming the other axioms equivalent to the replacement axiom together with the axiom of infinity.

It can be shown that for.

A - or - set of natural numbers is called - or - complete if for each other - is or quantity by a computable function to be reduced, so true. Apparently, the amounts of the codes are true - or phrases completely for their respective class, simply must be chosen such that it makes an appropriate setting. Due to the seclusion of predictability archetypes volumes are not full - definable and vice versa.

Reference to the arithmetic

In this section, ZF is required. From - definability of natural numbers and the arithmetic operations shows that each formula of first-order arithmetic can already be expressed as formula. Some can be the set

In the set

Translate one set is obtained accordingly by negations. Thus, the - definable languages ​​already contain all languages ​​, that is the whole arithmetic hierarchy. In even allow arbitrary formulas of arithmetic translate any stage, in particular the entire analytical hierarchy is included. Some can be the set

In the set ( here is a set that contains for )

Translate accordingly. The relationship is also apparent from the following more general observation: If we extend the Levy hierarchy by allowing a limited quantification and bounded quantification over all subsets (etc.), then the thus resulting hierarchy falls off the stage with the Levy hierarchy together.

The Levy hierarchy can be viewed in a concrete model of set theory. The set of all hereditarily finite sets is a model of ZF without the axiom of infinity. The in this model - definable subsets of the natural numbers, in the sense that a formula exists, so, just are the recursively enumerable sets, the definable subsets coincide with the recursive sets. More generally, the Levy hierarchy for this model is precisely the arithmetical hierarchy (apart from the stage, depending on the definition), of which it forms an abstraction in this sense.