Niedowodliwość 1000-1M18ND

Program zajęć obejmie następujące cztery bloki tematyczne.

1. Niedowodliwość ogólnie: twierdzenia Gödla i okolice.

Arytmetyka Peano PA jako kanoniczna teoria obiektów skończonych. Związki wyrażalności w arytmetyce z teorią obliczeń. Zdania przekątniowe. Twierdzenia Gödla i wyniki pokrewne (Tarskiego, Rossera). Niedowodliwość zasad refleksji.

2. Dowody twierdzeń kombinatorycznych wymagające odwołań do nieskończoności.

Twierdzenie Parisa-Harringtona jako przykład zdania kombinatorycznego niedowodliwego w PA. Związek z siłą logiczną nieskończonego twierdzenia Ramseya. Niedowodliwość wariantów twierdzenia Kruskala o drzewach w teoriach o sile zbliżonej do PA.

3. Siła i ograniczenia argumentów ze zwartości.

Słaby lemat Königa: aksjomat formalizujący argumenty ze zwartości w logice, topologii i analizie. Twierdzenie Harringtona o konserwatywności słabego lematu Königa nad aksjomatem wyróżniania dla zbiorów obliczalnych. Wnioski dotyczące niedowodliwości za pomocą słabego lematu Königa. Metoda forcingu dla aksjomatycznych teorii arytmetyki.

4. Konieczność odwołań do obiektów wykładniczo dużych

Arytmetyka ograniczona jako formalizacja idei arytmetyki bez funkcji wykładniczej. Niedowodliwość zasady szufladkowej w arytmetyce ograniczonej. W miarę wolnego czasu: dowodliwość istnienia nieskończenie wielu liczb pierwszych w arytmetyce ograniczonej (twierdzenie Parisa, Wilkiego i Woodsa).

5. Zagadnienia uzupełniające (w miarę wolnego czasu).

- Twierdzenie Matijasiewicza o nieistnieniu algorytmu rozstrzygającego problem istnienia rozwiązań równań diofantycznych (10. problem Hilberta). Wniosek: żadna dostatecznie silna teoria nie dowodzi wszystkich prawdziwych twierdzeń o nieistnieniu rozwiązań równań diofantycznych.
- Niedowodliwość wariantów twierdzenia Kruskala o drzewach w teoriach niepredykatywnych, istotnie silniejszych niż PA.
- Potencjalny temat na deser: Metody algebraiczne w badaniu niedowodliwości, czyli jakich aksjomatów potrzeba, by udowodnić niewymierność pierwiastka z 2?