Twierdzenie Tennenbauma - Tennenbaum's theorem

Nie należy mylić z konstrukcją Tennenbauma, która stanowi obliczalną kopię, która nie ma obliczalnych nieskończonych łańcuchów wstępujących lub zstępujących.${\ Displaystyle \ omega + \ omega ^ {*}}$

Twierdzenie Tennenbauma , nazwane na cześć Stanleya Tennenbauma, który przedstawił to twierdzenie w 1959 roku, jest wynikiem logiki matematycznej, która 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ą rekurencyjne funkcje + i x od do , rekurencyjny dwu miejsce relacja <on i wyodrębniła stałe takie, że ${\ displaystyle M}$${\ displaystyle N \ razy N}$${\ displaystyle N}$${\ displaystyle N}$${\ displaystyle n_ {0}, n_ {1}}$

${\ Displaystyle (N, \ oplus, \ otimes, <_ {M}, n_ {0}, n_ {1}) \ equiv M,}$

gdzie oznacza izomorfizm i jest zbiorem (standardowych) liczb naturalnych . Ponieważ izomorfizm musi być bijekcją, każdy model rekurencyjny jest policzalny. Istnieje wiele nieizomorficznych policzalnych niestandardowych modeli PA. ${\ displaystyle \ equiv}$${\ displaystyle N}$

Stwierdzenie twierdzenia

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

Szkic próbny

Szkic ten jest zgodny z argumentacją przedstawioną przez Kaye (1991). Pierwszym krokiem w dowodu wykazać, że jeżeli M oznacza dowolny policzalny nietypowa model PA, wówczas standardowy system M (zdefiniowany poniżej) zawiera co najmniej jeden zestaw nierekurencyjnego S . Drugim krokiem jest pokazanie, że jeśli operacja dodawania lub mnożenia na M byłaby rekurencyjna, to zbiór S byłby rekurencyjny, co jest sprzecznością.

Za pomocą metod stosowanych do kodowania uporządkowane krotki, każdy element może być postrzegane jako kod dla zestawu elementów M . W szczególności, jeśli pozwolimy być i- tą liczbą pierwszą w M , to . Każdy zbiór będzie ograniczony M , ale jeśli x jest niestandardowe, to zbiór może zawierać nieskończenie wiele standardowych liczb naturalnych. Standardowy system modelu jest kolekcja . Można wykazać, że standardowy system dowolnego niestandardowego modelu PA zawiera zbiór nierekursywny, odwołując się do twierdzenia o niekompletności lub bezpośrednio rozważając parę rekurencyjnie nierozłącznych zbiorów (Kaye 1991: 154). Są to zbiory rozłączne, więc nie ma zbioru rekurencyjnego z i . ${\ displaystyle x \ in M}$${\ Displaystyle S_ {x}}$${\ displaystyle p_ {i}}$${\ Displaystyle z \ w S_ {x} \ leftrightarrow M \ vDash p_ {z} | x}$${\ Displaystyle S_ {x}}$${\ Displaystyle S_ {x}}$${\ Displaystyle \ {S_ {x} \ nasadka N: x \ w M \}}$${\ Displaystyle A, B \ subseteq N}$${\ Displaystyle C \ subseteq N}$${\ Displaystyle A \ subseteq C}$${\ displaystyle B \ cap C = \ emptyset}$

Dla tej ostatniej konstrukcji rozpocząć z parą rekurencyjnie nierozłączne zestawy ponownie A i B . Dla liczby naturalnej x istnieje y takie, że dla wszystkich i <x , jeśli wtedy i jeśli wtedy . Przez właściwość przekroczenia oznacza to, że istnieje pewne niestandardowe x w M, dla którego istnieje (niekoniecznie niestandardowe) y w M, tak że dla każdego z mamy ${\ displaystyle i \ in A}$${\ displaystyle p_ {i} | y}$${\ displaystyle i \ in B}$${\ displaystyle p_ {i} \ nie | y}$${\ displaystyle m \ in M}$${\ displaystyle m <_ {M} x}$

${\ Displaystyle M \ vDash (m \ w A \ do p_ {m} | r) \ ziemia (m \ w B \ do p_ {m} \ nie | y)}$

Pozwolić być odpowiedni zestaw w standardowym systemie M . Ponieważ A i B są re, można to pokazać i . Stąd S jest zbiorem rozdzielającym dla A i B , a przy wyborze A i B oznacza to, że S jest nierekursywny. ${\ displaystyle S = N \ czapka S_ {y}}$${\ Displaystyle A \ subseteq S}$${\ displaystyle B \ cap S = \ emptyset}$

Teraz, aby udowodnić twierdzenie Tennenbauma, zacznij od niestandardowego policzalnego modelu M i elementu a w M , aby nie był rekurencyjny. Sposób ten dowód wykazuje, że ze względu na sposób standardowy system jest zdefiniowany, możliwe jest obliczenie funkcja charakterystyczna zbioru S przy użyciu funkcji addycyjną z M jak wyrocznię. W szczególności, jeśli jest elementem M odpowiadającym 0, a jest elementem M odpowiadającym 1, to dla każdego możemy obliczyć ( i razy). Aby zdecydować, czy liczba N jest S , pierwszego obliczeniowej p , z n -tego sile w N . Następnie wyszukaj element y z M, tak aby ${\ displaystyle S = N \ czapka S_ {a}}$${\ displaystyle \ oplus}$${\ displaystyle n_ {0}}$${\ displaystyle n_ {1}}$${\ displaystyle i \ in N}$${\ Displaystyle n_ {i} = n_ {1} \ oplus \ cdots \ oplus n_ {1}}$

${\ displaystyle a = \ underbrace {y \ oplus y \ oplus \ cdots \ oplus y} _ {p {\ text {razy}}} \ oplus n_ {i}}$

dla niektórych . To wyszukiwanie zostanie zatrzymane, ponieważ algorytm Euklidesa można zastosować do dowolnego modelu PA. Na koniec mamy wtedy i tylko wtedy, gdy i znalezione w wyszukiwaniu wynosi 0. Ponieważ S nie jest rekurencyjne, oznacza to, że operacja dodawania na M nie jest rekurencyjna . ${\ displaystyle i <p}$${\ displaystyle n \ in S}$

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

Bibliografia

• George Boolos , John P. Burgess i Richard Jeffrey (2002) Computability and Logic , 4th ed. Cambridge University Press. ISBN  0-521-00758-5
• Richard Kaye (1991) Modele arytmetyki Peano . Oxford University Press. ISBN  0-19-853213-X .
• Richard Kaye (wrzesień 2011). „Twierdzenie Tennenbauma o modelach arytmetyki”. W Juliette Kennedy i Roman Kossak (red.). Teoria mnogości, arytmetyka i podstawy matematyki - twierdzenia, filozofie (PDF) . Notatki do wykładów w logice. 36 . ISBN 9781107008045.
• Stanley Tennenbaum (1959) Non-Archimedean models for arytmetic , W: Notices of the American Mathematical Society 6, s. 270