Teoria hiperarytmetyczna - Hyperarithmetical theory

W teorii rekursji , teoria hyperarithmetic jest uogólnieniem Turinga obliczalności . Ma ścisły związek z definiowalnością w arytmetyce drugiego rzędu oraz ze słabymi systemami teorii mnogości, takimi jak teoria mnogości Kripkego-Platka . Jest to ważne narzędzie w efektywnej opisowej teorii mnogości .

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

Zbiory hiperarytmetyczne i definiowalność

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

Zbiory hiperarytmetyczne i iterowane skoki Turinga: hierarchia hiperarytmetyczna

Definicja zbiorów hiperarytmetycznych jako nie zależy bezpośrednio od wyników obliczalności. Druga, równoważna definicja pokazuje, że zbiory hiperarytmetyczne można zdefiniować za pomocą nieskończenie iterowanych skoków Turinga . Ta druga definicja pokazuje również, że zbiory hiperarytmetyczne można zaklasyfikować do hierarchii rozszerzającej hierarchię arytmetyczną ; zbiory hiperarytmetyczne to dokładnie te zbiory, którym przypisano rangę w tej hierarchii. ${\ Displaystyle \ Delta _ {1} ^ {1}}$

Każdy poziom hierarchii hiperarytmetycznej odpowiada policzalnej liczbie porządkowej ( liczba porządkowa), ale nie wszystkie policzalne liczby porządkowe odpowiadają poziomowi hierarchii. Numerami porządkowymi używanymi przez hierarchię są te z notacją porządkową , która jest konkretnym, efektywnym opisem liczby porządkowej.

Notacja porządkowa to efektywny opis liczby porządkowej policzalnej przez liczbę naturalną. Do zdefiniowania hierarchii hiperarytmetycznej potrzebny jest system notacji porządkowych. Podstawową właściwością, jaką musi mieć notacja porządkowa, jest to, że opisuje ona liczbę porządkową w kategoriach małych liczb porządkowych w efektywny sposób. Poniższa 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 λ, to jest notacją dla λ + 1; ${\ Displaystyle \ langle 1, n \ rangle }$
Załóżmy, że δ jest liczbą porządkową graniczną . Notacja dla δ jest liczbą postaci , gdzie e jest indeksem całkowitej obliczalnej funkcji tak , że dla każdego n , jest notacją dla liczby porządkowej λ _n mniejszej niż δ , a δ jest nadrzędną częścią zbioru . ${\ Displaystyle \ langle 2, e \ rangle }$ $\phi _{e}$ ${\ Displaystyle \ _ {e} (n)}$ ${\ Displaystyle \ {\ lambda _ {n} \ mid n \ w \ mathbb {N} \}}$

Istnieje tylko przeliczalnie wiele notacji porządkowych, ponieważ każdy zapis jest liczbą naturalną; tak więc istnieje policzalna liczba porządkowa, która jest najwyższą wartością wszystkich liczb porządkowych, które mają notację. Ta liczba porządkowa jest znana jako liczba porządkowa Church-Kleene i jest oznaczona . Zauważ, że ta liczba porządkowa jest nadal policzalna, symbol jest tylko analogią z pierwszą niepoliczalną liczbą porządkową, . Zbiór wszystkich liczb naturalnych będących notacjami porządkowymi jest oznaczony i nazwany Kleene's . ${\ Displaystyle \ omega _ {1} ^ {CK}}$ $\omega_{1}$ ${\ Displaystyle {\ Mathcal {O}}}$ ${\ Displaystyle {\ Mathcal {O}}}$

Notacje porządkowe służą do definiowania iterowanych skoków Turinga. Są to zbiory liczb naturalnych oznaczonych dla każdego . Załóżmy, że δ ma notację e . Zbiór jest zdefiniowany za pomocą e w następujący sposób. ${\ Displaystyle 0 ^ {(\ delta )}}$ ${\ Displaystyle \ delta <\ omega _ {1} ^ {CK}}$ ${\ Displaystyle 0 ^ {(\ delta )}}$

Jeśli δ = 0, to jest pustym zbiorem. ${\ Displaystyle 0 ^ {(\ delta )} = 0}$
Jeśli δ = λ + 1 to jest skok Turinga . Notacje i są powszechnie używane odpowiednio dla i . ${\ Displaystyle 0 ^ {(\ delta )}}$ ${\ Displaystyle 0 ^ {(\ lambda )}}$ $0'$ $0''$ ${\ Displaystyle 0 ^ {(1)}}$ ${\ Displaystyle 0 ^ {(2)}}$
Jeśli δ jest porządkową graniczną, niech będzie ciągiem liczb porządkowych mniejszych niż δ podanym w notacji e . Zestaw podaje reguła . To jest efektywne łączenie zbiorów . ${\ Displaystyle \ langle \ lambda _ {n} \ mid n \ w \ mathbb {N} \ rangle}$ ${\ Displaystyle 0 ^ {(\ delta )}}$ ${\ Displaystyle 0 ^ {(\ delta )} = \ {\ langle n ja \ rangle \ mid ja \ w 0 ^ {(\ lambda _ {n})} \}}$ ${\ Displaystyle 0 ^ {(\ lambda _ {n})}}$

Chociaż budowa zależy ze stałą notację §, a każdy nieskończona liczba porządkowa ma wiele zapisów, twierdzenie występów Spector że stopień Turinga od zależy tylko §, a nie na konkretnej notacji, a zatem jest dobrze zdefiniowany do stopień Turinga. ${\ Displaystyle 0 ^ {(\ delta )}}$ ${\ Displaystyle 0 ^ {(\ delta )}}$ ${\ Displaystyle 0 ^ {(\ delta )}}$

Hierarchia hiperarytmetyczna jest zdefiniowana z tych iterowanych skoków Turinga. Zbiór X liczb naturalnych jest klasyfikowany na poziomie δ hierarchii hiperarytmetycznej, dla , jeśli X jest redukowalną Turinga do . Zawsze będzie przynajmniej taki δ, jeśli taki istnieje; to najmniej δ mierzy poziom nieobliczalności X . ${\ Displaystyle \ delta <\ omega _ {1} ^ {CK}}$ ${\ Displaystyle 0 ^ {(\ delta )}}$

Zbiory hiperarytmetyczne i rekurencja w wyższych typach

Trzecia charakterystyka zbiorów hiperarytmetycznych, autorstwa Kleene'a, wykorzystuje funkcjonały obliczalne wyższego typu . Funkcjonalność typu 2 określają następujące zasady: ${\ Displaystyle {} ^ {2} E \ dwukropek \ mathbb {N} ^ {\ mathbb {N}} \ do \ mathbb {N}}$

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

jeśli istnieje i takie, że f ( i ) > 0,

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

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

Używając precyzyjnej definicji obliczalności względem 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 zbioru hiperarytmetycznego, niearytmetycznego jest zbiór T liczb Gödla formuł arytmetyki Peano, które są prawdziwe w standardowych liczbach naturalnych . Zbiór T jest Turingowym odpowiednikiem zbioru , a więc nie znajduje się wysoko w hierarchii hiperarytmetycznej, chociaż nie jest arytmetycznie zdefiniowany przez twierdzenie Tarskiego o niedefiniowalności . ${\ Displaystyle \ mathbb {N}}$ ${\ Displaystyle 0 ^ {(\ omega )}}$

Podstawowe wyniki

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

Wyniki dotyczące kompletności mają również fundamentalne znaczenie dla teorii. Zbiór liczb naturalnych jest kompletna , jeśli jest na poziomie od hierarchii analitycznej i każdego zbioru liczb naturalnych jest wiele jeden sprowadzić do niego. Definicja pełnego podzbioru przestrzeni Baire'a ( ) jest podobna. Kilka zestawów związanych z teorią hiperarytmetyczną jest kompletnych: ${\ Displaystyle \ Pi _ {1} ^ {1}}$ ${\ Displaystyle \ Pi _ {1} ^ {1}}$ ${\ Displaystyle \ Pi _ {1} ^ {1}}$ ${\ Displaystyle \ Pi _ {1} ^ {1}}$ ${\ Displaystyle \ mathbb {N} ^ {\ mathbb {N}}}$ ${\ Displaystyle \ Pi _ {1} ^ {1}}$

Kleene'a , zbiór liczb naturalnych będących notacjami dla liczb porządkowych ${\ Displaystyle {\ Mathcal {O}}}$
Zbiór liczb naturalnych e taki, że funkcja obliczalna oblicza funkcję charakterystyczną dobrego uporządkowania liczb naturalnych. Są to wskaźniki rekurencyjnych liczb porządkowych . ${\ Displaystyle \ phi _ {e} (x, y)}$
Zbiór elementów przestrzeni Baire'a, które są funkcjami charakterystycznymi dobrego uporządkowania liczb naturalnych (za pomocą efektywnego izomorfizmu . ${\ Displaystyle \ mathbb {N} ^ {\ mathbb {N}} \ cong \ mathbb {N} ^ {\ mathbb {N} \ razy \ mathbb {N}})}$

Wyniki znane jako ograniczenia wynikają z tych wyników kompletności. Dla dowolnego zbioru S notacji porządkowych istnieje taki, że każdy element S jest notacją dla liczby porządkowej mniejszej niż . Dla dowolnego podzbioru T przestrzeni Baire'a składającego się tylko z funkcji charakterystycznych dobrze uporządkowanych istnieje taki, że każda liczba porządkowa reprezentowana w T jest mniejsza niż . ${\ Displaystyle \ Sigma _ {1} ^ {1}}$ ${\ Displaystyle \ Sigma _ {1} ^ {1}}$ ${\ Displaystyle \ alfa <\ omega _ {1} ^ {CK}}$ ${\ Displaystyle \ alfa}$ ${\ Displaystyle \ Sigma _ {1} ^ {1}}$ ${\ Displaystyle \ alfa <\ omega _ {1} ^ {CK}}$ ${\ Displaystyle \ alfa}$

Zrelatywizowana hiperarytmetyka i hiperstopnie

Definicję z można zrelatywizować do zbioru X liczb naturalnych: w definicji zapisu porządkowego zmieniono klauzulę dotyczącą granicznych liczb porządkowych tak, że wyliczenie obliczalne ciągu zapisów porządkowych może używać X jako wyroczni. Zbiór liczb, które są notacją porządkową względem X, jest oznaczony . Najwyższe liczby porządkowe reprezentowane w jest oznaczone ; jest to liczba porządkowa policzalna nie mniejsza niż . ${\ Displaystyle {\ Mathcal {O}}}$ ${\ Displaystyle {\ Mathcal {O}} ^ {X}}$ ${\ Displaystyle {\ Mathcal {O}} ^ {X}}$ ${\ Displaystyle \ omega _ {1} ^ {X}}$ ${\ Displaystyle \ omega _ {1} ^ {CK}}$

