Lévyho hierarchie - Lévy hierarchy

v teorie množin a matematická logika, Lévyho hierarchie, představil Azriel Lévy v roce 1965 je hierarchie vzorců v formální jazyk z Teorie množin Zermelo – Fraenkel, kterému se obvykle říká jen jazyk teorie množin. To je analogické s aritmetická hierarchie který poskytuje klasifikace, ale pro věty jazyka aritmetiky.

Definice

V jazyce teorie množin atomové vzorce jsou ve tvaru x = y nebo x ∈ y, stojí za rovnost resp nastavit členství predikáty.

První úroveň hierarchie Levy je definována jako obsahující pouze vzorce bez neomezených kvantifikátorů a je označena ${ displaystyle Delta _ {0} = Sigma _ {0} = Pi _ {0}}$.^[1] Další úrovně jsou dány hledáním ekvivalentního vzorce v Prenex normální forma a počítání počtu změn kvantifikátory:

V teorii ZFC vzorec ${ displaystyle A}$ je nazýván:^[1]

${ displaystyle Sigma _ {i + 1}}$ -li ${ displaystyle A}$ je ekvivalentní k ${ displaystyle existuje x_ {1} ... existuje x_ {n} B}$ v ZFC, kde ${ displaystyle B}$ je ${ displaystyle Pi _ {i}}$

${ displaystyle Pi _ {i + 1}}$ -li ${ displaystyle A}$ je ekvivalentní k ${ displaystyle forall x_ {1} ... forall x_ {n} B}$ v ZFC, kde ${ displaystyle B}$ je ${ displaystyle Sigma _ {i}}$

Pokud je vzorec obojí ${ displaystyle Sigma _ {i}}$ a ${ displaystyle Pi _ {i}}$, to se nazývá ${ displaystyle Delta _ {i}}$. Protože vzorec může mít několik různých ekvivalentních vzorců v normální formě Prenex, mohl by patřit do několika různých úrovní hierarchie. V tomto případě je nejnižší možnou úrovní úroveň vzorce.

Lévyho hierarchie je někdy definována pro jiné teorie S. V tomto případě ${ displaystyle Sigma _ {i}}$ a ${ displaystyle Pi _ {i}}$ samy o sobě odkazují pouze na vzorce, které začínají nanejvýš posloupností kvantifikátorů i-1 střídání a ${ displaystyle Sigma _ {i} ^ {S}}$ a ${ displaystyle Pi _ {i} ^ {S}}$ odkazovat na vzorce ekvivalentní k ${ displaystyle Sigma _ {i}}$ a ${ displaystyle Pi _ {i}}$ vzorce v teorii S. Takže přesně řečeno úrovně ${ displaystyle Sigma _ {i}}$ a ${ displaystyle Pi _ {i}}$ výše uvedené Lévyho hierarchie pro ZFC by měl být označen ${ displaystyle Sigma _ {i} ^ {ZFC}}$ a ${ displaystyle Pi _ {i} ^ {ZFC}}$.

Příklady

Σ₀= Π₀= Δ₀ vzorce a pojmy

• x = {y, z}
• x ⊆ y
• X je tranzitivní sada
• X je pořadové číslo, X je limitní pořadové číslo, X je pořadovým nástupcem
• X je konečný řadový
• První počitatelný pořadový ω.
• F je funkce. Rozsah a doména funkce. Hodnota funkce na množině.
• Produkt dvou sad.
• Spojení množiny.

Δ₁-formule a pojmy

• X je opodstatněný vztah na y
• X je konečný
• Pořadové sčítání a násobení a umocňování
• Hodnost sady
• Přechodné uzavření sady

Σ₁-formule a pojmy

• X je počitatelný
• |X|≤|Y|, |X|=|Y|
• X je konstruovatelný

Π₁-formule a pojmy

• X je kardinál
• X je řádný kardinál
• X je limit kardinál
• X je nepřístupný kardinál.
• X je výkonová sada z y

Δ₂-formule a pojmy

• κ je γ-superkompaktní

Σ₂-formule a pojmy

• the Hypotéza kontinua
• existuje nepřístupný kardinál
• existuje a měřitelný kardinál
• κ je n-velký kardinál

Π₂-formule a pojmy

• The axiom konstruovatelnosti: PROTI = L

Δ₃-formule a pojmy

Σ₃-formule a pojmy

• Tady je superkompaktní kardinál

Π₃-formule a pojmy

• κ je rozšiřitelný kardinál

Σ₄-formule a pojmy

• Tady je rozšiřitelný kardinál

Vlastnosti

Jech p. 184 Devlin str. 29

Viz také

• aritmetická hierarchie
• Absolutnost

Reference

• Devlin, Keith J. (1984). Stavitelnost. Perspektivy v matematické logice. Berlín: Springer-Verlag. str.27 –30. Zbl  0542.03029.
• Jech, Thomas (2003). Teorie množin. Springer Monographs in Mathematics (Third Millennium ed.). Berlín, New York: Springer-Verlag. str. 183. ISBN  978-3-540-44085-7. Zbl  1007.03002.
• Kanamori, Akihiro (2006). "Levy a teorie množin" (PDF). Annals of Pure and Applied Logic. 140: 233–252. doi:10.1016 / j.apal.2005.09.009. Zbl  1089.03004. Archivovány od originál (PDF) dne 2016-10-20. Citováno 2014-08-16.
• Levy, Azriel (1965). Hierarchie vzorců v teorii množin. Mem. Dopoledne. Matematika. Soc. 57. Zbl  0202.30502.