Analytická hierarchie - Analytical hierarchy

v matematická logika a deskriptivní teorie množin, analytická hierarchie je rozšířením aritmetická hierarchie. Analytická hierarchie vzorců zahrnuje vzorce v jazyce aritmetika druhého řádu, které mohou mít kvantifikátory přes obě sady přirozená čísla, ${ displaystyle mathbb {N}}$ a další funkce z ${ displaystyle mathbb {N}}$ na ${ displaystyle mathbb {N}}$ . Analytická hierarchie sad klasifikuje sady podle vzorců, pomocí kterých je lze definovat; to je světelná plocha verze projektivní hierarchie.

Analytická hierarchie vzorců

Zápis ${ displaystyle Sigma _ {0} ^ {1} = Pi _ {0} ^ {1} = Delta _ {0} ^ {1}}$ označuje třídu vzorců v jazyce aritmetika druhého řádu bez nastavených kvantifikátorů. Tento jazyk neobsahuje nastavené parametry. Řecká písmena jsou zde světelná plocha symboly, které označují tuto volbu jazyka. Každý odpovídající tučně Symbol označuje odpovídající třídu vzorců v rozšířeném jazyce s parametrem pro každou z nich nemovitý; vidět projektivní hierarchie pro detaily.

Vzorec v jazyce aritmetiky druhého řádu je definován jako ${ displaystyle Sigma _ {n + 1} ^ {1}}$ Pokud to je logicky ekvivalentní na vzorec formuláře ${ displaystyle existuje X_ {1} cdots existuje X_ {k} psi}$ kde ${ displaystyle psi}$ je ${ displaystyle Pi _ {n} ^ {1}}$ . Vzorec je definován jako ${ displaystyle Pi _ {n + 1} ^ {1}}$ pokud je logicky ekvivalentní formuli formuláře ${ displaystyle forall X_ {1} cdots forall X_ {k} psi}$ kde ${ displaystyle psi}$ je ${ displaystyle Sigma _ {n} ^ {1}}$ . Tato indukční definice definuje třídy ${ displaystyle Sigma _ {n} ^ {1}}$ a ${ displaystyle Pi _ {n} ^ {1}}$ pro každé přirozené číslo ${ displaystyle n}$ .

Protože každý vzorec má a normální forma prenex, každý vzorec v jazyce aritmetiky druhého řádu je ${ displaystyle Sigma _ {n} ^ {1}}$ nebo ${ displaystyle Pi _ {n} ^ {1}}$ pro některé ${ displaystyle n}$ . Vzhledem k tomu, že do libovolného vzorce lze přidat nesmyslné kvantifikátory, jakmile je vzoru dána klasifikace ${ displaystyle Sigma _ {n} ^ {1}}$ nebo ${ displaystyle Pi _ {n} ^ {1}}$ pro některé ${ displaystyle n}$ dostane klasifikace ${ displaystyle Sigma _ {m} ^ {1}}$ a ${ displaystyle Pi _ {m} ^ {1}}$ pro všechny ${ displaystyle m}$ větší než ${ displaystyle n}$ .

Analytická hierarchie množin přirozených čísel

Klasifikaci je přiřazena sada přirozených čísel ${ displaystyle Sigma _ {n} ^ {1}}$ pokud je definovatelný a ${ displaystyle Sigma _ {n} ^ {1}}$ vzorec. Souboru je přiřazena klasifikace ${ displaystyle Pi _ {n} ^ {1}}$ pokud je definovatelný a ${ displaystyle Pi _ {n} ^ {1}}$ vzorec. Pokud je sada obojí ${ displaystyle Sigma _ {n} ^ {1}}$ a ${ displaystyle Pi _ {n} ^ {1}}$ pak je dána další klasifikace ${ displaystyle Delta _ {n} ^ {1}}$ .

The ${ displaystyle Delta _ {1} ^ {1}}$ sady se nazývají hyperaritmetické. Alternativní klasifikaci těchto sad prostřednictvím iterovaných vypočítatelných funkcionálů poskytuje hyperaritmetická teorie.

Analytická hierarchie na podmnožinách prostoru Cantor a Baire

Analytickou hierarchii lze definovat na jakékoli efektivní polský prostor; definice je obzvláště jednoduchá pro Cantor a Baireův prostor, protože odpovídají jazyku běžné aritmetiky druhého řádu. Cantorův prostor je množina všech nekonečných sekvencí 0s a 1s; Baireův prostor je množina všech nekonečných posloupností přirozených čísel. To jsou oba Polské prostory.

