Hierarchia Borela

W logice matematycznej hierarchia Borela jest warstwowaniem algebry Borela generowanej przez otwarte podzbiory polskiej przestrzeni ; elementy tej algebry nazywane są zbiorami borelowskimi . Każdemu zbiorowi borelowskiemu przypisana jest unikalna policzalna liczba porządkowa , nazywana rangą zbioru borelowskiego. Hierarchia Borela jest przedmiotem szczególnego zainteresowania w opisowej teorii mnogości .

Jednym z powszechnych zastosowań hierarchii Borela jest udowodnienie faktów dotyczących zbiorów Borela za pomocą indukcji pozaskończonej według rangi. Własności zbiorów małych skończonych szeregów są ważne w teorii i analizie miary .

Zestawy Borela

Algebra Borela w dowolnej przestrzeni topologicznej jest najmniejszym zbiorem podzbiorów przestrzeni, która zawiera zbiory otwarte i jest domknięta na przeliczalne sumy i dopełnienia . Można wykazać, że algebra Borela jest zamknięta również na przeliczalnych przecięciach.

Krótki dowód na to, że algebra Borela jest dobrze zdefiniowana, polega na wykazaniu, że cały zbiór mocy przestrzeni jest domknięty na dopełnienia i policzalne sumy, a zatem algebra Borela jest przecięciem wszystkich rodzin podzbiorów przestrzeni, które mają te właściwości domknięcia. Dowód ten nie podaje prostej procedury określania, czy zbiór jest borelowski. Motywacją dla hierarchii Borela jest zapewnienie bardziej wyraźnej charakterystyki zbiorów Borela.

Pogrubiona hierarchia Borela

Hierarchia Borela lub pogrubiona czcionka Hierarchia Borela w przestrzeni X składa się z klas ${\ Displaystyle \ mathbf {\ Sigma} _ {\ alfa} ^ {0}}$ , ${\ Displaystyle \ mathbf {\ Pi} _ {\ alfa} ^ {0}}$ $i$ dla każdej policzalnej liczby $.$ zera Każda z tych klas składa się z podzbiorów X . Klasy są definiowane indukcyjnie z następujących reguł:

Zbiór jest w ${\ Displaystyle \ mathbf {\ Sigma} _ {1} ^ {0}}$ wtedy i tylko wtedy, gdy jest otwarty.
Zbiór jest w ${\ Displaystyle \ mathbf {\ Pi} _ {\ alfa} ^ {0}}$ wtedy i tylko wtedy, gdy jego dopełnienie jest w ${\ Displaystyle \ mathbf {\ Sigma} _ {\ alfa} ^ {0}}$ .
Zbiór jest w ${\$ $Displaystyle \ mathbf {\ Sigma} _ {\ alfa} ^ {0}}$ dla ${\ Displaystyle \ alpha > 1} wtedy i tylko wtedy$ gdy istnieje sekwencja zestawów ${\ Displaystyle A_ {1}, A_ {2}, \ ldots}$ taka, że każdy $mathbf$ w $\ Pi} _ {\ alfa _ {i}} ^ {0}}$ ${\ Displaystyle \$ dla niektórych ${\ Displaystyle \ alpha _ {i}<\ alpha}$ $\ Displaystyle A = \ bigcup A_ {i}}$ = .
Zbiór jest w ${\ Displaystyle \ mathbf {\ Delta} _ {\ alfa} ^ {0}}$ wtedy i tylko wtedy, gdy oba są w ${\ Displaystyle \ mathbf {\ Sigma} _ {\ alfa} ^ {0}}$ i w ${\ Displaystyle \ mathbf {\ Pi} _ {\ alfa} ^ {0}}$ .

Motywacją dla hierarchii jest podążanie za sposobem, w jaki zbiór borelowski można zbudować ze zbiorów otwartych za pomocą dopełnienia i policzalnych związków. Mówi $;$ $, że zbiór$ ma skończoną rangę , jeśli jest w skończonej liczbie porządkowej w przeciwnym razie ma nieskończoną rangę .

Jeśli ${\ Displaystyle \ mathbf {\ Sigma} _ {1} ^ {0} \ subseteq \ mathbf {\ Sigma} _ {2} ^ {0}},$ można pokazać, że hierarchia ma następujące nieruchomości:

Dla każdego α , ${\ Displaystyle \ mathbf {\ Sigma} _ {\ alfa} ^ {0} \ kubek \ mathbf {\ Pi} _ {\ alfa} ^ {0} \ subseteq \mathbf {\Delta} _{\alpha +1}^{0}}$ . Tak więc, gdy zestaw jest w ${\ Displaystyle \ mathbf {\ Sigma} _ {\ alfa} ^ {0}}$ lub ${\ Displaystyle \ mathbf {\ Pi} _ {\ alfa} ^ {0}}$ , ten zbiór będzie we wszystkich klasach w hierarchii odpowiadających liczbom porządkowym większym niż α
${\ Displaystyle \ bigcup _ {\ alfa <\ omega _ {1}} \ mathbf {\ Sigma} _ {\ alfa }^{0}=\bigcup _{\alpha <\omega _{1}}\mathbf {\Pi} _{\alpha }^{0}=\bigcup _{\alpha <\omega _{1}} \mathbf {\Delta} _{\alfa}^{0}}$ . Co więcej, zbiór jest w tej unii wtedy i tylko wtedy, gdy jest borelowski.
Jeśli $\$ $α$ { \ $\ Sigma} _ {\ alfa} ^ {0}$ $dla$ dowolnego zatem hierarchia się nie załamuje

