Numeracja Gödla dla sekwencji

W matematyce numeracja Gödla dla sekwencji zapewnia skuteczny sposób przedstawienia każdej skończonej sekwencji liczb naturalnych jako pojedynczej liczby naturalnej. Podczas gdy osadzanie teoretyczne zestawu jest z pewnością możliwe, nacisk kładzie się na skuteczność funkcji manipulujących takimi reprezentacjami sekwencji: operacje na sekwencjach (dostęp do poszczególnych elementów, konkatenacja) można „zaimplementować” za pomocą totalnie rekurencyjnych funkcji , a w rzeczywistości przez prymitywne funkcje rekurencyjne .

Zwykle jest używany do budowania sekwencyjnych „ typów danych ” w arytmetycznych formalizacjach niektórych podstawowych pojęć matematyki. Jest to szczególny przypadek bardziej ogólnej idei numeracji Gödla . Na przykład teorię funkcji rekurencyjnych można uznać za sformalizowanie pojęcia algorytmu i można ją traktować jako język programowania do naśladowania list poprzez kodowanie sekwencji liczb naturalnych w pojedynczej liczbie naturalnej.

Numeracja Gödla

Oprócz używania numeracji Gödla do kodowania unikalnych sekwencji symboli w unikalne liczby naturalne (tj. umieszczania liczb w wzajemnie wykluczających się lub jeden do jednego odpowiednikach z sekwencjami), możemy jej używać do kodowania całych „architektur” wyrafinowanych „maszyn”. Na przykład, możemy zakodować algorytmy Markowa lub maszyny Turinga na liczby naturalne iw ten sposób udowodnić, że ekspresyjna siła teorii funkcji rekurencyjnych jest nie mniejsza niż w przypadku poprzednich maszynowych formalizacji algorytmów.

Dostęp do członków

Każda taka reprezentacja sekwencji powinna zawierać wszystkie informacje, takie jak w oryginalnej sekwencji — co najważniejsze, każdy pojedynczy element musi być możliwy do odzyskania. Jednak długość nie musi pasować bezpośrednio; nawet jeśli chcemy obsługiwać sekwencje o różnej długości, możemy przechowywać dane długości jako element dodatkowy lub jako drugi element uporządkowanej pary za pomocą funkcji parowania .

Oczekujemy, że istnieje skuteczny sposób na ten proces wyszukiwania informacji w postaci odpowiedniej funkcji totalnie rekurencyjnej. Chcemy znaleźć całkowicie rekurencyjną funkcję f z właściwością, że dla wszystkich n i dla dowolnego ciągu liczb naturalnych o długości n ${\ Displaystyle \ langle a_ {0}, \ kropki a_ {n -1}\rangle }$ , istnieje odpowiednia liczba naturalna a , zwana liczbą Gödla ciągu, taka, że dla wszystkich i gdzie ${\ Displaystyle 0 \ równoważnik ja \ równoważnik n-1}$ , ${\ Displaystyle f (a, i) = a_ {i}}$ .

Istnieją skuteczne funkcje, które mogą odzyskać każdego członka oryginalnej sekwencji z liczby Gödla sekwencji. Co więcej, niektóre z nich możemy zdefiniować w konstruktywny sposób, dzięki czemu możemy wyjść daleko poza zwykłe dowody istnienia .

Lemat Gödla o funkcji β

Dzięki pomysłowemu wykorzystaniu chińskiego twierdzenia o resztach $możemy$ konstruktywnie zdefiniować taką funkcję rekurencyjną używając prostych funkcji teorii liczb, z których wszystkie można zdefiniować w sposób całkowicie rekurencyjny), spełniając specyfikacje podane powyżej . Gödel zdefiniował $.$ Jest to prymitywna funkcja rekurencyjna .

Zatem dla wszystkich n i dla dowolnego ciągu liczb naturalnych o długości n ⟨ $\ Displaystyle \ langle a_ {0}, \ kropki a_ {n-1} \ rangle}$ liczba naturalna a , zwana liczbą Gödla ciągu taka, że ${\ Displaystyle \ beta (a, i) = a_ {i}}$ .

Korzystanie z funkcji parowania

