Zestawy kreatywne i produktywne

W teorii obliczalności zbiory produktywne i zbiory kreatywne to typy zbiorów liczb naturalnych , które mają ważne zastosowania w logice matematycznej . Są standardowym tematem w podręcznikach logiki matematycznej, takich jak Soare (1987) i Rogers (1987) .

Definicja i przykład

W pozostałej części tego artykułu załóżmy, że $rekurencyjnie$ dopuszczalną numeracją funkcji obliczalnych , a W _ja odpowiednią numeracją przeliczalnych .

Zbiór A liczb naturalnych nazywamy produktywnym $,$ jeśli istnieje całkowita rekurencyjna (obliczalna) funkcja ${\ displaystyle f}$ tak, że jeśli ${\ Displaystyle W_ {i} \ subseteq A}$ wtedy ${\ displaystyle f (i) \ in A \ setminus W_ {i}.}$ Funkcja ${\ displaystyle f}$ nazywana jest funkcją produktywną dla ${\ Displaystyle A.}$

Zbiór A liczb $,$ nazywamy kreatywnym jeśli A jest rekurencyjnie przeliczalny, a jego uzupełnienie . Jednak nie każdy produktywny zestaw ma rekurencyjnie przeliczalne uzupełnienie, jak pokazano poniżej.

Archetypowym $_$ _ _ _ Jego dopełnienie jest produktywne z funkcją produkcyjną fa ( ja ) ${\ Displaystyle {\ bar {K}} = \ {i \ mid i \ not \ in W_ {i} \}}$ = i (funkcja tożsamościowa).

Aby to zobaczyć, stosujemy definicję funkcji produkcyjnej i osobno pokazujemy, że ${\ Displaystyle i \ w {\ bar {K}}}$ i ${\ Displaystyle i \ nie \ w W_ {i }}$ :

${\ Displaystyle i \ in {\ bar {K}}}$ : załóżmy, że ${\ Displaystyle i \ w K}$ , wtedy ${\ Displaystyle i \ w W_ {i}}$ , teraz biorąc pod uwagę, że $\ Displaystyle i \ in {\ bar {K}}}$ ja prowadzi to do sprzeczności W ja ⊆ K. ¯ {\ Displaystyle W_ {i $\ bar {K}}}$ . więc ${\ Displaystyle i \ w {\ bar {K}}}$ .
${\ Displaystyle i \ nie \ w W_ {i}}$ : w rzeczywistości, gdyby ${\ Displaystyle i \ in W_ {i}}$ , to byłoby prawdą, że ${\ Displaystyle i \in K}$ , ale w poprzednim punkcie wykazaliśmy coś przeciwnego. więc ${\ Displaystyle i \ nie \ w W_ {i}}$ .

Nieruchomości

Żaden produktywny zbiór A nie może być rekurencyjnie przeliczalny, ponieważ ilekroć A zawiera każdą liczbę w zbiorze W _i zawiera inne liczby, a ponadto istnieje efektywna procedura wytworzenia przykładu takiej liczby z indeksu i . Podobnie żaden zbiór kreatywny nie może być rozstrzygalny , ponieważ oznaczałoby to, że jego dopełnienie, zbiór produktywny, jest rekurencyjnie przeliczalny.

Każdy produktywny zestaw ma funkcję produkcyjną, która jest iniekcyjna i całkowita .

Poniższe twierdzenia, pochodzące od Myhilla (1955), pokazują, że w pewnym sensie wszystkie zestawy kreatywne są podobne, a wszystkie zestawy produkcyjne są podobne do $displaystyle$ ${\ bar {K}}}$ .

Twierdzenie. Niech P będzie zbiorem liczb naturalnych. Następujące są równoważne:

