Axiomatische Verzamelingentheorie, Spring 2014

Axiomatische Verzamelingentheorie (Axiomatic Set Theory)

2013/2014; 2nd Semester; Block B

Institute for Logic, Language & Computation
Universiteit van Amsterdam

Instructor: Prof. Dr. Benedikt Löwe
Teaching Assistants: Julia Ilin and Hugo Nobrega.
Course Catalogue Number: 5122AXVE6Y (DataNose – important: see note on schedule below)
ECTS: 6

Time & Place:
Tuesday 15-17 (SP G2.10), Wednesday 11-13 (SP D1.114 / D1.116), Wednesday 17-19 (SP C1.112), Friday 13-15 (SP D1.112 / G0.05)

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. Skilful 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:

Homework.
- There will be 6 or 7 homework sheets.
- The homework sets are to be done by each student individually.
- The preferred method for submitting homework solutions is by handing them in before the start of the werkcollege on Wednesday morning. Electronic submissions are also possible, by email to ilin.juli (at) gmail.com or hugonobrega (at) gmail.com before the deadline. These must be in a single, legible PDF file. It is also possible to hand in your homework by putting it into Julia's or Hugo's mailboxes in the Logic department at Science Park 107, but in this case the deadline for submission is at 10:45am on the day of the submission deadline. It is important to respect the strict deadlines stated above; late homework will not be accepted.
Exam. The exam will be on 27 May 2014, 18-21, SP C1.110 – important: this is a recent change.
Final grade. The final grade for the course is composed 1/3 from the homework and 2/3 from the final exam.

If you do not pass the course in the first attempt, there will be a hertentamen on 7 July 2014, 13-16, SP B0.207. In those cases where it becomes necessary to redo (parts of) the homework component, we shall discuss individual solutions.

Literature.

Herbert B. Enderton, Elements of Set Theory, amazon.co.uk
Yiannis N. Moschovakis, Notes on Set Theory, amazon.co.uk
Heinz D. Ebbinghaus, Einführung in die Mengenlehre.
Thomas S. Jech, Set Theory, amazon.co.uk
Kenneth Kunen, Set Theory, amazon.co.uk

Course syllabus and schedule.

Note: We will take the liberty of exchanging some Hoorcolleges with Werkcolleges, and vice versa.
The actual schedule for the course is as follows – note that this does not completely match the schedule found on DataNose.

