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.