Úvod do matematické logiky

Sylabus

- Výroková logika (jazyk, formule, pravdivostní ohodnocení). Splnitelnost, tautologie. Pravdivostní tabulky. Jednoznačnost zápisu formulí.

- Sekvenční kalkulus (výrokový), jeho úplnost a korektnost. V. o dedukci.

- Logicky ekvivalentní formule, DNF a CNF. Reprezentace booleovských funkcí formulemi a jejich velikost. DeMorganovy zákony, komutatitivita, asociativita a distributivita konjunkce a disjunkce. Interpolace.

- Splnitelné množiny výrokových formulí. V. o kompaktnosti pro výrokovou logiku a její aplikace.

- Logika prvního řádu, jazyk, rovnost, termy, formule. Volné a vázané výskyty proměnných, otevřené formule, sentence.

- Logicky ekvivalentní formule, prenexní tvar formule a prenexní operace.

- Struktury a interpretace jazyka. Tarského definice splňování. Příklady: reálně uzavřená a algebraicky uzavřená tělesa, vektorové prostory, grupy, uspořádání, grafy, a pod.. Formule definující základní vlastnosti relací: relace ekvivalence, graf funkce, graf bijekce, a pod..

- Vnoření a izomorfismus struktur, podstruktury. Elementární ekvivalence. Teorie struktury. Zachovávání existenčních formulí nahoru a universálních dolů. Diagram struktury.

- Teorie, axiomy, model teorie. Př.: uspořádání, tělesa, grupy, relace ekvivalence, PA. Axiomy rovnosti.

- Sekvenční kalkulus pro logiku prvního řádu. V. o úplnosti (bez dk.).

- V. o kompaktnosti a její tři dúkazy: z V. o úplnosti, Henkinova konstrukce a ultraprodukt.

- Poznámky o Godelově větě o neúplnosti.

- Aplikace kompaktnosti: Elementární rozšíření, Lowenheim-Skolemova v. směrem nahoru. Nestandartní modely uspořádaného tělesa reálných čísel a okruhu celých čísel.

- Eliminace kvantifikátorů. Př.: hustá lineární uspořádání a RCF (bez dk.).

- Intuitivní teorie množin. Russellův paradox. Hilbertův program. Godelova v. o neúplnosti (neformálně).

- Axiomy teorie ZFC. Axiom výběru, Zornovo lema a princip dobrého uspořádání a jejich ekvivalence.

- Ordinály a jejich aritmetika. Transfinitní indukce.

- Koncept mohutnosti množin. Kardinály a jejich aritmetika. Cantorův diagonální argument, Cantor-Bernsteinova věta. Značení alef.

- Hypotéza kontinua (znění). Konigovo lema.

Anotace

Volitelný předmět pro bakalářské studium matematiky. Probíraná témata zahrnují základy výrokové a predikátové logiky a nejzákladnější pojmy a fakta z teorie modelů a teorie množin.