Twierdzenia Gödla i logiczne podstawy matematyki 3501-K-TGLPM-OG

1. Aksjomatyzacje arytmetyki: aksjomatyka Robinsona Q, aksjomatyka Peano PA, rola aksjomatów indukcji.
2. Arytmetyzacja składni i twierdzenie o reprezentowalności funkcji rekurencyjnych.
3. Lemat przekątniowy i I twierdzenie Gödla o niezupełności, nierozstrzygalność arytmetyki.
4. Warunki dowodliwości i II twierdzenie Gödla o niezupełności (tzw. twierdzenie o niedowodliwości niesprzeczności).
5. Hierarchia arytmetyczna, twierdzenie Parikha o funkcjach dowodliwie całkowitych, Σ1 – zupełność PA i jej zastosowania.
6. Twierdzenie Tarskiego o niedefiniowalności prawdy, informacje o aksjomatycznych teoriach prawdy.
7. Twierdzenie Gödla-Rossera o niezupełności, ω – reguła, ω – sprzeczność, paradoks Yablo.
8. Twierdzenie Löba, zasady refleksji, (globalna) refleksywność PA.
9. Niestandardowe modele PA: istnienie (jako wniosek z tw. Gödla), konstrukcje (zwartość, ultraprodukt), własności (lemat o przelewaniu i jego zastosowania, odcinki początkowe i przekroje, typ porządkowy modeli PA, twierdzenie Gaifmana, twierdzenie Macdowella-Speckera, twierdzenie Rylla-Nardzewskiego o nieskończonej aksjomatyzowalności PA)
10. Twierdzenie Tennenbauma o nierekurencyjności niestandardowych modeli PA.
11. Zasada kolekcji i jej zastosowania, zasada minimum, porównanie z indukcją.
12. Zasady kombinatoryczne niezależne od PA (twierdzenie Parisa-Harringtona), metoda indykatorów.
13. Informacje o matematyce odwrotnej i podsystemach arytmetyki drugiego rzędu, konserwatywność ACA0 nad PA.

5. Twierdzenie Tarskiego o niedefiniowalności prawdy,

Rodzaj przedmiotu

ogólnouniwersyteckie

Tryb prowadzenia

w sali

Efekty kształcenia

Wiedza i umiejętności:
- Student zna różne aksjomatyzacje arytmetyki i potrafi wskazać przyczyny oraz konsekwencje ich różnic.
- Student zna dowody twierdzeń Gödla o niezupełności, rozumie i potrafi udowodnić ich konsekwencje i rolę w podstawach matematyki, w tym rozumie elementarne, zagadnienia dotyczące predykatu prawdy.
- Student zna i rozumie metody konstruowania niestandardowych modeli arytmetyki oraz potrafi wskazać i udowodnić podstawowe własności tych modeli.
- Student zna zasady kombinatoryczne niedowodliwe w arytmetyce Peano i rozumie metody ich dowodzenia oraz dowodzenia ich niedowodliwości.
- Student wie, czym jest matematyka odwrotna i czym jest arytmetyka drugiego rzędu oraz jej podsystemy.

Kompetencje społeczne:
- aktywna postawa wobec problemów teoretycznych i praktycznych, w szczególności problemów sformułowanych z użyciem narzędzi logiki i arytmetyki
- rozwój zdolności poznawczych, samodzielności, wytrwałości w stawianiu pytań i szukaniu na nie odpowiedzi

Kryteria oceniania

- test końcowy: 60%
- prace domowe: 20%
- obecność i aktywność: 20%

Literatura

- P. Smith, An introduction to Gödel’s Theorems, Cambridge University Press 2013.
- P. Hajek, P. Pudlak, Metamathematics of First-Order Arithmetic.
- R. Kaye, Models of Peano Arithmetic, Oxford University Press 1991.
- A. Enayat, R. Kossak, Nonstandard models of Arithmetic and Set Theory, American Mathematical Society 2005.
- J. Kennedy, R. Kossak, Set Theory, Arithmetic and Foundations of Mathematics: Theorems, Philosophies, Cambridge University Press 2011.
- S. Simpson, Subsystems of Second Order Arithmetic, Cambridge University Press 2010.
- R. Kossak, J. Schmerl, The Structure of Models of Peano Arithmetic, Oxford University Press 2006.
- klasyczne i współczesne artykuły dotyczące arytmetyki i logiki.

Więcej informacji

Więcej informacji o poziomie przedmiotu, roku studiów (i/lub semestrze) w którym się odbywa, o rodzaju i liczbie godzin zajęć - szukaj w planach studiów odpowiednich programów. Ten przedmiot jest związany z programami:

Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb:

Strona przedmiotu 3501-K-TGLPM-OG w USOSweb