Cardinals · Definition

Cantor's diagonal theorem

set theorycardinals

Before you start you need to know

This theorem shows that some infinite sets cannot be listed, and it underlies the proof that \(\mathbb{R}\) is not countable.

Definition

Theorem proving that the set \(\{0,1\}^{\mathbb{N}}\) of binary sequences is not countable, by building a sequence that appears in no list.

\[t(n)=1-s_n(n)\]

Let \(s_1,s_2,s_3,\dots\) be any list of binary sequences, and let \(s_n(n)\) be the \(n\)-th term of \(s_n\). Define \(t(n)=1-s_n(n)\), that is, the diagonal term flipped from 0 to 1 or from 1 to 0. Since \(t(n)\neq s_n(n)\), the sequence \(t\) differs from \(s_n\) at position \(n\), so it does not appear in the list.

Therefore no list exhausts \(\{0,1\}^{\mathbb{N}}\), and there is no surjective function from \(\mathbb{N}\) onto \(\{0,1\}^{\mathbb{N}}\): the set is uncountable. The same argument, using binary or decimal expansions, shows that \(\mathbb{R}\) is uncountable too.

Example: with \(s_1=000\ldots\), \(s_2=111\ldots\) and \(s_3=0101\ldots\), the diagonal gives \(t(1)=1\), \(t(2)=0\) and \(t(3)=1\), so \(t\) begins \(101\ldots\). Typical mistake: thinking the proof depends on the particular list; it works for any list, because the construction of \(t\) always succeeds.

Think about it

Think about it: why does the construction of \(t\) work for any list?

Because \(t\) differs from each \(s_n\) at position \(n\), so it never equals any of them.

Exercises 10

  1. What does Cantor's diagonal theorem state?
  2. Which sequence does the diagonal proof build to escape a list?
  3. Is \(\mathbb{N}\) countable?
  4. Which of these sets is uncountable?
  5. With \(s_1=000\ldots\), \(s_2=111\ldots\) and \(s_3=0101\ldots\), what are the first three terms of the diagonal sequence \(t\), where \(t(n)=1-s_n(n)\)?
  6. Why can the diagonal sequence \(t\) not appear in a list \(s_1,s_2,\dots\)?
  7. What does the diagonal argument imply for \(\mathbb{R}\)?
  8. Which of these statements is true?
  9. Let \(A\) be the set of binary sequences with finitely many ones. Is \(A\) countable?
  10. Let \(f\colon\mathbb{N}\to\{0,1\}^{\mathbb{N}}\) be any function. Which of these sequences is guaranteed not to lie in the image of \(f\), for every choice of \(f\)?

References

  • Herbert B. Enderton, Elements of Set Theory, 1st edition, Academic Press, 1977.
  • Thomas Jech, Set Theory (The Third Millennium Edition), 3rd millennium edition, Springer, 2003.