Nasze konkretne rozwiązanie będzie zależeć od funkcji parowania — istnieje kilka sposobów implementacji funkcji parowania, więc należy wybrać jedną metodę. Teraz możemy abstrahować od szczegółów implementacji funkcji parowania. Musimy tylko znać jego „ interfejs ”: niech $π {\ displaystyle \ pi}$ K i L oznaczają odpowiednio funkcję parowania i jej dwie funkcje projekcji , spełniające specyfikację

{\ Displaystyle K \ lewo (\ pi \ lewo (x, y \ prawej) \ prawej) = x}

{\ Displaystyle L \lewo(\pi \lewo(x,y\prawo)\prawo)=y}

Nie będziemy tutaj omawiać i formalizować aksjomatu wykluczania obiektów obcych, ponieważ zrozumienie metody nie jest wymagane.

Reszta dla liczb naturalnych

Użyjemy innej funkcji pomocniczej, która obliczy resztę dla liczb naturalnych . Przykłady:

${\ Displaystyle \ operatorname {rem} (5,3) = 2}$
${\ Displaystyle \ operatorname {rem} (7,2) = 1}$

Można udowodnić, że ta funkcja może być zaimplementowana jako funkcja rekurencyjna.

Korzystanie z chińskiego twierdzenia o resztach

Implementacja funkcji β

Korzystając z chińskiego twierdzenia o resztach , możemy udowodnić, że implementacja jako ${\ displaystyle \ beta}$

{\ Displaystyle \ beta (s, i) = \ operatorname {rem} \ lewo (K \ lewo(s\prawo),\lewo(i+1\prawo)\cdot L\lewo(s\prawo)+1\prawo)}

będzie działać, zgodnie ze specyfikacją, $oczekujemy$ . Możemy użyć bardziej zwięzłej formy przez nadużycie notacji (stanowiącej rodzaj dopasowywania wzorców ):

{\ Displaystyle \ beta \ lewo (\ pi \ lewo (x_ {0}, m \ prawej) ,i\right)=\mathrm {rem} \left(x_{0},\left(i+1\right)\cdot m+1\right)}

Osiągnijmy jeszcze większą czytelność dzięki większej $ja$ i ponownemu użyciu ( ${\ Displaystyle m_ {i} = (i + 1) \ cdot m + 1}$ używane w informatyce): możemy napisać

{\ Displaystyle \ beta \ lewo (\ pi \ lewo (x_ {0}, m \ prawej), i \ prawej) = \ argumentacja {rem} \left(x_{0},m_{i}\right)}

.

W dowodzie $użyjemy$ tej

Ręcznie dostrojone założenia

Aby udowodnić poprawność powyższej definicji funkcji $użyjemy$ kilku lematów. Mają one swoje własne założenia. Teraz staramy się odkryć te założenia, ostrożnie kalibrując i dostrajając ich siłę: nie należy ich wypowiadać w zbyt ostrej lub niezadowalająco słabej formie.

Niech ${\ Displaystyle a_ {0}, \ kropki a_ {n-1}}$ będzie ciągiem liczb naturalnych. Niech m zostanie wybrane do zaspokojenia

{\ Displaystyle \ forall i \ in {\ overline {n}} \ setminus \ lewo \ {0 \ prawo \} \ lewo (i \ środkowy m \ prawo)}

{\ Displaystyle \ forall i <n \ lewo (a_ {i}<m_ {i} \ prawo)}

Pierwsze założenie jest rozumiane jako

{\ Displaystyle 1 \ środkowy m \ ziemia \ kropki \ ziemia n-1 \ połowa m}

Jest to konieczne, aby spełnić założenie chińskiego twierdzenia o resztach (być parami względnie pierwszymi ). W literaturze bywa, że wymaganie to zastępowane jest silniejszym, np. konstrukcyjnie zbudowanym z funkcji silni , ale do tego dowodu nie jest wymagana silniejsza przesłanka.

Drugie założenie w żaden sposób nie dotyczy chińskiego twierdzenia o resztach. Będzie to miało znaczenie w udowodnieniu, że ostatecznie spełniona jest specyfikacja dla ${\ displaystyle \ beta} .$ Zapewnia to, że $systemu$ kongruencji