Zbiory borelowskie małego rzędu

Klasy małej rangi są znane pod alternatywnymi nazwami w klasycznej opisowej teorii mnogości.

Zbiory $.$ zbiory Zbiory $.$ zbiorami
Zbiory $są$ przeliczalnymi związkami zbiorów zamkniętych i zbiorami fa _σ . Zbiory są klasą podwójną i można je zapisać jako przeliczalne przecięcie $zbiorów$ Zbiory te nazywane są zbiorami G _δ .

Hierarchia jasnej twarzy

Hierarchia Borela o jasnej twarzy jest efektywną wersją pogrubionej hierarchii Borela. Jest to ważne w efektywnej opisowej teorii mnogości i teorii rekurencji . Hierarchia Borela o jasnej powierzchni rozszerza arytmetyczną hierarchię podzbiorów efektywnej przestrzeni polskiej . Jest ściśle powiązany z hierarchią hiperarytmetyczną .

Hierarchię Lightface Borela można zdefiniować na dowolnej efektywnej polskiej przestrzeni. Składa się z klas ${\ Displaystyle \ Sigma _ {\ alfa} ^ {0}}$ , ${\ Displaystyle \ Pi _ {\ alfa} ^ {0}}$ i ${\ Displaystyle \ Delta _ {\ alfa} ^ {0}}$ dla każdej niezerowej policzalnej liczby porządkowej $mniejszej$ niż liczba porządkowa Churcha-Kleene'a ${\ Displaystyle \ omega _ {1} ^ {\ operatorname {CK}}$ . Każda klasa składa się z podzbiorów przestrzeni. Klasy i kody elementów klas są definiowane indukcyjnie w następujący sposób:

Zbiór jest $,$ tylko wtedy, gdy jest efektywnie otwarty , to znaczy zbiór otwarty który jest sumą obliczalnie przeliczalnej sekwencji podstawowych zbiorów otwartych. Kodem takiego zbioru jest para (0,e) , gdzie e jest indeksem programu wyliczającego sekwencję podstawowych zbiorów otwartych.
Zbiór jest ${\ Displaystyle \ Pi _ {\ alfa} ^ {0}}$ wtedy i tylko wtedy, gdy jego uzupełnieniem jest ${\ Displaystyle \ Sigma _ {\ alfa} ^ {0}}$ . Kodem dla jednego z tych zestawów jest para (1,c) , gdzie c jest kodem zestawu komplementarnego.
Zbiór to ${\ Displaystyle \ Sigma _ {\ alfa} ^ {0}}$ , jeśli istnieje przeliczalna sekwencja kodów dla sekwencji ${\ Displaystyle A_ {1}, A_ {2 } \ ldots }$ zestawów takich, że każdy jest dla pewnego $displaystyle \ alpha _ {i}<\ alpha}$ ${i}}$ $_ {\ alfa _ {i}} ^ {0}$ $}$ ${\ Displaystyle A = \ bigcup A_ {i}}$ i . Kodem dla $e$ jest para (2, e) , gdzie jest indeksem programu wyliczającego kody sekwencji $A_{i}}$ $\$ displaystyle .

Kod zestawu Lightface Borel zawiera pełne informacje o tym, jak odzyskać zestaw z zestawów o mniejszej randze. Kontrastuje to z hierarchią pogrubioną czcionką, w której taka skuteczność nie jest wymagana. Każdy zestaw Borela o jasnej twarzy ma nieskończenie wiele różnych kodów. Możliwe są inne systemy kodowania; kluczową ideą jest to, że kod musi skutecznie rozróżniać skutecznie otwarte zbiory, uzupełnienia zbiorów reprezentowanych przez poprzednie kody i obliczalne wyliczenia sekwencji kodów.

Można pokazać, że dla każdego $Sigma _$ zbiory w $\alpha }^{0}\setminus \Pi _{\alpha }^{0}}$ $\ Displaystyle \ Sigma$ , a zatem hierarchia się nie zawali. Żadne nowe zestawy nie byłyby jednak dodawane na etapie ${\ Displaystyle \ omega _ {1} ^ {\ operatorname {CK}}}$ .

$, że zbiór znajduje$ w jasnej hierarchii Borela wtedy i tylko wtedy, gdy znajduje się na hierarchii analitycznej . Zbiory te nazywane są również hiperarytmetycznymi .

