Skip to content
Tutorials Center
My learning

Topics

Lesson 23 of 37 · Cardinality and Orders

Cardinality and Countable Sets

Compare the sizes of infinite sets using bijections. Learn countable sets, Hilbert's hotel, why the integers and rationals are countable, and the Schroeder-Bernstein theorem.

How do you say two sets have the same size without counting? Pair their elements up. Two sets A and B have the same cardinality, written |A| = |B|, if there is a bijection A → B (see functions). This definition, due to Georg Cantor, works for infinite sets, where "count and compare" is impossible, and it leads to some of the most surprising results in mathematics.

We write |A| ≤ |B| if there is an injection A → B. The Schröder–Bernstein theorem says that if |A| ≤ |B| and |B| ≤ |A|, then |A| = |B|. You can therefore prove two sets are equinumerous by exhibiting two injections instead of a bijection.

Finite versus infinite

A set is finite if it is in bijection with {1, …, n} for some natural number n; otherwise it is infinite. A famous feature of infinite sets, which was once used as a definition by Dedekind: an infinite set can be put into bijection with a proper subset of itself. The map n ↦ 2n pairs ℕ with the even numbers, yet the evens are only a part of ℕ.

Python The naturals and the even numbers have the same size

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.

Countable sets

A set is countably infinite if it is in bijection with ℕ = {0, 1, 2, …}: you can list its elements as a₀, a₁, a₂, … with each element appearing exactly once. A set is countable if it is finite or countably infinite. The first infinite cardinality is called ℵ₀ (aleph-null).

Hilbert's Hotel. A hotel with infinitely many rooms is full. A new guest arrives: move the guest in room n to room n+1 and put the newcomer in room 0. A bus with infinitely many new guests arrives: move room n to room 2n and give the guests the odd rooms. Even ℵ₀ + ℵ₀ = ℵ₀.

Python Hilbert's Hotel as functions

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 integers and the rationals

The integers ℤ are countable: list them as 0, 1, −1, 2, −2, 3, …. The map sends n ≥ 0 evenly and negative numbers oddly.

The set of ordered pairs ℕ × ℕ is countable too. Imagine an infinite grid and walk through it along diagonals: (0,0), (1,0), (0,1), (2,0), (1,1), (0,2), …. The Cantor pairing function π(a, b) = (a + b)(a + b + 1)/2 + b is an explicit bijection ℕ × ℕ → ℕ. Since every positive rational p/q is a pair, ℚ is countable as well (map each rational to its lowest-terms pair, an injection into ℕ × ℕ; with the trivial injection ℕ → ℚ, Schröder–Bernstein finishes).

flowchart LR
    A["(0,0)"] --> B["(1,0)"] --> C["(0,1)"] --> D["(2,0)"] --> E["(1,1)"] --> F["(0,2)"] --> G["..."]

Walking the grid along diagonals gives every pair a finite position.

Python Cantor pairing and listing the rationals

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 of countable sets

  • A subset of a countable set is countable.
  • A finite union of countable sets is countable; so is a countable union of countable sets (this step needs a choice of enumeration for each set, a mild use of the axiom of choice).
  • The set of finite strings over a finite alphabet, and therefore the set of all programs in any programming language, is countable.
  • The set of algebraic numbers (roots of integer polynomials) is countable.

The last fact has a surprising consequence for computing: there are only countably many programs, so any problem space with uncountably many answers has problems no program solves. The next lesson, Cantor's diagonal argument, shows that such sets exist.

Python Enumerating all finite strings

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.

"Countable" means "can be listed", not "can be listed by hand" or "has a nice formula". Showing a listing exists, even a slow one, is the entire proof.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. What does |A| = |B| mean for infinite sets?

    Cantor defined equal cardinality by the existence of a bijection, which does not require counting.
  2. 2. Which set is NOT countable?

    All three can be listed. The reals will be the first uncountable set in the next lesson.
  3. 3. In Hilbert's Hotel, how can a full hotel host infinitely many new guests?

    The map n → 2n is injective and leaves every odd room free.
  4. 4. What does Schröder–Bernstein state?

    If |A| ≤ |B| and |B| ≤ |A| then |A| = |B|.

Summary

  • Sets have the same cardinality when a bijection exists; this works for infinite sets.
  • An infinite set can match a proper subset of itself, like ℕ and the even numbers.
  • ℕ, ℤ, ℕ × ℕ, ℚ and the set of finite strings are all countable, with cardinality ℵ₀.
  • Schröder–Bernstein lets you compare cardinalities with injections.

Next: Cantor's Diagonal Argument and Uncountability