Countability and Complements
A set may be uncountable even when a familiar countable set has been removed from it. The real numbers provide the central example: the rationals are countable, but removing them leaves the irrational numbers, which are uncountable. The key reasoning is not a subtraction rule for sizes. Instead, it is a contradiction: if both pieces were countable, their union would be countable too.
We use two results established in the earlier material: the rational numbers \(\mathbb{Q}\) are countable, and the real interval \([0,1]\) is uncountable by Cantor’s diagonal argument. The same argument establishes that \(\mathbb{R}\) is uncountable. The countability results needed to combine these facts are stated and justified first.
It is also useful to recognize countable sets as sets that can be listed by a sequence, allowing repetitions when the set is finite. For a nonempty countable set, such a sequence can be chosen to include every element. Conversely, if a sequence lists every element of a set, assign each element the least index at which it appears; this gives an injection of the set into \(\mathbb{N}\). These equivalent descriptions let us combine lists without needing to remove repetitions.
Proof. If \(A\) is countable and \(B\subseteq A\), an injection from \(A\) to \(\mathbb{N}\) restricts to an injection from \(B\) to \(\mathbb{N}\), so \(B\) is countable. For the union statement, if either set is empty, the union is the other countable set. Otherwise choose sequences \((a_n)\) and \((b_n)\) that list \(A\) and \(B\), repeating terms if either set is finite. The sequence \(a_1,b_1,a_2,b_2,\dots\) lists every element of \(A\cup B\). A set listed by a sequence is countable, by assigning each element its first index. Thus \(A\cup B\) is countable. \(\square\)
The Irrational Numbers Are Uncountable
Proof. Suppose, for contradiction, that \(\mathbb{R}\setminus\mathbb{Q}\) is countable. The rationals \(\mathbb{Q}\) are countable by the earlier enumeration of the rational numbers. By the lemma, the union of these two countable sets is countable. But \(\mathbb{R}=\mathbb{Q}\cup(\mathbb{R}\setminus\mathbb{Q})\), so this would make \(\mathbb{R}\) countable. This contradicts the uncountability of the real numbers established by Cantor’s diagonal argument. Therefore \(\mathbb{R}\setminus\mathbb{Q}\) is uncountable. \(\square\)
The argument depends on both pieces of information: the rationals are countable, and the reals are uncountable. Knowing only that the rationals are countable would not show that their complement is uncountable. It is the size of the whole set, together with the fact that a union of two countable sets is countable, that forces the conclusion.
Worked Example: Irrationals in the Real Line
Apply the theorem to identify the size of the set of irrational real numbers. The rationals and irrationals are disjoint: a real number cannot both belong to \(\mathbb{Q}\) and not belong to \(\mathbb{Q}\). Every real number belongs to exactly one of these two sets, so their union is all of \(\mathbb{R}\):
If the irrational set were countable, then both sets on the right would be countable. The lemma would make their union countable, contradicting the uncountability of \(\mathbb{R}\). Hence the irrational set is uncountable. This conclusion concerns the size of the set, not whether it contains particular familiar examples: for instance, \(\sqrt{2}\) is one irrational number, but one example alone does not establish uncountability.
Check: the conclusion does not say that the rationals are absent from \(\mathbb{R}\); they form the other piece of the displayed union. It says that the remaining piece, \(\mathbb{R}\setminus\mathbb{Q}\), cannot be listed as a finite set or a sequence.
Removing Countably Many Points
Proof. Suppose instead that \(X\setminus C\) is countable. The set \(C\) is countable by hypothesis, so the lemma says that \(C\cup(X\setminus C)\) is countable. Since \(C\subseteq X\), every point of \(X\) is either in \(C\) or in \(X\setminus C\), and no point is in both. Thus \(X=C\cup(X\setminus C)\), which would make \(X\) countable. This contradicts the hypothesis that \(X\) is uncountable. Therefore \(X\setminus C\) is uncountable. \(\square\)
This proves more than the claim that at least one point remains after removing \(C\). It proves that the remaining set is itself uncountable. The hypothesis \(C\subseteq X\) matters because the decomposition \(X=C\cup(X\setminus C)\) requires it. The hypothesis that \(X\) is uncountable matters too: removing a countable subset from a countable set can leave a countable set, or even the empty set.
Worked Example: Irrationals in the Closed Unit Interval
Consider \(D=[0,1]\setminus\mathbb{Q}\), the irrational numbers in the closed unit interval. The set \(C=[0,1]\cap\mathbb{Q}\) is a subset of \(\mathbb{Q}\), so it is countable by the subset part of the lemma. The earlier diagonal argument establishes that \([0,1]\) is uncountable. Since \(C\subseteq[0,1]\), the removal theorem applies with \(X=[0,1]\):
It follows that \(D\) is uncountable. In particular, restricting attention to a bounded interval does not make the irrational numbers countable. The rational points removed from the interval form a countable set, while the interval itself is uncountable.
Check: the decomposition is exactly \([0,1]=C\cup D\). It includes both endpoints: \(0\) and \(1\) belong to \(C\), since both are rational, and neither belongs to \(D\).
Worked Example: Removing an Explicit Countable Set
Let \(C=\{0\}\cup\{1/n:n\in\mathbb{N}\}\subseteq\mathbb{R}\). To list it, define \(c_1=0\) and \(c_{n+1}=1/n\) for every \(n\in\mathbb{N}\). The first terms are \(c_1=0\), \(c_2=1/1=1\), \(c_3=1/2\), and \(c_4=1/3\). In general, this sequence lists \(0\) and every \(1/n\), so it lists all of \(C\).
There are no repetitions: \(1/m=1/n\) for positive integers \(m,n\) implies \(m=n\), and each \(1/n\) is positive, so none equals \(0\). Thus the sequence lists the elements of \(C\) without repetition, and \(C\) is countable. Because \(\mathbb{R}\) is uncountable and \(C\subseteq\mathbb{R}\), the removal theorem gives that \(\mathbb{R}\setminus C\) is uncountable.
Check: the point \(0\) is removed as the first listed element, and \(1/3\) is removed as \(c_4=1/(4-1)\). The theorem concerns all real numbers not listed in the sequence; it does not assert that this complement has a simple enumeration.
A Common Pitfall: Subtraction Is Not the Proof
A tempting but invalid calculation is to write \(|\mathbb{R}\setminus\mathbb{Q}|=|\mathbb{R}|-|\mathbb{Q}|\) and then reason about the result as if subtracting an infinite size worked like subtracting finite integers. This expression does not justify a cardinality conclusion. The valid proof instead uses the set identity \(\mathbb{R}=\mathbb{Q}\cup(\mathbb{R}\setminus\mathbb{Q})\) and the proved fact that a union of two countable sets is countable.
The corresponding false inference “\(A\) is countable, so its complement is countable” also fails in a direct example. Take \(A=\mathbb{Q}\subseteq\mathbb{R}\). The set \(A\) is countable, but its complement \(\mathbb{R}\setminus A\) is uncountable by the theorem above. The correct conclusion is conditional: when \(X\) is uncountable and \(C\subseteq X\) is countable, \(X\setminus C\) is uncountable. Countability of the removed set by itself says nothing about the size of its complement in an unspecified space.
These arguments are useful whenever a set is divided into a countable part and a remaining part. If the whole set is known to be uncountable, the remaining part cannot also be countable. In this way, a diagonal argument about an interval or the real line can yield uncountability results for sets defined by excluding a familiar countable collection.
Check Your Understanding
For each question, identify the set decomposition or countability fact that justifies your conclusion.
- Suppose \(X\) is uncountable and \(C\subseteq X\) is finite. What can be concluded about \(X\setminus C\), and which theorem applies?
- Why does the countability of \(\mathbb{Q}\) alone not prove that \(\mathbb{R}\setminus\mathbb{Q}\) is uncountable?
- Let \(C=\mathbb{Z}\subseteq\mathbb{R}\). Use the removal theorem to determine whether \(\mathbb{R}\setminus\mathbb{Z}\) is countable or uncountable.
- Explain why \([0,1]\setminus\mathbb{Q}\) is uncountable, naming the two countability facts used.
- Give a countable set \(C\subseteq\mathbb{R}\) for which \(\mathbb{R}\setminus C\) is empty. What hypothesis of the removal theorem does this example fail?