To install click the Add extension button. That's it.

The source code for the WIKI 2 extension is being checked by specialists of the Mozilla Foundation, Google, and Apple. You could also do it yourself at any point in time.

4,5
Kelly Slayton
Congratulations on this excellent venture… what a great idea!
Alexander Grigorievskiy
I use WIKI 2 every day and almost forgot how the original Wikipedia looks like.
Live Statistics
English Articles
Improved in 24 Hours
Added in 24 Hours
Languages
Recent
Show all languages
What we do. Every page goes through several hundred of perfecting techniques; in live mode. Quite the same Wikipedia. Just better.
.
Leo
Newton
Brights
Milds

Lévy hierarchy

From Wikipedia, the free encyclopedia

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 a similar classification for sentences of the language of arithmetic.

YouTube Encyclopedic

  • 1/5
    Views:
    1 433
    36 093
    5 322
    532
    309 512
  • Joel David Hamkins : The hierarchy of second-order set theories between GBC and KM and beyond
  • The Continuum Hypothesis and the search for Mathematical Infinity, W. Hugh Woodin
  • Levy Processes and Applications to Machine Learning
  • Hierarchical Regulatory Domain Inference from Hi-C Data
  • Elite and Levy Units of the Eastern Roman Army

Transcription

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 .[1] 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:[2]p. 184

A formula is called:[1][3]

  • if is equivalent to in ZFC, where is
  • if is equivalent to in ZFC, where is
  • If a formula has both a form and a form, it is called .

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]

Lévy's original notation was (resp. ) due to the provable logical equivalence,[4] strictly speaking the above levels should be referred to as (resp. ) to specify the theory in which the equivalence is carried out, however it is usually clear from context.[5]pp. 441–442 Pohlers has defined in particular semantically, in which a formula is " in a structure ".[6]

The Lévy hierarchy is sometimes defined for other theories S. In this case and by themselves refer only to formulas that start with a sequence of quantifiers with at most i−1 alternations,[citation needed] and and refer to formulas equivalent to and formulas in the language of the theory S. So strictly speaking the levels and of the Lévy hierarchy for ZFC defined above should be denoted by and .

Examples

Σ000 formulas and concepts

Δ1-formulas and concepts

Σ1-formulas and concepts

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

Π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

Properties

Let . The Lévy hierarchy has the following properties:[2]p. 184

  • If is , then is .
  • If is , then is .
  • If and are , then , , , , and are all .
  • If and are , then , , , , and are all .
  • If is and is , then is .
  • If is and is , then is .

Devlin p. 29

See also

References

  • 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". Annals of Pure and Applied Logic. 140 (1–3): 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. Vol. 57. Zbl 0202.30502.

Citations

  1. ^ a b Walicki, Michal (2012). Mathematical Logic, p. 225. World Scientific Publishing Co. Pte. Ltd. ISBN 9789814343862
  2. ^ a b T. Jech, 'Set Theory: The Third Millennium Edition, revised and expanded'. Springer Monographs in Mathematics (2006). ISBN 3-540-44085-2.
  3. ^ J. Baeten, Filters and ultrafilters over definable subsets over admissible ordinals (1986). p.10
  4. ^ a b A. Lévy, 'A hierarchy of formulas in set theory' (1965), second edition
  5. ^ K. Hauser, "Indescribable cardinals and elementary embeddings". Journal of Symbolic Logic vol. 56, iss. 2 (1991), pp.439--457.
  6. ^ W. Pohlers, Proof Theory: The First Step into Impredicativity (2009) (p.245)
  7. ^ a b c d e f g h i j Jon Barwise, Admissible Sets and Structures. Perspectives in Mathematical Logic (1975)
  8. ^ a b c d e f D. Monk 2011, Graduate Set Theory (pp.168--170). Archived 2011-12-06
  9. ^ W. A. R. Weiss, An Introduction to Set Theory (chapter 13). Accessed 2022-12-01
  10. ^ K. J. Williams, Minimum models of second-order set theories (2019, p.4). Accessed 2022 July 25.
  11. ^ F. R. Drake, Set Theory: An Introduction to Large Cardinals (p.83). Accessed 1 July 2022.
  12. ^ a b c Azriel 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
This page was last edited on 31 January 2024, at 04:40
Basis of this page is in Wikipedia. Text is available under the CC BY-SA 3.0 Unported License. Non-text media are available under their specified licenses. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc. WIKI 2 is an independent company and has no affiliation with Wikimedia Foundation.