Discrete Math · Undergraduate

Countable and Uncountable Sets: Sizes of Infinity

Quick answer

Two sets have the same size, or cardinality, when a bijection pairs their elements exactly. A set is countable if it is finite or can be listed as a first, second, third element and so on, matching the natural numbers. The even numbers, the integers and even the rational numbers are countable. The real numbers are not: Cantor's diagonal argument builds a number missing from any proposed list. So some infinite sets are strictly larger than others.

What you'll learn

  • Define equal cardinality with bijections
  • Show that the integers and the rationals are countable
  • Prove the real numbers are uncountable with the diagonal argument
  • Use countability to compare infinite sets

Counting by pairing

Two finite sets have the same size when their elements can be paired off with none left over. For infinite sets, take that as the definition: AA and BB have the same cardinality when there is a bijection between them.

A set is countable if it is finite or has the same cardinality as N={0,1,2,…}\mathbb{N} = \{0, 1, 2, \ldots\}. Equivalently, its elements can be listed as a sequence that reaches each one after finitely many steps.

Infinite sets behave strangely under this rule. The map n↦2nn \mapsto 2n pairs the natural numbers with the even numbers, so the evens, a part of N\mathbb{N}, are as numerous as all of N\mathbb{N}.

Why the rationals can be listed

Write the positive fractions pq\tfrac{p}{q} in a grid, pp across and qq down. Listing one row at a time would never finish the first row. Instead, walk the diagonals, where p+qp + q is constant: 11\tfrac{1}{1}; then 21,12\tfrac{2}{1}, \tfrac{1}{2}; then 13,22,31\tfrac{1}{3}, \tfrac{2}{2}, \tfrac{3}{1}; and so on, skipping values seen before, such as 22=11\tfrac{2}{2} = \tfrac{1}{1}. Each diagonal is finite, so every fraction is reached after finitely many steps. The rationals are countable.

Listing the fractions along diagonals A grid of fractions p over q, with p from 1 to 4 across and q from 1 to 4 down. A zigzag path visits 1/1, 2/1, 1/2, 1/3, 2/2, 3/1, 4/1, 3/2, 2/3, 1/4, sweeping one diagonal at a time. The repeated value 2/2 is marked in a second color and skipped in the list. 1/1 2/1 3/1 4/1 1/2 2/2 3/2 1/3 2/3 1/4
Listing the fractions along diagonals

Worked examples

Common mistakes

Practice problems

  1. Give a bijection from N={0,1,2,…}\mathbb{N} = \{0, 1, 2, \ldots\} to the odd natural numbers.

    Answer

    n↦2n+1n \mapsto 2n + 1

    Full solution

    It is one-to-one, and every odd number 2n+12n + 1 comes from nn.

  2. Is the set of all finite strings of 00s and 11s countable?

    Answer

    Yes

    Full solution

    List them by length: there are finitely many of each length, 2k2^k of length kk.

  3. Is the set of all infinite sequences of 00s and 11s countable?

    Answer

    No

    Full solution

    Given any list, flip the nn-th entry of the nn-th sequence. The new sequence is not on the list.

  4. Explain why the union of two countable sets is countable.

    Answer

    Interleave the two lists: a1,b1,a2,b2,…a_1, b_1, a_2, b_2, \ldots, skipping repeats.

    Full solution

    Each element appears at a finite position in the merged list.

  5. Are the irrational numbers countable?

    Answer

    No

    Full solution

    R\mathbb{R} is the union of the rationals and the irrationals. If both were countable, so would be R\mathbb{R}.

  6. Using the formula in Example 3, find the position of (0,3)(0, 3).

    Answer

    99

    Full solution

    3⋅42+3=9\tfrac{3 \cdot 4}{2} + 3 = 9.

  7. Show that (0,1)(0, 1) and (0,2)(0, 2) have the same cardinality.

    Answer

    x↦2xx \mapsto 2x is a bijection.

    Full solution

    It is one-to-one, and each y∈(0,2)y \in (0, 2) comes from y2∈(0,1)\tfrac{y}{2} \in (0, 1).

  8. A student says the rationals must be uncountable because between any two there is another. What is wrong?

    Answer

    Density is about order, not size; the diagonal listing reaches every rational.

    Full solution

    The listing ignores the order on the number line. It only needs each fraction to appear at some finite position.

Frequently asked questions

What does it mean for a set to be countable?

It is finite, or there is a bijection between it and the natural numbers, so its elements can be listed in a sequence that eventually reaches each one.

Are there as many even numbers as natural numbers?

Yes. The map n ↦ 2n pairs them exactly, even though the evens are a proper subset.

Why are the rational numbers countable?

Arrange the fractions p/q in a grid and walk through it along diagonals, skipping repeats. Every fraction is reached after finitely many steps.

What is Cantor's diagonal argument?

Given any list of real numbers in (0, 1), build a number whose n-th digit differs from the n-th digit of the n-th number. It differs from every number on the list, so no list contains all reals.

Are some infinities bigger than others?

Yes. The reals are uncountable, so there is no bijection with the naturals. Cantor also showed every set is smaller than the set of its subsets.