{\ Displaystyle x \ równoważnik a_ {i} {\ pmod {m_ {i}}}}

dla każdego ja gdzie

{\ Displaystyle 0 \ równoważnik ja \ równoważnik n -1}

również zadowala

\ Displaystyle a_ {i} = \ operatorname {rem} ({\ tylda {x}}, m_ {i})}

.

Silniejsze $styl wyświetlania m_{i}}$ m wymagające $_$ drugie $założenie$ jak wyżej).

Dowód, że założenie (współpierwotności) dla chińskiego twierdzenia o resztach jest spełnione

W sekcji Ręcznie dostrojone założenia wymagaliśmy tego

{\ Displaystyle \ forall i \ in {\ overline {n}} \ setminus \ lewo \ {0 \ prawo \} \ lewo (i \ środkowy m \ prawo)}

. Chcemy udowodnić, że możemy stworzyć ciąg par względnie pierwszych w sposób, który okaże się zgodny z Implementacją funkcji β .

Szczegółowo:

{\ Displaystyle \ forall i <n, j <n \; \ lewo (i \ neq j \ \ strzałka w prawo \mathrm {liczba pierwsza} \left(m_{i},m_{j}\right)\right)}

pamiętając, że $m$ $i} = (i + 1) \ cdot m + 1$ { .

Dowód jest sprzeczny; zakładamy zaprzeczenie pierwotnego stwierdzenia:

{\ Displaystyle \ istnieje i <n, j <n \; \ lewo (i \ neq j \land \lnot \mathrm {liczba pierwsza} \left(m_{i},m_{j}\right)\right)}

Pierwsze kroki

Wiemy, co oznacza relacja „względnie pierwsza” (na szczęście jej zaprzeczenie można sformułować w zwięzłej formie); zatem podstawmy w odpowiedni sposób:

{\ Displaystyle \ istnieje ja <n, j <n \; \ lewo ( i\neq j\land \exists p\in \mathrm {Pierwszy} \;\left(p\mid m_{i}\land p\mid m_{j}\right)\right)}

Używając formy normalnej prenex „więcej” (ale zwróć uwagę na notację podobną do ograniczeń w kwantyfikatorach):

{\ Displaystyle \ istnieje ja <n, j <n, p \ w \ operatorname { Prime} \;\left(i\neq j\land p\mid m_{i}\land p\mid m_{j}\right)}

Ze względu na twierdzenie o podzielności , $i} \ land p \ mid m_ {j}}$ {

{\ Displaystyle p \ mid m_ {i} -m_ {j}}

.

Zastępując definicje -notacji $sekwencji$ , otrzymujemy $cdot m}$ ${\ Displaystyle m_ {i} -m_ {j} = (ij$ , stąd (ponieważ aksjomaty równości postulują, że tożsamość jest relacją kongruencji ) otrzymujemy

{\ Displaystyle p \ mid (ij) \ cdot m}

.

Ponieważ p jest elementem pierwszym (należy zauważyć, że używana jest właściwość elementu nieredukowalnego ), otrzymujemy

{\ Displaystyle p \ mid ij \ lor p \ mid m}

.

Odwołując się do pierwszego ręcznie dostrojonego założenia

Teraz musimy uciec się do naszego założenia

{\ Displaystyle \ forall i \ in {\ overline {n}} \ setminus \ lewo \ {0 \ prawo \} \ lewo (i \ środkowy m \ prawo)}

.

Założenie zostało starannie wybrane, aby było jak najsłabsze, ale wystarczająco mocne, abyśmy mogli z niego skorzystać teraz.

Zakładana negacja pierwotnego stwierdzenia zawiera odpowiednie stwierdzenie egzystencjalne przy użyciu indeksów ${\ displaystyle i <n \ land j <n \ land i \ neq j}$ ; pociąga to za sobą ${\ Displaystyle ij \ in {\ overline {n}} \ setminus \ lewo \ {0 \ prawo \}}$ , więc można zastosować wspomniane założenie, więc ${\ displaystyle ij \ mid m}$ trzyma.

Używanie twierdzenia (o przedmiocie) rachunku zdań jako lematu

Możemy to udowodnić na kilka sposobów znanych z rachunku zdań

{\ Displaystyle \ lewo (A \ ziemia \ lewo (A \ strzałka w prawo B \ w prawo) \ w prawo) \ strzałka w prawo B}

posiada.

Ponieważ ${\ Displaystyle ij \ mid m}$ , przez właściwość przechodniości relacji podzielności , ${\ Displaystyle p \ mid ij \ rightarrow p \ mid m}$ . Zatem (ponieważ aksjomaty równości postulują tożsamość jako relację kongruencji)

{\ Displaystyle p \ środkowy m}

można udowodnić.

Dotarcie do sprzeczności

Zawarta negacja pierwotnego stwierdzenia

{\ displaystyle p \ mid m_ {i}}

i właśnie to udowodniliśmy

{\ displaystyle p \ mid m}

.

Zatem,

{\ Displaystyle p \ mid m_ {i} - \ lewo (i + 1 \ prawo) \ cdot m}

też powinien trzymać. Ale po zastąpieniu definicji m ${\ displaystyle m_ {i$ }

{\ Displaystyle m_ {i} - \ lewo (i + 1 \ prawo) \ cdot m = 1}

Zatem podsumowując powyższe trzy stwierdzenia, przez przechodniość równości ,

{\ displaystyle p \ środek 1}

też powinien trzymać.

Jednak w zaprzeczeniu pierwotnego stwierdzenia p jest egzystencjalnie kwantyfikowane i ograniczone do liczb pierwszych ${\ displaystyle \ istnieje p \ in \ operatorname {liczba pierwsza}}$ . To ustanawia sprzeczność, do której chcieliśmy dotrzeć.

Koniec reductio ad absurdum

Dochodząc do sprzeczności z jej zaprzeczeniem, właśnie udowodniliśmy oryginalne stwierdzenie:

{\ Displaystyle \ forall i <n, j <n \; \ lewo (i \ neq j \ strzałka w prawo \mathrm {liczba pierwsza} \left(m_{i},m_{j}\right)\right)}

System równoczesnych kongruencji

Budujemy system jednoczesnych kongruencji

{\ Displaystyle x \ równoważnik a_ {0} {\ pmod {m_ {0}}}}

{\ Displaystyle \ vdots}

{\ styl wyświetlania x\odpowiednik a_{n-1}{\pmod {m_{n-1}}}}

Możemy to zapisać w bardziej zwięzły sposób:

\ Displaystyle \ forall i <n \; \ lewo (x \ równoważnik a_ {i} {\ pmod {m_ {i}}} \ prawej)}

Poniżej zostanie podanych wiele stwierdzeń, wszystkie zaczynające się od „ ${\ Displaystyle \ forall i <n \; \ lewo (\ kropki \ po prawej)}$ ". Aby $,$ zakresie kwantyfikacji Zatem ${\ displaystyle \ forall i <n (}$ zaczyna się tutaj.

Wybierzmy rozwiązanie $.$ układu jednoczesnych kongruencji Musi istnieć co najmniej jedno rozwiązanie, ponieważ są parami porównywalne, jak udowodniono w poprzednich sekcjach, więc możemy odnieść się do rozwiązania zapewnionego m , $Displaystyle m_ {0}, \ kropki m_ {n-1}}$ przez chińskie twierdzenie o resztach. $Zatem$ od teraz możemy uważać satysfakcjonujące

{\ Displaystyle x_ {0} \ równoważnik a_ {i} {\ pmod {m_ {i}}}}

,

co oznacza (z definicji arytmetyki modularnej ), że

\ Displaystyle \ operatorname {rem} \ lewo (x_ {0}, m_ {i} \ prawej) = \ operatorname {rem} \ lewo(a_{i},m_{i}\prawo)}

