Logika matematyczna II 1000-1M16L2
Wykład składał się będzie z dwu zasadniczych części, uzupełnionych pewnymi bardziej zaawansowanymi tematami dostosowanymi m.in. do zainteresowań słuchaczy.
I. Elementy teorii modeli
1. Własność eliminacji kwantyfikatorów, typowe konsekwencje.
2. Klasyczne przykłady eliminacji kwantyfikatorów: arytmetyka Presburgera, ciała algebraicznie domknięte, ciała uporządkowane domknięte w sensie rzeczywistym. Zastosowania algebraiczne eliminacji kwantyfikatorów: twierdzenie Axa-Grothendiecka, twierdzenie Hilberta o zerach, 17. problem Hilberta. Informacja o strukturach o-minimalnych i ich własnościach.
3. Realizacja i omijanie typów, struktura przestrzeni typów. Modele pierwsze, atomowe i nasycone. Charakteryzacja teorii ω-kategorycznych.
4. Logika L_{ω1,ω}. Informacja o hipotezie Vaughta, twierdzenie Morleya o liczbie modeli przeliczalnych.
II. Twierdzenia limitacyjne
1. Teorie interpretujące arytmetykę, kodowanie ciągów i reprezentacja funkcji obliczalnych. Formuły uniwersalne.
2. Twierdzenie Tarskiego o niedefiniowalności prawdy. Twierdzenia Gödla o niezupełności. Niestandardowe modele arytmetyki i twierdzenie Tennenbauma.
III. Uzupełnienia
1. Tematy zaawansowane wybrane na podstawie możliwości czasowych i preferencji słuchaczy, np.: szkic dowodu twierdzenia Morleya o kategoryczności w mocach nieprzeliczalnych; twierdzenie Parisa-Harringtona lub inne twierdzenie o podobnym charakterze; twierdzenie Matijasiewicza (nierozstrzygalność 10. problemu Hilberta); słaby Lemat Königa i jego konserwatywność nad wyróżnianiem dla zbiorów obliczalnych, twierdzenie o niskiej bazie.
Koordynatorzy przedmiotu
Rodzaj przedmiotu
Założenia (opisowo)
Efekty kształcenia
Student:
1. rozumie technikę eliminacji kwantyfikatorów i zna klasyczne przykłady jej zastosowania. Umie użyć eliminacji kwantyfikatorów, żeby udowodnić wybrane twierdzenia z algebry.
2. zna podstawowe pojęcia klasycznej teorii modeli, w tym pojęcia związane z realizacją i omijaniem typów. Zna charakteryzację teorii przeliczalnie kategorycznych w językach przeliczalnych i umie ją udowodnić. Zna sformułowanie twierdzenia Morleya o kategoryczności w mocach nieprzeliczalnych.
3. zna definicję i podstawowe własności logiki infinitarnej L_{ω1,ω}. Zna sformułowanie hipotezy Vaughta oraz twierdzenie Morleya o liczbie przeliczalnych modeli, a także jego dowód oparty na analizie fragmentów L_{ω1,ω}.
4. zna definicję Arytmetyki Peano i jej typowych podteorii. Rozumie ideę kodowania ciągów skończonych, obliczeń i innych obiektów dyskretnych w arytmetyce.
5. zna sformułowania klasycznych twierdzeń limitacyjnych: Tarskiego, Gödla, Tennenbauma. Umie udowodnić te twierdzenia.
6. Zna wybrane bardziej zaawansowane twierdzenia limitacyjne i ideę ich dowodów, a także rozumie ich znaczenie.
Kryteria oceniania
Egzamin.
Literatura
1. Z. Adamowicz, P. Zbierski. Logika matematyczna. PWN 1991.
2. D. Marker. An Invitation to Mathematical Logic. Springer 2024/
3. D. Marker. Model Theory: an Introduction. Springer 2002.
4. W. Hodges. A shorter model theory. Cambridge 1997.
5. K. Tent, M. Ziegler. A Course in Model Theory. Cambridge 2012.
6. J. Avigad, Mathematical Logic and Computation, Cambridge 2022.
7. R. Kaye. Models of Peano Arithmetic. Oxford 1991.
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: