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