Odwołując się do drugiego dostrojonego założenia

Przypomnij sobie drugie założenie, „ ${\ Displaystyle \ forall i <n \; \ lewo (a_ {i}<m_ {i} \ prawo)} ”$ i pamiętaj, że jesteśmy teraz w zakresie niejawnej kwantyfikacji dla i , więc nie powtarzamy jej kwantyfikacji dla każdego stwierdzenia.

Drugie założenie sugeruje, że ${\ displaystyle a_ {i}<m_ {i}}$

{\ Displaystyle \ operatorname {rem} \ lewo (a_ {i}, m_ {i} \ prawej) = a_ {i}}

.

Teraz przez przechodniość równości otrzymujemy

{\ Displaystyle \ operatorname {rem} \ lewo (x_ {0}, m_ {i} \ prawej) = a_ {i}}

.

CO BYŁO DO OKAZANIA

Naszym pierwotnym celem było udowodnienie, że definicja

{\ Displaystyle \ beta \ lewo (\ pi \ lewo (x_ {0}, m \ prawej), i \ prawej) = \ argument matematyczny {rem} \left(x_{0},m_{i}\right)}

jest dobre do osiągnięcia tego, co zadeklarowaliśmy w specyfikacji $:$ chcemy $\ lewo (\ pi \ lewo (x_ { 0},m\right),i\right)=a_{i}}$ trzymać.

