Teoria hiperarytmetyczna

W teorii rekurencji teoria hiperarytmetyczna jest uogólnieniem obliczalności Turinga . Ma ścisłe powiązania z definiowalnością w arytmetyce drugiego rzędu oraz ze słabymi systemami teorii mnogości , takimi jak teoria mnogości Kripkego – Plateka . Jest to ważne narzędzie w efektywnej opisowej teorii mnogości .

Centralnym punktem teorii hiperarytmetyki są zbiory liczb naturalnych znane jako zbiory hiperarytmetyczne . Istnieją trzy równoważne sposoby definiowania tej klasy zbiorów; badanie związków między tymi różnymi definicjami jest jedną z motywacji do studiowania teorii hiperarytmetycznej.

Zbiory hiperarytmetyczne i definiowalność

Pierwsza definicja zbiorów hiperarytmetycznych wykorzystuje hierarchię analityczną . Zbiór liczb naturalnych jest klasyfikowany na poziomie $z$ formuły arytmetyki drugiego rzędu tylko kwantyfikatorami zbioru egzystencjalnego i żadnym innym zbiorem kwantyfikatory. Zestaw jest klasyfikowany na poziomie ${\ Displaystyle \ Pi _ {1} ^ {1}}$ hierarchii analitycznej, jeśli można ją zdefiniować za pomocą formuły arytmetyki drugiego rzędu z tylko uniwersalnymi kwantyfikatorami zbiorów i bez innych kwantyfikatorów zbiorów. Zestaw jest ${\ Displaystyle \ Delta _ {1} ^ {1}}$ , jeśli jest zarówno ${\ Displaystyle \ Sigma _ {1} ^ {1}},$ jak i ${\ Displaystyle \ Pi _{1}^{1}}$ . Zbiory hiperarytmetyczne są dokładnie zbiorami. ${\ Displaystyle \ Delta _ {1} ^ {1}}$

Zbiory hiperarytmetyczne i iterowane skoki Turinga: hierarchia hiperarytmetyczna

Definicja zbiorów hiperarytmetycznych jako $zależy$ bezpośrednio od wyników Druga, równoważna definicja pokazuje, że zbiory hiperarytmetyczne można definiować za pomocą nieskończenie iterowanych skoków Turinga . Ta druga definicja pokazuje również, że zbiory hiperarytmetyczne można sklasyfikować w hierarchię rozszerzającą hierarchię arytmetyczną ; zbiory hiperarytmetyczne to dokładnie te zbiory, którym przypisano rangę w tej hierarchii.

Każdy poziom hierarchii hiperarytmetycznej jest indeksowany przez policzalną liczbę porządkową (porządkową), ale nie wszystkie policzalne liczby porządkowe odpowiadają poziomowi hierarchii. Liczby porządkowe używane przez hierarchię to te z notacją porządkową , która jest konkretnym, skutecznym opisem liczby porządkowej.

Notacja porządkowa to skuteczny opis policzalnej liczby porządkowej za pomocą liczby naturalnej. Do zdefiniowania hierarchii hiperarytmetycznej wymagany jest system notacji porządkowych. Podstawową właściwością, jaką musi mieć notacja porządkowa, jest to, że skutecznie opisuje ona liczbę porządkową w kategoriach mniejszych liczb porządkowych. Następująca definicja indukcyjna jest typowa; wykorzystuje funkcję parowania ${\ Displaystyle \ langle \ cdot, \ cdot \ rangle}$ .

Liczba 0 jest zapisem liczby porządkowej 0.
Jeśli n jest notacją dla porządkowej λ $dla$ λ + 1
Załóżmy, że δ jest graniczną liczbą porządkową . Notacja dla δ jest liczbą postaci ${\ Displaystyle \ langle 2, e \ rangle}$ , gdzie e jest indeksem całkowitej obliczalnej funkcji takiej jak ${\ Displaystyle \ phi _ {e}}$ że dla każdego n , ${\ Displaystyle \ phi _ {e} (n)}$ jest notacją dla liczby porządkowej λ _n mniejszej niż δ, a δ jest supem zbioru ${\ Displaystyle \ {\ lambda _ {n} \ środkowy n \ w \ mathbb {N} \}}$ .

Można to również zdefiniować, przyjmując efektywne łączenia na wszystkich poziomach, zamiast tylko notacji dla granicznych liczb porządkowych.

Istnieje tylko policzalnie wiele notacji porządkowych, ponieważ każda notacja jest liczbą naturalną; tak więc istnieje policzalna liczba porządkowa, która jest supremum wszystkich liczb porządkowych, które mają notację. $.$ znana jako liczba porządkowa Church- i Zauważ, że ta liczba porządkowa jest nadal policzalna, a symbol jest jedynie analogią do pierwszej niepoliczalnej liczby porządkowej, ${\ Displaystyle \ omega _ {1}}$ . Zbiór wszystkich liczb naturalnych, które są notacjami porządkowymi, oznaczamy ${\ Displaystyle {\ mathcal {O}}}$ i nazywał się Kleene's ${\ displaystyle {\ mathcal {O}}}$ .

Notacje porządkowe są używane do definiowania iterowanych skoków Turinga. Zbiory liczb naturalnych użyte do zdefiniowania hierarchii to $} }$ każdego . $do$ . ${\ Displaystyle 0 ^ {(\ delta)}}$ jest czasami również oznaczane ${\ Displaystyle H (\ delta)}$ lub dla oznaczenia ${\ Displaystyle H_ {e}}$ $}$ dla ${\ displaystyle \ delta}$ . Załóżmy, że δ ma oznaczenie e . Zbiory te zostały po raz pierwszy zdefiniowane przez Davisa (1950) i Mostowskiego (1951). Zbiór ${\ Displaystyle 0 ^ {(\ delta)}}$ jest zdefiniowany za pomocą e w następujący sposób.

