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

Niedowodliwość

Informacje ogólne

Kod przedmiotu: 1000-1M18ND Kod Erasmus / ISCED: 11.1 / (0541) Matematyka
Nazwa przedmiotu: Niedowodliwość
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: angielski
Rodzaj przedmiotu:

monograficzne

Założenia (opisowo):

Znajomość logiki na poziomie np. wykładu fakultatywnego "Logika matematyczna". Niezbędna wiedza na temat liczb porządkowych i kardynalnych (którą można nabyć np. na wykładzie "Teoria mnogości") zostanie przypomniana na początku semestru.

Skrócony opis:

Wykład będzie poświęcony kilku ważnym typom twierdzeń o niedowodliwości w teoriach aksjomatycznych. Twierdzenia o niedowodliwości są formalnym świadectwem tego, że pewne problemy matematyczne nie mogą być rozstrzygnięte za pomocą określonych metod, pojęć czy obiektów.

Pełny opis:

Program zajęć obejmie następujące cztery bloki tematyczne.

1. Niesprzeczność hipotezy continuum.

Aksjomatyka teorii mnogości. Przypomnienie liczb porządkowych i kardynalnych. Zbiory konstruowalne i ich własności. Prawdziwość CH w uniwersum zbiorów konstruowalnych. W miarę wolnego czasu: twierdzenie Scotta o nieistnieniu liczb mierzalnych w uniwersum zbiorów konstruowalnych.

2. Dowody twierdzeń kombinatorycznych wymagające odwołań do nieskończoności.

Arytmetyka Peano PA jako kanoniczna teoria obiektów skończonych. Twierdzenie Gödla i wyniki pokrewne. Twierdzenie Parisa-Harringtona jako przykład zdania kombinatorycznego niedowodliwego w PA. Związek z siłą logiczną nieskończonego twierdzenia Ramseya.

3. Siła i ograniczenia argumentów ze zwartości.

Słaby lemat Königa: aksjomat formalizujący argumenty ze zwartości w logice, topologii i analizie. Twierdzenie Harringtona o konserwatywności słabego lematu Königa nad aksjomatem wyróżniania dla zbiorów rozstrzygalnych. Wnioski dotyczące niedowodliwości za pomocą słabego lematu Königa. Metoda forcingu dla aksjomatycznych teorii arytmetyki.

4. Konieczność odwołań do obiektów wykładniczo dużych

Arytmetyka ograniczona jako formalizacja idei arytmetyki bez funkcji wykładniczej. Niedowodliwość zasady szufladkowej w arytmetyce ograniczonej. W miarę wolnego czasu: dowodliwość istnienia nieskończenie wielu liczb pierwszych w arytmetyce ograniczonej (twierdzenie Parisa, Wilkiego i Woodsa).

Literatura:

1. T. Jech, Set Theory, The Third Millenium Edition, Springer 2006.

2. R. Kaye, Models of Peano Arithmetic, Oxford 1991.

3. S. G. Simpson, Subsystems of Second Order Arithmetic, Cambridge 2009.

4. J. Krajicek, Bounded Arithmetic, Propositional Logic, and Complexity Theory, Cambridge 1995.

5. Artykuły badawcze i inne źródła uzupełniające.

Metody i kryteria oceniania:

Egzamin.

Zajęcia w cyklu "Semestr letni 2018/19" (zakończony)

Okres: 2019-02-16 - 2019-06-08
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, Bartosz Wcisło
Lista studentów: (nie masz dostępu)
Zaliczenie: Zaliczenie na ocenę
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Warszawski.