to teraz zobaczyć na podstawie przechodniości równości , patrząc na powyższe trzy równania.

(Duży zakres i kończy się tutaj.)

Istnienie i wyjątkowość

Właśnie udowodniliśmy poprawność definicji $wymaga$ jej specyfikacja

{\ Displaystyle \ forall a_ {0}, \ kropki, a_ {n-1} \; \ istnieje s \; \forall i<n\;\beta (s,i)=a_{i}}

jest spełniony. Chociaż udowodnienie tego było najważniejsze dla ustalenia schematu kodowania sekwencji, musimy jeszcze wypełnić pewne luki. Są to pojęcia pokrewne, podobne do istnienia i niepowtarzalności (chociaż o niepowtarzalności należy tu rozumieć „co najwyżej jedno”, a połączenie obu jest ostatecznie opóźnione).

Unikalność kodowania, osiągnięta poprzez minimalizację

Nasze ostateczne pytanie brzmi: jaka liczba powinna oznaczać kodowanie sekwencji ${\ Displaystyle \ lewo \ langle a_ {0}, \ kropki, a_ {n-1} \ prawo \ rangle}$ ? Specyfikacja deklaruje jedynie kwantyfikację egzystencjalną, a nie funkcjonalne połączenie. Chcemy konstruktywnego i algorytmicznego połączenia: (całkowitej) funkcji rekurencyjnej, która wykonuje kodowanie.

Całość, ponieważ minimalizacja jest ograniczona do funkcji specjalnych

Tę lukę można wypełnić w prosty sposób: zastosujemy minimalizację , a całość wynikowej funkcji zapewni wszystko, co do tej pory udowodniliśmy (tj. poprawność definicji $).$ spełnienie jej specyfikacji ). A właściwie specyfikacja

{\ Displaystyle \ forall a_ {0}, \ kropki, a_ {n-1} \; \ istnieje s \; \forall i<n\;\beta (s,i)=a_{i}}

pełni tu rolę pojęcia bardziej ogólnego („funkcja specjalna”). Znaczenie tego pojęcia polega na tym, że umożliwia nam oddzielenie (pod)klasy (całkowitych) funkcji rekurencyjnych od (nad)klasy funkcji cząstkowych rekurencyjnych. Krótko mówiąc, specyfikacja mówi, że funkcja f spełnia specyfikację

{\ Displaystyle f \ lewo (a_ {0}, \ kropki, a_ {n-1 },s\right)=0\leftrightarrow \forall i<n\;\left(\beta (s,i)=a_{i}\right)}

jest funkcją specjalną; to znaczy dla każdej ustalonej kombinacji argumentów przedostatnich funkcja f ma pierwiastek w swoim ostatnim argumencie:

{\ Displaystyle \ forall a_ {0}, \ kropki, a_ {n-1} \; \ istnieje s\;\lewo(f\lewo(a_{0},\kropki,a_{n-1},s\prawo)=0\prawo)}

Funkcję numeracji Gödla g można wybrać jako całkowicie rekurencyjną

Wybierzmy zatem minimalną możliwą liczbę, która dobrze pasuje do specyfikacji funkcji: β $\ displaystyle \ beta}$

