5. Countability and diagonal arguments

Learning goals and conventions

Compare finite and infinite sets by functions rather than by visual size; enumerate products and rational numbers; write a complete diagonal contradiction. We use $\mathbb N=\{0,1,2,\ldots\}$. A set is countable if it is finite or can be listed as a sequence with every element occurring. It is countably infinite if it is in bijection with $\mathbb N$. Repeated elements in a listing can be removed by retaining their first appearances; an infinite listed set then has an enumeration without repetition.

A subset of a countable set is countable: scan the enumeration and keep only members of the subset. For $\mathbb N^2$, order pairs by $m+n$ and then by $m$ within each diagonal. There are finitely many pairs before any fixed pair, and every pair appears. Hence a product of two countable sets is countable by applying their enumerations to this diagonal list. This argument extends to every fixed finite product, not to a countably infinite product.

Theorem: countable unions with specified enumerations

If for each $j\in\mathbb N$ a set $A_j$ has a specified listing (finite lists are allowed), then $\bigcup_jA_j$ is countable.

Proof. List index pairs $(j,k)$ diagonally. At each pair, output the $k$th element of $A_j$ if it exists, and otherwise skip that pair. Every element belongs to some $A_j$ and appears at a finite position in its list, so it appears in the output. Remove repeated appearances if needed. Empty sets contribute no elements. The statement explicitly supplies enumerations; selecting infinitely many unspecified enumerations involves additional foundational choice questions not needed here.

Thus $\mathbb Z$ is countable via $0,1,-1,2,-2,\ldots$, and $\mathbb Q$ is countable by listing numerator–positive-denominator pairs and outputting their fractions. Distinct pairs may represent the same rational; duplicates do not prevent countability.

Theorem: Cantor's diagonal theorem

No map $F:X\to\mathcal P(X)$ is surjective, for any set $X$.

Proof. Given such a map, form $D=\{x\in X:x\notin F(x)\}$. If $D=F(d)$ for some $d\in X$, then $d\in D$ holds exactly when $d\notin F(d)=D$, a contradiction in either case. Thus $D$ is missing from the range. In particular $\mathcal P(\mathbb N)$ cannot be listed by the natural numbers.

To connect this to real numbers without ambiguous decimals, map $A\subseteq\mathbb N$ to

$$x_A=\sum_{n=0}^{\infty}\frac{2\mathbf1_A(n)}{3^{n+1}}\in[0,1].$$

If $A,B$ first differ at $m$, the leading difference has magnitude $2/3^{m+1}$ while all later terms together have magnitude at most $1/3^{m+1}$. Therefore $x_A\ne x_B$. This injects the uncountable power set into $[0,1]$, so the interval and $\mathbb R$ are uncountable. The argument avoids relying on uniqueness of decimal representations.

Worked examples

An infinite subset can have the same size. The map $n\mapsto2n$ bijects $\mathbb N$ with the even nonnegative integers. Infinite sets can be equinumerous with proper subsets; finite intuition about leftover elements is not a proof of smaller cardinality.

Algebraic real numbers are countable. Integer polynomials form a countable union of finite tuples of integers, one tuple length per degree. Each nonzero polynomial has finitely many real roots. Using a deterministic order on its finite real root set, the union theorem makes the collection of all algebraic real numbers countable. Since $\mathbb R$ is uncountable, nonalgebraic (transcendental) real numbers exist; this proof does not identify a particular one.

Graded practice

1. Foundation. Give a bijection from $\mathbb N$ to the positive odd integers.
2. Core. Prove that $\mathbb Q\times\mathbb Q$ is countable.
3. Core. Show that the set of finite binary strings is countable, but the set of infinite binary sequences is uncountable.
4. Proof. If $U$ is uncountable and $C\subseteq U$ is countable, prove $U\setminus C$ is uncountable.

Full solutions

1. The map $n\mapsto2n+1$ is injective, and every positive odd integer has exactly that form, so it is a bijection.
2. Choose a listing of rationals. Feed its index pairs through a diagonal enumeration of $\mathbb N^2$ and output the corresponding rational pairs. Every pair appears; repetitions may be removed.
3. For each length $n$ there are $2^n$ strings. Listing by length, then lexicographically, enumerates all finite strings. An infinite binary sequence is the indicator of a subset of $\mathbb N$. Cantor's theorem shows that those subsets, hence those sequences, cannot be listed.
4. If $U\setminus C$ were countable, a listing of it interleaved with a listing of $C$ would list their union $U$, contradicting uncountability. Therefore the complement cannot be countable.

Summary and term definitions

An enumeration lists every element; a bijection pairs elements uniquely in both directions. A diagonal argument constructs an object differing from the $n$th proposed entry at a controlled $n$th feature. Algebraic numbers solve nonzero integer polynomial equations. Countability is preserved by fixed finite products and by enumerated countable unions, but not by infinite binary products.