Introduction to Mathematical Logic - NALG108

• Title: Úvod do matematické logiky
• Guaranteed by: Department of Algebra (32-KA)
• Faculty: Faculty of Mathematics and Physics
• Actual: from 2014
• Semester: winter
• E-Credits: 3
• Hours per week, examination: winter s.:2/0, Ex [HT]
• Capacity: unlimited
• Min. number of students: unlimited
• 4EU+: no
• Virtual mobility / capacity: no
• State of the course: cancelled
• 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.
• Classification: Mathematics > Algebra, Discrete Mathematics
• Is incompatible with: NMAG162
• Is interchangeable with: NMAG162

Annotation

English

Last update: T_KA (11.04.2007)

Introductory course of mathematical logic. Covered topics include basics of propositional and predicate logic, and the most fundamental concepts and facts of model theory and set theory useful in many other mathematical areas.

Czech

Last update: T_KA (11.04.2007)

Úvodní přednáška matematické logiky. Probíraná témata zahrnují základy výrokové a predikátové logiky a nejzákladnější pojmy a fakta teorie modelů a teorie množin užitečná v řadě jiných matematických oborech.

Literature

English

Last update: KRAJICEK/MFF.CUNI.CZ (01.10.2009)

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: KRAJICEK/MFF.CUNI.CZ (01.10.2009)

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: prof. RNDr. Jan Krajíček, DrSc. (06.03.2007)

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.

If time permits: Turing machines. Universal Turing machine and algorithmic undecidability of the Halting problem. Hilbert's 10th problem.

Decidability of the theory of the real closed field.

Czech

Last update: prof. RNDr. Jan Krajíček, DrSc. (06.03.2007)

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.

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

Zbude-li čas: Turingovy stroje, Universální Turingův stroj a algoritmická nerozhodnutelnost Halting problému.

10.Hilbertův problém. Rozhodnutelnost teorie reálných čísel.