Logika matematyczna

fakultatywne

Wstęp do matematyki (potok I) 1000-111bWMAa

Wprowadzenie do klasycznych zagadnień logiki matematycznej z elementami teorii modeli.

Jeśli w wykładzie nie będą uczestniczyć słuchacze obcojęzyczni, wykład będzie prowadzony po polsku.

Systemy relacyjne. Podsystem, zanurzenie, izomorfizm. Algebry

Boole'a. (4 wykłady)

Język logiczny dla danej klasy systemów. Termy i formuły, zasada

indukcji. (1 wykład)

Prawdziwość formuł w systemach - definicja Tarskiego. Teorie i

modele. (2 wykłady)

Rachunek logiczny. Twierdzenie Goedla o pełności. Twierdzenie o

zwartości. (3 wykłady)

Funkcje Skolema i generowanie podmodeli. Realizacja typów - modele pierwsze i uniwersalne.

Kryterium Tarskiego-Vaughta elementarności podmodelu. (2

wykłady)

Ultraprodukt. Modele przeliczalnie nasycone. Modelowa zupełność dla ciał

uporządkowanych domkniętych (przy założeniu hipotezy

continuum). (2 wykłady)

Twierdzenie Tarskiego o eliminacji kwantyfikatorów dla ciał uporządkowanych

domkniętych (w sensie rzeczywistym). (1 wykład)

Z. Adamowicz, P. Zbierski, Logika matematyczna, PWN, Warszawa 1991.

J. Barwise, ed., Handbook of Mathematical Logic, North-Holland, Amsterdam 1978.

J.L. Bell, A.B. Slomson, Models and Ultraproducts: An Introduction, North-Holland, Amsterdam 1986.

R.C. Lyndon, O logice matematycznej, PWN, Warszawa 1978.

Student:

1. zna podstawowe pojęcia związane ze składnią i semantyką logiki zdań. Zna twierdzenie o zwartości dla logiki zdań i potrafi podać przykład jego zastosowania. Potrafi udowodnić, że każda formuła jest logicznie równoważna formule w postaci koniunkcyjno-alternatywnej i alternatywno-koniunkcyjnej, a także znajdować postaci normalne dla zadanych formuł. Zna przynajmniej jeden przykład systemu dowodowego dla rachunku zdań i twierdzenie o pełności dla tego systemu;

2. zna definicję struktury relacyjnej (systemu relacyjnego) i definicje podstawowych operacji na strukturach relacyjnych. Umie zilustrować te definicje przykładami. Zna podstawowe pojęcia i twierdzenia teorii algebr Boole'a, w tym pojęcia filtru i ultrafiltru oraz twierdzenie Stone'a o reprezentacji algebr Boole'a jako ciał zbiorów;

3. zna podstawowe pojęcia związane ze składnią i semantyką logiki pierwszego rzędu, w tym pojęcia spełniania i prawdy. Rozumie, jakie klasy formuł zachowują wartość logiczną przy poszczególnych operacjach na strukturach. Zna typowe przykłady tautologii w logice pierwszego rzędu oraz twierdzenie o preneksowej postaci normalnej. Umie sprowadzać proste formuły do preneksowej postaci normalnej;

4. rozumie pojęcie definiowalnej (skończenie aksjomatyzowalnej) i aksjomatyzowalnej klasy struktur. Potrafi konstruować zdania mające określoną wartość logiczną w danych strukturach oraz zdania bądź zbiory zdań aksjomatyzujące określone klasy struktur. Zna pojęcie zbioru definiowalnego i potrafi konstruować formuły definiujące określone zbiory w danych strukturach. Potrafi dowodzić niedefiniowalności zbiorów za pomocą automorfizmów;

5. zna twierdzenie o zwartości dla logiki pierwszego rzędu;

6. zna pojęcie ultraproduktu, przykłady ultraproduktów i twierdzenie Łosia o spełnianiu w ultraproduktach;

7. Potrafi dowodzić nieaksjomatyzowalności klas struktur za pomocą twierdzenia o zwartości bądź twierdzenia Łosia. Zna twierdzenie Frayne'a, Morela i Scotta charakteryzujące klasy aksjomatyzowalne;

8. zna przykład systemu dowodowego dla logiki pierwszego rzędu i twierdzenie o pełności dla tego systemu;

9. zna pojęcie podstruktury elementarnej i twierdzenia Skolema-Löwenheima. Potrafi używać twierdzeń Skolema-Löwenheima do konstruowania struktur o zadanej z góry mocy i określonych własnościach logicznych.

1. Do egzaminu w pierwszym terminie dopuszczone zostaną osoby, które uzyskają co najmniej 50% punktów z zadań domowych.

2. Egzaminy odbywające się w sesji będą się składały z części pisemnej, obejmującej teorię i zadania (dla wszystkich) oraz ustnej (patrz p. 3).

3. W szczególnych wypadkach wykładowca może zaproponować studentowi egzamin ustny, którego wynik może zmienić ocenę wynikającą z egzaminu pisemnego. Na dopuszczenie do egzaminu ustnego wpływ ma liczba punktów z zadań domowych oraz opinia z ćwiczeń. Liczba zaproszeń na egzamin ustny może istotnie wzrosnąć, jeśli egzamin pisemny będzie zdalny.

4. O egzamin w terminie zerowym mogą się ubiegać osoby, które w ocenie prowadzących zajęcia mieszczą się (pod względem punktów za zadania domowe, aktywności na ćwiczeniach, ew. aktywności na wykładzie) wśród czołowych 10% uczestników kursu. O możliwość przystąpienia do egzaminu zerowego można się starać począwszy od 15 stycznia 2024 r. Egzamin zerowy będzie wyłącznie ustny i będzie sprawdzał zarówno umiejętność rozwiązywania zadań, jak i znajomość teorii.

5. Ocena z przedmiotu wystawiana jest wyłącznie na podstawie egzaminu.

6. W związku z zaleceniem Dziekana Wydziału MIiM, dotyczącym częstego wietrzenia sal, wykłady (dwa razy po 45 minut z piętnastominutową przerwą) w miarę możliwości będą się odbywać przy otwartych oknach. Proszę wszystkich, żeby w związku z tym mieli ze sobą ciepłe swetry lub inne okrycia.