stopień PA

W matematycznej dziedzinie teorii obliczalności stopień PA jest stopniem Turinga , który oblicza pełne rozszerzenie arytmetyki Peano (Jockusch 1987). Te stopnie są ściśle związane z funkcjami bez punktów stałych (DNR) i zostały dokładnie zbadane w teorii rekurencji.

Tło

W teorii rekurencji ${B }}$ { \ Displaystyle $\$ phi { oznacza funkcję obliczalną e , która używa zbioru B liczb naturalnych jako wyroczni.

Zbiór A liczb naturalnych jest redukowalny przez Turinga do zbioru B , jeśli istnieje obliczalna funkcja , która, biorąc pod uwagę wyrocznię dla zbioru B , oblicza funkcję charakterystyczną χ _A zbioru A. Oznacza to, że istnieje e takie , że ${\ Displaystyle \ chi _ {A} = \ phi _ {e} ^ {B}}$ . Ta zależność jest oznaczona jako A ≤ _TB ; relacja ≤ _T jest w przedsprzedaży .

Dwa zestawy liczb naturalnych są równoważne Turingowi , jeśli każdy z nich można zredukować do drugiego. Notacja A ≡ _TB wskazuje, że A i B są równoważne Turingowi. Relacja ≡ _T jest relacją równoważności znaną jako równoważność Turinga. Stopień Turinga to zbiór zbiorów liczb naturalnych, taki, że dowolne dwa zbiory w zbiorze są równoważne Turingowi. Równoważnie stopień Turinga jest klasą równoważności relacji ≡ _T .

Stopnie Turinga są częściowo uporządkowane przez redukowalność Turinga. Notacja a ≤ _T b wskazuje, że istnieje zbiór w stopniu b , który oblicza zbiór w stopniu a . Równoważnie, a ≤ _T b zachodzi wtedy i tylko wtedy, gdy każdy zbiór w b oblicza każdy zbiór w a .

że funkcja f od liczb naturalnych do liczb naturalnych jest diagonalnie nierekurencyjna (DNR) , jeśli dla wszystkich n , ${\ Displaystyle f (n) \ not = \ phi _ { n} (n)} (tutaj$ $)$ jeśli . Jeśli zakres f jest zbiorem {0,1}, to f jest DNR ₂ funkcjonować. Wiadomo, że istnieją funkcje DNR, które nie obliczają żadnej funkcji DNR ₂ .

Uzupełnienia arytmetyki Peano

Uzupełnieniem arytmetyki Peano jest zestaw formuł w języku arytmetyki Peano, taki, że zbiór jest spójny w logice pierwszego rzędu i taki, że dla każdej formuły albo ta formuła, albo jej zaprzeczenie jest zawarte w zbiorze. Po ustaleniu numeracji Gödla formuł w języku PA można identyfikować uzupełnienia PA ze zbiorami liczb naturalnych, a tym samym mówić o obliczalności tych uzupełnień.

0 Stopień Turinga jest definiowany jako stopień PA , jeśli istnieje zbiór liczb naturalnych w stopniu, który oblicza zakończenie arytmetyki Peano. (Jest to równoważne twierdzeniu, że każdy zbiór w stopniu oblicza uzupełnienie PA.) Ponieważ nie ma obliczalnych uzupełnień PA, stopień składający się z obliczalnych zbiorów liczb naturalnych nie jest stopniem PA.

Ponieważ PA jest skuteczną teorią pierwszego rzędu, uzupełnienia PA można scharakteryzować jako nieskończone ścieżki przez określone poddrzewo obliczeniowe 2 ^<ω . Zatem stopnie PA są dokładnie tymi stopniami, które obliczają nieskończoną ścieżkę przez to drzewo.

Nieruchomości

Stopnie PA są zamknięte w górę w stopniach Turinga: jeśli a jest stopniem PA, a a ≤ _T b , to b jest stopniem PA.

000 Stopień Turinga , który jest stopniem problemu zatrzymania , jest stopniem PA. Istnieją również stopnie PA, które nie są wyższe niż „. Na przykład twierdzenie o niskiej podstawie implikuje, że istnieje niski stopień PA. Z drugiej strony Antonín Kučera udowodnił, że istnieje stopień mniejszy niż ', który oblicza funkcję DNR, ale nie jest stopniem PA (Jockusch 1989:197).

Carl Jockusch i Robert Soare (1972) udowodnili, że stopnie PA są dokładnie stopniami funkcji DNR ₂ .

Z definicji stopień jest PA wtedy i tylko wtedy, gdy oblicza ścieżkę przez drzewo uzupełnień arytmetyki Peano. Silniejsza właściwość zachodzi: stopień a jest stopniem PA wtedy i tylko wtedy, gdy a oblicza ścieżkę przez każde nieskończone obliczalne poddrzewo 2 ^<ω (Simpson 1977).

Kryterium kompletności Arslanowa

$)$ charakterystykę, które zestawy ce są kompletne (tj. odpowiednik . Dla zestawu ce ${\ Displaystyle A \ subseteq \ mathbb {N}}$ , ${\ Displaystyle A \ równoważnik _ {\ operatorname {T}} \ varnothing '}$ wtedy i tylko wtedy, gdy ${\ ce displaystyle A}$ oblicza funkcję DNR. W szczególności każdy stopień PA to DNR ₂ , a zatem DNR, więc ${\ displaystyle \ varnothing '}$ to jedyny stopień ce PA.

Zobacz też

Carl Jockusch (1987), „Stopnie funkcji bez punktów stałych”, Logic Colloquium '87 , Fenstad, Frolov i Hilpinen, red., North-Holland, ISBN 0-444-88022-4
⁰ Carl Jockusch i Robert Soare (1972), „Π ₁ klasy i stopnie teorii”, Transactions of the American Mathematical Society , t. 173, s. 33–56.
Stephen G. Simpson (1977), „Stopnie nierozwiązywalności: przegląd wyników”, Handbook of Mathematical Logic , Barwise (red.), North-Holland, s. 631–652. ISBN 0-444-86388-5