Definicję można również zrelatywizować do dowolnego zbioru liczb naturalnych. Jedyną zmianą w definicji jest to, że jest ona zdefiniowana jako X, a nie pusty zbiór, więc jest to skok Turinga X i tak dalej. Zamiast kończyć się w hierarchii względem X, przechodzi przez wszystkie liczby porządkowe mniejsze niż . ${\ Displaystyle 0 ^ {(\ delta )}}$ ${\ Displaystyle X}$ ${\ Displaystyle X ^ {(0)}}$ ${\ Displaystyle X ^ {(1)} = X'}$ ${\ Displaystyle \ omega _ {1} ^ {CK}}$ ${\ Displaystyle \ omega _ {1} ^ {X}}$

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

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

Uogólnienia

Teoria hiperarytmetyczna jest uogólniona przez teorię α-rekurencji , która jest badaniem definiowalnych podzbiorów dopuszczalnych liczb porządkowych . Teoria hiperarytmetyczna jest szczególnym przypadkiem, w którym α jest . ${\ Displaystyle \ omega _ {1} ^ {CK}}$

Stosunek do innych hierarchii

Jasna twarz		Pogrubienie
Σ⁰ ₀ =⁰ ₀ =⁰ ₀ (czasami to samo co Δ⁰ ₁)		Σ⁰ ₀= Π⁰ ₀= Δ⁰ ₀ (jeśli zdefiniowano)
Δ⁰ ₁= rekurencyjne		Δ⁰ ₁= clopen
Σ⁰ ₁= rekurencyjnie przeliczalne	Π⁰ ₁ = współrekurencyjnie przeliczalny	Σ⁰ ₁= G = otwarte	Π⁰ ₁= F = zamknięte
Δ⁰ ₂		Δ⁰ ₂
Σ⁰ ₂	Π⁰ ₂	Σ⁰ ₂= F _σ	Π⁰ ₂= G _δ
Δ⁰ ₃		Δ⁰ ₃
Σ⁰ ₃	Π⁰ ₃	Σ⁰ ₃= G _δσ	Π⁰ ₃= F _σδ
⋮		⋮
Σ⁰ _<ω =⁰ _<ω =⁰ _<ω =¹ ₀ =¹ ₀ =¹ ₀= arytmetyczne		Σ⁰ _<ω= Π⁰ _<ω= Δ⁰ _<ω= Σ¹ ₀= Π¹ ₀= Δ¹ ₀ = arytmetyka pogrubiona
⋮		⋮
Δ⁰ _α(α rekurencyjne )		Δ⁰ _α( policzalne α )
Σ⁰ _α	Π⁰ _α	Σ⁰ _α	Π⁰ _α
⋮		⋮
Σ⁰ _ω^CK ₁ =⁰ _ω^CK ₁ =⁰ _ω^CK ₁ =¹ ₁= hiperarytmetyczny		Σ⁰ _{ω ₁}= Π⁰ _{ω ₁}= Δ⁰ _{ω ₁}= Δ¹ ₁= B = Borel
Σ¹ ₁ = analiza jasnej powierzchni	Π¹ ₁ = koanalityczna jasna powierzchnia	Σ¹ ₁= A = analityczny	Π¹ ₁= CA = koanalityczny
Δ¹ ₂		Δ¹ ₂
Σ¹ ₂	Π¹ ₂	Σ¹ ₂ = PCA	Π¹ ₂ = CPCA
Δ¹ ₃		Δ¹ ₃
Σ¹ ₃	Π¹ ₃	Σ¹ ₃ = PCPCA	Π¹ ₃ = CPCPCA
⋮		⋮
Σ¹ _<ω =¹ _<ω =¹ _<ω =² ₀ =² ₀ =² ₀= analityczny		Σ¹ _<ω= Π¹ _<ω= Δ¹ _<ω= Σ² ₀= Π² ₀= Δ² ₀= P = rzutowe
⋮		⋮

Bibliografia

H. Rogers, Jr., 1967. Teoria funkcji rekurencyjnych i efektywnej obliczalności , wydanie drugie 1987, MIT Press. ISBN 0-262-68052-1 (miękka okładka ), ISBN 0-07-053522-1
G. Sacks, 1990. Wyższa teoria 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

Zewnętrzne linki

Opisowa teoria mnogości . Notatki Davida Markera, University of Illinois w Chicago. 2002.
Logika matematyczna II . Notatki Daga Normanna, Uniwersytet w Oslo. 2005.

Languages

In other projects