{\ Displaystyle g: \ mathbb {N} ^ {n} \ do \ mathbb {N}}

{\ Displaystyle \ lewo \ langle a_ {0}, \ kropki, a_ {n-1} \ prawo \ rangle \ longmapsto \ mu a. \ lewo [\ forall i <n \; \ lewo (\ beta \ lewo (a ,i\prawo)=a_{i}\prawo)\prawo]}

.

Można udowodnić (używając pojęć z poprzedniej sekcji), że g jest (całkowite) rekurencyjne.

Dostęp długości

Jeśli zastosujemy powyższy schemat do kodowania sekwencji tylko w kontekstach, w których długość sekwencji jest ustalona, to nie powstaje żaden problem. Innymi słowy, możemy ich używać w analogiczny , jak tablice są używane w programowaniu.

Ale czasami potrzebujemy dynamicznie rozciągających się sekwencji lub musimy poradzić sobie z sekwencjami, których długości nie można wpisać w sposób statyczny. Innymi słowy, możemy kodować sekwencje w sposób analogiczny do list w programowaniu.

Aby zilustrować oba przypadki: jeśli utworzymy numerację Gödla maszyny Turinga, to każdy wiersz w macierzy „programu” można przedstawić za pomocą krotek, sekwencji o stałej długości (a więc bez przechowywania długości), ponieważ liczba kolumn jest ustalona. Ale jeśli chcemy wnioskować o rzeczach podobnych do konfiguracji (maszyn Turinga), a konkretnie, jeśli chcemy zakodować znaczną część taśmy działającej maszyny Turinga, to musimy reprezentować sekwencje wraz z ich długością. Możemy naśladować dynamicznie rozciągające się sekwencje, reprezentując konkatenację sekwencji (lub przynajmniej rozszerzając sekwencję o jeszcze jeden element) za pomocą całkowicie rekurencyjnej funkcji.

Długość może być przechowywana po prostu jako element dodatkowy:

{\ Displaystyle g: \ mathbb {N} ^ {*} \ do \ mathbb {N}}

{\ Displaystyle \ lewo \ langle a_ {0}, \ kropki, a_ {n-1}, a_ {n} \ prawo \ rangle \ longmapsto \ mu a. \ lewo [a_ {0} = n \ ziemia \ dla wszystkich ja <n\;\left(\beta \left(a,i+1\right)=a_{i}\right)\right]}

.

Odpowiednia modyfikacja dowodu jest prosta i polega na dodaniu nadwyżki

{\ Displaystyle x \ równoważnik n {\ pmod {m_ {0}}}}

do systemu równoczesnych kongruencji (pod warunkiem, że indeks elementu nadwyżkowego jest wybrany jako 0). Należy również odpowiednio zmodyfikować założenia.

Notatki

^ ^a ^b Mnich 1976 : 56–58
^ ^a ^b Csirmaz 1994 : 99–100 (patrz online )
^ Mnich 1976 : 72–74
^ Mnich 1976 : 52–55
^ ^a ^b ^c ^d Csirmaz 1994 : 100 (patrz online )
^ Smullyan 2003 : 56 (= Rozdział IV, § 5, przypis 1)
^ Mnich 1976 : 58 (= Thm 3,46)
^ Hughes 1989 (patrz online zarchiwizowane 2006-12-08 w Wayback Machine )
^ Burris 1998 : tekst uzupełniający, arytmetyka I , lemat 4
^ ^a ^b zobacz także pojęcia pokrewne, np. „równi za równych” ( przezroczystość referencyjna ) i inne pokrewne pojęcie prawo Leibniza / tożsamość nieodróżnialnych
^ albo dowód teoretyczny (kroki algebraiczne); lub semantyczne ( tablica prawdy , metoda tablic analitycznych , diagram Venna , diagram Veitcha / mapa Karnaugha )
^ Mnich 1976 : 45 (= Def 3.1.)
^ Np. zdefiniowany przez

${\ Displaystyle f: \ mathbb {N} ^ {n + 1} \ do \ mathbb {N}}$

