PG6.3 Countable sets

Simulate

Check the claim with numbers

Two finite sets have the same size when a bijection pairs them off (lesson PG6.2). The same idea measures infinite sets. Can the whole numbers $\mathbb{Z} = \{\ldots, -2, -1, 0, 1, 2, \ldots\}$ be paired off with $\mathbb{N} = \{1, 2, 3, \ldots\}$ ?

Try a list that takes 0 first, then steps out in both directions: $0, 1, -1, 2, -2, \ldots$ . As a formula, place $n$ holds $\frac{n}{2}$ for even $n$ and $\frac{1 - n}{2}$ for odd $n$ .

def f(n): return n // 2 if n % 2 == 0 else (1 - n) // 2 print([f(n) for n in range(1, 12)]) values = [f(n) for n in range(1, 2002)] print(sorted(values) == list(range(-1000, 1001)), len(set(values)) == len(values))

⌘/Ctrl + Enter runs the cell

The first 11 places hold $0, 1, -1, 2, -2, \ldots, 5, -5$ . The first 2,001 places hold every whole number from $-1000$ to 1000, each exactly once.

Conjecture

f: \mathbb{N} \to \mathbb{Z}

The first 2,001 places. The proof must show that every whole number gets exactly one place, however far out.

Countable sets

Take a list $s_1, s_2, s_3, \ldots$ in which every element of a set $S$ appears exactly once. It is a bijection from $\mathbb{N}$ to $S$ : place $n$ goes to $s_n$ .

Rule: Countable

\begin{gathered} S \text{ is countable when} \\ S \text{ is finite, or there is} \\ \text{a bijection } f: \mathbb{N} \to S \end{gathered}

A countable set is one whose elements can be listed, each at exactly one place. An infinite countable set is countably infinite: the same size as $\mathbb{N}$ .

Format 1

Reorder the steps

Here is the proof that $f$ is a bijection, with its lines shuffled. Put them in order with the arrows, or drag a line by its handle.

Surjective as well: a whole number $k \ge 1$ is $f(2k)$ , and a whole number $k \le 0$ is $f(1 - 2k)$ , where $1 - 2k$ is odd and at least 1.
For $k \ge 1$ , an even $n = 2k$ gives $f(n) = k \ge 1$ , and an odd $n = 2k - 1$ gives $f(n) = 1 - k \le 0$ .
Both even gives $\frac{n}{2} = \frac{n'}{2}$ , and both odd gives $\frac{1 - n}{2} = \frac{1 - n'}{2}$ . Either way $n = n'$ .
So $f$ is a bijection from $\mathbb{N}$ to $\mathbb{Z}$ , and $\mathbb{Z}$ is countable.
Define $f: \mathbb{N} \to \mathbb{Z}$ by $f(n) = \frac{n}{2}$ for even $n$ and $f(n) = \frac{1 - n}{2}$ for odd $n$ .
Injective: if $f(n) = f(n')$ , that value is either positive or not, so by the line before, $n$ and $n'$ are both even or both odd.

$\mathbb{Z}$ looks twice as big as $\mathbb{N}$ , yet the two have the same size. Infinite sets behave differently from finite ones, so claims about their sizes need proofs.

Simulate

Listing pairs

The pairs of whole numbers, $\mathbb{N} \times \mathbb{N} = \{(m, n) : m, n \in \mathbb{N}\}$ , fill an infinite grid. List them along diagonals: $(1, 1)$ , then $(1, 2), (2, 1)$ , then $(1, 3), (2, 2), (3, 1)$ , and so on.

Diagonal $d$ holds the pairs with $m + n - 1 = d$ . The cell builds the list for the first 100 diagonals and checks a formula for the place of each pair.

listing = [(m, d + 1 - m) for d in range(1, 101) for m in range(1, d + 1)] print(listing[:10]) def place(m, n): d = m + n - 1 return (d - 1) * d // 2 + m print(len(listing), len(set(listing)) == len(listing)) print(all(place(m, n) == i + 1 for i, (m, n) in enumerate(listing))) print(place(3, 5)) small = [(m, n) for m in range(1, 4) for n in range(1, 4)] rows = set((1, n) for n in range(1, 10**6 + 1)) print(sum(q in rows for q in small), max(place(m, n) for m, n in small))

⌘/Ctrl + Enter runs the cell

The first 100 diagonals hold 5,050 different pairs, and the formula gives the place of every one. For example, $(3, 5)$ sits at place 24.

The last line compares a row-by-row list, which gives the first million places to row 1. Of the 9 pairs with both entries at most 3, it places only 3. The diagonals place all 9 within the first 13 places.

Conjecture

\mathbb{N} \times \mathbb{N}

5,050 pairs on 100 diagonals. The proof shows the formula gives every pair one place, and uses every place once.

Format 2

Fill the gap

The proof, with its key steps left out. Type each missing piece as you would a quick answer, such as d^2 or (d+1)/2, then check.

d

How to type answers

Powers with ^, brackets round a power that is a sum: r^k, r^(k+1).
Fractions with / and brackets: (1-r)/(1+r). Multiply with * or side by side: 2k+1.
Press Enter in any box to check them all.

The same list, with repeats such as $\frac{2}{4} = \frac{1}{2}$ skipped, lists every positive fraction $\frac{m}{n}$ . So the positive rational numbers are countable too.

Format 3

Find the error

A first attempt that lists the pairs row by row. In the simulation, a million places of this list held only 3 of the 9 pairs with entries up to 3. Find the faulty line.

Lesson PG6.4 shows that some infinite sets cannot be listed at all, however cleverly.

f: \mathbb{N} \to S

Countable sets

Check the claim with numbers

Countable sets

Rule: Countable

Reorder the steps

Listing pairs

Fill the gap

Find the error

Summary card

Free further reading