SubjectsSubjects(version: 945)
Course, academic year 2023/2024
   Login via CAS
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 2023 to 2023
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
Guarantor: prof. RNDr. Jan Krajíček, DrSc.
Class: M Bc. FM
M Bc. FM > Doporučené volitelné
M Bc. MMIB > Doporučené volitelné
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
In complex pre-requisite: NMAG351
Annotation -
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.
Course completion requirements - Czech
Last update: 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:

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


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

Charles University | Information system of Charles University |