III WARSZTATY Logiki, Informatyki i Filozofii Nauki, 1999

Andrzej Grzegorczyk

Zagadnienia Rozstrzygalności

Popularyzacja problemu oraz sprawy do zbadania

(streszczenie)

 

Motto

Matematycy myślą przy pomocy wyobrażenia funkcji (odwzorowania, przyporządkowania). Praktycy szukają sposobów rozwiązywania problemów (procedur, algorytmów, maszyn). Natomiast filozofowie chcą poznawać stany rzeczy (zbiory, relacje i ich zachodzenie).

---

W tym opracowaniu staram się rozwijać ujęcie filozoficzne omijając funkcje i algorytmy. Na tym podłożu powstają też zagadnienia warte dalszych badań.

 

Popularyzować wyniki dotyczące nierozstrzygalności próbowałem na kilka sposobów. Przedstawienia zwięzłe okazują się często nieprecyzyjne, a precyzyjne stają się bardzo rozwlekłe i żmudne. Wydaje mi się, że w obecnym opracowaniu uzyskuję lepszy rodzaj uprzystępnienia sprawy niż w podręczniku Zarys logiki matematycznej (wyd. 6, 1984) i niż w książeczce Zagadnienia rozstrzygalności (1962), ale nie przedstawiam całości rozumowania z maksymalną ścisłością. Natomiast stawiam kilka problemów do rozwiązania. Problemy te mogą być ważne też dla techniki komputerowej.

 

 

1

Część wstępna

(wprowadzenie intuicyjne oraz ogólne filozoficzne komentarze)

 

Zakładam, że pewna ilość ogólnych pojęć wyjściowych jest znana czytelnikowi, nie mniej scharakteryzuję pewne ich własności.

 

1. Podstawowa charakterystyka wiedzy ogólnej

Wiedzę swoją wyrażamy przy pomocy sformułowań językowych. Stanowią one nie tylko przekaz, ale podstawę rozumienia tego, co można nazwać treścią wiedzy. Wśród sformułowań językowych ważnymi są nazwy rzeczy. Podstawową właściwością w operowaniu nazwami jest to, że rzeczy podobne (potocznie traktowane często jako: takie same) oznaczamy tą samą nazwą. Istotną cechą wiedzy jest więc to, że

Używając jednej nazwy myślimy o wielu przedmiotach

Formułując swoje spostrzeżenia o świecie często

wypowiadamy się o wszystkich rzeczach, które oznaczamy tą samą nazwą.

W ten sposób dochodzimy do wyróżnienia dwóch narzędzi myśli, którymi są

Pojęcie zbioru i kwantyfikacja

Pojęcie zbioru, to pojęcie (wyobrażenie, czy idea) , które ściśle się wiąże z używaniem słowa wszystkie. Mianowicie w sensie semantycznym, jak się zdaje pierwotnym dla rozumienia pojęcia zbioru:

 

Zbiór rzeczy podpadających pod pewną nazwę, to: wszystkie te rzeczy, o których mówimy przy pomocy tej nazwy.

Kwantyfikacja , to używanie operatorów zwanych: kwantyfikatorami. Podstawowym takim operatorem jest Operator: Wszystkie... (stosowany do pewnej nazwy).

Zbiory, to np. LUDZIE, KRZESŁA, LICZBY, KONIE, ale też ŻOŁNIERZE KRÓLESTWA LAPUCJI, KONIE CZARNE, KRZESŁA WYŚCIEŁANE.

Nazwą zbioru można nazwać nazwę wspólną wszystkich rzeczy, które wchodzą w skład zbioru.

 

Zwróćmy teraz uwagę na Ogólny charakter wiedzy.

Wiedzę o świecie można sobie podzielić na wiedzę o konkretnych rzeczach (lub wydarzeniach), oraz wiedzę o zbiorach rzeczy (lub wydarzeń), czyli wiedzę, jak gdyby równocześnie o wszystkich rzeczach objętych jedną nazwą ogólną (która może być w szczególności nazwą złożoną, opisową, jak np. KRZESŁA WYŚCIEŁANE).

Jednakże wiedza o konkretnych rzeczach jednostkowych, która nie wkraczałaby w pytania dotyczące zbiorów jest bardzo uboga.

Pojedynczej rzeczy dotyczy rodzaj wiedzy, który można określić jako:

rozpoznawanie (identyfikacja) konkretnej rzeczy

Ma ona miejsce wtedy, gdy np. rozpoznaję, że osoba, którą właśnie widzę na ulicy to pan prezes Łapówkowicz, którego wczoraj poznałem na wizycie u ministra Bezduszewa. Konkretne rzeczy rozpoznajemy bez świadomości tego, na jakiej podstawie to czynimy. Podobnie rozpoznają konkretne rzeczy inne zwierzęta.

Większość naszej wiedzy specyficznie ludzkiej dotyczy zbiorów lub cech zbiorowych. Daje się więc określić jako : wiedza o zbiorach.

Jeśli nawet interesuję się w danym momencie tylko panem prezesem Łapówkowiczem, to np. zauważam, że ma on dzisiaj ciemne okulary. A noszenie ciemnych okularów jest pewną cechą ogólną. Istnieje zbiór ludzi noszących ciemne okulary i pan Łapówkowicz do nich należy. Większość ludzkiej wiedzy o konkretach ma więc charakter ogólny. Nawet, jeśli dotyczy rzeczy konkretnej, to jest odpowiedzią na pytanie: Czy pewne konkretne A jest B? Gdzie B jest pewną nazwą ogólną.

 

Ważnym elementem wiedzy jest przy tym wiedza o wszystkich rzeczach wchodzących w skład zbioru, czyli wiedza stanowiąca odpowiedź na pytanie, które nazwiemy pytaniem generalnym:

Pytanie generalne:

Czy wszystkie A są jakieœ (np. czy są B)?

albo inaczej mówiąc:

Czy każde A jest B?

Zastanawiając się nad tą kwestią można zauważyć Teoretyczny charakter wiedzy ogólnej. Odpowiedź na pytanie generalne: “czy wszystkie A są B?” jest mianowicie zwykle uciążliwa, bo często trzeba pytać o każdy z przedmiotów oznaczanych nazwą A osobno. Ale w pewnych szczególnych przypadkach nie musimy pytać o każdy przypadek osobno, bo wiemy, że ten sam ‘los’ spotyka (spotkał) wszystkie egzemplarze zbioru A.

Na następujące pytania o wszystkie egzemplarze pewnego zbioru odpowiadamy bez przeglądania wszystkich egzemplarzy tego zbioru:

Czy wszystkie dinozaury wyginęły?

Czy wszystkie słonie żyją w Afryce?

Czy każde krzesło jest wyściełane?

Czy dla każdej liczby istnieje większa od niej liczba pierwsza?

Na pytania te odpowiadamy bez przeglądania wszystkich egzemplarzy zbioru, o który chodzi. Przytem czynimy to z różnych powodów. (Podstawą odpowiedzi na powyższe pytania są bądź twierdzenia nauki, bądź kontrprzykłady z doświadczenia własnego.)

Uogólniając doświadczenia analityczne można powiedzieć, że na pytanie generalne odpowiadamy bardzo często w oparciu o pewną teorię, o pewien system przekonań, w szczególności opieramy się często o teorię logiczną, mianowicie o pewien powszechnie przyjęty sposób operowania słowem wszystkie. Sposób ten (bardzo naturalny, ale właśnie należący do systemu logiki) zawiera między innymi regułę, która mówi, że:

jeśli znalazłem takie A, które nie jest B, to nie wszystkie A są B.

A więc: jeśli spotkałem słonia w Warszawie, to nie wszystkie słonie żyją w Afryce. Natomiast system biologii upewnia mnie, że dinozaury wyginęły.

 

2. Zagadnienie rozstrzygalności teorii i ogólne pojęcie rozstrzygalności, obliczalności, (sprawdzalności) zbiorów i relacji

Duża część naszej wiedzy ujęta jest w pewne teorie, czyli systemy dedukcyjne, złożone z twierdzeń wyprowadzanych z założeń (aksjomatów) przy pomocy reguł logiki. Cecha rozstrzygalności, o której zamierzamy mówić w dalszym ciągu dotyczy właśnie teorii pojętych jako systemy dedukcyjne. Określenie jest następujące:

 

