Niezupełność teorii matematycznych

Opis i plan

Warsztaty dotyczyć będą głównie słynnego wyniku K. Gödla na temat niezupełności, które zadało w 1931 r. kłam próbom sprowadzenia całej matematyki do takiego stanu, w którym każde prawdziwe zdanie matematyczne dałoby się wywieść z ustalonych aksjomatów, a najlepiej jeszcze bezmyślnie za pomocą pewnego uniwersalnego algorytmu. Problem zaczyna się już na poziomie liczb naturalnych. Tzw. pierwsze twierdzenie Gödla o niezupełności w uproszczeniu brzmi tak: "żadne sensowne teorie formalne (w komplecie z systemem dowodzenia), które są niesprzeczne i zawierają podstawową arytmetykę liczb naturalnych, nie są w stanie udowodnić wszytkich prawdziwych zdań o liczbach naturalnych".

Po pierwsze zrozumiemy, co to twierdzenie (w pewnej wersji) mówi, czyli wyjaśnimy sobie jak uprawiać ścisłą matematykę o twierdzeniach i ich dowodach. Przybliżymy sobie formalizm logiki pierwszego rzędu, rozważymy parę aksjomatyk liczb naturalnych, a dla tych najskromniejszych wskażemy palcem, jako przystawkę, niedowodliwe zdania prawdziwe.

Z drugiej strony, spróbujemy ten słynny wynik udowodnić, czyli będzie o tym jak uczciwie w języku pierwszego rzędu dla liczb, dodawania i mnożenia sformułować zdanie G, które okazuje się równoważnie znaczyć "nie da się udowodnić G". Pomówimy więc o tym, jak coraz bardziej złożone (pierwotnie rekurencyjne) własności liczb dają się wyrazić przez sprytne konstrukcje w logice pierwszego rzędu, a także o tym, dlaczego te własności nam wystarczają do konstrukcji G. Pominiemy pewne techniczne, ale w miarę niezaskakujące, detale. Nie braknie nam jednak zadań do rozwiązania, żeby oswoić się ze światem matematyki "o matematyce".

Przy okazji tych rozważań pomówimy również o dość pokrewnych wynikach: niemożności dowodu niesprzeczności, czyli drugim twierdzeniu Gödla o niezupełności, a także twierdzeniu Tarskiego o niedefiniowalności prawdy.

Możliwe, że wskażemy też pewne naturalne prawdziwe zdania w języku arytmetyki, które wymykają się np. aksjomatyce Peano.

Przy okazji tego wszystkiego może nam starczyć czasu, żeby trochę się pobawić samą logiką pierwszego rzędu, czyli opowiedzieć sobie o tym, jak:

• konstruować egzotyczne modele liczb naturalnych/rzeczywistych (np. z "nieskończenie małymi") za pomocą twierdzenia Łosia i twierdzenia o zwartości rachunku zdań,
• odróżniać (lub nie) modele (np. teorii porządków) za pomocą gier Ehrenfeuchta,
• przyprawić się o ból głowy paradoksem Skolema.

Wymagania

(szkolna) logika zdaniowa, trochę minimalnego obycia z kwantyfikatorami/formułami pierwszego rzędu, ale w zakresie, który przećwiczą zadania, indukcja matematyczna.

Kwalifikacja

W poniedziałek pojawią się już wszystkie zadania. Rozwiązania należy wysyłać na adres emailowy orlef.damian@gmail.com, preferowany tytuł maila w formacie "[WWW13] - imię i nazwisko". Czas do 10.07.