Obyčejná axiomatizace aritmetika druhého řádu používá jazyk založený na množině, ve kterém lze přirozeně považovat množinu kvantifikátorů za kvantifikaci v Cantorově prostoru. Podskupině Cantorova prostoru je přiřazena klasifikace ${ displaystyle Sigma _ {n} ^ {1}}$ pokud je definovatelný a ${ displaystyle Sigma _ {n} ^ {1}}$ vzorec. Souboru je přiřazena klasifikace ${ displaystyle Pi _ {n} ^ {1}}$ pokud je definovatelný a ${ displaystyle Pi _ {n} ^ {1}}$ vzorec. Pokud je sada obojí ${ displaystyle Sigma _ {n} ^ {1}}$ a ${ displaystyle Pi _ {n} ^ {1}}$ pak je dána další klasifikace ${ displaystyle Delta _ {n} ^ {1}}$ .

Podmnožina Baireova prostoru má odpovídající podmnožinu Cantorova prostoru pod mapou, která přebírá každou funkci ${ displaystyle omega}$ na ${ displaystyle omega}$ k charakteristické funkci jeho grafu. Podmnožině Baireova prostoru je dána klasifikace ${ displaystyle Sigma _ {n} ^ {1}}$ , ${ displaystyle Pi _ {n} ^ {1}}$ nebo ${ displaystyle Delta _ {n} ^ {1}}$ právě tehdy, má-li odpovídající podmnožina Cantorova prostoru stejnou klasifikaci. Ekvivalentní definice analytické hierarchie v prostoru Baire je dána definováním analytické hierarchie vzorců pomocí funkční verze aritmetiky druhého řádu; pak lze z hierarchie v prostoru Baire definovat analytickou hierarchii na podmnožinách Cantorova prostoru. Tato alternativní definice poskytuje přesně stejné klasifikace jako první definice.

Protože Cantorův prostor je homeomorfní pro jakoukoli konečnou pravouhlou mocninu sebe sama a Bairův prostor je homeomorfní pro jakoukoli konečnou pravouhlou mocninu sama o sobě, analytická hierarchie platí stejně dobře pro konečnou kartézskou moc jednoho z těchto prostorů. Podobné rozšíření je možné pro spočetné síly a k produktům sil Cantorova prostoru a sil Baireho prostoru.

Rozšíření

Stejně jako v případě aritmetická hierarchie lze definovat relativizovanou verzi analytické hierarchie. Jazyk je rozšířen a přidán symbol konstantní množiny A. Vzorec v rozšířeném jazyce je indukčně definován jako ${ displaystyle Sigma _ {n} ^ {1, A}}$ nebo ${ displaystyle Pi _ {n} ^ {1, A}}$ pomocí stejné indukční definice jako výše. Vzhledem k sadě ${ displaystyle Y}$ , množina je definována jako ${ displaystyle Sigma _ {n} ^ {1, Y}}$ pokud je definovatelný a ${ displaystyle Sigma _ {n} ^ {1, A}}$ vzorec, ve kterém je symbol ${ displaystyle A}$ je interpretován jako ${ displaystyle Y}$ ; podobné definice pro ${ displaystyle Pi _ {n} ^ {1, Y}}$ a ${ displaystyle Delta _ {n} ^ {1, Y}}$ aplikovat. Sady, které jsou ${ displaystyle Sigma _ {n} ^ {1, Y}}$ nebo ${ displaystyle Pi _ {n} ^ {1, Y}}$ , pro libovolný parametr Y, jsou zařazeny do projektivní hierarchie.

Příklady

Množina všech přirozených čísel, která jsou indexy vypočítatelných ordinálů, je a ${ displaystyle Pi _ {1} ^ {1}}$ sada, která není ${ displaystyle Sigma _ {1} ^ {1}}$ .
Sada prvků Cantorova prostoru, které jsou charakteristickými funkcemi uspořádání řádků ${ displaystyle omega}$ je ${ displaystyle Pi _ {1} ^ {1}}$ sada, která není ${ displaystyle Sigma _ {1} ^ {1}}$ . Ve skutečnosti tato sada není ${ displaystyle Sigma _ {1} ^ {1, Y}}$ pro libovolný prvek ${ displaystyle Y}$ prostoru Baire.
Pokud axiom konstruovatelnosti drží pak existuje podmnožina produktu prostoru Baire se sebou, která je ${ displaystyle Delta _ {2} ^ {1}}$ a je grafem a objednávání prostoru Baire. Pokud platí axiom, pak existuje také a ${ displaystyle Delta _ {2} ^ {1}}$ dobré uspořádání Cantorova prostoru.