P jest produktywny.
$K}}}$ { jest 1-redukowalny do P.
${\ Displaystyle {\ bar {K}}}$ jest m-redukowalny do P. .

Twierdzenie. Niech C będzie zbiorem liczb naturalnych. Następujące są równoważne:

C jest kreatywny.
C jest 1-zupełne
C jest rekurencyjnie izomorficzne z K , to znaczy istnieje całkowita obliczalna bijekcja f na liczbach naturalnych taka, że f ( C ) = K .

Zastosowania w logice matematycznej

Zbiór wszystkich dających się udowodnić zdań w efektywnym systemie aksjomatycznym jest zawsze zbiorem rekurencyjnie przeliczalnym . Jeśli system jest odpowiednio złożony, jak arytmetyka pierwszego rzędu , to zbiór T liczb Gödla zdań prawdziwych w systemie będzie zbiorem produktywnym, co oznacza, że ilekroć W jest rekurencyjnie przeliczalnym zbiorem zdań prawdziwych, istnieje co najmniej jedno zdanie prawdziwe, którego nie ma w W. Można to wykorzystać do ścisłego dowodu pierwszego twierdzenia Gödla o niezupełności , ponieważ żaden rekurencyjnie przeliczalny zbiór nie jest produktywny. Dopełnienie zbioru T nie będzie rekurencyjnie przeliczalne, a zatem T jest przykładem zbioru produktywnego, którego uzupełnienie nie jest twórcze.

Historia

Przełomowy artykuł Posta (1944) zdefiniował koncepcję, którą nazwał zestawem kreatywnym. Powtarzając, zbiór $wymieniony$ powyżej i zdefiniowany jako dziedzina funkcji ${\ Displaystyle d (x) = [[x]] ($ , który bierze przekątną wszystkich wyliczonych 1-miejscowych obliczalnych funkcji częściowych i dodaje do nich 1, jest przykładem zbioru kreatywnego. Post podał wersję twierdzenia Gödla o niezupełności, używając jego zbiorów twórczych, w których pierwotnie Gödel w pewnym sensie skonstruował zdanie, które można swobodnie przetłumaczyć jako mówiące: „Jestem nie do udowodnienia w tej teorii aksjomatycznej”. Jednak dowód Gödla nie działał z koncepcją zdań prawdziwych, a raczej wykorzystywał koncepcję spójnej teorii, co doprowadziło do drugiego twierdzenia o niezupełności . Po tym, jak Post zakończył swoją wersję niekompletności, dodał, co następuje:

„Wniosek jest nieunikniony, że nawet w przypadku tak ustalonego, dobrze zdefiniowanego zbioru twierdzeń matematycznych myślenie matematyczne jest i musi pozostać zasadniczo twórcze”.

Zwykły zestaw kreatywny $zdefiniowany$ funkcji diagonalnej swój własny $rozwój$ Alan Turing $funkcję$ artykule z 1936 roku na temat maszyny Turinga wykazał istnienie uniwersalnego komputera, który oblicza . Funkcja jest zdefiniowana w taki sposób, że ( $}$ zastosowania instrukcji zakodowanych przez $\$ wejścia $Displaystyle \ Phi (w, x) =$ ${\ displaystyle x}$ ${\ Displaystyle f (x) = \ Phi ( e, x)}$ i jest uniwersalna w tym sensie, że każda obliczalna funkcja częściowa $jest$ dana przez dla wszystkich gdzie $koduje$ ${\ displaystyle e}$ instrukcje dla ${\ displaystyle f$ . $_$ powyższej _ ${\ Displaystyle d (x) = [[x]] (x) + 1}$ . Ostatecznie idee te są powiązane z tezą Churcha , która mówi, że matematyczne pojęcie obliczalnych funkcji cząstkowych jest poprawną formalizacją efektywnie obliczalnej funkcji cząstkowej, której nie można ani udowodnić, ani obalić. Church użył rachunku lambda , wyidealizowany komputer Turinga, a później Emil Post w swoim podejściu, z których wszystkie są równoważne.

Deborah Joseph i Paul Young ( 1985 ) sformułowali analogiczną koncepcję, kreatywność wielomianową , w teorii złożoności obliczeniowej i wykorzystali ją do dostarczenia potencjalnych kontrprzykładów dla hipotezy Bermana-Hartmanisa o izomorfizmie zbiorów NP-zupełnych .

Notatki

Davis, Martin (1958), Obliczalność i nierozwiązywalność , Seria w przetwarzaniu informacji i komputerach , Nowy Jork: McGraw-Hill, MR 0124208 . Przedrukowany w 1982 roku przez Dover Publications.
Enderton, Herbert B. (2010), Teoria obliczalności: wprowadzenie do teorii rekurencji , Academic Press, ISBN 978-0-12-384958-8 .
Józef, Debora ; Young, Paul (1985), „Kilka uwag na temat funkcji świadka dla zbiorów niewielomianowych i niekompletnych w NP” , Theoretical Computer Science , 39 (2–3): 225–237, doi : 10.1016 / 0304-3975 (85) 90140-9 , MR 0821203
Kleene, Stephen Cole (2002), Logika matematyczna , Mineola, NY: Dover Publications Inc., ISBN 0-486-42533-9 , MR 1950307 . Przedruk oryginału z 1967 r., Wiley, MR 0216930 .
Myhill, John (1955), „Zestawy kreatywne”, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik , 1 (2): 97–108, doi : 10.1002/malq.19550010205 , MR 0071379 .
Post, Emil L. (1944), „Rekurencyjnie przeliczalne zbiory liczb całkowitych dodatnich i ich problemy decyzyjne”, Biuletyn Amerykańskiego Towarzystwa Matematycznego , 50 (5): 284–316, doi : 10.1090 / S0002-9904-1944-08111- 1 , MR 0010514
Rogers, Hartley, Jr. (1987), Teoria funkcji rekurencyjnych i efektywnej obliczalności (wyd. 2), Cambridge, MA: MIT Press, ISBN 0-262-68052-1 , MR 0886890 .
Soare, Robert I. (1987), Rekurencyjnie wyliczalne zbiory i stopnie: badanie funkcji obliczalnych i zbiorów generowanych obliczeniowo , Perspectives in Mathematical Logic , Berlin: Springer-Verlag, ISBN 3-540-15299-7 , MR 0882921 .