Administrivia Prerequisites, text and syllabus Exams, HW and grading policy Homework sets Homework solutions Handouts Lecture summaries

Set theory

 

Administrivia

The course meets at 12:30 MWF in PH 226 A. Office hours by appointment, please send email to jcumming@andrew.cmu.edu to arrange an appointment.

Homework will be set most Mondays, will be due on the following Monday, and should be returned graded by the Monday after that. Late homework will not be accepted under any circumstances, but the lowest homework score will be dropped.

The graders for this course are Sam Ziegler and Rohit Garg. Questions about grading should be addressed to them in the first instance.

 

Prerequisites, text and syllabus

Prerequisites: Ability to write a mathematical proof.

The text is Professor Schimmerling's forthcoming textbook "Undergraduate set theory".

Tentative syllabus (this will firm up as the term progresses):

  1. Introduction
  2. The axioms of ZFC
  3. Recursion and induction
  4. Ordinals and cardinals
  5. Applications

 

Exams, HW and grading policy

There will be a midterm and a final. Grades will be assigned according to a formula in which (roughly speaking) homework counts 35 percent, the midterm counts 30 percent and the final counts 35 percent. I encourage collaboration on the homework but you must write up your solutions by yourself.

 

Homework sets and exams

  1. Homework 1:
    1. Exercise 2.2
    2. Exercise 2.3
    3. Exercise 2.10 (extra credit if you can show that the set of equivalence classes is not countable)
    4. Is the set of all finite sets of natural numbers countable or uncountable? (you should justify your answer)
  2. Homework 2: In exercises 2.4, 2.6 and 2.8 you must write the proofs in the following way: every time you make an assertion that a set exists (or that two sets are equal) you must state which axiom(s)of set theory you are using. You may use the usual informal style for 2.12 but of course your arguments must be based on the axioms for Boolean algebras given on page 18 of the notes.
    1. Exercise 2.4
    2. Exercise 2.6
    3. Exercise 2.8
    4. Exercise 2.12
  3. Homework 3:
    1. Define a relation R on pairs of natural numbers as follows: (a, b) R (c, d) if and only if EITHER a < c OR a=c, b < d. Prove that R is well-founded.
    2. Recall that a binary relation on X is a subset of X^2. With this convention, say that C is a chain of binary relations on X if and only if C is nonempty, every R in C is a binary relation on X, and C is linearly ordered by inclusion. Prove that if C is a chain of partial orderings of X, then the union of C is a partial ordering of X.
    3. A partial ordering R of X will be called maximal if no proper superset of R is a partial ordering of X. Prove that R is maximal if and only if R is a linear ordering of X.
    4. Let X be the set of all functions from the set N of natural numbers to N. Define a binary relation R on X as follows: f R g if and only if there is an integer m such that f(n) < g(n) for all n > m. Prove or disprove each of the following assertions:
      1. R is transitive.
      2. R is well-founded.
      3. For every countable subset Y of X, there is h in X such that g R h for all g in Y.
  4. Homework 4:
    1. Exercise 3.3
    2. Exercise 3.4
    3. Exercise 3.6
    4. Prove that the collection of all countable ordinals is an ordinal. Prove that it is the least uncountable ordinal.
    5. True or false? For every ordinal alpha there is an ordinal beta such that alpha + beta = beta. You should either prove it or give a counterexample.
  5. The midterm. This exam is due at my office (Wean 7101) by 5pm on Thursday March 5th. You may not collaborate but may consult any printed or online source (please cite them). You should contact me with any questions or corrections. Ian Voysey kindly typeset this exam in TeX. Here is a pdf file and here is the TeX source. I retired the HTML version that was here until Sunday morning: it contained some mistakes which are now fixed in the TeX/PDF versions. At a suggestion from Trevor Burns I have clarified the language of question 1. I also fixed an error in Q3 pointed out by Einam Livnat.
  6. Homework 6: TeX and PDF. Due Mon 30.
  7. Final: TeX and PDF.

 

Homework solutions

Please tell me if there is anything in the solutions that you either do not understand or feel to be wrong. I will then expand or fix them as needed.

  1. Solutions for Homework 1.
  2. Solutions for Homework 3.
  3. Solutions for Homework 4.
  4. Solutions for Midterm.
  5. Solutions for Homework 6.

Handouts

Lecture summaries