Logika matematyczna II
Informacje ogólne
Kod przedmiotu: | 1000-1M16L2 |
Kod Erasmus / ISCED: | (brak danych) / (brak danych) |
Nazwa przedmiotu: | Logika matematyczna II |
Jednostka: | Wydział Matematyki, Informatyki i Mechaniki |
Grupy: |
Przedmioty monograficzne dla matematyki 2 stopnia Przedmioty obieralne na studiach drugiego stopnia na kierunku bioinformatyka |
Punkty ECTS i inne: |
(brak)
|
Język prowadzenia: | (brak danych) |
Rodzaj przedmiotu: | monograficzne |
Założenia (opisowo): | Znajomość logiki i teorii mnogości na poziomie kursowych wykładów Logika matematyczna i Wstęp do matematyki. Może się przydać pewne oswojenie z algebrą (ciała algebraicznie domknięte itp.) i teorią mnogości (np. liczby porządkowe i kardynalne), ale nie będzie ono wymagane. |
Skrócony opis: |
Wykład obejmuje wybrane zagadnienia z logiki wykraczające poza program wykładu kursowego, ze szczególnym uwzględnieniem podstawowych pojęć teorii modeli oraz twierdzeń o niedowodliwości w systemach aksjomatycznych. Tematyka obejmie między innymi: eliminację kwantyfikatorów i jej zastosowania w algebrze, struktury o-minimalne, ω-kategoryczność, podstawowe informacje o kategoryczności w mocach nieprzeliczalnych, a także twierdzenia limitacyjne: Tarskiego, Gödla, Parisa-Harringtona, w miarę możliwości Matijasiewicza. |
Pełny opis: |
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). |
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. |
Efekty uczenia się: |
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. |
Metody i kryteria oceniania: |
Egzamin. |
Właścicielem praw autorskich jest Uniwersytet Warszawski.