Określenie wyjściowe: (mające charakter prakseologiczny)

Teoria jest rozstrzygalna, gdy istnieje metoda dająca się ująć w postaci przepisu pozwalającego na mechaniczne sprawdzanie, czy zdanie poprawnie zbudowane w terminach teorii jest, czy też nie jest twierdzeniem teorii.

Mechaniczne sprawdzanie może oczywiście być przedstawione jako sprawdzanie komputerowe. Teoria rozstrzygalna jest więc przykładem teorii na gruncie której twórczość ludzka może być całkowicie zastąpiona przez pracę komputera. Zagadnienie, czy wszelkie teorie są rozstrzygalne wiąże się więc z problemem: w jakim stopniu twórczość ludzka może być zastąpiona przez komputery, które niewątpliwie bardzo ludziom pomagają w pracy intelektualnej.

Warto więc pokazać zarówno teoria rozstrzygalne jak i nierozstrzygalne, znane na gruncie matematyki.

Powyżej podane wyjściowe, intuicyjne pojęcie rozstrzygalności daje się rozszerzyć i przenieść na dowolne zbiory.

(Uogólnione) Prakseologiczne Określenie wyjściowe :

Zbiór dowolnych przedmiotów jest rozstrzygalny (możemy mówić też: algorytmiczny, efektywnie rozpoznawalny, obliczalny), wtedy gdy istnieje taka metoda rozpoznawania elementów tego zbioru, dająca się ująć w postaci przepisu pozwalającego na mechaniczne sprawdzanie, czy dowolny przedmiot danej dziedziny należy, czy też nie należy do tego zbioru.

Rozpoznawać można dowolne przedmioty materialne. Metodę można nazwać metodą rozpoznawania, gdy jest skuteczna i w skończonym czasie zapewnia rozpoznanie interesującej nas cechy badanego obiektu.

Napisy są przedmiotami materialnymi, które w ramach europejskiego przedstawienia wiedzy naukowej reprezentują ważne składniki naszej wiedzy. Stąd rozważania o rozstrzygalnych (obliczalnych) zbiorach twierdzeń naukowych, podobnie jak i liczb naturalnych, można opisać jako badania zbiorów napisów. (Liczby reprezentujemy przez napisy, mianowicie przez liczebniki, które są nazwami liczb.)

Teorie matematyczne mają w naszej kulturze postać systemów dedukcyjnych, które można przedstawić jako zbiory napisów o następujących właściwościach:

1. Wszystkie wyrażenia teorii są zbudowane ze skończonej ilości symboli wyjściowych.

2. Aksjomaty teorii są łatwo (efektywnie) rozpoznawalne (stanowią zbiór rozstrzygalny).

3. Wszystkie wyrażenia poprawnie zbudowane są efektywnie rozpoznawalne. Istnieje dokładny przepis budowy wyrażeń poprawnie zbudowanych.

4. Wiele szczególnych rodzajów wyrażeń stanowi zbiory efektywnie rozpoznawalne (obliczalne), oraz wiele można ustawić w efektywny sposób w ciąg ponumerowany liczbami naturalnymi.

Szczególnym przypadkiem właściwości 4. (z której będziemy korzystać), jest możliwość efektywnego ponumerowania wszystkich wyrażeń zdaniowych poprawnie zbudowanych mających jedną zmienną wolną o postaci “x”. To ponumerowanie można sobie np. przedstawić jako zaczynające się od wyrażeń najkrótszych i przechodzące do wyrażeń coraz dłuższych. A wśród wyrażeń o tej samej długości kolejność może być alfabetyczna ze względu na ustaloną, alfabetyczną kolejność znaków wyjściowych Przy takim ponumerowaniu pierwszymi wyrażeniami tego ciągu mogą być np. następujące wyrażenia: x = 0, x = x, jako mające tylko trzy znaki. Po tym idą wyrażenia 4-znakowe, np.: x = S0, x = Sx, itd. Pewną ustaloną numerację tych wyrażeń oznaczmy przez Yn(x). Możliwa jest więc np. taka numeracja przy której:

Y0(x) to wyrażenie: x = 0

Y1(x) to: x = x

Y2(x) to: x = S0

Y3(x) to: x = Sx

Którymś kolejnym wyrażeniem tego ciągu będzie też np. $y(x=yŽxąy) itd.

Numeracja ta może łatwo zostać opisana jako efektywna (obliczalna) w tym sensie, że dla każdego danego naturalnego n każdy łatwo będzie umiał wskazać wyrażenie: Yn(x).

W matematyce pojęcie obliczalności stosuje się głównie do zbiorów liczb naturalnych i określa się je na gruncie arytmetyki. Istnieje przy tym odpowiedniość między pojęciem intuicyjnym rozstrzygalności i arytmetycznym pojęciem obliczalności. Odpowiedniość tę ujmuje opis języka nauki zwany arytmetyzacją języka.

Arytmetyzacją języka jest pewien dający się łatwo opisać sposób przyporządkowania, zgodnie z którym: zarówno poszczególnym literom języka (lub znakom złożonym traktowanym jako nierozdzielne) są przyporządkowane liczby naturalne, jak i napisom złożonym z tych znaków są przyporządkowane liczby naturalne, jak i ciągom skończonym napisów są również przyporządkowane liczby naturalne. W ten sposób istnieje efektywna odpowiedniość między zbiorami tworów językowych i zbiorami liczb, między relacjami wśród tworów językowych i relacjami wśród liczb.

Podane powyżej wyjściowe intuicyjne określenie obliczalności zbiorów dowolnych przedmiotów można łatwo przenieść na zbiory i relacje liczb naturalnych. Obliczalność (sprawdzalność, rozstrzygalność) zbiorów i relacji wśród liczb naturalnych ma następujący intuicyjny sens metamatematyczny.

Relacja na liczbach naturalnych jest obliczalna, gdy jest zdefiniowana takim wyrażeniem matematycznym, że istnieje ogólna metoda stwierdzania, czy relacja ta zachodzi dla dowolnych liczb naturalnych.

Każde stwierdzenie zachodzenia pewnej relacji dla liczb naturalnych można uważać za pewne postępowanie dowodowe na gruncie arytmetyki liczb naturalnych.

Relacja dana R może mieć swój symbol arytmetyczny, gdy jest jedną z relacji oznaczanych terminami pierwotnymi arytmetyki, albo też ma swoją arytmetyczną definicję. Liczby naturalne też mają swoje arytmetyczne definicje, np w postaci następników zera: 0, S0, SS0, SSS0, SSSS0 . itd. Ogólnie przyjmujemy, że definicją liczby naturalnej n jest liczebnik postaci: S...S0, gdzie znaków S (następnika) jest ilość n. Skrótowo liczebnik ten będziemy zapisywali jako: Sⁿ0.

 

Przypuśćmy, że relacja R jest w arytmetyce definiowalna przy pomocy wyrażenia:

F(x,y) mającego dwie zmienne wolne. Wówczas zachodzenie relacji R między liczbami naturalnymi n oraz m może być w arytmetyce wypowiedziane w postaci twierdzenia:

F(Sⁿ0,S^m0). W ten sposób dochodzimy do następującej definicji obliczalności:

Jest to metamatematyczna definicja obliczalności:

 

Def 1 Jeśli Arytmetyka (Ar)jest niesprzeczna, to:

Relacja R określona na liczbach naturalnych jest obliczalna wtedy, gdy istnieje takie wyrażenie arytmetyczne “F”, że dla dowolnej pary liczb naturalnych n oraz m zachodzą następujące równoważności:

(A) R(n,m) ş “F(Sⁿ0,S^m0)” Î Ar

(B) non R(n,m) ş “non F(Sⁿ0,S^m0)” Î Ar

To samo dotyczy relacji jednoargumentowych, czyli zbiorów. Napiszmy to nawet dokładniej, bo będziemy z tego korzystać:

Relacja jednoargumentowa P. (czyli zbiór liczb naturalnych) jest obliczalny, gdy istnieje takie wyrażenie arytmetyczne “Y(x)” o jednej zmiennej wolnej x, że jeśli zamiast tej zmiennej będziemy podstawiać liczebniki “Sⁿ0” i otrzymywać wyrażenia podstawieniowe, które mogą być oznaczane przez “Y(Sⁿ0)”, to zachodzić będą następujące równoważności:

(A) P(n) ş “Y(Sⁿ0)”Î Ar,

(B) non P(n) ş “nonY(Sⁿ0)”Î Ar,

Sens tej definicji jest taki, że relacja jest obliczalna, wtedy gdy jej zachodzenie, jak również jej nie-zachodzenie jest stwierdzalne przy pomocy odpowiednich twierdzeń wyprowadzonych w Arytmetyce Ar. Ar oznacza tu ustalony przyjęty system aksjomatyczny arytmetyki liczb naturalnych (rozumiany jako zbiór twierdzeń).

 

Podamy teraz aksjomatykę takiego systemu arytmetyki pierwszego rzędu, który w dalszym ciągu będziemy właśnie uważać za ten system Ar do którego odnoszą się nasze rozważania:

Przyjmujemy obecnie, że nasza arytmetyka Ar zawiera jako pojęcia pierwotne: zero 0, następnik S, mniejszość <, dodawanie +, mnożenie · i potęgowanie pot .

Ze względu na wygodę własną przyjmuję niekonwencjonalną symbolikę potęgowania:

xpoty zamiast x^y

Podstawowe aksjomaty o tych pojęciach, to:

1 non(0= Sx) 2 x=0 Ú $ y x=Sy 3 Sx=Sy ® x=y

 

4 x+0=x 5 x+Sy=S(x+y)

 

6 x<y ® non(y<x) 7 x<y Ú x=y Ú y<x 8 (x<y Ù y<z) ® x<z

 

9 0<Sx 10 x<y ® Sx<Sy 11 x<Sy ® (x<y Ú x=y)

 

12 x· 0=0 13 x· Sy=x· y+x

 

14 xpot0=S0 15 xpotSy= x· (xpoty)

Istnieje wiele ścisłych matematycznych definicji zbioru relacji obliczalnych.

Przyjmując inną definicję obliczalności twierdzenie charakteryzujące relacje obliczalne w powyższy sposób dowodzi się jako

Twierdzenie o mocnej reprezentowalności relacji obliczalnych w arytmetyce liczb naturalnych.

 

3. Ogólno filozoficzny sens rozstrzygalności

Zgodnie z powyżej przytoczonymi charakterystykami rozstrzygalności, jeśli teoria jest rozstrzygalna, to sprawdzenie czy określone zdanie jest twierdzeniem teorii powinno sprowadzać się do pewnego postępowania dającego się przeprowadzić w skończonej ilości prostych zabiegów myślowych będących zabiegami na symbolach. Natomiast treść przypisana zdaniu może być złożona, może np. dotyczyć zbioru nieskończonego. Zdanie badane może mianowicie być odpowiedzią na pytanie nazwane powyżej pytaniem generalnym. Może mieć postać:

Czy każde A jest B?

Na gruncie teorii rozstrzygalnej możemy mieć więc do czynienia z pewnym paradoksalnym zjawiskiem, że pytania dotyczące wszystkich przedmiotów zbioru nieskończonego rozstrzygamy przy pomocy postępowania, które składa się zawsze ze skończonej ilości kroków, skończonej ilości prostych zabiegów myślowych na symbolach.

Paradoksalność tej sytuacji można scharakteryzować następująco. Zasadniczym sposobem wzbogacania naszej wiedzy ogólnej jest stwierdzanie pewnych faktów.

Stąd naturalnym wydaje się, że: pytania o poszczególne elementy zbioru są bardziej elementarne od pytań o cały zbiór, czyli o wszystkie jego element. Dlatego, żeby przekonać się, czy wszystkie A są jakieś (są B), podstawową metodą wydaje się sprawdzenie po kolei, czy rzeczywiście każde A jest B. Chcąc odpowiedzieć na podstawowe pytanie generalne wydaje się, że w wielu przypadkach musimy po prostu przeglądać po kolei wszystkie przedmioty oznaczone nazwą “A”, czyli np. ustawić je sobie w ciąg: A₁ A₂ A₃ ..., a następnie o każdym z tych przedmiotów po kolei badać, czy jest on B.

Sprawdzanie kolejne dla każdego A zachodzenia pewnego faktu elementarnego może być dość żmudne. Stąd właśnie z czysto praktycznego względu zagadnienie rozstrzygalności może wydawać się ważne. Sprowadza się ono do kwestii możliwości jakby przeformułowania postaci pytania generalnego:

czy można tak przeformułować Pytanie generalne, ażeby odpowiadać na to pytanie można było bez sprawdzania dla każdego A odpowiedniego faktu elementarnego?

Postać pytania generalnego jest szczególnie ważna gdy zbiór A jest zbiorem nieskończonym, bo wówczas przejrzenie w skończonym czasie wszystkich elementarnych faktów dotyczących elementów zbioru A jest oczywiście nie możliwe.

Być może w świecie fizycznym nie istnieją zbiory nieskończone, ale w naszej wyobraźni rozważamy zbiory nieskończone. Zwłaszcza matematyka jest fantazjowaniem na temat zbiorów nieskończonych. Wyobrażamy sobie możliwość kreowania w czasie coraz to nowych obiektów wyobraźni, np. coraz większych liczb naturalnych przez każdorazowe dodanie jedynki do liczby już znanej. Wyobrażamy sobie też, że na linii prostej i w każdym jej odcinku jest nieskończenie wiele punktów, ponieważ między dwoma punktami można zawsze znaleźć jakieś punkty pośrednie, w szczególności punkt leżący pośrodku między danymi dwoma punktami a i b. I podobnie jest we wszystkich teoriach matematycznych.

Można powiedzieć, że doświadczenia badawcze w zakresie podstaw matematyki przeprowadzone w 20 wieku dają dość dobrą odpowiedź na powstające w tym zakresie zagadnienia rozstrzygalności. Odpowiedź najogólniejsza jest taka, że:

Zagadnienie rozstrzygalności zależy od pewnych treściowych właściwości pojęć, które stanowią przedmiot teorii.

Istnieją takie układy pojęć (oraz aksjomatów je charakteryzujących), dla których można podać ogólną metodę przeformułowywania pytań generalnych, że odpowiedź na dowolne pytanie generalne (czy każde A jest B?) nie będzie wymagała sprawdzań własności B dla wszystkich indywiduów będących elementami zbioru A, ale daje się wykonać w skończonej ilości kroków bez względu na wielkość zbioru A. Natomiast:

Istnieją też i takie układy aksjomatów, że takiej ogólnej metody przeformułowywania pytania generalnego nie ma. ażeby można było zawsze odpowiadać na takie pytania w skończonym postępowaniu.

Przeformułowaniem, o jakie chodzi, jest tutaj umiejętność wskazania takiego nowego pytania, które w oparciu o naszą wiedzę jest pytaniem:

1. Równoważnym pytaniu wyjściowemu.

2. Dotyczy pewnego innego zbioru A` , który jest zbiorem skończonym.

3. Jest pytaniem o łatwo stwierdzalne fakty elementarne dotyczące elementów tego nowego zbioru A`.

 

Istnieją proste przykłady całych grup pytań generalnych, dla których zagadnienie rozstrzygalności rozwiązuje się pozytywnie. Okazuje się mianowicie, że:

Każde pytanie generalne dotyczące liczb rzeczywistych i sformułowane przy pomocy samych tylko pojęć logicznych, bez użycia pojęć teoriomnogościowych, oraz przy użycia jako pojęć matematycznych tylko: mniejszości, dodawania i mnożenia - jest pytaniem rozstrzygalnym. (Jest to twierdzenie A. Tarskiego o rozstrzygalności teorii liczb rzeczywistych.) (Pożyteczne są tu ćwiczenia w sprawdzaniu formuł zapisanych przy pomocy wyżej wymienionych pojęć.)

 