Vlastnosti

Pro každého ${ displaystyle n}$ máme následující přísná omezení:

{ displaystyle Pi _ {n} ^ {1} podmnožina Sigma _ {n + 1} ^ {1}}

,

{ displaystyle Pi _ {n} ^ {1} podmnožina Pi _ {n + 1} ^ {1}}

,

{ displaystyle Sigma _ {n} ^ {1} podmnožina Pi _ {n + 1} ^ {1}}

,

{ displaystyle Sigma _ {n} ^ {1} podmnožina Sigma _ {n + 1} ^ {1}}

.

Sada, která je uvnitř ${ displaystyle Sigma _ {n} ^ {1}}$ pro některé n se říká, že je analytické. Je třeba rozlišovat toto použití od termínu analytická sada což má jiný význam.

Stůl

Lightface		Tučné písmo
Σ⁰ ₀ = Π⁰ ₀ = Δ⁰ ₀ (někdy stejné jako Δ⁰ ₁)		Σ⁰ ₀ = Π⁰ ₀ = Δ⁰ ₀ (pokud je definováno)
Δ⁰ ₁ = rekurzivní		Δ⁰ ₁ = clopen
Σ⁰ ₁ = rekurzivně spočetné	Π⁰ ₁ = ko-rekurzivně vyčíslitelné	Σ⁰ ₁ = G = otevřeno	Π⁰ ₁ = F = Zavřeno
Δ⁰ ₂		Δ⁰ ₂
Σ⁰ ₂	Π⁰ ₂	Σ⁰ ₂ = F_σ	Π⁰ ₂ = G_δ
Δ⁰ ₃		Δ⁰ ₃
Σ⁰ ₃	Π⁰ ₃	Σ⁰ ₃ = G_δσ	Π⁰ ₃ = F_σδ
⋮		⋮
Σ⁰ _<ω = Π⁰ _<ω = Δ⁰ _<ω = Σ¹ ₀ = Π¹ ₀ = Δ¹ ₀ = aritmetický		Σ⁰ _<ω = Π⁰ _<ω = Δ⁰ _<ω = Σ¹ ₀ = Π¹ ₀ = Δ¹ ₀ = tučné písmo aritmetické
⋮		⋮
Δ⁰ _α (α rekurzivní )		Δ⁰ _α (α počitatelný )
Σ⁰ _α	Π⁰ _α	Σ⁰ _α	Π⁰ _α
⋮		⋮
Σ⁰ _ω^CK ₁ = Π⁰ _ω^CK ₁ = Δ⁰ _ω^CK ₁ = Δ¹ ₁ = hyperaritmetické		Σ⁰ _ω₁ = Π⁰ _ω₁ = Δ⁰ _ω₁ = Δ¹ ₁ = B = Borel
Σ¹ ₁ = světelná plocha analytická	Π¹ ₁ = světelný povrch coanalytic	Σ¹ ₁ = A = analytický	Π¹ ₁ = CA = koanalytický
Δ¹ ₂		Δ¹ ₂
Σ¹ ₂	Π¹ ₂	Σ¹ ₂ = PCA	Π¹ ₂ = CPCA
Δ¹ ₃		Δ¹ ₃
Σ¹ ₃	Π¹ ₃	Σ¹ ₃ = PCPCA	Π¹ ₃ = CPCPCA
⋮		⋮
Σ¹ _<ω = Π¹ _<ω = Δ¹ _<ω = Σ² ₀ = Π² ₀ = Δ² ₀ = analytické		Σ¹ _<ω = Π¹ _<ω = Δ¹ _<ω = Σ² ₀ = Π² ₀ = Δ² ₀ = P = projektivní
⋮		⋮

Viz také

Rychle rostoucí hierarchie

Reference

Rogers, H. (1967). Teorie rekurzivních funkcí a efektivní vypočítatelnost. McGraw-Hill.
Kechris, A. (1995). Klasická deskriptivní teorie množin (Postgraduální texty z matematiky 156 ed.). Springer. ISBN 0-387-94374-9.

Analytická hierarchie na PlanetMath.