Uniwersytet Warszawski, Wydział Nauk Ekonomicznych - Centralny System Uwierzytelniania
Strona główna

Niedowodliwość

Informacje ogólne

Kod przedmiotu: 1000-1M18ND
Kod Erasmus / ISCED: 11.1 Kod klasyfikacyjny przedmiotu składa się z trzech do pięciu cyfr, przy czym trzy pierwsze oznaczają klasyfikację dziedziny wg. Listy kodów dziedzin obowiązującej w programie Socrates/Erasmus, czwarta (dotąd na ogół 0) – ewentualne uszczegółowienie informacji o dyscyplinie, piąta – stopień zaawansowania przedmiotu ustalony na podstawie roku studiów, dla którego przedmiot jest przeznaczony. / (0541) Matematyka Kod ISCED - Międzynarodowa Standardowa Klasyfikacja Kształcenia (International Standard Classification of Education) została opracowana przez UNESCO.
Nazwa przedmiotu: Niedowodliwość
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: 6.00 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: angielski
Rodzaj przedmiotu:

monograficzne

Założenia (opisowo):

Znajomość logiki na poziomie np. wykładu fakultatywnego "Logika matematyczna". Mile widziana jest podstawowa wiedza na temat liczb porządkowych (którą można nabyć np. na wykładzie "Teorii mnogości") i teorii obliczeń (obliczalność i nieobliczalność, istnienie maszyny uniwersalnej), ale te tematy zostaną przypomniane w trakcie zajęć.

Tryb prowadzenia:

w sali

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. W tej edycji kursu skupimy się na wynikach o niedowodliwości twierdzeń mających konkretną treść kombinatoryczną lub teorioliczbową w teoriach o sile porównywalnej z Arytmetyką Peano, czyli kanoniczną teorią formalizującą "matematykę obiektów skończonych".

Pełny opis:

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

1. Niedowodliwość ogólnie: twierdzenia Gödla i okolice.

Arytmetyka Peano PA jako kanoniczna teoria obiektów skończonych. Związki wyrażalności w arytmetyce z teorią obliczeń. Zdania przekątniowe. Twierdzenia Gödla i wyniki pokrewne (Tarskiego, Rossera). Niedowodliwość zasad refleksji.

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

Twierdzenie Parisa-Harringtona jako przykład zdania kombinatorycznego niedowodliwego w PA. Związek z siłą logiczną nieskończonego twierdzenia Ramseya. Niedowodliwość wariantów twierdzenia Kruskala o drzewach w teoriach o sile zbliżonej do PA.

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 obliczalnych. 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).

5. Zagadnienia uzupełniające (w miarę wolnego czasu).

- Twierdzenie Matijasiewicza o nieistnieniu algorytmu rozstrzygającego problem istnienia rozwiązań równań diofantycznych (10. problem Hilberta). Wniosek: żadna dostatecznie silna teoria nie dowodzi wszystkich prawdziwych twierdzeń o nieistnieniu rozwiązań równań diofantycznych.

- Niedowodliwość wariantów twierdzenia Kruskala o drzewach w teoriach niepredykatywnych, istotnie silniejszych niż PA.

- Potencjalny temat na deser: Metody algebraiczne w badaniu niedowodliwości, czyli jakich aksjomatów potrzeba, by udowodnić niewymierność pierwiastka z 2?

Literatura:

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

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

3. A. Freund, Unprovability in Mathematics: A First Course on Ordinal Analysis (arXiv:2109.06258) i Impredicativity and Trees with Gap Condition: A Second Course on Ordinal Analysis (arXiv:2204.09321).

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

5. Y. Manin, A Course in Mathematical Logic for Mathematicians, Second Edition, Springer 2009.

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

Metody i kryteria oceniania:

Egzamin.

Zajęcia w cyklu "Semestr letni 2024/25" (jeszcze nie rozpoczęty)

Okres: 2025-02-17 - 2025-06-08
Wybrany podział planu:
Przejdź do planu
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: Zaliczenie na ocenę
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Warszawski, Wydział Nauk Ekonomicznych.
ul. Długa 44/50
00-241 Warszawa
tel: +48 22 55 49 126 https://www.wne.uw.edu.pl/
kontakt deklaracja dostępności mapa serwisu USOSweb 7.0.4.0-3 (2024-06-10)