Można przy tym zauważyć, że dość paradoksalnym byłoby, gdyby każda teoria była rozstrzygalna. Gdyby mianowicie każde pytanie generalne dotyczące każdego zbioru nieskończonego było rozstrzygalne, to znaczyłoby, że

pytanie o wszystkie elementy pewnego zbioru może być zawsze zamienione na pytanie o skończoną ilość przypadków, ale należących do innego zbioru.

Rozstrzygalność by znaczyła, że każde zagadnienie dotyczące zbiorów nieskończonych można uprościć i sprowadzić do zagadnienia dotyczącego zbioru skończonego.

Rozstrzygalność by więc znaczyła, że nieskończoność jest iluzją, bo zawsze można tak przeformułować rozważane zagadnienie (dane w postaci pytania generalnego), że odpowiedź na nie sprowadza się do badania skończonej ilości przypadków, tylko innych niż te, które sobie pierwotnie wyobrażaliśmy. Cała klasyczna matematyka operująca zbiorami nieskończonymi byłaby całkowitym tworzeniem iluzji.

Mówienie o nieskończoności byłoby więc, możemy tak powiedzieć, pewną formą oszustwa (lub samo-oszustwa) intelektualnego, skoro każdy problem można tak przeformułować, że o nieskończoności można nie mówić.

