Sylabus a literatura k prednasce

"Uvod do matematicke logiky", Jan Krajicek



Informace o zkousce.



Studentsky logicky seminar (kazdy semestr).
Slozitost dukazu a automaticke dokazovani (prednaska na jare 2011).

Sylabus:

  • Vyrokova logika: jazyk, formule, pravdivostni ohodnoceni. Splnitelnost, tautologie. Pravdivostni tabulky. Jednoznacnost zapisu formuli.

  • Vyrokovy pocet (sekvencni kalkulus nebo Hilbertovsky), jeho uplnost a korektnost. V. o dedukci.

  • Logicky ekvivalentni formule, DNF a CNF. Reprezentace booleovskych funkci formulemi a jejich velikost. DeMorganovy zakony, komutativita, asociativita a distributivita konjunkce a disjunkce. Interpolace.

  • Splnitelne mnoziny vyrokovych formuli. V. o kompaktnosti pro vyrokovou logiku.

  • Pr.: kompaktnost 3-obarvitelnosti nekonecnych grafu, pravdivostni ohodnoceni v booleovske algebre podmnozin dane mnoziny.

  • Logika prvniho radu, jazyk, rovnost, termy, formule. Volne a vazane vyskyty promennych, otevrene formule, sentence. Logicky ekvivalentni formule, prenexni tvar formule a prenexni operace.

  • Struktury a interpretace jazyka. Tarskeho definice splnovani. Pr. struktur: usporadane teleso realnych cisel, teleso komplexnich cisel, grupy, vektorove prostory, okruh celych cisel, usporadani, grafy.

  • Formule definujici zakladni vlastnosti relaci: relace ekvivalence, graf funkce, graf bijekce, a pod. .

  • Vnoreni a izomorfismus struktur, podstruktury. Elementarni ekvivalence. Teorie struktury. Zachovavani existencnich resp. universalnich formuli v nad- resp. pod-strukturach. Diagram struktury.

  • Teorie, axiomy, model teorie. Pr. teorii: usporadani, telesa, grupy, relace ekvivalence, PA. Axiomy rovnosti.

  • Predikatovy pocet (sekvenci kalkulus nebo Hilbertovsky). V. o uplnosti. Idea Henkinovy konstrukce.

  • V. o kompaktnosti a jeji dva dukazy: z V. o uplnosti a ultraprodukt.

  • Bude-li dost casu: Neformalne a bez dk. Lindstromova veta a specialni vyznam logiky 1.radu (versus logika 2.r., nove kvantifikatory, nekonecne formule, atd.).

  • Bez dk.: Nerozhodnutelnost vlastnosti, je-li formule dokazatelna v predikatovem poctu. Rekursivni vycislitelnost mnoziny dokazatelnych formuli. Rozhodnutelnost relace splnovani v usporadanem telese realnych cisel, nerozhodnutelnost splnovani v prirozenych cislech. Slabsi forma Godelovy v. o neuplnosti: Zadna algoritmicky rozhodnutelna teorie majici prirozena cisla za model neni uplna.

  • Aplikace kompaktnosti: Elementarni rozsireni, Lowenheim-Skolemova v. smerem nahoru, nestandartni modely telesa realnych cisel a prirozenych cisel. Teorie teles charakteristiky 0 a charakteristiky p > 0.

  • Bude-li dost casu: Skolemovske funkce a Skolemizace teorie. Lowenheim-Skolemova v. smerem dolu.

  • Ehrenfeucht - Fraisseho hra a elementarni ekvivalence. Pr.: husta linearni usporadani.

  • Eliminace kvantifikatoru. Pr.: husta linearni usporadani (s dk.), a bez dk. realne uzavrena telesa, algebraicky uzavrena telesa (bude-li cas: prirozena cisla s naslednikem, Pressburgerova aritmetika). Pozn. o rozhodnutelnosti teorie realne usporadaneho telesa. Ne-eliminovatelnost kvantifikatoru ve strukture prirozenych cisel.

  • Intuitivni teorie mnozin, Russelluv paradox. Hilbertuv program. Godelova v. o neuplnosti a nedokazatelnosti bezespornosti (neformalne).

  • Axiomy teorie ZF. Axiom vyberu AC, Zornovo lema ZL a princip dobreho usporadani WO, a jejich ekvivalence nad ZF. Teorie ZFC.

  • Ordinaly a jejich aritmetika. Transfinitni indukce. Pr.: Herkules a Hydra.

  • Mohutnost mnoziny. Cantorova veta (diagonalizace). Cantor-Bernsteinova veta. Bude-li cas: kardinaly a jejich aritmetika, znaceni alef, kofinalita, nedosazitelne kardinaly. Pozn. o Eulerove charakteristice.

  • Hypoteza kontinua. Konigovo lema.

  • Zbude-li cas naznacim (ale nebudu zkouset): Turingovy stroje. Universalni Turinguv stroj a algoritmicka nerozhodnutelnost Halting problemu. 10.Hilbertuv problem.

    Literatura:

    Nejvhodnejsi (a na webu!):

  • V.Svejdar, Logika: neuplnost, slozitost a nutnost (pdf soubor), Academia, Praha, 2002.

  • L. van den Dries, Lecture notes on mathematical logic (pdf soubor). Kap. 1. - 4. obsahuji temer vse, co prednasim. (ps soubor)

  • R. Honzik, A quick guide to independence results in set theory. Kap. 1 a 2 probiraji zaklady t.mozin. (Aktualni bibliograficke udaje jsou na www strance autora.)

    Dalsi literatura cesky:

  • A.Sochor, Klasicka matematicka logika, Karolinum, Praha, 2001.

  • B.Balcar a P.Stepanek, Teorie mnozin, Academia, Praha, 1986.

    Vhodne knihy dostupne v knihovne MFF:

  • H.D.Ebinghaus, J.Flum, W.Thomas, Mathematical Logic, 2.vyd., Springer-Verlag, 1994.

  • R.Cori, D.Lascar, Mathematical Logic (Part I.), Oxford U. Press, 2000.

    Knihovna MFF ma radu dalsich klasickych ucebnic matematicke logiky (Shoenfield, Kleene, Mendelsohn, Bell-Machover,...) ale ty jsou vesmes prilis podrobne pro uvodni kurs.