Uniwersytet Warszawski - Centralny System UwierzytelnianiaNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

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 IV - V roku matematyki
Punkty ECTS i inne: 6.00
zobacz reguły punktacji
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ących 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.

Zajęcia w cyklu "Semestr letni 2020/21" (jeszcze nie rozpoczęty)

Okres: 2021-02-22 - 2021-06-13
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Leszek Kołodziejczyk
Prowadzący grup: Leszek Kołodziejczyk
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Przedmiot dedykowany programowi:

4EU+KURSY

Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Warszawski.