Używanie słowa ‘wszystko’, czyli używanie kwantyfikatora ogólnego byłoby tylko pewnym nieistotnym chwytem retorycznym, skoro zamiast mówić o wszystkich elementach nieskończonego zbioru A zawsze można powiedzieć tę samą w istocie informację, ale jako coś mówiącego o skończonej, a więc o ‘małej’ ilości elementów pewnego innego zbioru A`. Kwantyfikatory nie miałyby właściwie w takiej sytuacji poznawczego znaczenia.

Twierdzenie Gödela o nierozstrzygalności arytmetyki jest więc twierdzeniem, że na gruncie arytmetyki liczb naturalnych iluzja taka nie ma miejsca. Pytania o wszystkie liczby naturalne sformułowane przy pomocy dodawania i mnożenia są pytaniami, dla których nie ma ogólnej metody redukowania ich do pytań o skończoną ilość jakichś przypadków.

Twierdzenie o nierozstrzygalności teorii bogatych jest więc też twierdzeniem o istotności poznawczej kwantyfikatorów w strukturze ludzkiej wiedzy.

Teorie rozstrzygalne przestają być interesujące dla matematyków, Twierdzenie o rozstrzygalności właściwie staje się zakończeniem badań nad taką teorią. Dalszej twórczości już się nie spodziewamy. Natomiast teorie nierozstrzygalne nie przestają uchodzić za twórcze. Twierdzenie Gödela pokazuje więc, że twórczość w matematyce, w zakresie dowodzenia twierdzeń, (poza przypadkami uchodzącymi za bardzo proste)

nie jest redukowalna do szukania algorytmów, a następnie do mechanicznego sprawdzania.

 

 

2

Część główna (streszczenie podstawowych elementów dowodu nierozstrzygalności arytmetyki)

 

1. Klasy relacji różnoargumentowych, podobnych ze względu na definiowalność

Przy rozważaniu spraw rozstrzygalności i tworów matematycznych z tym związanych patrzymy na byty matematyczne pod kątem środków logicznych przy pomocy których zostają określone. W związku z tym tworzymy takie klasy, że do jednej klasy zaliczamy zarówno zbiory, jak i relacje dwuargumentowe, trójargumentowe i dowolnie wieloargumentowe, które mają tę wspólną cechę, że są definiowalne przy pomocy wybranych metod logicznych. Interesować nas zwłaszcza będą: Klasy zamknięte ze względu na definiowanie przy pomocy spójników zdaniowych. Klasy zamknięte ze względu na definiowanie przy pomocy utożsamienia i ustalania zmiennych, oraz klasy bytów definiowanych przy użyciu wybranej ilości wybranych układów kwantyfikatorów. Przy przechodzeniu od jednej klasy tworów definiowalnych do klasy tworów definiowalnych przy pomocy bogatszej aparatury ważnym pojęciem jest pojęcie relacji uniwersalnej.

Zajmować się będziemy relacjami wśród liczb naturalnych.

Def 2 Relacja dwuargumentowa R jest relacją uniwersalną dla klasy K relacji jednoargumentowych gdy:"A(AÎKŽ$n(nÎNŮ"x(A(x) ş R(n,x)))),

gdzie N oznacza zbiór liczb naturalnych.

Odnotujmy twierdzenie:

 

T 1 Jeśli klasa K jest zamknięta ze względu na utożsamianie zmiennych i ze względu na negację, to relacja uniwersalna dla zbiorów klasy K nie należy do klasy K

Dowód. Przypuśćmy, że R jest relacją uniwersalną dla zbiorów klasy K. Stąd zgodnie z Def 2.:

(1) "A(AÎKŽ$n(nÎNŮ"x(A(x) ş R(n,x)))),

Jeśli R należy do K, to ze względu na założone zamkniętości również: następujące relacje należą do K: R₁ = {x: R(x,x)} (definiowanie przez utożsamienie zmiennych), oraz

R₂ = {x: non R(x,x)} (definiowanie przez negację).

Czyli pisząc wyraźniej:

(2) R₂(x) ş non R(x,x))

Gdyby R₂ było w K, to zgodnie z (1) istniałoby takie n, że:

(3) "x(R₂(x) şR(n,x))

Skoro wzór (3) zachodzi dla każdego x, to zachodzi również dla n. A więc mięlibyśmy:

R₂(n)şR(n,n).

Tymczasem równoważność ta zgodnie (2) znaczy, że:

non R(n,n)şR(n,n).

Otrzymaliśmy więc sprzeczność, która dowodzi, że przypuszczenie, iż R należy do klasy K dla której jest relacją uniwersalną, jest przypuszczeniem fałszywym.

Z twierdzenia tego nie będziemy korzystali bezpośrednio przy dowodzie nierozstrzygalności arytmetyki. Zobaczymy, że dowód nierozstrzygalności arytmetyki będzie wzorowany na powyższym dowodzie, chociaż nieco bardziej złożony.

 

2. Arytmetyzacja sformalizowanego języka systemu arytmetyki

Do dowodu nierozstrzygalności arytmetyki potrzebna jest wiedza o możliwości opisu przy pomocy relacji obliczalnych pewnych podstawowych i dość elementarnych związków syntaktycznych między wyrażeniami. Nie będziemy się więc zajmować samymi tylko liczbami naturalnymi, ale zajmiemy się też wyrażeniami wchodzącymi w skład teorii matematycznych. Do nich, jak już zauważyliśmy, pojęcie obliczalności również można odnieść.

Przede wszystkim wrócimy do badania numeracji wszystkich funkcji zdaniowych arytmetycznych wyrażalnych w języku arytmetyki liczb naturalnych i zauważymy, że ciąg Yn(x), o którym była mowa w części pierwszej, jest definiowalny w samej arytmetyce liczb naturalnych. Jest to podstawowy rezultat arytmetyzacji języka. Chcąc to pokazać, trzeba po kolei rozważać pewne podstawowe pojęcia arytmetyczne.

Arytmetyzacja jako opis języka przy pomocy liczb naturalnych korzysta z pewnych ważnych właściwości liczb naturalnych. Przede wszystkim z faktu, że każda liczba naturalna daje się przedstawić jednoznacznie jako iloczyn liczb pierwszych:

a = 2pot k_0· 3pot k_1· 5pot k_2· ...· p_npot k_n

2,3,5...p_n jest ciągiem liczb pierwszych.

W ten sposób liczba a reprezentuje jednoznacznie ciąg liczb: k₀, k₁, k₂,...k_n.

Wyrażenia teorii sformalizowanej są zbudowane ze skończonej ilości symboli. Np. arytmetyka liczb naturalnych, którą będziemy rozważali może być zbudowana z 15 symboli:

( , ) ® non + · pot = $ " x / 0 S

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Symbol 13 pozwala tworzyć dowolnie wiele nowych zmiennych liczbowych:

x, x/, x//, x/// itd.

Jeśli symbolom powyższym przyporządkujemy liczby pod nimi umieszczone, to np.:

napisowi “x = x” zostaje przyporządkowana liczba: 2^12· 3⁹ · 5¹²

napisowi “x = 0” zostaje przyporządkowana liczba: 2^12· 3⁹ · 5¹⁴ itd.

Teraz następuje dość ważne dla całej konstrukcji spostrzeżenie arytmetyczne. Okazuje się mianowicie, że

wszystkie podstawowe pojęcia arytmetyki potrzebne do opisania działań na liczbach odpowiadających działaniom na napisach dają się łatwo zdefiniować w samej arytmetyce Ar jako działania obliczalne.

Dzięki temu można zrealizować podstawowy cel arytmetyzacji, czyli opisywanie języka teorii poprzez opis liczb reprezentujących wyrażenia języka i związków liczbowych między nimi.

Podamy definicje arytmetyczne wyjściowych pojęć potrzebnych w tej konstrukcji. Przy tym definicje te będą operowały wyłącznie kwantyfikatorami o ograniczonym zakresie, co zostaje wykorzystane w dalszym ciągu.

(podzielność) x½ y º (x=y Ú $ z ( z<y Ù y=x · z) )

(jedynka) 1=S(0) (różność) x ą y º non(x=y)

(zbiór liczb pierwszych) Pr(y) º yą 0 Ù yą 1Ù " x((x< yÙ x½ y ) ® (x=y Ú x=1))

(największy wykładnik, do którego podniesiona liczba x jest jeszcze dzielnikiem liczby y):

z = exp(x,y) º ((y=0Ú y=1)Ù z=0) Ú (1<yÙ z<yÙ x pot z½ yÙ non( x pot z+1½ y))

(liczba a jest iloczynem liczb pierwszych mniejszych od pewnej liczby):

il(a) º aą 0Ù aą 1Ù $ y( y<a Ù " x((x<y Ù Pr(x)) ® exp(x,a)=1)Ù " x((x<aÙ xï a) ® x<y)

(q jest następną liczbą pierwszą po p):

Nast(p,q) º Pr(p) Ù Pr(q) Ù " r((r<q Ù Pr(r)) ® (r<p Ú r=p))

( b jest iloczynem “regularnym” liczb pierwszych, czyli takim, że każda następna liczba pierwsza ma w b wykładnik o jeden większy)

Reg(b) º b=2Ú ( exp(2,b)=1Ù $ a(a<bÙ il(a)Ù a½ bÙ " c(c<bÙ il(c)Ù c½ b ® (c<aÚ c=a))Ù " p,q ((p<bÙ q<bÙ p½ a Ù q½ a Ù Pr(p)Ù Pr(q)Ù Nast.(p,q)) ® exp(q,b) = exp(p,b)+1) ))

Liczba regularna b ma więc postać: b = 2· 3^2· 5^3· ... · p_nⁿ⁺¹

(ciąg liczb pierwszych)

x=p_n º (Pr(x)Ù $ b(b<xpot(x pot x) Ù Reg(b) Ù exp(x,b)=n+1))

 

Operowanie funkcją ciągu liczb pierwszych i funkcją exp pozwala na zdefiniowanie dwóch podstawowych funkcji: funkcji długości wyrażenia i funkcji odpowiadającej syntaktycznemu pojęciu konkatenacji

(długość) dł(x)=d º $ c(c<xÙ d=c+1Ù exp(p_c,x)ą 0 Ù " u((u<xÙ c<u) ® exp(p_u,x)=0)

(konkatenacja)

y=x!z º dł(y)=dł(x)+dł(z) Ù " c(c<yÙ c<dł(x) ® exp(p_c,x)=exp(p_c,y)) Ù " c(c<y ® exp(p_c+dł(x),y)=exp(p_c,z))

Konkatenacją dwóch liczb jest taka liczba y, której pierwsza część ma składniki takie jak pierwsza liczba x, a druga część ma składniki takie jak druga liczba z. Konkatenacją dwóch wyrażeń nazywa się bowiem wyrażenie powstające przez połączenia dwóch wyrażeń w jedno, w taki sposób, że pierwszym jego członem jest pierwsze wyrażenie, a drugim drugie.

Konkatenacja pozwala na opisywanie związków między liczbami, które stanowią odpowiedniki związków między wyrażeniami.

Dla przykładu opiszmy teraz kiedy liczba x traktowana jako wyrażenie języka teorii powstaje przy pomocy reguły odrywania z liczb y i z traktowanych jako wyrażenia, z których y jest implikacją, a z poprzednikiem tej implikacji. Mianowicie:

x jest oderwaniem z od y º y=z!(2⁴!x)

Pamiętamy bowiem, że 4 jest numerem znaku implikacji. Stąd z!(2⁴!x) symbolizuje implikację o poprzedniku z i następniku x.

Analogicznie można opisać wszystkie inne operacje logiczne na wyrażeniach.

Rezultatem arytmetyzacji jest następujące przekonanie:

 

Przekonanie podstawowe:

Zbiór napisów jest rozstrzygalny (obliczalny) w sensie określenia wyjściowego, wtedy i tylko wtedy gdy zbiór ich numerów jest obliczalny w sensie określenia metamatematycznego.

Podobnie wszelkie działania na napisach są rozstrzygalne wtedy i tylko wtedy gdy odpowiadające im działania na liczbach są obliczalne.

 

3. Dowód twierdzenia o istotnej nierozstrzygalności arytmetyki liczb naturalnych

Teraz mamy możliwość przedstawić najbardziej intuicyjną, jak się zdaje, wersję dowodu nierozstrzygalności arytmetyki.

 

T2 Każda teoria niesprzeczna zawierająca w sobie arytmetykę Ar liczb naturalnych jest nierozstrzygalna

Dowód. Będzie on wzorowany na dowodzie twierdzenia T1, które tylko po to zostało powyżej przytoczone, żeby zwrócić uwagę na podobieństwo wnioskowania.

Wracamy do rozważenia ciągu Yn(x) wszystkich funkcji zadaniowych arytmetycznych, o którym mówiliśmy w punkcie 2 pierwszej części tej pracy. Podobieństwo do dowodu T1 polega na tym, że ciąg Yn(x) możemy potraktować jako relację dwuargumentową uniwersalną dla wszystkich relacji jednoargumentowych reprezentowalnych w Ar.

Jeśli efektywny jest ciąg Yn(x) , to również efektywny jest ciąg następujących podstawień:

w n tej formule poprawnej Yn(x) (o jednej zmiennej wolne x) zamiast tej zmiennej wstawiamy stałą (liczebnik) Sⁿ0. Tak utworzoną formułę możemy oznaczyć przez

Yn(Sⁿ0) .

Również jeśli poprzedzimy każdy wyraz tego ciągu znakiem negacji, to powstały w ten sposób ciąg negacji będzie ciągiem efektywnym. Ciąg ten można oznaczyć przez:

non Yn(Sⁿ0) . Początkowe wyrazy tego ciągu, to:

non Y0(0) czyli non 0=0

non Y1(S¹0) czyli non S0=S0

non Y2(S²0) czyli nonSS0=S0

non Y3(S³0) czyli non SSS0=SSSS0 itd.

 

Rozważmy teraz zbiór P* liczb naturalnych określony następująco:

P* = {n: “non Yn(Sⁿ0)” Î T}

czyli pisząc dokładniej:

(2) P*(n) º “non Yn(Sⁿ0)” Î T

 

Dowód twierdzenia przebiega w trzech krokach.

Krokiem pierwszym jest udowodnienie następującej przesłanki warunkowej, że:

(Przesłanka pierwsza) Jeśli T jest teorią rozstrzygalną, to zbiór P* jest obliczalny.

 

Dowód tej implikacji jest dość intuicyjny: rozważamy dowolną liczbę naturalną n i chcemy się przekonać, czy należy do zbioru P*, czy nie. Przepis na postępowanie sprawdzające jest następujący:

Znajdź najpierw formułę “Yn(x)”. Napisz liczebnik “Sn0”, wstaw ten liczebnik w miejsce zmiennej wolnej “x” w powyższej formule. Poprzedź całą formułę symbolem negacji “non”. Przy pomocy metody rozstrzygania istniejącej dla teorii T rozstrzygnij, czy powstała w ten sposób formuła: “non Yn(Sⁿ0)” jest, czy też nie jest twierdzeniem teorii T.

Następnym krokiem jest odwołanie się do Przekonania podstawowego, oraz do Def 1. (lub do twierdzenia o mocnej reprezentowalności zbiorów obliczalnych w arytmetyce liczb naturalnych). Stąd otrzymujemy, że:

Jeśli zbiór P* jest obliczalny, to dla zbioru P* istnieje takie wyrażenie arytmetyczne “Y(x)” o jednej zmiennej wolnej “x”, które reprezentuje w arytmetyce zbiór P* w sensie spełniania równoważności: (A) i (B), wymienionych w Def 1.

Wszystkie wyrażenia arytmetyczne o jednej zmiennej wolnej “x” mamy ujęte w efektywnym ciągu “Yn(x)”. Stąd wynika więc, że istnieje taka liczba naturalna k, że wyrażenie “Yk(x)” jest tym wyrażeniem arytmetycznym , które reprezentuje w arytmetyce zbior P*, czyli, że spełnione są następujące równoważności (A`) i (B`):

(A`) P*(n) ş “Yk(Sⁿ0)”Î Ar,