Jeśli δ = 0, to ${\ Displaystyle 0 ^ {(\ delta)} = 0}$ jest zbiorem pustym.
Jeśli δ = λ + 1, to ${\ Displaystyle 0 ^ {(\ delta)}}$ jest skokiem Turinga z ${\ Displaystyle 0 ^ {(\ lambda)}}$ . Zbiory i odpowiednio ${\ Displaystyle 0 ^ {(1)}$ } $0''$ $( 2 ) {$ \ $0'$ and , respectively.
Jeśli δ jest graniczną liczbą porządkową, niech będzie sekwencją liczb porządkowych mniejszą niż δ określoną przez ${\ Displaystyle \ langle \ lambda _ {n} \ mid n \ in \ mathbb {N} \ rangle}$ notacja e . Zbiór ${\ Displaystyle 0 ^ {(\ delta)}}$ jest określony przez regułę ${\ Displaystyle 0 ^ {(\ delta)} = \ {\ langle n, i \ rangle \ mid i \ in 0 ^ {(\ lambda _ {n})} \}}$ . To jest efektywne połączenie zbiorów ${\ Displaystyle 0 ^ {(\ lambda _ {n})}}$ .

Chociaż konstrukcja zależy od posiadania ustalonej notacji dla δ ${ \ displaystyle 0 ^ {(\ delta)}} zależy$ $,$ nieskończona liczba porządkowa ma wiele notacji, twierdzenie Spectora pokazuje stopień Turinga $jest$ , a nie od konkretnej użytej notacji, a zatem dobrze zdefiniowany aż do stopnia Turinga

Hierarchia hiperarytmetyczna jest definiowana na podstawie tych iterowanych skoków Turinga. Zbiór X jest klasyfikowany na poziomie δ hierarchii hiperarytmetycznej, dla ${\ Displaystyle \ delta <\ omega _ {1} ^ {CK}}$ , jeśli X jest redukowalny przez Turinga do ${\ Displaystyle 0 ^ {(\ delta)}}$ . Zawsze będzie przynajmniej takie δ, jeśli takie istnieje; to właśnie to najmniejsze δ mierzy poziom nieobliczalności X .

Zbiory hiperarytmetyczne i rekurencja w typach wyższych

Trzecia charakterystyka zbiorów hiperarytmetycznych, za sprawą Kleene, wykorzystuje obliczalne funkcjonały wyższego typu . $_$ typu _ zasady:

{\ Displaystyle {} ^ {2} E (f) = 1 \ quad},

jeśli istnieje ja takie, że fa ( ja ) > 0,

{\ Displaystyle {} ^{2}E(f)=0\quad }

jeśli nie ma i takiego, że f ( i ) > 0.

Używając precyzyjnej definicji obliczalności w odniesieniu do funkcjonału typu 2, Kleene wykazał, że zbiór liczb naturalnych jest hiperarytmetyczny wtedy i tylko wtedy, gdy jest obliczalny względem ${\ displaystyle {} ^ {2} e}$ .

Przykład: zbiór prawdy arytmetyki

Każdy zbiór arytmetyczny jest hiperarytmetyczny, ale istnieje wiele innych zbiorów hiperarytmetycznych. Jednym z przykładów zestawu hiperarytmetycznego, niearytmetycznego jest zbiór T liczb Gödla formuł arytmetyki Peano , które są prawdziwe w standardowych liczbach naturalnych. ${\ displaystyle \ mathbb {N}}$ . Zbiór T jest odpowiednikiem Turinga zbioru , a więc nie znajduje się wysoko w hierarchii hiperarytmetycznej, chociaż nie można $go$ Twierdzenie Tarskiego o niedefiniowalności .

Podstawowe wyniki

Podstawowe wyniki teorii hiperarytmetyki pokazują, że trzy powyższe definicje definiują ten sam zbiór zbiorów liczb naturalnych. Te równoważności wynikają z Kleene.

Wyniki kompletności są również fundamentalne dla teorii. Zbiór liczb naturalnych jest ${1} ^$ ${1}$ 1 1 \ Displaystyle a każdy $zbiór$ liczb naturalnych jest -jeden redukowalny niego Definicja pełnego podzbioru przestrzeni Baire'a ( ${\ Displaystyle \ Pi _ {1} ^ {1}}$ ${\ Displaystyle \ mathbb {N} ^ {\ mathbb {N}}}$ ) jest podobny. Kilka zestawów związanych z teorią hiperarytmetyczną jest kompletnych: ${\ Displaystyle \ Pi _ {1} ^ {1}}$

Kleene's , zbiór liczb naturalnych, które są zapisami liczb porządkowych ${\ displaystyle {\ mathcal {O}}}$
Zbiór liczb naturalnych e $,$ że funkcja obliczalna liczb naturalnych Są to indeksy rekurencyjnych liczb porządkowych .
Zbiór elementów przestrzeni Baire'a , które są charakterystycznymi funkcjami dobrego uporządkowania liczb naturalnych (przy użyciu efektywnego izomorfizmu) ${\ Displaystyle \ mathbb {N} ^ {\ mathbb {N}} \ cong \mathbb {N} ^{\mathbb {N} \times \mathbb {N} })}$ .

kompletności $ograniczenia$ znane jako z tych wyników Dla każdego $zestawu$ notacji porządkowych istnieje $}$ ${\ Displaystyle \ alpha <\ omega _ {1}$ { } tak, że każdy element S jest notacją dla liczby porządkowej mniejszej niż ${\ displaystyle \ alpha}$ . Dla dowolnego ${\ Displaystyle \ Sigma _ {1} ^ {1}}$ podzbiór T przestrzeni Baire'a składający się tylko z charakterystycznych funkcji uporządkowania studni, istnieje ${\ Displaystyle \ alfa <\ omega _ {1} ^ {CK}}$ tak, że każda liczba porządkowa reprezentowana w T jest mniejsza niż ${\ displaystyle \ alpha}$ .

Relatywizowana hiperarytmetyczność i hiperstopnie

Definicję można zrelatywizować do zbioru X liczb naturalnych: w definicji $notacji porządkowej klauzula dotycząca liczb porządkowych granicznych jest$ tak, że obliczalne wyliczenie ciągu notacje porządkowe mogą używać X jako wyroczni. Zbiór liczb, które są notacjami porządkowymi względem X , jest oznaczony ${\ displaystyle {\ mathcal {O}} ^ {X}}$ . Supremum liczb porządkowych reprezentowanych w jest oznaczone ${\ Displaystyle {\ mathcal {O}} ^ {X}}$ ${\ Displaystyle \ omega _ {1} ^ {X}}$ ; jest to policzalna liczba porządkowa nie mniejsza niż ${\ Displaystyle \ omega _ {1} ^ {CK}}$ .

Definicję $zbioru$ zrelatywizować do $.$ naturalnych Jedyna zmiana w definicji polega na tym, że definiuje się $= X ′ {\ Displaystyle X ^ {(1)}$ jako $)}=X'}$ ${\ Displaystyle X ^ {(0)}$ } to skok Turinga dla X , i tak dalej. Zamiast kończyć się na ${\ Displaystyle \ omega _ {1} ^ {CK}}$ hierarchia względem X przebiega przez wszystkie liczby porządkowe mniejsze niż ${\ Displaystyle \ omega _ {1} ^ {X}}$ .

