Introduction to Mathematical Logic - NMAG162

• Title: Úvod do matematické logiky
• Guaranteed by: Department of Algebra (32-KA)
• Faculty: Faculty of Mathematics and Physics
• Actual: from 2012 to 2014
• Semester: summer
• E-Credits: 3
• Hours per week, examination: summer s.:2/0, Ex [HT]
• Capacity: unlimited
• Min. number of students: unlimited
• 4EU+: no
• Virtual mobility / capacity: no
• State of the course: taught
• Language: Czech
• Teaching methods: full-time
• Teaching methods: full-time
• Additional information: http://www.karlin.mff.cuni.cz/~krajicek/ml.html
• Guarantor: prof. RNDr. Jan Krajíček, DrSc.
• Class: 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
• Classification: Mathematics > Algebra, Discrete Mathematics
• Incompatibility : NALG108
• Interchangeability : NALG108

Annotation

English

Last update: 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.

Czech

Last update: 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.

Literature

English

Last update: 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

Czech

Last update: 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

Syllabus

English

Last update: 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.

Czech

Last update: 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.