- Partially ordered sets. Chains and antichains. Examples. Erdos-Szekeres’ theorem or a similar theorem. The construction of a poset over the quotient space of a quasi-ordered set.
- Comparison of sets. The definition of cardinality as as an equivalence class over equinumerousity. The Cantor-Bernstein theorem. Cantor’s theorem on the cardinality of the power-set.
- Countable sets. The square of the natural numbers. Finite sequences over a countable set. Construction of the ordered set of rational numbers. Uniqueness of the rational ordering.
- Ramsey’s theorem. Applications.
- The construction of the ordered real line as a quotient over Cauchy sequences of rationals.
- Konig’s lemma on countably infinite trees with finite levels. Applications. A countable graph is k-colorable iff every finite subgraph of it is k-colorable.
- Well ordering. Isomorphisms between well-ordered sets. The axiom of choice formulated as the well-ordering principle. Example. Applications. An arbitrary graph is k–colorable iff every finite subgraph is k-colorable.
- Zorn’s lemma. Applications. Existence of a basis in a vector space. Existence of a spanning tree in an arbitrary graph.
- Discussion of the axioms of set theory and the need for them. Russle’s paradox. Ordinals.
- Transfinite induction and recursion. Applications. Construction of a subset of the plane with exactly 2 point in every line.
- Infinite cardinals as initial ordinals. Basic cardinal arithmetic. Cardinalities of well known sets. Continuous real functions, all real runctions, the automorphisms of the real field (with and without order).
University course catalogue: 201.1.0171