Countability and diagonalization

Comparison of sets by injections and bijections, the Cantor–Bernstein theorem, countable sets, Cantor's diagonal argument and the cardinality of the continuum. The last lesson applies diagonalization to computation: counting arguments, effective diagonalization, the halting set, and constructions by finite extension. It uses the universal function of the course on models of computation; the first five lessons have no prerequisite.

Contents

1. 1

   Equipotence and subpotence

   Comparison of sets by bijections and injections; finite sets and the pigeonhole principle.

   1. 1.1 Functions and inverses
   2. 1.2 Equipotence
   3. 1.3 Finite sets
   4. 1.4 Subpotence
   5. 1.5 Exercises
   6. 1.6 Notes and references
   35 min
2. 2

   The Cantor–Bernstein theorem

   Two sets each injecting into the other are equipotent; explicit form of the bijection; the role of the axiom of choice.

   1. 2.1 The key lemma
   2. 2.2 The theorem
   3. 2.3 The bijection, explicitly
   4. 2.4 The role of the axiom of choice
   5. 2.5 Exercises
   6. 2.6 Notes and references
   35 min
3. 3

   Countable sets

   Characterizations of countable sets; subsets of ℕ; products, unions, finite strings, rationals and algebraic numbers.

   1. 3.1 Definition and characterizations
   2. 3.2 The smallest infinity
   3. 3.3 Pairs and tuples
   4. 3.4 Unions
   5. 3.5 Finite strings and finite sets
   6. 3.6 Exercises
   7. 3.7 Notes and references
   40 min
4. 4

   The diagonal argument

   Cantor space; uncountability of the sets of binary sequences, of integer sequences, of power sets and of ℝ by diagonalization; a general form of the argument.

   1. 4.1 Cantor space
   2. 4.2 The diagonal argument
   3. 4.3 A general form
   4. 4.4 Every set is smaller than its power set
   5. 4.5 The real numbers
   6. 4.6 Exercises
   7. 4.7 Notes and references
   40 min
5. 5

   The cardinality of the continuum

   The sets of binary sequences, of integer sequences, of real numbers and of real sequences are equipotent; removing a countable set does not change their cardinality; the continuum hypothesis.

   1. 5.1 Codings inside Cantor space
   2. 5.2 The real line
   3. 5.3 Removing a countable set
   4. 5.4 Cantor space and the Cantor set
   5. 5.5 The continuum hypothesis
   6. 5.6 Exercises
   7. 5.7 Notes and references
   35 min
6. 6

   Diagonalization and computation

   Counting arguments; effective diagonalization against uniformly computable sequences; partial functions and the halting set; diagonalization by requirements.

   1. 6.1 Counting
   2. 6.2 Effective diagonalization
   3. 6.3 Partial functions
   4. 6.4 Diagonalization by requirements
   5. 6.5 Exercises
   6. 6.6 Notes and references
   40 min