Choosing a Cardinality Proof for Standard Sets

Choose the Proof to Fit the Set

Cardinality questions about familiar sets call for different proof strategies. To show that a set is countable, one can often give an enumeration or inject it into \(\mathbb{N}\). For products, a pairing function turns two indices into one. For real intervals, however, an attempted list is exactly what a diagonal argument defeats. The aim here is to choose a method that matches the structure of the set, then check that the method actually proves the claim.

For a countable set, choose the simplest route available. An explicit enumeration is useful when the elements have a natural order. An injection into \(\mathbb{N}\) is often cleaner when each element has a finite code. If a set is a product, encode its coordinates as a pair of natural-number indices. To prove uncountability, a diagonal construction is useful when a proposed enumeration would give each object a sequence of entries, such as decimal digits.

Finite Unions and Products

Proof. Let \(A\) and \(B\) be countable. By the definition of countability, choose injections \(i_A:A\to\mathbb{N}\) and \(i_B:B\to\mathbb{N}\); if one of the sets is empty, its injection is the empty function. Define a function from \(A\cup B\) to \(\mathbb{N}\times\{1,2\}\) by sending \(x\in A\) to \((i_A(x),1)\), and sending \(x\in B\setminus A\) to \((i_B(x),2)\). This function is injective: elements assigned different second coordinates have different images, while elements assigned the same second coordinate have different first coordinates because the relevant \(i_A\) or \(i_B\) is injective. The finite-product result for countable sets, established in the earlier material on finite products, says \(\mathbb{N}\times\{1,2\}\) is countable. Thus \(A\cup B\) injects into a countable set and is countable. Repeating this argument proves the finite-union statement; the empty union is empty and hence countable. \(\square\)

For products, the key device is a pairing function: a bijection from \(\mathbb{N}\times\mathbb{N}\) to \(\mathbb{N}\). One standard choice, with \(\mathbb{N}=\{1,2,\dots\}\), lists pairs by diagonals:

The earlier result on pairing natural numbers establishes that this formula gives a bijection. Its purpose is to turn two indices into one without losing the ability to distinguish pairs. If \(A\) and \(B\) inject into \(\mathbb{N}\), compose their coordinate injections with \(\pi\); the resulting map \(A\times B\to\mathbb{N}\) is injective. The same reasoning, applied repeatedly, handles any finite product of countable sets.

Fractions: Use a Canonical Code

Proof. Every rational number has a unique representation \(p/q\) in lowest terms with \(p\in\mathbb{Z}\), \(q\in\mathbb{N}\), and \(\gcd(|p|,q)=1\). For zero, this representation is \(0/1\). Let \(\iota:\mathbb{Z}\to\mathbb{N}\) be the index map from an enumeration of the integers; it is a bijection. Associate to \(p/q\) the pair \((\iota(p),q)\). Unique reduced representations imply that distinct rationals give distinct pairs. Since \(\mathbb{N}\times\mathbb{N}\) injects into \(\mathbb{N}\) by the pairing function, this gives an injection \(\mathbb{Q}\to\mathbb{N}\), so \(\mathbb{Q}\) is countable. It is infinite because it contains the infinitely many distinct integers. Therefore it is countably infinite. \(\square\)

The requirement that the fraction be reduced matters for the coding argument. For instance, \(1/2\) and \(2/4\) are the same rational number, not two different elements of \(\mathbb{Q}\). A list that includes both is not a one-to-one enumeration, although repetition alone would not prevent a list from covering the set. Canonical representations make the injection argument direct: one rational number has one code, and distinct rational numbers have distinct codes.

Real Intervals: Defeat Every Proposed List

Proof. Suppose, for contradiction, that \([0,1]\) is countable. Since it is infinite, it could then be listed as \(x_1,x_2,\dots\). For each \(x_n<1\), choose a decimal expansion that is not eventually all \(9\)s; a terminating decimal is written with zeros after its final nonzero digit. Write its \(n\)th decimal digit as \(a_n\). If \(x_n=1\), set \(a_n=0\). Define \(d_n=1\) when \(a_n\ne1\), and \(d_n=2\) when \(a_n=1\). The decimal \(y=0.d_1d_2d_3\dots\) lies in \([0,1]\), since all its digits are \(1\) or \(2\). It is not eventually all \(9\)s, so it is in the chosen unambiguous form. For each \(n\), its \(n\)th digit differs from the \(n\)th digit of \(x_n\) if \(x_n<1\); it also differs from \(x_n=1\), since \(y<1\). Therefore \(y\ne x_n\) for every \(n\), contradicting that the list contains every point of \([0,1]\). Thus \([0,1]\) is uncountable.

Now let \(a<b\). The function \(t\mapsto a+(b-a)t\) is a bijection from \([0,1]\) to \([a,b]\), so \([a,b]\) is uncountable. For the open interval \((a,b)\), the function \(t\mapsto a+(b-a)(1/4+t/2)\) is an injection from \([0,1]\) into \((a,b)\): its values range from \(a+(b-a)/4\) to \(a+3(b-a)/4\), both strictly between \(a\) and \(b\). If \((a,b)\) were countable, this injection would imply \([0,1]\) was countable, which it is not. The same argument applies to intervals with one or both endpoints included, since each contains a nonempty open interval. \(\square\)

A Common Pitfall: Decimal Ambiguity

A diagonal proof must account for the fact that some real numbers have two decimal expansions. For example, \(0.5000\dots=0.4999\dots\). A flawed argument might construct \(0.4999\dots\) as a number differing in a chosen digit from a listed expansion \(0.5000\dots\), then claim the new number is absent from the list. That conclusion does not follow: the two decimals represent the same real number.

The correction is to choose the listed expansions so none is eventually all \(9\)s, using trailing zeros for terminating decimals, and to construct the diagonal number with digits only \(1\) and \(2\). The constructed expansion is not eventually all \(9\)s either. Under this convention, distinct digit strings represent distinct reals, so the disagreement at position \(n\) proves that the constructed number is not the \(n\)th listed real. The diagonal argument then establishes a genuine difference in numbers, not just in notation.