Uniwersytet Warszawski - Centralny System Uwierzytelniania
Strona główna

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) Podstawowe informacje o zasadach przyporządkowania punktów ECTS:
  • roczny wymiar godzinowy nakładu pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się dla danego etapu studiów wynosi 1500-1800 h, co odpowiada 60 ECTS;
  • tygodniowy wymiar godzinowy nakładu pracy studenta wynosi 45 h;
  • 1 punkt ECTS odpowiada 25-30 godzinom pracy studenta potrzebnej do osiągnięcia zakładanych efektów uczenia się;
  • tygodniowy nakład pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się pozwala uzyskać 1,5 ECTS;
  • nakład pracy potrzebny do zaliczenia przedmiotu, któremu przypisano 3 ECTS, stanowi 10% semestralnego obciążenia studenta.

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ą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.

Przedmiot nie jest oferowany w żadnym z aktualnych cykli dydaktycznych.
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Warszawski.
ul. Banacha 2
02-097 Warszawa
tel: +48 22 55 44 214 https://www.mimuw.edu.pl/
kontakt deklaracja dostępności USOSweb 7.0.3.0-2b06adb1e (2024-03-27)