Countable and Uncountable Sets
Which infinite sets are the same size as \(\mathbb{Z}^{+}\), and which are strictly bigger. A set is countable when its elements can be listed, and uncountable when no list can contain them all. Sizes are compared with bijections and injections, as set out in cardinality. The lectures are 2026-09-14-cardinalities (the listings) and 2026-09-15-countable-and-uncountable-sets (the definitions and the uncountable sets).
The definitions
A set \(X\) is finite if and only if \(X = \emptyset\) or \(|X| = |\{1,2,\dots,n\}|\) for some \(n \in \mathbb{Z}^{+}\).
A set is infinite if and only if it is not finite.
A set \(X\) is countable if and only if it is finite or \(|X| = |\mathbb{Z}^{+}|\).
A set \(X\) is uncountable if and only if it is not countable.
A set \(X\) is countably infinite if and only if it is countable and infinite.
Every set falls in exactly one of three classes, and “countable” and “infinite” each cover two of them:
| finite | countably infinite | uncountable | |
|---|---|---|---|
| countable? | yes | yes | no |
| infinite? | no | yes | yes |
| \(\lvert X\rvert\) | \(0\) or \(n\) | \(\lvert\mathbb{Z}^{+}\rvert\) | \(> \lvert\mathbb{Z}^{+}\rvert\) |
| examples | \(\emptyset\), \(\{1, \dots, n\}\), \(\{0,1\}\) | \(\mathbb{Z}^{+}\), \(2\mathbb{Z}\), \(\mathbb{Z}\), \(\mathbb{Q}^{+}\), \(\mathbb{Q}\), \(\mathbb{Z} \times \mathbb{Z}\) | \((0,1)\), \(\mathbb{R}\), \(\mathcal{P}(\mathbb{Z}^{+})\) |
The trap is that countable includes finite. “Countable” is not a word for a kind of infinity; “countably infinite” is.
Listing a set
\(X\) is countably infinite if and only if the elements of \(X\) can be written as an infinite list, \(X = \{x_1, x_2, x_3, \dots\}\), where the \(x_i\) are all distinct.
A list is a bijection \(f : \mathbb{Z}^{+} \to X\), \(f(i) = x_i\). “All distinct” is one-to-one, and “every element of \(X\) is somewhere in the list” is onto. To show a set is countably infinite it is enough to describe a list and convince yourself of those two things.
The listings that matter:
| Set | List | Where |
|---|---|---|
| \(2\mathbb{Z}^{+}\) | \(2, 4, 6, 8, \dots\) | 2026-09-14-cardinalities |
| \(\mathbb{Z}\) | \(0, 1, -1, 2, -2, 3, -3, \dots\) | Figure 1; as a formula in cardinality |
| \(\mathbb{Q}^{+}\) | along the anti-diagonals of the \(\frac{a}{b}\) grid, skipping repeats | 2026-09-14-cardinalities |
| \(\mathbb{Z} \times \mathbb{Z}\) | out along a square spiral from \((0,0)\) | 2026-09-14-cardinalities |
| \(\mathbb{Q}\) | along the same spiral, counting only lowest-terms pairs \((a,b)\), with the sign kept in one fixed place (here \(b \geq 1\)) | 2026-09-14-cardinalities |
They are all built the same way. Break the set into finite batches that together cover it, and list the batches one after another. Because each batch is finite, every element comes up after finitely many steps. The batches are \(\{n, -n\}\) for \(\mathbb{Z}\), the anti-diagonals \(a + b = s\) for \(\mathbb{Q}^{+}\), and the square rings for \(\mathbb{Z} \times \mathbb{Z}\).
Figure 1: Two attempts to list \(\mathbb{Z}\); the number above each integer is its place in the list. Top: alternating out from 0 — \(0, 1, -1, 2, -2, \dots\) — reaches every integer after finitely many steps (\(-n\) is in place \(2n+1\)), so it is a list of all of \(\mathbb{Z}\). Bottom: all the positive integers first never finishes them, so 0 and the negatives never get a place, and it is not a list of \(\mathbb{Z}\) at all. A listing must reach every element after finitely many steps; going out in finite batches, here the pairs \({n, -n}\), is how to guarantee it.
Subsets of countable sets
Theorem: Any subset of a countable set is countable.
Corollary: Any set with an uncountable subset is uncountable.
The corollary is the contrapositive of the theorem. For the theorem, take a list of the countable set, keep the members of the subset in the order they come up, and cross out the rest. What is left is a list of the subset, finite if only finitely many survive. The key special case:
Every infinite subset of \(\mathbb{Z}^{+}\) has the same cardinality as \(\mathbb{Z}^{+}\).
Proof. Let \(A \subseteq \mathbb{Z}^{+}\) be infinite. Let \(a_1\) be the least element of \(A\), \(a_2\) the least element of \(A - \{a_1\}\), \(a_3\) the least element of \(A - \{a_1, a_2\}\), and so on. Each step is allowed by the well-ordering principle: what is left is a set of positive integers, and it is non-empty because \(A\) is infinite. Define \(f : \mathbb{Z}^{+} \to A\) by \(f(i) = a_i\).
- \(f\) is one-to-one, because \(a_1 < a_2 < a_3 < \cdots\), so different positions hold different numbers.
- \(f\) is onto, because an element \(a \in A\) has fewer than \(a\) elements of \(A\) below it, all positive integers less than \(a\). So \(a\) is the least element left after at most \(a - 1\) steps, and is picked as some \(a_j\).
So \(|\mathbb{Z}^{+}| = |A|\). \(\square\)
Figure 2: An infinite subset of \(\mathbb{Z}^{+}\), the primes, listed by always taking the least element not yet used. The well-ordering principle guarantees a least element at every step, and the list is increasing, so no prime is used twice. No prime is skipped either: a prime \(p\) has only finitely many primes below it, so it is reached after finitely many steps — 13 has five primes below it and is sixth. So \(i \mapsto a_i\) is a bijection from \(\mathbb{Z}^{+}\) to the primes, and the primes, a sparse and irregular subset, are exactly as numerous as the positive integers.
\(A \subseteq \mathbb{Z}^{+}\) is used twice: in the well-ordering step, which needs a least element at every stage, and in the onto step, “fewer than \(a\) elements below it”. The same construction on \(\mathbb{Q}^{+}\) itself breaks at the first of these, because there is no least positive rational, and that is why \(\mathbb{Q}^{+}\) needed the grid.
\(\mathbb{R}\) is uncountable
It is enough to show that the interval \((0,1)\) is uncountable, because \((0,1) \subseteq \mathbb{R}\) and the corollary does the rest.
Theorem. \((0,1)\) is uncountable.
Proof (by contradiction). Suppose \((0,1)\) is countable. It is infinite, so its elements can be written in a list \(r_1, r_2, r_3, \dots\). Write each as a decimal, \[r_n = 0.\,d_{n1}\,d_{n2}\,d_{n3}\,\dots\] Define a number \(d = 0.\,e_1\,e_2\,e_3\,\dots\) digit by digit, from the diagonal digits \(d_{11}, d_{22}, d_{33}, \dots\): \[e_n = \begin{cases} 1 & \text{if } d_{nn} \neq 1, \\ 2 & \text{if } d_{nn} = 1. \end{cases}\] Then \(d \in (0,1)\). For every \(n\), \(d\) differs from \(r_n\) in the \(n\)-th decimal place, so \(d \neq r_n\). So \(d\) is not in the list, a contradiction. Hence \((0,1)\) is uncountable, and so is \(\mathbb{R}\). \(\square\)
This is Cantor’s diagonal argument. It is worked on a concrete table in 2026-09-15-countable-and-uncountable-sets. Three points in it are easy to get wrong:
- It defeats every list, not one list. The proof never uses anything about the particular list. Whatever list is proposed, the diagonal manufactures a number it misses. That is what “no bijection from \(\mathbb{Z}^{+}\) exists” requires.
- Why the digits 1 and 2. Some numbers have two decimal expansions: \(0.1999\ldots = 0.2000\ldots\). If \(d\) could end in all 0s or all 9s, “differs in a digit” might not mean “is a different number”. A decimal made of 1s and 2s has only the one expansion, so it really is different from every \(r_n\).
- The same argument on \(\mathbb{Q}\) fails. The diagonal of a list of rationals produces a real number, and nothing forces it to be rational. So there is no contradiction, and indeed \(\mathbb{Q}\) is countable.
Not only is \(\mathbb{R}\) bigger than \(\mathbb{Z}^{+}\), it is no bigger than the interval inside it: \(|(0,1)| = |\mathbb{R}|\).
Figure 3: Why the open interval \((0,1)\) has as many points as the whole line. Bend \((0,1)\) into a circle resting on the line, so that its two missing endpoints would meet at the top point \(N\), which is left out. A ray from \(N\) through any other point of the circle meets the line exactly once, and every point of the line is hit by exactly one such ray. Points near the top land far out, the bottom point lands at 0, and nothing is left over on either side — a bijection \((0,1) \to \mathbb{R}\).
The irrational numbers are uncountable as well. If they were countable, \(\mathbb{R} = \mathbb{Q} \cup (\mathbb{R} - \mathbb{Q})\) would be a union of two countable sets and so countable (practice-problems, question 3).
The hierarchy
\[|\emptyset| < |\{1,2,\dots,n\}| < |\mathbb{Z}^{+}| = |\mathbb{Z}| = |\mathbb{Q}| < |\mathbb{R}| < |\mathcal{P}(\mathbb{R})|\]
Figure 4: The sizes of sets met in the course, smallest on the left. Countable covers the first three blocks, empty, finite and countably infinite; infinite covers the last two. Within a block the sets have equal size wherever the chain above writes \(=\): every countably infinite set is the size of \(\mathbb{Z}^{+}\). Crossing a boundary is a strict step up, and the step from countably infinite to uncountable is the diagonal argument. The last block is not all one size: \(\mathcal{P}(\mathbb{R})\) is strictly bigger than \(\mathbb{R}\).
Each strict step has a reason:
- \(|\emptyset| < |\{1, \dots, n\}|\). There is an injection from \(\emptyset\) (the empty function), but no function at all from a non-empty set to \(\emptyset\), so no bijection.
- \(|\{1, \dots, n\}| < |\mathbb{Z}^{+}|\). \(\{1, \dots, n\}\) sits inside \(\mathbb{Z}^{+}\), but no bijection exists, since \(\mathbb{Z}^{+}\) is not finite.
- \(|\mathbb{Z}^{+}| < |\mathbb{R}|\). \(\mathbb{Z}^{+} \subseteq \mathbb{R}\) gives \(\leq\), and the diagonal argument rules out \(=\).
- \(|\mathbb{R}| < |\mathcal{P}(\mathbb{R})|\). Stated without proof. Beyond the course: Cantor’s theorem says \(|A| < |\mathcal{P}(A)|\) for every set \(A\), by a diagonal argument on subsets. So the chain never stops: \(\mathcal{P}(\mathcal{P}(\mathbb{R}))\) is bigger again, and there is no largest size.
How to show a set is countable, or uncountable
Countable — any one of:
- It is finite.
- Write down a list, in finite batches, and check that every element appears exactly once.
- Give a bijection with a set already known to be countable, such as \(\mathbb{Z}^{+}\), \(\mathbb{Z}\), \(\mathbb{Q}\) or \(\mathbb{Z} \times \mathbb{Z}\).
- Give an injection into a countable set. The image is a subset of a countable set, so it is countable, and the injection is a bijection onto its image, so the set itself is countable too. With an injection the other way as well, Schröder–Bernstein gives the exact cardinality, as in the proof that \(\mathbb{Z}^{+} \times \mathbb{Z}^{+}\) is countable using \((a,b) \mapsto 3^a 5^b\) (2026-09-15-countable-and-uncountable-sets).
Uncountable — any one of:
- It contains an uncountable subset, such as an interval of \(\mathbb{R}\).
- There is an injection from a known uncountable set into it, for example from \((0,1)\).
- A diagonal argument: assume a list, and build an element the list misses.
Whatever the direction, the argument has to be a proof. Not being able to think of a list does not show that none exists.
What is assessed. The course practice set marks its whole countable-and-uncountable section (§28) “not assessed in MATH1061”, while Lecture 22 marks only the proof that \(\mathbb{R}\) is uncountable and the countability of \(\mathbb{Z}^{+} \times \mathbb{Z}^{+}\) as not assessed. The two disagree, so check with the course.
See also
- cardinality — bijections, the \(|X| = |Y|\) template, \(\leq\) by injection, Schröder–Bernstein
- strong-induction-and-the-well-ordering-principle — the principle that lists an infinite subset of \(\mathbb{Z}^{+}\)
- proof-techniques — proof by contradiction, the shape of the diagonal argument
- rational-and-irrational-numbers — \(\mathbb{Q}\) and \(\overline{\mathbb{Q}}\), on either side of the countable line
- 2026-09-14-cardinalities — Lecture 21 · 2026-09-15-countable-and-uncountable-sets — Lecture 22
- practice-problems — §28, with full worked solutions and the computability application