Andrzej Grzegorczyk

Konspekt zajęć nt.

Zagadnienia rozstrzygalności

 

Zajęcia składają się z trzech sesji. Na początku zostaje postawiony problem rozstrzygalności jako problem filozoficzny. Odpowiedź na dowolne pytanie naukowe zależy często od sposobu sformułowania zagadnienia badawczego. Stąd zadanie rozstrzygalności można określić jako: takie przeformułowanie pytania, ażeby odpowiedź na pytanie wyjściowe sprowadzała się do odpowiedzi na względnie małą ilość prostych zabiegów sprawdzających. Jeśli teoria jest rozstrzygalna, to każde pytanie na jej gruncie ma takie przeformułowanie bez względu na to, czy (zgodnie z wyobrażeniem towarzyszącym rozwijaniu teorii) pytanie dotyczy skończonej, czy nieskończonej ilości przedmiotów. Rozstrzygalność pytania dotyczącego nieskończonego zbioru wydaje się szczególnie paradoksalna. Możliwość przeformułowania pytania generalnego: Czy wszystkie A są F? wskazuje na pewną jakby pozorność kwantyfikatora ogólnego na gruncie danej teorii. Teoria jest nie tyle teorią nieskończonej ilości przedmiotów, o których mówimy, co teorią pewnej skończonej ilości prostych cech tych przedmiotów, - cech wyróżnionych zwykle w dowodzie rozstrzygalności przeprowadzonym metodą eliminacji kwantyfikatorów (przykłady). Można uważać, że gdyby wszystkie teorie były rozstrzygalne, to znaczyłoby, że wszystkie pytania generalne są pozorne, a kwantyfikator ogólny jest tworem jakby iluzorycznym.

W sesji drugiej zostaje pokazany najłatwiejszy dowód istnienia teorii nierozstrzygalnej (arytmetyka liczb naturalnych). Z nierozstrzygalności prosto wynika niezupełność.

W sesji trzeciej dowodzimy jaki najprostszy kształt może mieć zdanie nierozstrzygalne w arytmetyce. Okazuje się, że są to zdania będące odpowiedzią na pytanie generalne: Czy wszystkie liczby naturalne są F? Przy tym właściwość F jest tego rodzaju, że dla każdej konkretnej liczby naturalnej 0,1,2,3,4,5 ... itd. twierdzeniami arytmetyki są zdania: F(0), F(1), F(2), F(3), F(4), F(5),... itd. Natomiast zdanie ogólne: “Dla każdej liczby naturalnej x F(x).” nie jest twierdzeniem arytmetyki, ani również jego negacja nie jest twierdzeniem arytmetyki. Nasuwająca się tu zasada uogólniania nie jest zasadą dającą się wypowiedzieć w postaci jednego efektywnego przepisu analogicznego do innych praw i reguł logiki. Można to podsumować w postaci stwierdzenia, że nieskończoność, do jakiej prowadzi arytmetyczna wyobraźnia, jest niesprowadzalna do żadnej dającej się pomyśleć skończoności.

Przy okazji pokazana jest pewna nowa perspektywa konstruktywistycznej wizji wiedzy, oraz związana z nią nowa formalna definicja konstruktywności (efektywności, obliczalności) na gruncie bardzo ogólnego systemu metalogiki.

Zalecane lektury