Kod dla jasnego zestawu Borela A może być użyty do indukcyjnego zdefiniowania drzewa, którego węzły są oznaczone kodami. Korzeń drzewa jest oznaczony kodem dla A . Jeśli węzeł jest oznaczony kodem postaci (1,c) , to ma węzeł potomny, którego kodem jest c . Jeżeli węzeł jest oznaczony kodem postaci (2,e) , to ma jedno dziecko dla każdego kodu wyliczonego przez program o indeksie e . Jeśli węzeł jest oznaczony kodem postaci (0,e), to nie ma dzieci. To drzewo opisuje, w jaki sposób A jest budowane ze zbiorów o mniejszej randze. Liczby porządkowe użyte do konstrukcji A zapewniają, że to drzewo nie ma nieskończonej ścieżki, ponieważ każda nieskończona ścieżka przez drzewo musiałaby zawierać nieskończenie wiele kodów zaczynających się od 2 , a zatem dawałaby nieskończoną malejącą sekwencję liczb porządkowych. I odwrotnie, jeśli dowolne poddrzewo ma swoje węzły oznaczone kodami w spójny sposób, a drzewo nie ma nieskończonych ścieżek, to kod w korzeniu ω $\ Displaystyle \ omega ^ {<\ omega} \,}$ drzewo jest kodem zestawu Lightface Borel. Ranga tego zbioru jest ograniczona typem porządku drzewa w porządku Kleene-Brouwera . Ponieważ drzewo jest definiowalne arytmetycznie, ta ranga musi być mniejsza niż ${\ Displaystyle \ omega _ {1} ^ {\ operatorname {CK}}}$ . Takie jest pochodzenie porządkowej Church-Kleene w definicji hierarchii jasnej twarzy.

Stosunek do innych hierarchii

Jasna twarz		Pogrubiona czcionka
⁰ ₀⁰ ₀⁰ ₀ Σ = Π = Δ (czasami to samo co Δ ⁰ ₁ )		Σ ⁰ ₀ = Π ⁰ ₀ = Δ ⁰ ₀ (jeśli zdefiniowano)
Δ ⁰ ₁ = rekurencyjny		Δ ⁰ ₁ = domknięty
Σ ⁰ ₁ = rekurencyjnie przeliczalny	Π ⁰ ₁ = współrekurencyjnie przeliczalny	Σ ⁰ ₁ = G = otwarty	Π ⁰ ₁ = F = zamknięty
Δ ⁰ ₂		Δ ⁰ ₂
Σ ⁰ ₂	Π ⁰ ₂	Σ ⁰ ₂ = fa _σ	Π ⁰ ₂ = G _δ
Δ ⁰ ₃		Δ ⁰ ₃
Σ ⁰ ₃	Π ⁰ ₃	Σ ⁰ ₃ = G _δσ	Π ⁰ ₃ = fa _σδ
⋮		⋮
Σ ⁰ _<ω = Π ⁰ _<ω = Δ ⁰ _<ω = Σ ¹ ₀ = Π ¹ ₀ = Δ ¹ ₀ = arytmetyczne		Σ ⁰ _<ω = Π ⁰ _<ω = Δ ⁰ _<ω = Σ ¹ ₀ = Π ¹ ₀ = Δ ¹ ₀ = pogrubiona czcionka arytmetyczna
⋮		⋮
Δ ⁰ _α (α rekurencyjny )		Δ ⁰ _α (α policzalne )
Σα ⁰ _{_}	Πα ⁰ _{_}	Σα ⁰ _{_}	Πα ⁰ _{_}
⋮		⋮
Σ ⁰ _{ω ^CK₁} = Π ⁰ _{ω ^CK₁} = Δ ⁰ _{ω ^CK₁} = Δ ¹₁ = hiperarytmetyczny		Σ ⁰ _{ω ₁} = Π ⁰ _{ω ₁} = Δ ⁰ _{ω ₁} = Δ ¹₁ = B = Borel
Σ ¹₁ = analityk jasnej twarzy	Π ¹₁ = koanalityczny o jasnej twarzy	Σ ¹₁ = A = analityczny	Π ¹₁ = CA = koanalityczny
Δ ¹₂		Δ ¹₂
Σ ¹₂	Π ¹₂	Σ ¹₂ = PCA	Π ¹₂ = CPCA
Δ ¹₃		Δ ¹₃
Σ ¹₃	Π ¹₃	Σ ¹₃ = PCPCA	Π ¹₃ = CPCPCA
⋮		⋮
Σ ¹_<ω = Π ¹_<ω = Δ ¹_<ω = Σ ² ₀ = Π ² ₀ = Δ ² ₀ = analityczny		Σ ¹_<ω = Π ¹_<ω = Δ ¹_<ω = Σ ² ₀ = Π ² ₀ = Δ ² ₀ = P = rzutowa
⋮		⋮

Kechris, Aleksander . Klasyczna opisowa teoria mnogości . Absolwent Teksty z matematyki t. 156, Springer-Verlag, 1995. ISBN 3-540-94374-9 .
Jech, Tomasz . Teoria mnogości , wydanie 3. Springera, 2003. ISBN 3-540-44085-2 .

Zobacz też