Logika matematyczna II 1000-1M16L2
Wykład składał się będzie z dwu części. Wybór bardziej zaawansowanego materiału będzie częściowo zależał od 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. Modele pierwsze, atomowe i nasycone. Charakteryzacja teorii ω-kategorycznych.
4. W miarę wolnego czasu i w razie zainteresowania słuchaczy: twierdzenie Morleya o liczbie modeli przeliczalnych bądź twierdzenie Morleya o kategoryczności w mocach nieprzeliczalnych.
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.
3. Twierdzenie Parisa-Harringtona.
4. W miarę wolnego czasu i w razie zainteresowania słuchaczy: twierdzenie Matijasiewicza (nierozstrzygalność 10. problemu Hilberta).
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ę Arytmetyki Peano i jej typowych podteorii. Rozumie ideę kodowania ciągów skończonych, obliczeń i innych obiektów dyskretnych w arytmetyce.
4. zna sformułowania klasycznych twierdzeń limitacyjnych: Tarskiego, Gödla, Tennenbauma. Umie udowodnić te twierdzenia. Zna sformułowanie twierdzenia Parisa-Harringtona i ideę jego dowodu.
5. zna sformułowanie twierdzenia Matijasiewicza i rozumie jego znaczenie.
Kryteria oceniania
Egzamin.
Literatura
1. Z. Adamowicz, P. Zbierski. Logika matematyczna. PWN 1991.
2. D. Marker. Model Theory: an Introduction. Springer 2002.
3. W. Hodges. A shorter model theory. Cambridge 1997.
4. K. Tent, M. Ziegler. A Course in Model Theory. Cambridge 2012.
5. 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:
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: