Skip to content
Tutorials Center
My learning

Topics

Lesson 23 of 38 Β· Countable and Uncountable Sets

Countable Sets and Hilbert's Hotel

Learn what countably infinite means, show that the integers are countable with an explicit bijection, and explore Hilbert's hotel in Python.

A set is countable if its elements can be listed in a sequence, one after another, so that every element eventually appears at some finite position. The natural numbers 0, 1, 2, 3, ... are the model: the set β„• has cardinality β„΅β‚€, and a set is countably infinite exactly when it can be matched with β„•.

Countable infinity is the smallest kind of infinity. In this lesson you will see which familiar sets are countable, why some of them seem to be "bigger" than β„• but are not, and how a famous imaginary hotel makes the idea concrete.

Definitions

  • A set A is countably infinite if |A| = β„΅β‚€, that is, there is a bijection β„• β†’ A. Such a bijection is a way of listing A as aβ‚€, a₁, aβ‚‚, ... without repeats and without omissions.
  • A is countable if it is finite or countably infinite. Equivalently, there is an injection A β†’ β„•.
  • A set that is not countable is uncountable. The next lessons show such sets exist.

Some authors use "countable" for "countably infinite" only. Always check the convention.

The integers

The integers β„€ = {..., -2, -1, 0, 1, 2, ...} stretch infinitely in both directions. Yet they can be listed by alternating signs: 0, -1, 1, -2, 2, -3, 3, .... As a formula, the bijection f: β„• β†’ β„€ is

Text
f(n) =  n/2          if n is even
f(n) = -(n + 1)/2    if n is odd

So f(0) = 0, f(1) = -1, f(2) = 1, f(3) = -2, and so on. The inverse is f⁻¹(z) = 2z if z β‰₯ 0 and f⁻¹(z) = -2z - 1 if z < 0.

Python List the integers

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Listing is the proof

To show a set is countable, give a rule that produces its elements in order so that each element is reached after finitely many steps. A generator in a program is exactly this. A "list" that has one element beyond all the others, like 1, 3, 5, ... , 2, 4, 6, ... (all odds, then all evens), is not a valid listing, since the first even number would sit at position "after infinitely many".

Python Generators as listings

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Closure properties

Several quick facts follow from the definition:

  1. Every subset of a countable set is countable. An infinite subset of β„• can be listed in increasing order. If S βŠ† β„• is infinite, the map taking k to "the k-th smallest element of S" is a bijection β„• β†’ S.
  2. The union of two countable sets is countable. List one set at the even positions and the other at the odd positions; that is the interleaving trick from cardinal arithmetic.
  3. The product of two countable sets is countable. This needs a new idea; see the rationals.
  4. Every infinite set contains a countably infinite subset (using the axiom of choice for the general case; for subsets of β„•, nothing special is required).

Hilbert's hotel

The German mathematician David Hilbert popularized a thought experiment. A hotel has rooms numbered 1, 2, 3, ... forever, and every room is occupied. A new guest arrives. Can the hotel house them?

Yes. Ask each guest to move from room n to room n + 1. Room 1 becomes free. This is the bijection n ↦ n + 1 from {1, 2, 3, ...} onto {2, 3, 4, ...}.

What if infinitely many new guests arrive, numbered 1, 2, 3, ...? Ask each guest in room n to move to room 2n. All the even rooms are filled, and the odd rooms are empty for the newcomers. Again a bijection β„• β†’ evens does the work.

And a bus carrying countably many guests for each of countably many buses? That uses β„• Γ— β„•, and it is solved in the next lesson.

Python Hilbert's hotel simulator

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The simulation only shows a finite window, but every step is a formula valid for all rooms at once. The hotel is not magic: it only shows that "full" has no meaning for infinite sets.

Hilbert's hotel is a metaphor for bijections of β„• with a proper subset or with itself plus more. It is not a physical claim.

Check your understanding

Quick check Β· 4 questions

of 4 answered You scored / 4 Β· perfect!

  1. 1. Which listing proves that the integers are countable?

    Alternating signs reaches every integer after finitely many steps. The other two listings put the negatives after infinitely many positives.
  2. 2. A set is countable if...

    Countable means finite or countably infinite.
  3. 3. In Hilbert's hotel, how do you make room for one extra guest?

    Shifting everyone up one room frees room 1.
  4. 4. Which statement about subsets of a countable set is true?

    An infinite subset of a countable set can be listed in increasing order, so it is countably infinite.

Summary

  • A set is countably infinite if it can be matched with β„•, equivalently listed aβ‚€, a₁, aβ‚‚, ...; its cardinality is β„΅β‚€.
  • β„€ is countable: list 0, 1, -1, 2, -2, ... using an explicit bijection.
  • A valid listing reaches every element after finitely many steps.
  • Subsets and unions of two countable sets are countable.
  • Hilbert's hotel illustrates β„΅β‚€ + 1 = β„΅β‚€ and β„΅β‚€ + β„΅β‚€ = β„΅β‚€.

Next: The Rationals Are Countable