Lévy hierarchy

From Wikipedia, the free encyclopedia
  (Redirected from Levy hierarchy)
Jump to: navigation, search

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[edit]

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^{ZFC} _i and \Pi^{ZFC} _i.

Examples[edit]

Σ000 formulas and concepts[edit]

  • 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.

Δ1-formulas and concepts[edit]

  • 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

Σ1-formulas and concepts[edit]

  • x is countable
  • |X|<|Y|, |X|=|Y|
  • x is constructible

Π1-formulas and concepts[edit]

Δ2-formulas and concepts[edit]

  • κ is γ-supercompact

Σ2-formulas and concepts[edit]

Π2-formulas and concepts[edit]

Δ3-formulas and concepts[edit]

Σ3-formulas and concepts[edit]

Π3-formulas and concepts[edit]

Σ4-formulas and concepts[edit]

Properties[edit]

Jech p. 184 Devlin p. 29

See also[edit]

References[edit]

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