(B`) non P*(n) ş “nonYk(Sⁿ0)”Î Ar,

dla każdej liczby naturalnej n. Wobec tego z równoważności te są w szczególności spełnione dla n=k. Krok ten prowadzi więc do następujące przesłanki:

(przesłanka druga) Jeśli P* jest obliczalne, to istnieje taka liczba k, że

(3) P*(k) ş “Yk(S^k0)”Î Ar,

(4) non P*(k) ş “nonYk(S^k0)”Î Ar,

Z definicji zbioru P*, czyli ze wzoru (2) wynika natomiast, że:

(4) P*(k) ş “nonYk(S^k0)”Î T.

Teraz możemy przeprowadzić następujące rozumowanie pozwalające na podsumowanie dowodu. Jest to:

(Przesłanka trzecia) Jeśli istnieje takie k , że (3) i (4), to Teoria T byłaby sprzeczna.

Dowód przesłanki trzeciej.

Jeśli zachodziłoby non P*(k) , to zgodnie ze wzorem (4) mięlibyśmy, że “nonYk(S^k0)”Î Ar. Ponieważ Ar zawiera się w T , to byłoby również, że “nonYk(S^k0)”Î T. Wówczas jednak zgodnie z (2) wynikałoby, że P*(k) . Udowodniliśmy więc implikację postaci:

Jeśli non P*(k) , to P*(k)

Stąd zgodnie z prawem logiki : (non p Ž p) Ž p udowodniliśmy, że P*(k) .

Jeśli zaś zachodzi P*(k), to zgodnie z (3) mięlibyśmy, że “Yk(S^k0)”Î Ar, a ponieważ przyjęliśmy, że Ar zawiera się w T, więc byłoby, że “Yk(S^k0)”Î T. Z drugiej strony ze wzoru (2) wynika, że jeśli zachodzi P*(k), to “nonYk(S^k0)”Î T. Jeśli więc zachodzi P*(k), to zbiór T byłby sprzeczny, bo zawierałby zdanie “Yk(S^k0)” , oraz jego negację.

Podsumowanie całego dowodu: Jeśli zbiór T jest niesprzeczny, tak jak to założyliśmy w twierdzeniu, to zgodnie z przesłanką trzecią nie może istnieć takie k o którym mowa w jej poprzedniku. Wobec tego zgodnie z przesłanką drugą zbiór P* nie może być obliczalny. Wobec tego (zgodnie z przesłanką pierwszą) również zbiór T nie może być rozstrzygalny.

 

K. Gödel w pierwszej swojej pracy o nierozstrzygalności (Űber formal unentscheidbare Sätze...1931) podkreśla związek powyżej przedstawionego rozumowania (zwanego też czasem rozumowaniem przekątniowym) z tzw. antynomią Kłamcy. Istotnie ten sposób rozumowania można opisać jako poszukiwanie (przy pomocy funkcji uniwersalnej , jak to podkreślałem wcześniej,) takiej wypowiedzi, która by przeczyła samej sobie.

 

5. Wnioski dotyczące niezupełności arytmetyki

 

T 3 Każda teoria T zupełna, oparta o logikę i mająca obliczalną aksjomatykę jest teorią rozstrzygalną

Dowód. Jeśli teoria T jest sprzeczna, to jest rozstrzygalna, bo do teorii sprzecznej należą wszystkie zdania, a zbiór wszystkich zdań jest rozstrzygalny. Jeśli teoria T jest niesprzeczna, to przepis na rozstrzyganie o dowolnym zdaniu Z czy należy do T, czy nie można opisać następująco:

Określamy pewien naturalny porządek wszystkich skończonych ciągów zdań zbudowanych sensownie z terminów pierwotnych teorii T. (Od najkrótszych ciągów najkrótszych zdań do coraz dłuższych.) Przeglądamy kolejne elementy tego porządku i badamy je pod względem tego, czy dany ciąg skończony: 1. Zaczyna się od skończonej ilości aksjomatów teorii T; 2. Kończy się zdaniem Z, lub zdaniem: non Z, oraz 3. Stanowi poprawny, oparty o logikę, dowód. Wszystkie trzy wymienione właściwości dają się efektywnie sprawdzić. Jeśli przy tym przeglądaniu natrafimy na dowód zdania Z, to Z jest twierdzeniem teorii T, a jeśli natrafimy na dowód zdania non Z, to Z nie jest twierdzeniem teorii T.

Procedura ta jest obliczalna, ponieważ teoria T jest z założenia zupełna, a więc albo zdanie Z albo zdanie non Z ma swój dowód. A więc przeglądanie ciągów pod kątem tego, czy są dowodami dla Z lub dla non Z zawsze się zakończy natrafieniem na jedną z tych ewentualności i tylko na jedną z nich, skoro T jest niesprzeczna.

 

T 4 Jeśli teoria T jest nierozstrzygalna, oparta o logikę, mająca obliczalną aksjomatykę i zawiera arytmetykę Ar, to T jest niezupełna

Dowód. Jeśli T jest nierozstrzygalna, to jest niesprzeczna, bo zbiór sprzeczny jako pełny jest rozstrzygalny. Zgodnie z T 3 teoria T nie może być zupełna.

 

T 5 Jeśli teoria T ma obliczalną aksjomatykę, jest niesprzeczna, oparta o logikę i zawiera arytmetykę Ar, to jest niezupełna

Dowód. Jeśli T jest niesprzeczna i zawiera Ar, to zgodnie z T 2 jest nierozstrzygalna, a następnie zgodnie z T 4 jest niezupełna.

 

 

3

Część trzecia

Wnioski dotyczące postaci zdań niezależnych

 

W naturalny sposób nasuwa się pytanie: jaką najprostszą postać może posiadać w arytmetyce Ar zdanie niezależne od jej aksjomatów, czyli takie, które ani samo nie jest twierdzeniem, ani jego negacja? Pytanie to wiąże się z pytaniem: jaką postać najprostszą posiadają formuły definiujące relacje obliczalne?

Najpierw zajmiemy się relacjami obliczalnemi, a następnie postacią zdań niezależnych. Zaczniemy od innej nieco definicji obliczalności. Wstępem do niej będzie definicja pewnej węższej klasy relacji definiowalnych mianowicie klasy relacji elementarnie obliczalnych (zwanych w skrócie elementarnymi), określonych w dziedzinie liczb naturalnych.

 

Def 3 Klasa relacji elementarnych jest najmniejszą klasą relacji zawierającą jako elementy wyjściowe relacje: x=0, x=Sy, x<y, x=y+z, x=y· z, x=ypotz , oraz zamkniętą ze względu na operacje utożsamiania i ustalania zmiennych, podstawiania funkcji (wyrażających relacje już należące do naszej klasy) za zmienne, oraz ze względu na operacje rachunku zdań i kwantyfikatorów ograniczonych.

Przykładami relacji elementarnych są wszystkie relacje arytmetyczne określone w punkcie 2 drugiej części wykładu (punkcie poświęconym arytmetyzacji języka sformalizowanych teorii matematycznych). Wszystkie wymienione tam relacje, jak podzielność, zbiór liczb pierwszych, ciąg liczb pierwszych, funkcja exp, konkatenacja, operacja odrywania były określone przy pomocy definicji nie wyprowadzających poza wyżej określoną klasę relacji elementarnych. W szczególności dbaliśmy o to, żeby wszystkie kwantyfikatory użyte w definicji były kwantyfikatorami ograniczonymi.

W szczególności uzyskujemy też następujące:

 

Twierdzenie o elementarności relacji dowodu:

Relacja: m jest numerem poprawnego dowodu wyprowadzającego z aksjomatów Ar twierdzenie o numerze n, jest relacją obliczalną elementarną.

 

Dowód polega na przejrzeniu, że wszystkie definicje pojęć potrzebnych do określenia arytmetycznego odpowiednika relacji dowodu dają się wypowiedzieć przy pomocy relacji wyjściowych oraz operacji rachunku zdań i kwantyfikatorów o ograniczonym zakresie.

Istotnie, dowodem twierdzenia jest skończony ciąg zdań, który zaczyna się od aksjomatów, kończy się twierdzeniem dowodzonym, a wszystkie pozostałe zdania tego ciągu są otrzymywane ze wcześniejszych zdań tego ciągu przy pomocy logicznych reguł.

Arytmetyzacją dowodu jest więc relacja liczbowa R(m,n) taka, że:

m. jest liczbą, którą rozumiemy jako ciąg: k₀, k₁, k₂,...,k_u. W tym oczywiście sensie, że:

m = 2pot k_0· 3pot k_1· 5pot k_2· ...· p_upot k_u

Czyli poszczególne wyrazy tego ciągu są wyznaczone przez liczbę m. jako wykładniki w jej rozwinięciu: k_i=exp(p_i,m.) .

początkowymi wyrazami tego ciągu są numery aksjomatów. Np. możemy przyjąć, że k₀, k₁,...,k₂₀ są numerami aksjomatów. (Numery aksjomatów są pewnymi liczbami stałymi.)

ostatni wyraz ciągu: k_u = n .(Czyli jest numerem dowodzonego twierdzenia.)

dla każdego i<u , jeśli i>20, to istnieją takie j, s<i, że: k_i powstaje z k_j oraz k_s przez zastosowanie jednej z reguł dowodzenia. (W punkcie 2 części 2 jest opisana tylko reguła odrywania jako operacja na numerach napisów, ale wszystkie inne reguły logiki dają się analogicznie opisać jako relacje elementarne.)

Powyższy opis liczby m można określić jako opis ‘wewnętrzny’. Wszystkie liczby stanowiące elementy opisu są wyraźnie mniejsze od liczby m. Wszystkie kwantyfikatory są lub mogą być ograniczone do liczb mniejszych od liczby m. Relacja R jest więc relacją elementarną.

 

T 6 Każda relacja elementarna jest obliczalna i reprezentowalna w Ar przez formułę arytmetyczną, która ją w naturalny sposób definiuje.

Dowód . Do tej pory nie zajmowaliśmy się bliżej dowodami na gruncie arytmetyki Ar.

Łatwo sprawdzić, że: z pierwszych trzech aksjomatów wynikają wszystkie zdania prawdziwe będące nierównościami postaci: “non(k = m)” dla dwóch różnych liczebników k i m. Np. “non(SSS0 = SS0)” (czyli: “3 ą 2”). Równości prawdziwe są postaci k=k, a więc wynikają z samej logiki identyczności. Spostrzeżenia te można podsumować w postaci równoważności:

k=Sm º “k=Sm” Î Ar Przyjmujemy tu skrót: k = S^k0.

k ą Sm º “non(k = Sm)” Î Ar

Dowód w metateorii powyższych równoważności posługuje się zasadą indukcji w metateorii, ale nie musi ona występować w samej teorii.

Zgodnie z wyjściową definicją obliczalności równoważności powyższe oznaczają, że relacja: k=Sm jest obliczalna i reprezentowalna w Ar przez formułę “x=Sy” pierwotną w Ar.

Z aksjomatów 9 i 10 wynikają wszystkie prawdziwe nierówności postaci: k<m. Natomiast prawdziwe negacje: non(k<n) wynikają z aksjomatów 6 i 7.

Łatwo sprawdzić, że następne aksjomaty Ar wyżej wymienione przenoszą tę właściwość na dodawanie, mnożenie i potęgowanie. Prawdziwe równości typu: n+m=k wynikają z aksjomatów 4 i 5 charakteryzujących indukcyjnie dodawanie, oraz z już udowodnionej reprezentowalności następnika, a prawdziwe negacje: non(n+m=k) wynikają z aksjomatów 6 i 7 oraz z udowodnionych równości i mniejszości. Analogicznie jest dla mnożenia i potęgowania.

Dotychczasowy wywód możemy podsumować w postaci przesłanki, że:

Jeśli arytmetyka Ar jest niesprzeczna, to wyjściowe relacje elementarne są obliczalne (oraz reprezentowalne w Arytmetyce przez formuły pierwotne Ar, które są bezkwantyfikatorowe).

Następnie zauważymy, że:

Jeśli relacje A i B są reprezentowane w Ar odpowiednio przez formuły x i y , to relacja utworzona z relacji A i B przez operacje nie wyprowadzające z klasy relacji elementarnych jest reprezentowana w Ar przez formułę powstającą w analogiczny sposób z formuł x i y .

Wystarczy rozważyć operacje: negacji, koniunkcji i kwantyfikatora ogólnego ograniczonego. (Dla utożsamiania i ustalania zmiennych, oraz dla podstawiania funkcji, wyrażających relacje elementarne sprawa wydaje się oczywista.)

Jeśli A i B są reprezentowane przez x i y , to znaczy, że:

(1) A(n) º “x (n)” Î Ar (2) B(n) º “y (n)” Î Ar

nonA(n) º “non x (n)” Î Ar nonB(n) º “non y (n)” Î Ar

Ze wzorów powyższych i praw logiki łatwo widać, że:

A(n)Ù B(n) º “x (n)” Î ArÙ “y (n)” Î Ar º “x (n)Ù y (n)” Î Ar

Podobnie uzyskujemy równoważność (B) czyli pełną reprezentowalność koniunkcji.

Krok dla negacji wynika z prawa podwójnego przeczenia. Ciekawsze jest przejście dla kwantyfikatora ograniczonego.

Zakładamy więc, że (1) i dowodzimy, że

(3) " n(n<k ® A(n) º “" x( x<k ® x (x))” Î Ar

(4) non(" n(n<k ® A(n)) º “non(" x( x<k ® x (x)))”

Aby dowieść powyższych równoważności wystarczy zauważyć, że z aksjomatów przyjętych w Ar wynikają tezy arytmetyczne:

non(x<0)

oraz wszystkie tezy typu:

x<S0 º x=0

x<SS0 º x=0 Ú x=S0

x<SSS0 º x=0 Ú x=S0 Ú x=SS0

Czyli

5. dla każdego k>0: “ x<k º x=0 Ú x=S0 Ú ... Ú x=S^k-10” Î Ar

Dowód (5) jest oczywiście przez indukcję, ale w metasystemie. Z (5), oraz z praw kwantyfikatorowych wynikają tezy o których mowa we wzorach (3) i (4).

 

Teraz podamy inną arytmetyczną definicję obliczalności:

 

Def 3 Relacja arytmetyczna P jest obliczalna, gdy istnieją takie dwie relacje elementarne R i U (mające o jeden argument więcej), że:

(C) P(n) º $ m R(m,n) oraz (D) non P(n) º $ m U(m,n)

 

T 7 Jeśli Ar jest niesprzeczna, to definicja metamatematyczna pokrywa się z arytmetyczną

Skrót dowodu. Jeśli Ar jest niesprzeczna i relacja P jest obliczalna w sensie Def 1 , to znaczy, że spełnione są wzory (A) i (B) wymienione w Def 1.

We wzorach tych występują stwierdzenia postaci:

“f ” Î Ar oraz “nonf ” Î Ar

Należeć do zbioru Ar znaczy tyle co posiadać dowód. Stwierdzenia te dają się więc wypowiedzieć w postaci zdań mówiących, że dla pewnych elementarnych relacji R i U:

$ m R(m,n) $ m U(m,n)

gdzie R(m,n) mówi, że m jest numerem dowodu zdania “f ” o numerze n, a U(m,n) mówi, że m jest numerem dowodu zdania “nonf ” o numerze n. Relacja bycia numerem dowodu jest bowiem relacją elementarną zgodnie z twierdzeniem o elementarności relacji dowodu. Relacje R i U są więc elementarne. Relacja P spełnia więc warunki (C) oraz (D) definicji Def 3 .

Odwrotnie, jeśli P spełnia warunki Def 3, czyli dla pewnych relacji elementarnych R oraz U zachodzą wzoru: (C) oraz (D), to wówczas sposób rozstrzygania zachodzenia względnie nie zachodzenia relacji P można opisać jako obliczalny w podstawowym intuicyjnym sensie następująco:

przeglądamy wszystkie liczby naturalne m po kolei, (od zera). Ponieważ relacje R oraz U są obliczalne zgodnie z twierdzeniem T6, przeto możemy dla każdej liczby naturalnej m. sprawdzać czy zachodzą relacje: R(m,n) oraz U(m,n). Ponieważ zgodnie z prawem wyłączonego środka albo zachodzi P(n) albo nonP(n), wobec tego przeglądając wszystkie liczby naturalne natrafimy w końcu na taką liczbę m, dla której będzie zachodzić relacja R(m,n) lub będzie zachodzić relacja U(m,n). Procedura ta da więc zgodnie ze wzorami (C) oraz (D) w skończonym czasie wynik rozstrzygający o zachodzeniu lub nie zachodzeniu relacji P(n).

 

T8 Jeśli Ar jest niesprzeczna, to dla każdej relacji obliczalnej istnieje taka formuła ją reprezentująca (w sensie spełniania wzorów (A) i (B) z definicji Def 1 , że: formuła ta jest postaci $ z f gdzie formuła f jest formułą elementarną, czyli wyłącznie z kwantyfikatorami ograniczonymi.

Dowodu tego twierdzenia nie będę tutaj powtarzał, ponieważ nie potrafię obecnie wskazać innego dowodu, poza powtórzeniem dowodu znajdującego się w książce: Zarys logiki matematycznej, wydanie 6 s.423 (jako Twierdzenie 20*). Dowód ten korzysta z z funkcji elementarnych. Natomiast uważam, że istnieje możliwość dowodu, który nie operowałby pojęciem funkcji, a jedynie pojęciem relacji elementarnej.

 

T 9 Jeśli T jest niesprzeczna i zawiera arytmetykę, to zbiór zdań arytmetycznych teorii T mających postać $ z f gdzie formuła f jest formułą elementarną, jest zbiorem nierozstrzygalnym

Dowód. Jest w zasadzie powtórzeniem dowodu podstawowego twierdzenia T 2 o nierozstrzygalności. Oznaczmy przez E zbiór zdań arytmetyki mających postać: $ z f , gdzie f jest formułą elementarną, czyli mającą wszystkie kwantyfikatory ograniczone. Niech F n(x) będzie efektywnym ciągiem wszystkich takich formuł z jedną zmienną wolną x. Efektywnym jest wówczas również ciąg podstawień i ciąg ich negacji, czyli ciąg formuł postaci:

nonF n(Sⁿ0)

Badamy zbiór: Q={n: “nonF n(Sⁿ0)”Î T}

Następnie w sposób analogiczny jak w dowodzie T2 dowodzimy, że Q jest rozstrzygalne, co prowadzi do sprzeczności.

 

T 10 Jeśli T ma obliczalną aksjomatykę, jest niesprzeczna i zawiera Ar, to istnieje w T zdanie arytmetyczne niezależne od T mające postać $ x f gdzie formuła f jest formułą elementarną

Dowód również analogiczny jak dowód T 3.

Zdanie niezależne: znaczy tutaj zdanie, które ani ono, ani jego negacja nie jest twierdzeniem teorii.

Jako komentarz do tego twierdzenia możemy powrócić do filozoficznych rozważań z części pierwszej. Skoro istnieje zdanie postaci: $ x f , które nie jest twierdzeniem, ani jego negacja nie jest twierdzeniem, to znaczy, że istnieje problem typu:

Czy wszystkie liczby naturalne są jakieś?

Które zawiera w sobie tylko kwantyfikatory ograniczone, którego na gruncie naszej teorii nie możemy rozstrzygnąć. Teorie o rekurencyjnej aksjomatyce nie pozwalają na wyprowadzenie wszystkich twierdzeń arytmetycznych o stosunkowo prostej budowie, mianowicie takich, w których mówimy tylko o stosunkowo prostych własnościach liczb, bo o własnościach, do których zbadania nie ma potrzeby odwoływania się do liczb większych od liczby rozważanej.

Okazuje się, że liczby naturalne stanowią tak bogatą rozmaitość, że nie istnieje ogólna metoda, która by pozwalała każde tego typu (a więc stosunkowo proste teoretycznie) pytanie o wszystkie liczby naturalne sprowadzić do pytania o skończoną ilość jakichś wyraźnie wskazanych przypadków.

Kiedyś powtarzano jako dowcip pytanie: Czy Bóg może stworzyć taki kamień, którego nie mógłby podnieść? Analiza tego pytania pokazuje, że pojęciem wszechmocy operujemy w potocznym użyciu w sposób sprzeczny. Ludzie natomiast istotnie zbudowali takie twory wyobraźni, mianowicie matematykę, których w jakimś sensie nie potrafią udźwignąć tak, jak by tego chcieli. Chcą mianowicie mieć wyraźne, (czyli rozstrzygalne) metody weryfikacji swoich twierdzeń. Ale dla każdej takiej metody odpowiadania na pytania potrafią stawiać pytania, na które nie potrafią odpowiedzieć.

 

Na marginesie tych badań powstają natomiast zagadnienia związane z opisem relacji obliczalnych w sposób niezależny od funkcji obliczalnych. Historycznie pierwszym określeniem relacji obliczalnej było określenie mówiące, że

R jest obliczalne gdy istnieje funkcja obliczalna f taka, że dla wszelkich a

R(a) º f(a)=0

Typ definicyjny relacji zostaje w ten sposób wyznaczony przez typ definicyjny funkcji. Powstaje więc np. pytanie: czy relacje wyznaczone przez funkcje pierwotnie rekurencyjne są tymi samymi, co relacje wyznaczone przez funkcje elementarne?

Podobne pytanie: czy zbiór relacji elementarnych można scharakteryzować jako najmniejszy zbiór relacji zawierający tylko podzielność i mniejszość, oraz zamknięty ze względu na kwantyfikatory ograniczone, rachunek zdań i utożsamianie zmiennych?

Pytania takie zainicjował już Leszek Pacholski w latach 70-tych. Może są rozwiązane? (Nie wiem, bo nie dość śledziłem ostatnio ‘na rynku’ te sprawy.)

Definicja obliczalności Def 3 nasuwa też zagadnienie: zamiast arytmetyki użyć system mający jedynie pojęcie konkatenacji jako pojęcie pierwotne, a kwantyfikator ograniczony zdefiniować jako zrelatywizowany do fragmentów pewnego wyrażenia. Opisać względnie prosty i elegancki system mający konkatenację jako termin pierwotny (oraz stałą indywiduową), w którym będzie można reprezentować wszystkie relacje obliczalne zdefiniowane jako przedstawialne dualnie w postaci: jeden kwantyfikator egzystencjalny nieograniczony, a po nim już same ograniczone, analogicznie do Def 3. Mięlibyśmy formalną metalogikę uwolnioną od matematyki, która potrzebna była Gödelowi naprawdę tylko do reprezentowania ciągów skończonych.