${\ Displaystyle f \ lewo (a_ {0}, \ kropki, a_ {n-1}, s \ prawej) = {\ rozpocząć {przypadki} 0 i \ operatorname { if} \;\forall i<n\;\left(\beta (s,i)=a_{i}\right)\\1&\mathrm {if} \;\exists i<n\;\left(\ beta (s,i)\neq a_{i}\right)\end{przypadki}}}$
^ Mnich 1976 : 53 (= Def 3.20, Lem 3.21)
^ Csirmaz 1994 : 101 (= Thm 10,7, Conseq 10,8), patrz online

Burris, Stanley N. (1998). „Tekst uzupełniający, arytmetyka I” . Logika dla matematyki i informatyki . Sala Prentice'a. ISBN 978-0-13-285974-5 .
Csirmaz, László; Hajnal, Andras (1994). „Rekurzív függvények” . Matematikai logika (postscript + gzip) (w języku węgierskim). Budapeszt: Uniwersytet Eötvös Loránd. {{ cite book }} : |format= wymaga |url= ( pomoc ) Każdy rozdział można dosłownie pobrać ze strony autora .
Hughes, John (1989). „Dlaczego programowanie funkcjonalne ma znaczenie” . Dziennik komputerowy . 32 (2): 98–107. doi : 10.1093/comjnl/32.2.98 . Zarchiwizowane od oryginału w dniu 8 grudnia 2006 r.
Mnich, J. Donald (1976). Logika Matematyczna . Absolwent Teksty z matematyki. Nowy Jork • Heidelberg • Berlin: Springer-Verlag. ISBN 9780387901701 .
Smullyan, Raymond Merrill (1992). Twierdzenia Gödla o niezupełności . Oxford University Press. ISBN 978-0-19-504672-4 .
Smullyan, Raymond Merrill (2003). Gödel nemteljességi tételei (w języku węgierskim). Budapeszt: Typotex. ISBN 978-963-9326-99-6 . Tłumaczenie Smullyana 1992 .

Linki zewnętrzne

Burris, Stanley N. (1998). „Tekst uzupełniający, arytmetyka I” . Logika dla matematyki i informatyki . Sala Prentice'a. ISBN 978-0-13-285974-5 .

[chinese_pairing-1] Mnich 1976 : 56–58

[chinese_pairing2-2] Csirmaz 1994 : 99–100 (patrz online )

[Markov-3] Mnich 1976 : 72–74

[Turing-4] Mnich 1976 : 52–55

[rem-5] Csirmaz 1994 : 100 (patrz online )

[6] Smullyan 2003 : 56 (= Rozdział IV, § 5, przypis 1)

[Godel_beta-7] Mnich 1976 : 58 (= Thm 3,46)

[whyfp-8] Hughes 1989 (patrz online zarchiwizowane 2006-12-08 w Wayback Machine )

[ArithmeticI-9] Burris 1998 : tekst uzupełniający, arytmetyka I , lemat 4

[congid-10] zobacz także pojęcia pokrewne, np. „równi za równych” ( przezroczystość referencyjna ) i inne pokrewne pojęcie prawo Leibniza / tożsamość nieodróżnialnych

[11] wód teoretyczny (kroki algebraiczne); lub semantyczne ( tablica prawdy , metoda tablic analitycznych , diagram Venna , diagram Veitcha / mapa Karnaugha )

[special_function-12] Mnich 1976 : 45 (= Def 3.1.)

[13] Np. zdefiniowany przez

${\ Displaystyle f: \ mathbb {N} ^ {n + 1} \ do \ mathbb {N}}$

${\ Displaystyle f \ lewo (a_ {0}, \ kropki, a_ {n-1}, s \ prawej) = {\ rozpocząć {przypadki} 0 i \ operatorname { if} \;\forall i<n\;\left(\beta (s,i)=a_{i}\right)\\1&\mathrm {if} \;\exists i<n\;\left(\ beta (s,i)\neq a_{i}\right)\end{przypadki}}}$

[stat-14] Mnich 1976 : 53 (= Def 3.20, Lem 3.21)

[dyn-15] Csirmaz 1994 : 101 (= Thm 10,7, Conseq 10,8), patrz online