Relatywizowana hierarchia hiperarytmetyczna służy do definiowania redukowalności hiperarytmetycznej . Biorąc pod uwagę zbiory X i Y , mówimy $^ {Y}}$ $Y {\$ wtedy, gdy istnieje $<\ omega$ takie, że X jest redukowalne przez Turinga do ${\ Displaystyle Y ^ {(\ delta)}}$ . Jeśli ${\ Displaystyle X \ równoważnik _ {HYP} Y}$ i ${\ Displaystyle Y \ równoważnik _ {HYP} X},$ a następnie zapis ${\ Displaystyle X \ równoważnik _{HYP}Y}$ służy do wskazania, że X i Y są hiperarytmetycznie równoważne . Jest to bardziej zgrubna relacja równoważności niż równoważność Turinga ; na przykład każdy zestaw liczb naturalnych jest hiperarytmetycznie równoważny skokowi Turinga , ale nie jest odpowiednikiem skoku Turinga. Klasy równoważności równoważności hiperarytmetycznej są znane jako hiperstopnie .

Funkcja, która przyjmuje zbiór, jest znana jako $hiperskok$ przez skoku Turinga. Ustalono wiele właściwości hiperskoku i hiperstopni. W szczególności wiadomo, że problem Posta dla hiperstopni ma pozytywną odpowiedź: dla każdego zbioru X liczb naturalnych istnieje zbiór Y takich liczb naturalnych, że ${\ Displaystyle X <_ {HYP} Y <_ {HYP} {\ mathcal {O}} ^ {X}}$ .

Uogólnienia

Teorię hiperarytmetyczną uogólnia teoria α-rekursji , która zajmuje się badaniem definiowalnych podzbiorów dopuszczalnych liczb porządkowych . Teoria hiperarytmetyczna jest szczególnym przypadkiem, w którym α wynosi ${\ Displaystyle \ omega _ {1} ^ {CK}}$ .

Stosunek do innych hierarchii

Jasna twarz		Pogrubiona czcionka
⁰ ₀⁰ ₀⁰ ₀ Σ = Π = Δ (czasami to samo co Δ ⁰ ₁ )		Σ ⁰ ₀ = Π ⁰ ₀ = Δ ⁰ ₀ (jeśli zdefiniowano)
Δ ⁰ ₁ = rekurencyjny		Δ ⁰ ₁ = domknięty
Σ ⁰ ₁ = rekurencyjnie przeliczalny	Π ⁰ ₁ = współrekurencyjnie przeliczalny	Σ ⁰ ₁ = G = otwarte	Π ⁰ ₁ = 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
⋮		⋮

H. Rogers, Jr., 1967. Theory of Recursive Functions and Effective Computability , wydanie drugie 1987, MIT Press. ISBN 0-262-68052-1 (miękka okładka), ISBN 0-07-053522-1
G. Sacks, 1990. Teoria wyższej rekurencji , Springer-Verlag. ISBN 3-540-19305-7
S. Simpson, 1999. Podsystemy arytmetyki drugiego rzędu , Springer-Verlag.
CJ Ash, JF Knight , 2000. Struktury obliczeniowe i hierarchia hiperarytmetyczna , Elsevier. ISBN 0-444-50072-3

Cytaty

Linki zewnętrzne

Opisowa teoria mnogości . Notatki Davida Markera z University of Illinois w Chicago. 2002.
Logika matematyczna II . Notatki Daga Normanna z Uniwersytetu w Oslo. 2005.
Antonio Montalbán: twórca treści z Uniwersytetu Kalifornijskiego w Berkeley i YouTube