Úvod do matematické logiky - NMAG162

• Anglický název: Introduction to Mathematical Logic
• Zajišťuje: Katedra algebry (32-KA)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2023
• Semestr: letní
• E-Kredity: 3
• Rozsah, examinace: letní s.:2/0, Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: vyučován
• Jazyk výuky: čeština
• Způsob výuky: prezenční
• Způsob výuky: prezenční
• Garant: prof. RNDr. Jan Krajíček, DrSc.
• Třída: M Bc. FM; M Bc. FM > Doporučené volitelné; M Bc. MMIB; M Bc. MMIB > Doporučené volitelné; M Bc. MMIT; M Bc. MMIT > Povinně volitelné; M Bc. MMIT > 2. ročník; M Bc. OM; M Bc. OM > Zaměření MSTR; M Bc. OM > Doporučené volitelné; M Bc. OM > 2. ročník
• Kategorizace předmětu: Matematika > Algebra, Diskrétní matematika
• Neslučitelnost : NALG108
• Záměnnost : NALG108
• Ve slož. prerekvizitě: NMAG351

Anotace

čeština

Poslední úprava: G_M (15.05.2012)

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.

angličtina

Poslední úprava: G_M (15.05.2012)

An elective course for bachelor's program in mathematics. The covered topics include basics of propositional and predicate logic, and fundamental concepts of model theory and set theory.

Podmínky zakončení předmětu

Poslední úprava: prof. RNDr. Jan Krajíček, DrSc. (27.04.2020)

Písemná zkouška. Je možné, že se bude konat distanční formou (o přesné formě zkoušky budete včas informováni).

Redukovaný sylabus: http://www.karlin.mff.cuni.cz/~krajicek/ml2020.html

Literatura

čeština

Poslední úprava: RNDr. Pavel Zakouřil, Ph.D. (11.08.2015)

• V.Švejdar, Logika: neúplnost, složitost a nutnost, Academia, Praha, 2002.
• R.Cori, D.Lascar, Mathematical Logic (part I.), Oxford University Press, 2000.
• H.D.Ebinghaus, J.Flum, W.Thomas, Mathematical Logic, 2.vyd., Springer Verlag, 1994.
• literatura na webu (a další literatura): viz http://www.karlin.mff.cuni.cz/~krajicek/ml.html
• Videozáznamy přednášek

angličtina

Poslední úprava: G_M (23.04.2012)

R.Cori, D.Lascar, Mathematical Logic (part I.), Oxford University Press, 2000.

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

viz http://www.karlin.mff.cuni.cz/~krajicek/ml.html

Sylabus

čeština

Poslední úprava: G_M (15.05.2012)

• 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.

angličtina

Poslední úprava: G_M (15.05.2012)

• Propositional logic: language, formulas, truth assignments. Satisfiability, tautologies. Truth tables. Unique readability of formulas.

• Sequent calculus for propositional logic, its completeness and soundness. Deduction thm.

• Logically equivalent formulas, DNF and CNF. A representation of boolean functions by formulas a their sizes. DeMorgan laws, commutativity, associativity, and distributivity of conjunction and disjunction. Interpolation.

• Satisfiable sets of propositional formulas. Compactness thm. for propositional logic and its applications.

• First order logic, language, equality, terms, formulas. Free and bound occurences of variables. Logically equivalent formulas, prenex formulas and prenex operations.

• Structures and interpretation of a language. Tarski's truth definition. Examples of structures.

• Embedding and isomorphism of structures, substructures. Elementary equivalence. The theory of a structure. Preservation of existential formulas upwards and universal formulas downwards. The diagram of a structure.

• Theories, axioms, models of theories. Examples of theories.

• Sequent calculus for predicate calculus. Completeness theorem (without prf.).

• Compactness thm and its three proofs: from Completeness thm., Henkin construction and ultraproduct.

• Applications of compactness: Lowenheim-Skolem thm. upwards. Nonstandard models of reals and natural numbers.

• Quantifier elimination. Ex.: dense linear ordering and RCF (without prf.).

• Intuitive set theory. Russell's paradox. Hilbert's program and Godel's thm. (without prf.).

• Axioms of ZFC. Axiom of choice, Zorn lemma and well-ordering principle, and their equivalence.

• Ordinals and their arithmetic. Transfinite induction.

• Cardinality of an infinite set, cardinal numbers and their arithmetic. Cantor's diagonal argument. Cantor-Bernstein theorem. The aleph notation.

• Continuum hypothesis (statement). Konig's lemma.