Intro to logic and sets
- 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).