SubjectsSubjects(version: 849)
Course, academic year 2019/2020
   Login via CAS
Introduction to Mathematical Logic - NMAG162
Title in English: Úvod do matematické logiky
Guaranteed by: Department of Algebra (32-KA)
Faculty: Faculty of Mathematics and Physics
Actual: from 2019
Semester: summer
E-Credits: 3
Hours per week, examination: summer s.:2/0 Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: taught
Language: Czech
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. MMIB > 1. ročník
M Bc. MMIT > Doporučené volitelné
M Bc. OM
M Bc. OM > Zaměření MSTR
M Bc. OM > Doporučené volitelné
M Bc. OM > 1. 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.
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 |