Introduction to set theory

Ordered sets and well ordered sets. Ordinals. Linearly ordered sets. Uniqueness of countable linear orders without endpoints.

The set of finite ordinals, construction of the natural numbers, the induction principle and some of its equivalents.

Countable sets, construction of the rational numbers.

Construction of the real field.

Cardinality, cardinals, and the Cantor-Bernstein theorem.

Uncountable sets, Cantor’s theorem, applications.

The axiom of choice and its equivalents (the well ordering principle, Zorn’s lemma).

Applications of the axiom of choice. Transfinite induction.

Throughout the course we will see applications of the course’ material in algebra, logic, graph theory, Euclidean spaces and infinite combinatorics.

1. 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.
2. 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.
3. 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.
4. Ramsey’s theorem. Applications.
5. The construction of the ordered real line as a quotient over Cauchy sequences of rationals.
6. 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.
7. 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.
8. Zorn’s lemma. Applications. Existence of a basis in a vector space. Existence of a spanning tree in an arbitrary graph.
9. Discussion of the axioms of set theory and the need for them. Russel’s paradox. Ordinals.
10. Transfinite induction and recursion. Applications. Construction of a subset of the plane with exactly 2 point in every line.
11. 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).

90% final exam and 10% HW assignments. A passing grade in 4/6 assignments is a prerequisite for obtaining a grade in the course.