## Axiomatische Verzamelingentheorie

### 2012/2013; 2nd Semester

Institute for Logic, Language & Computation
Universiteit van Amsterdam

Instructor: Prof. Dr. Benedikt Löwe
Teaching Assistants: Takanori Hida, Zhenhao Li.
Vakcode: WI305096
ECTS: 6
Time & Place:
February & March 2013: Tuesday 15-17 (SP C1.112), Friday 13-15 (SP C1.112)
April & May 2013: Tuesday 13-15 (SP C1.112), Wednesday 13-15 (SP F1.02)
Course language: English
Intended audience: B.Sc. students of Mathematics, M.Sc. students of Logic.

Goal of this course: Understanding of the connections between logic and set theory, in particular the axiomatic approach. Skillful handling of ordinals and cardinals, in particular the methods of transfinite induction and recursion.

Content of the course: Axioms of Set Theory, Set Theory as a Foundations of Mathematics, Ordinal Numbers, Cardinal Numbers, Axiom of Choice. Possibly basics of some additional topics such as set theory of the reals, descriptive set theory, and large cardinals.

Prerequisites: Mathematical maturity, decent understanding of first-order logic.

Evaluation:

1. Homework.
• There will be 12 to 13 homework sheets.
• You are allowed to either work alone or in a group of at most two people for the homework. It is not necessary to stay in the same group for every homework set.
• Homework is handed in either before class on the day of the deadline mentioned on the homework set or by e-mail to T.Hida(at)uva.nl. Late homework is not accepted.
2. Exam. The exam will be on 28 May 2013, 13-16, USC Sporthal 2.
3. Final grade. The final grade is the average of the grade of the Homework component and the Exam component calculated according to the OER regulations (Part A, Article 23).

If you do not pass the course in the first attempt, there will be a hertentamen. In those cases where it becomes necessary to redo (parts of) the homework component, we shall discuss individual solutions.

Literature.

Course syllabus.

5 February 2013 Motivation (1): Set theory as a field of mathematics, paradoxes of the infinite, definition of "of equal size", Cantor's theorem without proof, existence of transcendental numbers, transfinite procedures. Motivation (2): Set theory as a foundations of mathematics. Models of set theory as graphs. The language of set theory. The existence axiom, the extensionality axiom, the Aussonderungsaxiom. Proof that the empty set exists and is unique. Consistency proofs for very weak systems of set theory. The pairing axiom. Proof that no model of Ex+Ext+Aus+Pair can be finite. Desired set operations from our ordinary mathematical practice: the Cartesian product. Operations defined by formulas; notational abbreviations in set theory. Proving that an operation is total. The binary union axiom and the power set axiom. Construction of the Cartesian product with binary union and power set. Models of (Ex)+(Ext)+(Aus)+(Pow) are infinite. The union axiom and arbitrary unions and intersections. The axiom system FST of finite set theory. Relations and functions in FST. Cantor's theorem. The model HF of the hereditarily finite sets. Dedekind-finiteness. Inductive sets. The axiom of infinity. (Brief discussion of HW set #1.) The definition of the natural numbers and the set of natural numbers. Properties of the natural numbers. Constructing the integers and rational numbers as set-theoretic quotients. Construction of the real numbers: Dedekind cuts. Size of infinite sets: the notion of equinumerosity. Zermelo set theory proves that there is an uncountable set. Skolem paradox. Classes and proper classes. Examples of proper classes: there is no set of all singletons, no set of all groups, etc. For every non-empty set, the class of sets equinumerous to it is a proper class. The axiom scheme of Replacement. Sketch that if you iterate the HF construction, you get a model of Z in which Replacement is false. The axiom scheme of Foundation and the axiom of Foundation. Wellfoundedness. Principle of Induction, principle of weak induction, and least number principle on the natural numbers. Proof of the recursion theorem for functions on the natural numbers. Grassmann recursion equations for addition and multiplication on the natural numbers. Induction on wellorders. The recursion theorem for wellorders. Ordinals: the natural numbers are ordinals. Closure properties of ordinals. Statement of the fundamental theorem on wellorders (without proof). Properties of ordinals: irreflexivity, linear order, wellfoundedness of the class of ordinals, transitive sets of ordinals are ordinals. Burali-Forti paradox: there is no set of all ordinals. Class version of the recursion theorem. Application: ordinal addition. Some properties of ordinal addition: failure of commutativity. Limit ordinals. Ordinal multiplication and exponentiation. Gamma-, delta- and epsilon-numbers. Normal ordinal operations and the fixed point theorem. The existence of uncountable ordinals via the coding method of coding countable ordinals as subsets of the natural numbers. Hartogs' Theorem. The aleph function and its properties. Fixed points of the aleph function and their size. Infinite cardinals. Proof that every wellordered set is in bijection with a cardinal. Zermelo's well-ordering theorem (without proof). Proof of Zermelo's well-ordering theorem. Choice functions. The axiom of choice. Cardinality of sets in ZFC. Fragments of the axiom of choice. Some history of the axiom of choice and some consequences (without proof). Countable unions of countable sets are countable (using the countable axiom of choice). The well-ordering theorem implies the Axiom of Choice. Zorn's lemma and its equivalence to the Axiom of Choice. Cardinal addition and multiplication. Proof that κ+κ = κ. Hessenberg's theorem (without proof). Proof of Hessenberg's Theorem. Cardinal exponentiation. The continuum function. Hausdorff's Formula. Cofinality. The gimel function. Fundamental theorem of cardinal arithmetic (recursive determination of κλ in terms of the continuum function and the gimel function. Von Neumann hierarchy. Mirimanoff rank. Characterization of the axiom of foundation in terms of the von Neumann hierarchy.