Twierdzenie Tennenbauma

Nie należy mylić z konstrukcją Tennenbauma obliczalnej kopii ${\ Displaystyle \ omega + \ omega ^ {*}}$ bez obliczalnych nieskończonych rosnących lub malejących łańcuchów.

Twierdzenie Tennenbauma , nazwane na cześć Stanleya Tennenbauma , który przedstawił to twierdzenie w 1959 r., jest wynikiem logiki matematycznej , który stwierdza, że ​​żaden policzalny niestandardowy model arytmetyki Peano pierwszego rzędu (PA) nie może być rekurencyjny (Kaye 1991: 153ff).

Struktury rekurencyjne dla PA

Struktura w języku PA jest $rekurencyjna$ jeśli istnieją funkcje rekurencyjne i ${\ Displaystyle$$\ otimes}$ z $mathbb {N$ { $\ Displaystyle \ mathbb {N} \ razy$ } $dwumiejscowej$ _do $rekurencyjnej$ relacji i stałych $displaystyle n_ {0}, n_ {1}}$ takie, że

${\ Displaystyle (\ mathbb {N}, \ oplus, \ czasami, <_ {M}, n_ {0}, n_ {1}) \cong M,}$

gdzie $izomorfizm$ i jest zbiorem $($ ) liczb naturalnych . Ponieważ izomorfizm musi być bijekcją , każdy model rekurencyjny jest policzalny. Istnieje wiele nieizomorficznych policzalnych niestandardowych modeli PA.

Stwierdzenie twierdzenia

Twierdzenie Tennenbauma mówi, że żaden przeliczalny niestandardowy model PA nie jest rekurencyjny. Co więcej, ani dodawanie, ani mnożenie takiego modelu nie może być rekurencyjne.

Szkic dowodowy

Szkic ten jest zgodny z argumentacją przedstawioną przez Kaye (1991). Pierwszym krokiem w dowodzie jest pokazanie, że jeśli M jest dowolnym policzalnym niestandardowym modelem PA, to system standardowy M (zdefiniowany poniżej) zawiera co najmniej jeden nierekurencyjny zbiór S . Drugim krokiem jest pokazanie, że gdyby operacja dodawania lub mnożenia na M była rekurencyjna, to ten zbiór S byłby rekurencyjny, co jest sprzecznością.

$Dzięki$ metodom używanym do kodowania uporządkowanych krotek każdy można $jako$ dla zestawu elementów W szczególności, jeśli pozwolimy być $liczbą$ tą pierwszą w M , to ${\ Displaystyle Z \ w S_ {x} \ strzałka w lewo M \ vDash p_ {z} | x}$ . Każdy zestaw $,$ ograniczony w $M$ , ale jeśli x to zbiór może zawierać nieskończenie wiele standardowych liczb naturalnych Standardowym systemem modelu jest kolekcja ${\ Displaystyle \ {S_ {x} \ czapka \ mathbb {N}: x \ w M \}}$ . Można wykazać, że system standardowy dowolnego niestandardowego modelu PA zawiera zbiór nierekurencyjny, albo odwołując się do twierdzenia o niezupełności, albo bezpośrednio rozważając parę rekurencyjnie nierozłącznych zbiorów (Kaye 1991:154). Są to rozłączne re zestawy $N$$subseteq \ mathbb {$ \ z ${\ Displaystyle A \ subseteq C}$ i ${\ Displaystyle B \ czapka C = \ pusty zbiór}$ .

W przypadku tej drugiej konstrukcji zacznij od pary rekurencyjnie nierozłącznych zestawów A i B . Dla liczby naturalnej x istnieje y takie , że dla wszystkich ja < x , jeśli ${\ Displaystyle i \ in A}$ to ${\ Displaystyle p_ {i} | y}$ i jeśli ${\ Displaystyle i \ w B}$ to ${\ Displaystyle p_ {i} \ nmid y}$ . Przez overspill , oznacza to, że istnieje jakieś niestandardowe x w M , dla którego istnieje (koniecznie niestandardowe) y w M , tak że dla każdego ${\ Displaystyle m \ in M}$ z ${\ displaystyle m <_{M}x}$ , mamy

${\ Displaystyle M \ vDash (m \ w A \ do p_ {m} | y) \ ziemia (m \ w B \to p_{m}\nśrodek y)}$

Niech ${\ Displaystyle S = \ mathbb {N} \ cap S_ {y}}$ będzie odpowiednim zbiorem w standardowym systemie M . Ponieważ A i B są re, można pokazać, że $emptyset}$ = $cap S =$ . Stąd S jest zbiorem oddzielającym dla A i B , i przez wybór A a B oznacza to, że S jest nierekurencyjne.

$Teraz , aby$ Tennenbauma, zacznij od niestandardowego policzalnego modelu M i elementu a w M tak . Metoda dowodu pokazuje, że ze względu na sposób zdefiniowania systemu standardowego możliwe jest obliczenie funkcji charakterystycznej zbioru S za pomocą funkcji dodawania $M$ jako wyroczni W szczególności, jeśli ${\ Displaystyle n_ {0}}$ to element M odpowiadający 0, a to element M odpowiadający 1, to dla każdego $∈$$i \ in \ mathbb {N}}$ możemy obliczyć ${\ Displaystyle n_ {i} = n_ {1} \ oplus \ cdots \ oplus n_ {1}}$ ( i razy). Aby zdecydować, czy liczba n należy do S , najpierw oblicz p , n - tą liczbę pierwszą w ${\ Displaystyle \ mathbb {N}}$ . Następnie wyszukaj element y z M , aby

${\ Displaystyle a = \ underbrace {y \ oplus y \ oplus \ cdots \ oplus y} _ {p {\ tekst {razy}}} \ oplus n_ { I}}$

dla niektórych ${\ displaystyle i <p}$ . To poszukiwanie zostanie zatrzymane, ponieważ algorytm Euklidesa można zastosować do dowolnego modelu PA. Wreszcie mamy $S$ i tylko wtedy, gdy i znalezione w wyszukiwaniu wynosiło 0. Ponieważ nie jest rekurencyjne, to, że operacja dodawania na jest nierekurencyjna.

Podobny argument pokazuje, że możliwe jest obliczenie funkcji charakterystycznej S przy użyciu mnożenia M jako wyroczni, więc operacja mnożenia na M jest również nierekurencyjna (Kaye 1991:154).

•   Boolos, George ; Burgess, John P .; Jeffrey, Richard (2002). Obliczalność i logika (wyd. 4). Wydawnictwo Uniwersytetu Cambridge . ISBN 0-521-00758-5 .
•   Kaye, Richard (1991). Modele arytmetyki Peano . Oxford University Press . ISBN 0-19-853213-X .
•   Kaye, Richard (wrzesień 2011). „Twierdzenie Tennenbauma dla modeli arytmetyki”. W Juliette Kennedy i Roman Kossak (red.). Teoria mnogości, arytmetyka i podstawy matematyki - twierdzenia, filozofie (PDF) . Notatki z wykładów z logiki . Tom. 36. ISBN 9781107008045 .
• Tennenbaum, Stanley (1959). „Modele niearchimedesowe dla arytmetyki”. Zawiadomienia Amerykańskiego Towarzystwa Matematycznego . 6 : 270.