Logika III 3800-L323-F
W trakcie wykładu zostaną omówione następujące zagadnienia. Każde z poniżej wymienianych twierdzeń zostaje przedstawione z dowodu.
-0 Informacje o programie Hilberta i tle filozoficznym Twierdzenia Godla.
-1 Arytmetyka I-ego rzędu vs. teoria mnogości zbiorów skończonych.
– kodowanie zbiorów skończonych w liczbach naturalnych.
– interpretacja teorii ZFC_fin w arytmetyce Peana.
– Definicje rekurencyjne w arytmetyce.
-2 Reprezentowalność zbiorów rekurencyjnych w arytmetyce Robinsona
- zbiory Delta_0-, Sigma_1- i Pi_1-definiowalne. Intuicje obliczeniowe.
- pojęcie reprezentowalności i silnej reprezentowalności w teorii aksjomatycznej. Charakteryzacja zbiorów Delta_1 jako zbiorów silnie reprezentowalnych w arytmetyce Robinsona.
-3 Twierdzenia Godlowskie
– Lemat przekątniowy.
– Twierdzenie Tarskiego o niedefiniowalności prawdy.
– I i II twierdzenie Godla.
– Warunki dowodliwości Godla-Loba. Twierdzenie Loba. Twierdzenie Rossera.
-4 Informacje o maszynach Turinga. Problemy rekurencyjnie przeliczalne i rekurencyjne. Związki z definiowalnością w modelu standardowym. Funkcje rekurencyjne i pierwotnie rekurencyjne.
-5 Twierdzenie o pełności dla logiki pierwszego rzędu (metodą Henkina).
-6 Modele niestandardowe arytmetyki i teorii mnogości.
Rodzaj przedmiotu
Założenia (opisowo)
Koordynatorzy przedmiotu
Efekty kształcenia
Nabyta wiedza:
- Zna filozoficzne motywacje twierdzeń limitacyjnych.
- Zna podstawowe fakty dotyczące siły wyrażalności arytmetyki pierwszego rzędu.
- Zna strukturę dowodu twierdzeń limitacyjnych (wymienionych w punkcie 3 pełnego opisu).
- Zna definicje: maszyny Turinga, zbioru rekurencyjnego i rekurencyjnie przeliczalnego. Zna związki zbiorów rekurencyjnie przeliczalnych/ rekurencyjnych i zbiorów Sigma_1 definiowalnych. Rozumie różnicę pomiędzy funkcjami rekurencyjnymi i funkcjami pierwotnie rekurencyjnymi.
- Zna strukturę dowodu twierdzenia o pełności.
- Rozumie strukturę porządkową przeliczalnych niestandardowych modeli arytmetyki Peana.
- Wie co to są elementy niestandardowe w niestandardowych modelach arytmetyki i teorii mnogości.
Nabyte umiejętności:
- Umie kodować zbiory skończone w liczbach naturalnych.
- Umie definiować arytmetycznie podstawowe zbiory i relacje w modelu standardowym.
- Umie udowodnić istnienie modeli niestandardowych arytmetyki i teorii mnogości.
- Umie przedstawić strukturę dowodu twierdzeń limitacyjnych omawianych na wykładzie.
- Umie wykazywać nadużycia w filozoficznych argumentacjach wykorzystujących twierdzenia limitacyjne.
Nabyte kompetencje społeczne:
- Umie precyzyjnie przedstawiać swoje argumenty.
- Umie analizować argumentację innych osób.
- Umie uważnie słuchać innych.
Kryteria oceniania
Wykład: egzamin ustny, ćwiczenia: 4 krótkie kolokwia organizowane w trakcie semestru. Podejście do egzaminu z wykładu jest możliwe dopiero po zaliczeniu ćwiczeń.
Dopuszczalna liczba nieobecności podlegających usprawiedliwieniu: wykład 2, ćwiczenia 2
Literatura
P. Hajek, P. Pudlak – Metamathematics of First-order Arithmetic, Cambridge University Press, 2017
R. Kaye – Models of Peano Arithmetic, 1991, Oxford
R. I. Soare -Turing Computability, Springer 2016
Więcej informacji
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: