Mathematical Logic and Theory of Algorithms

Passport

• Where and when. Semesters I–II of the 01.03.02 “Applied Mathematics and Informatics” program, “Mathematics” track, 2025 intake.
• Workload. 225 hours, 5 credits: 90 hours and 2 credits in semester I, 135 hours and 3 credits in semester II. In total, 120 contact hours (60 lecture hours, 60 seminar hours), 75 hours of independent work and 30 hours of exam preparation.
• Department. Department of Discrete Mathematics.
• Lecturer. The available 2022 program names Associate Professor E. V. Dashkov as lecturer. This is historical information from the document, not confirmation of lecturer assignments for the 2025 intake.
• Final assessment. Assessment is scheduled in both semesters; its form for a particular group should be checked in the current curriculum.

Contents of the published program

Below is the complete list from the available 2022 program “Mathematical Logic”, lecturer E. V. Dashkov. It contains 24 topics and is published as a historical version, not as a fixed program for the 2025 intake.

1. The intuitive notion of a set, elements, inclusion, equality, ways of forming sets, the empty set and Russell’s paradox.
2. Union, intersection, complement and their identities; Kuratowski pairs, Cartesian product, ordered \(n\)-tuples and powers of a set.
3. Binary relations, inverse and composition, relations on a set, images and preimages.
4. Functionality, injectivity, surjectivity and totality of relations; partial functions and functions of several arguments.
5. Injections, surjections, bijections, equinumerosity, comparison of cardinalities, Cantor’s theorem and the Cantor–Bernstein–Schröder theorem, the axiom of choice and indexed families.
6. Reflexivity, symmetry and transitivity; partial and linear orders, bounds, supremum, infimum, lattices, chains and antichains.
7. Equivalence relations, equivalence classes, quotient sets and partitions.
8. Finite sets, induction, the pigeonhole principle, cardinality and the recursion theorem.
9. Cardinality properties of finite and countable sets, the sum and product rules, countable unions.
10. Words and formal languages, concatenation, prefixes and suffixes, inductive definitions and structural induction.
11. Well-founded and well-ordered sets, the induction principle, limit elements.
12. The structure of well-ordered sets, addition and multiplication of them.
13. Initial segments, isomorphism and comparison of well-ordered sets.
14. Comparing a well-ordered set with its subset, subtraction and division with remainder.
15. Chains in a partially ordered set, Zorn’s lemma, Zermelo’s theorem and their relation to the axiom of choice.
16. Algorithms, computable functions, decidable and computably enumerable sets, Post’s theorem.
17. The \(T\)-predicate of an algorithm, the graph theorem for computable functions, images and preimages, the semicharacteristic function.
18. The universal computable function, the self-applicability and halting problems, examples of enumerable and undecidable sets.
19. The principal universal function, coding of pairs, Kleene’s fixed point theorem, the recursion theorem and mutual recursion.
20. Index sets, the Rice–Uspensky and Rice–Shapiro theorems, \(m\)-reducibility.
21. Turing machines and the realization of properties of algorithms in the models of Turing machines and partial recursive functions.
22. The untyped \(\lambda\)-calculus: terms, combinators, \(\beta\)- and \(\eta\)-reductions, normal form and the Church–Rosser theorem.
23. Representability of partial functions in the \(\lambda\)-calculus, encoding of logic and natural numbers, composition and primitive recursion.
24. Fixed-point combinators, recursion and minimization, equivalence of the models of partial recursive functions and the \(\lambda\)-calculus, undecidability of the \(\lambda\)-calculus and Scott’s theorem.

Grading

No current, publicly available grading scheme with numerical thresholds was found.

Sources and currency

2022 program, department materials archive, 01.03.02 curriculum, 2025 intake.