1 April 2014 Tuesday	Hoorcollege 15-17 G2.10	Motivation (1): Set theory as a field of mathematics, paradoxes of the infinite, definition of "of equal size". Motivation (2): Set theory as a foundations of mathematics.
2 April 2014 Wednesday	Hoorcollege 11-13 D1.114	The language of set theory. Models of set theory as graphs. Introducing relations and terms into the language of set theory by definition. The extensionality axiom.
2 April 2014 Wednesday	Hoorcollege 17-19 C1.112	The separation axiom scheme. Proof that in (Ext)+(Sep) the empty set exists and is unique. Consistency proofs for very weak systems of set theory. The pairing axiom. Proof that no model of (Ext)+(Sep)+(Pair) can be finite. Homework set 1 handed out (due 9 April 2014 before the morning werkcollege).
4 April 2014 Friday	Hoorcollege 13-15 G0.05	Binary intersections and unions. Proof that (Int) follows from (Ext)+(Sep), but that (BinUn) does not follow even from (Ext)+(Sep)+(Pair) [note: these proofs are not found in the course literature]. Arbitrary unions, the union axiom. Proof that (BinUn) follows from (Ext)+(Pair)+(Un). Proof that no model of (Ext)+(Sep)+(Pair)+(BinUn) can be of bounded degree. Definition of ordered pairs and informal discussion of cartesian products.
8 April 2014 Tuesday	Hoorcollege 15-17 G2.10	Power sets and the power set axiom. Cartesian products. The axiom system FST of finite set theory. Differences between classes and sets, coextensionality, proper classes. Proof that (Ext)+(Sep)+(Pair) does not imply (Pow). Construction of the model H_∞ of FST (this is called the hereditarily finite sets model and is also sometimes denoted by HF).
9 April 2014 Wednesday	Werkcollege 11-13 D1.114	Recap of some of the material seen in week 1. Solutions to Homework set 1. More exercises done in class, and their solutions discussed. Homework set 2 handed out (due 16 April 2014 before the morning werkcollege) – note that there is a typo in Julia's email address in the homework file; the correct address is `ilin.juli (at) gmail.com`.
9 April 2014 Wednesday	Hoorcollege 17-19 C1.112	Relations in FST: defining the set of relations between given sets, and defining sets of relations with certain properties between given sets by using (Sep) with the appropriate formula. Structures in FST: formal definitions of graphs, partial orders, groups, and other mathematical structures in our desiderata. The quotient of a set by an equivalence relation.
11 April 2014 Friday	Werkcollege 13-15 G0.05	Recap of material from the lectures and in-class exercises.
15 April 2014 Tuesday	Hoorcollege 15-17 G2.10	Recap of what we can do in FST (e.g., define groups, fields, topological spaces) and cannot do in FST (e.g., define metric spaces). Informal discussion of finite and infinite sets. Dedekind-infinite sets. Inductive sets, and the axiom of infinity. The axiom system Z of Zermelo set theory. The set of natural numbers in Z, and proof that it is a Peano structure. The sets of integers, rational numbers, real numbers, and complex numbers (all in Z), and some alternative definitions for some cases. Informal discussion of the usual axioms of set theory we haven't yet seen, and the axiom systems ZF, ZF^–, ZFC^–, and ZFC.
16 April 2014 Wednesday	Werkcollege 11-13 D1.114	Discussion of Homework set 2. Example of solution to exercise 2
16 April 2014 Wednesday	Hoorcollege 17-19 C1.112	Definition of "is of same the size as" and "is at most as big as" relations between sets. (Formal) definitions of finite, infinite, countable, and uncountable sets. Cantor's theorem. Formulas representing functions, and the axiom of replacement. Informal introduction to definitions by recursion. Homework set 3 handed out (due 23 April 2014 before the morning werkcollege)
22 April 2014 Tuesday	Hoorcollege 15-17 G2.10	Proof that Separation follows from Replacement. Finite sequences. The basic recursion theorem (in Zermelo set theory). Complete induction vs order induction. Two generalizations of the basic recursion theorem (still provable in Z).
23 April 2014 Wednesday	Werkcollege 11-13 D1.114	Discussion of Homework set 3.
23 April 2014 Wednesday	Hoorcollege 17-19 C1.112	Dedekind's Theorem (any two Peano structures are isomorphic). Definition of transitive closure of a relation. The least number principle and wellfoundedness of relations. Equivalence of wellfoundedness and the principle of order induction. 3rd generalization of the recursion theorem (in ZF^–). Homework set 4 handed out (due 30 April 2014 before the morning werkcollege)
25 April 2014 Friday	No class	PhDs in Logic conference in Utrecht.
29 April 2014 Tuesday	Hoorcollege 15-17 G2.10	Wellfounded relations and wellorders. Successor functions in wellorders (without largest elements), and successor and limit elements in a wellorder. Comparing wellorders, and the statement and idea of the proof of the Fundamental Theorem for Wellorders.
30 April 2014 Wednesday	Werkcollege 11-13 D1.114	Discussion of Homework set 4, and additional discussion of Homework set 3. Example of solution to exercise 4 of homework set 3.
30 April 2014 Wednesday	Hoorcollege 17-19 C1.112	Proof of the Fundamental Theorem for Wellorders. Proof that any collection of wellorders is itself wellordered in a certain sense. Definitions of transitive sets and ordinal numbers. Properties of ordinal numbers. Homework set 5 is now available (due 7 May 2014 before the morning werkcollege)
6 May 2014 Tuesday	Werkcollege 15-17 G2.10	Explicit statement and proof of Transfinite Induction. Exercises.
7 May 2014 Wednesday	Werkcollege 11-13 D1.114	Discussion of Homework set 5 and of some exercises from 6 May.
7 May 2014 Wednesday	Hoorcollege 17-19 C1.112	Proof that every wellorder is isomorphic to some ordinal, via the Mostowski Collapsing Lemma. Proof of Hartogs's theorem: for every set there is an ordinal which does not inject into it. Proof of the Transfinite Recursion theorem, and some applications: addition and multiplication of ordinals, and the Aleph sequence. Introduction of the Axiom of Choice, and proof that AC implies that every set is wellorderable. Homework set 6 handed out (due 14 May 2014 before the morning werkcollege)
9 May 2014 Friday	Hoorcollege 13-15 G0.05	Cardinal Comparison (CC), including a proof that CC is equivalent to AC. Notions of comparability of cardinals via injections and surjections and their equivalence on the basis of AC. Zorn's Lemma and its equivalence to AC. The aleph sequence revisited: successor and limit cardinals. Cardinals of countable cofinality (examples). Regular cardinals. Proof (using AC) that all successor cardinals are regular.
13 May 2014 Tuesday	Hoorcollege 15-17 G2.10	The cofinality of a limit ordinal (different equivalent formulations). Properties of the cofinality (cf(α) is a regular cardinal). Singular cardinals of uncountable cofinality. Cardinalities of standard sets such as the set of real numbers. The beth numbers. The continuum hypothesis. The generalized continuum hypothesis.
14 May 2014 Wednesday	Werkcollege 11-13 D1.114	Discussion of Homework set 6.
14 May 2014 Wednesday	Hoorcollege 17-19 C1.112	Size of the set of real numbers. n-ary expansion of real numbers. Cardinal arithmetic: addition and multiplication. Triviality theorem (addition and multiplication coincide with the maximum function). Definition of ω_α = ℵ_α in order to stress that we are talking about the ordinal character of a cardinal. Cardinal exponentiation; basic properties. The Hausdorff Formula. Statement of Kőnig's Lemma (no proof). The von Neumann hierarchy (definition). Homework set 7 handed out (due 21 May 2014 before the morning werkcollege)
16 May 2014 Friday	Werkcollege 13-15 G0.05	Recap.
20 May 2014 Tuesday	Hoorcollege 15-17 G2.10	Equivalence (under AC) of wellfoundedness and the nonexistence of infinite descending chains. The axiom of foundation, and equivalent statements under AC. Properties of the von Neumann hierarchy, and its connections with (Found). Handout with the proof of Kőnig's lemma.
21 May 2014 Wednesday	Werkcollege 11-13 D1.114	Discussion of Homework set 7, and discussion of the training exam.