Lecture 22 — Countable and Uncountable Sets

lecture
discrete-math
set-theory
functions
cardinality
proof

Pre-work: Video 028 (Countable and Uncountable Sets). The reference notes are countable-and-uncountable-sets for the definitions and the big results, and cardinality for comparing sizes with injections and surjections and for the Schröder–Bernstein Theorem. The proof for infinite subsets of \(\mathbb{Z}^{+}\) is carried over from 2026-09-14-cardinalities.

Learning goals

  1. Understand countability and cardinalities of finite and infinite sets.
  2. Prove properties concerning countable and uncountable sets.

The whole topic in one line, with each stretch labelled:

\[|\emptyset| < |\{1,2,\dots,n\}| < |\mathbb{Z}^{+}| = |\mathbb{Z}| = |\mathbb{Q}| < |\mathbb{R}| < |\mathcal{P}(\mathbb{R})|\]

\(\lvert\emptyset\rvert\) \(\lvert\{1,2,\dots,n\}\rvert\) \(\lvert\mathbb{Z}^{+}\rvert = \lvert\mathbb{Z}\rvert = \lvert\mathbb{Q}\rvert\) \(\lvert\mathbb{R}\rvert\), \(\lvert\mathcal{P}(\mathbb{R})\rvert\)
label empty finite (and non-empty) countably infinite uncountable

The chain is drawn out, with every step explained, in countable-and-uncountable-sets.

Three questions to start with

Infinite subsets of \(\mathbb{Z}^{+}\)

Every infinite subset of \(\mathbb{Z}^{+}\) has the same cardinality as \(\mathbb{Z}^{+}\).

Proof. Let \(A = \{a_1, a_2, a_3, \dots\}\) be an infinite subset of \(\mathbb{Z}^{+}\) such that \(a_1 < a_2 < a_3 < \cdots\), that is, let \(a_1\) be the least element of \(A\), let \(a_2\) be the least element of \(A - \{a_1\}\), let \(a_3\) be the least element of \(A - \{a_1, a_2\}\), …and so on…

Define \(f : \mathbb{Z}^{+} \to A\) where \(f(i) = a_i\).

  • Then \(f\) is a function since it maps each positive integer (element of the domain) to a unique element of \(A\) (the co-domain).
  • Suppose \(f(i) = f(j)\) for positive integers \(i\) and \(j\). Then \(a_i = a_j\) but the elements of the set \(A\) are all different so this means \(i = j\). Thus, \(f\) is one-to-one.
  • For each \(a_j \in A\), we have \(j \in \mathbb{Z}^{+}\) and \(f(j) = a_j\) so \(f\) is onto.

Therefore, \(f\) is a bijection, and hence \(|\mathbb{Z}^{+}| = |A|\).

The three bullets are the three parts of the \(|X| = |Y|\) template: a function, one-to-one, onto. The set-up rests on:

The Well-Ordering Principle for the integers: If \(S\) is a non-empty set of integers all of which are greater than some fixed integer, then \(S\) has a least element.

The onto bullet leans on something the set-up does not say out loud: that every element of \(A\) is one of the \(a_j\). An infinite set could in principle have elements the “and so on” never reaches. It cannot happen here. An element \(a \in A\) has fewer than \(a\) elements of \(A\) below it (they are positive integers less than \(a\)), so after at most \(a - 1\) steps \(a\) is the least element left, and it is picked. That is one of two places \(A \subseteq \mathbb{Z}^{+}\) is used. The other is the well-ordering step. Each \(A - \{a_1, \dots, a_{i-1}\}\) is a set of positive integers, non-empty because \(A\) is infinite, so the Well-Ordering Principle gives it a least element. That step is where the same construction on \(\mathbb{Q}^{+}\) itself fails, since there is no least positive rational.

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.

Countable is an or: finite, or \(|X| = |\mathbb{Z}^{+}|\). It includes every finite set, and “countably infinite” is the name for the second case alone.

Worked: the set of terms of a sequence. If \(x_1, x_2, x_3, \dots\) is any infinite sequence, then \(\{x_1, x_2, x_3, \dots\}\) is:

(A) finite (B) infinite (C) countable (D) uncountable (E) countably infinite
✗ ✗ \(\checkmark\) ✗ ✗

One sequence for each way it can go:

  • \(2, 4, 6, 8, \dots\) gives \(\{2, 4, 6, \dots\} = 2\mathbb{Z}^{+}\), which is infinite;
  • \(1, 0, 1, 0, 1, 0, 1, 0, \dots\) gives \(\{0, 1\}\), which is finite.

An infinite sequence can have a finite set of terms, because a sequence may repeat and a set forgets repeats. That rules out (A), (B) and (E) as “always” answers. What always holds is (C). The terms are listed by the sequence itself, so the set is either finite or can be listed without repeats by dropping the duplicates. Comparing sizes puts it in one line, since \(i \mapsto x_i\) is onto the set.

Countable sets, and lists

\(\mathbb{Z}^{+}\), \(2\mathbb{Z}\), \(\mathbb{Z}\), \(\mathbb{Q}^{+}\), \(\mathbb{Q}\) and \(\mathbb{Z} \times \mathbb{Z}\) are all countable.

\(X\) is countably infinite if and only if the elements of \(X\) can be written as an infinite list. That is, \(X = \{x_1, x_2, x_3, \dots\}\), where the \(x_i\) are all distinct.

The two directions:

  • If \(X = \{x_1, x_2, \dots\}\), then \(f(i) = x_i\) is a bijection \(f : \mathbb{Z}^{+} \to X\).
  • If \(f : \mathbb{Z}^{+} \to X\) is a bijection, then we let \(x_i = f(i)\) and we have \(X = \{x_1, x_2, \dots\}\).

A list is a bijection from \(\mathbb{Z}^{+}\): position \(i\) holds \(x_i\). Write \(\mathbb{Z}^{+}\) (\(1\ 2\ 3\ 4\ \cdots\)) above \(X\) (\(x_1\ x_2\ x_3\ x_4\ \cdots\)) and join each \(i\) straight down to \(x_i\). Those joins are the bijection \(f : \mathbb{Z}^{+} \to X\). Distinct is what makes the list one-to-one, and “every element appears somewhere” is what makes it onto.

Theorem: Any subset of a countable set is countable.

Corollary: Any set with an uncountable subset is uncountable.

Examples \(\mathbb{R}\) and \(\mathcal{P}(\mathbb{Z}^{+})\) are examples of uncountable sets. \(\mathbb{R}\) and \(\mathcal{P}(\mathbb{Z}^{+})\) are infinite, \(|\mathbb{R}| \neq |\mathbb{Z}^{+}|\), \(|\mathcal{P}(\mathbb{Z}^{+})| \neq |\mathbb{Z}^{+}|\).

The corollary is the theorem’s contrapositive, since “countable” and “uncountable” are negations of each other. The theorem generalises the result for infinite subsets of \(\mathbb{Z}^{+}\). List the big set, keep the members of the subset in the order they appear, and skip the rest. What is left is still a list, possibly finite. That \(\mathcal{P}(\mathbb{Z}^{+})\) is uncountable is stated without proof.

Quick overview of the proof that \(\mathbb{R}\) is uncountable

This proof is not assessed.

The proof shows that the interval \((0,1) = \{x \in \mathbb{R} \mid 0 < x < 1\}\) is uncountable. It is a proof by contradiction. Assume \((0,1)\) is countable. Then the elements of \((0,1)\) can be written in a list.

1st 2nd 3rd 4th 5th 6th 7th
1 → 0. 3 6 6 7 8 1 2 …
2 → 0. 4 5 4 0 9 9 2 …
3 → 0. 2 4 5 6 8 9 2 …
0. 3 3 3 3 3 3 5 …
0. 1 1 1 1 1 1 7 …
0. 5 6 8 7 4 4 7 …
0. 3 4 1 0 0 4 1 …
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮

The bold digit in each row is on the diagonal. Make a real number \(d\) that differs from every other number in the list, by changing each diagonal digit. Where the diagonal digit is not 1 (the 3, 5, 5, 3 and 4) it becomes a 1. Where the diagonal digit is 1 it becomes a 2.

\[0.\,3\,5\,5\,3\,1\,4\,1\,\dots \quad\longrightarrow\quad 0.\,1\,1\,1\,1\,2\,1\,2\,\dots\]

The number on the right is \(d\). It is not in the list. Contradiction. So \((0,1)\) is uncountable.

\((0,1) \subseteq \mathbb{R}\), and any set with an uncountable subset is uncountable. This proves that \(\mathbb{R}\) is uncountable.

Figure 1: The diagonal argument on the first seven numbers of a supposed list of \((0,1)\). The shaded cells are the diagonal: the first digit of the first number, the second digit of the second, and so on. The new number \(d\) is built one decimal place at a time by changing the diagonal digit: 1 if that digit is not 1, and 2 if it is. So \(d\) differs from the \(n\)-th number in the \(n\)-th place, for every \(n\), and cannot be anywhere in the list. Whatever list is proposed, \(d\) is missing from it, so no list of \((0,1)\) exists.

Two remarks. Why \(d\) uses only 1s and 2s. Some real numbers have two decimal names, \(0.1999\ldots = 0.2000\ldots\). A \(d\) built from 0s and 9s might be a second name for a number that is in the list. A \(d\) using only the digits 1 and 2 has just the one decimal name, so “differs in some digit” really does mean “is a different number”. Why the proof is by contradiction. “Uncountable” means no bijection from \(\mathbb{Z}^{+}\) exists, a statement about every possible list. Assuming one list and producing a missing number from it disposes of every list at once, the pattern of proof-techniques.

In fact \(|(0,1)| = |\mathbb{R}|\). Take \((0,1)\) as a segment with open ends and bend it into a circle resting on the real line. A line from the top of the circle through a point on it carries on down to a point of the real line. That is a bijection between the open interval and the whole real line, drawn in countable-and-uncountable-sets.

Worked: a short interval and a long one

Prove that if \(A = [0,1]\) and \(B = [6,9]\), then \(|A| = |B|\). Recall that for \(a, b \in \mathbb{R}\), \([a,b] = \{x \in \mathbb{R} : a \leq x \leq b\}\).

The bijection between \([0,1]\) and \([6,9]\) is a projection. Lines fan out from a point \(c\), cross the short segment \(0\) to \(1\) and hit the long segment \(6\) to \(9\). For a formula, use \(y = mx + c\): the line through \((0,6)\) and \((1,9)\) is \(y = 3x + 6\). The proof has the three parts of the \(|X| = |Y|\) template.

It is a function from \(A\) to \(B\). Let \(f : A \to B\) be defined by \(f(x) = 3x + 6\). Since \(x \in A\) is a real number, \(3x + 6 \in \mathbb{R}\) and is unique. Since \(0 \leq x \leq 1\) we have \(3(0) + 6 \leq f(x) \leq 3(1) + 6\), that is, \(6 \leq f(x) \leq 9\). So \(f\) is indeed a function from \(A\) to \(B\).

One-to-one. Suppose \(x_1, x_2 \in A\) with \(f(x_1) = f(x_2)\). Then \(3x_1 + 6 = 3x_2 + 6\), \(3x_1 = 3x_2\), \(x_1 = x_2\). \(\therefore f\) is one-to-one.

Onto. Suppose \(y \in B = [6,9]\). Consider \(x = \frac{y-6}{3} \in \mathbb{R}\). Since \(y \geq 6\) we have \(x \geq \frac{6-6}{3} = 0\). Since \(y \leq 9\) we have \(x \leq \frac{9-6}{3} = 1\). \(\therefore x \in A\), and \[f\!\left(\frac{y-6}{3}\right) = 3\left(\frac{y-6}{3}\right) + 6 = y - 6 + 6 = y. \qquad \therefore f \text{ is onto.}\]

\(\therefore |A| = |B|\). The \(x\) in the onto part comes from solving backwards: \(y = 3x + 6\), so \(\frac{y-6}{3} = x\).

As in 2026-09-14-cardinalities, the range checks are the part to get right. \(6 \leq f(x) \leq 9\) is what makes \(f\) a function into \(B\), and \(0 \leq x \leq 1\) is what puts the candidate preimage in \(A\).

Figure 2: A bijection between \([0,1]\) and \([6,9]\) by projection. Every ray from \(c\) crosses the short segment once and the long segment once, so it pairs one point of each: nothing is missed and nothing is shared. Because the segments are parallel, the long one is three times the length, and the end rays pair 0 with 6 and 1 with 9, the ray through \(x\) lands at \(3x + 6\) — the formula in the proof is this picture. A longer segment does not have more points.

Definition of \(|A| \geq |B|\) and the Schröder–Bernstein Theorem

For any sets \(A\) and \(B\):

\(|A| \leq |B| \leftrightarrow \exists\) injective \(f : A \to B\). \(\qquad\) \(|A| \geq |B| \leftrightarrow \exists\) surjective \(f : A \to B\).

\(|A| < |B| \leftrightarrow \exists\) injective \(f : A \to B\) but \(\nexists\) bijective \(f : A \to B\).

\(|A| > |B| \leftrightarrow \exists\) surjective \(f : A \to B\) but \(\nexists\) bijective \(f : A \to B\).

There is no guarantee that the injection for \(|A| \leq |B|\) and the surjection for \(|A| \geq |B|\) are the same function.

The Schröder–Bernstein Theorem. For all sets \(A\) and \(B\), if \(|A| \leq |B|\) and \(|A| \geq |B|\), then \(|A| = |B|\).

To show \(|A| = |B|\), instead of finding a bijection from \(A\) to \(B\), you can find a function that shows \(|A| \leq |B|\) and a different function that shows \(|B| \leq |A|\).

The theorem is on the course formula sheet (formula-sheet). It is not obvious. It says two one-way comparisons, made with two unrelated functions, guarantee a two-way pairing that neither function need be. The course does not prove it, and it is used here as a tool. Cardinality sets out why the definitions are the natural ones.

Pre-class quiz questions

Q2. If \(X\) and \(Y\) are sets such that \(|X| \leq |Y|\), then

Answer
(a) there is a bijective function \(f : X \to Y\). No. Might have \(\lvert X\rvert < \lvert Y\rvert\).
(b) there is no bijective function \(f : X \to Y\). No. Might have \(\lvert X\rvert = \lvert Y\rvert\).
(c) there is an injective function \(f : X \to Y\). Yes. Works if \(\lvert X\rvert < \lvert Y\rvert\) and if \(\lvert X\rvert = \lvert Y\rvert\).
(d) there is a surjective function \(f : X \to Y\). No. Might have \(\lvert X\rvert < \lvert Y\rvert\).

Q3. To show that \(|X| = |Y|\) it is sufficient to show that

Answer
(a) there is an injective function \(f : X \to Y\). No. This shows \(\lvert X\rvert \leq \lvert Y\rvert\) but might have \(\lvert X\rvert < \lvert Y\rvert\).
(b) there is a surjective function \(f : X \to Y\). No. This shows \(\lvert X\rvert \geq \lvert Y\rvert\) but might have \(\lvert X\rvert > \lvert Y\rvert\).
(c) there is an injective function \(f : X \to Y\) and there is a surjective function \(g : X \to Y\). Yes. This shows \(\lvert X\rvert \leq \lvert Y\rvert\) and \(\lvert X\rvert \geq \lvert Y\rvert\), so \(\lvert X\rvert = \lvert Y\rvert\).
(d) there is an injective function \(f : X \to Y\) and there is a surjective function \(g : Y \to X\). No. This shows \(\lvert X\rvert \leq \lvert Y\rvert\) and \(\lvert Y\rvert \geq \lvert X\rvert\), so might have \(\lvert X\rvert < \lvert Y\rvert\).
(e) none of the above is sufficient.

In Q3 the surjection is \(g : X \to Y\) in (c) and \(g : Y \to X\) in (d). That one arrow is the whole difference between (c) and (d). A surjection \(Y \to X\) gives \(|Y| \geq |X|\), which is the same fact as the injection already gave, so (d) says one thing twice.

Worked: a closed interval and an open one

Prove that if \(A = [0,1]\) and \(B = (6,9)\), then \(|A| = |B|\). Recall that for \(a, b \in \mathbb{R}\), \([a,b] = \{x \in \mathbb{R} : a \leq x \leq b\}\), \((a,b) = \{x \in \mathbb{R} : a < x < b\}\).

The projection that worked for the short interval and the long one now fails. The endpoints \(0\) and \(1\) are in \(A\), and they would have to go to \(6\) and \(9\), which are not in \(B\). So the proof goes in two halves and never finds the bijection.

Show \(|A| \leq |B|\). Define \(f : A \to B\) by \(f(x) = x + 7\). If \(x \in [0,1]\) then \(x + 7 \in [7,8] \subseteq (6,9)\), so \(f\) is indeed a function from \(A\) to \(B\). Suppose \(x_1, x_2 \in [0,1]\) and \(f(x_1) = f(x_2)\); then \(x_1 + 7 = x_2 + 7\), so \(x_1 = x_2\). \(\therefore f\) is one-to-one, \(\therefore |A| \leq |B|\).

Show \(|B| \leq |A|\). Define \(g : B \to A\) by \(g(x) = \frac{x}{9}\). If \(x \in (6,9)\) then \(\frac{6}{9} < \frac{x}{9} < \frac{9}{9}\), i.e. \(g(x) \in \left(\frac{2}{3}, 1\right) \subseteq [0,1]\). Suppose \(x_1, x_2 \in (6,9)\) and \(g(x_1) = g(x_2)\); so \(\frac{x_1}{9} = \frac{x_2}{9}\), so \(x_1 = x_2\). \(\therefore g\) is one-to-one, \(\therefore |B| \leq |A|\).

\(\therefore\) By SBT \(|A| = |B|\).

Figure 3: The two injections between \(A = [0,1]\) and \(B = (6,9)\), each interval drawn at its own scale. \(f(x) = x + 7\) sends the closed interval \([0,1]\) into \((6,9)\), landing on the green band \([7,8]\). \(g(x) = x/9\) sends the open interval \((6,9)\) into \([0,1]\), landing on the purple band \((\frac{2}{3}, 1)\). Neither is onto, so neither is a bijection. Together they show \(|A| \leq |B|\) and \(|B| \leq |A|\), and the Schröder–Bernstein Theorem then guarantees that a bijection exists, without anyone having to find it.

This is how the theorem is applied. Schröder–Bernstein is for when a bijection is awkward to write down but injections both ways are easy. An injection only has to fit one set inside the other without collisions. There is no need to cover every point, and no need to worry about which endpoints are open. A bijection from \([0,1]\) to \((6,9)\) does exist, but it has to do something awkward at the endpoints. One way: send \(0 \mapsto \frac12\), \(1 \mapsto \frac13\) and \(\frac1n \mapsto \frac1{n+2}\) for \(n \geq 2\), fix every other point, and then apply \(x \mapsto 3x + 6\). The first step is a bijection from \([0,1]\) to \((0,1)\): the sequence \(\frac12, \frac13, \frac14, \dots\) moves two places along to make room for the endpoints, the Hilbert’s Hotel trick. That construction is not needed for the course.

Worked: \(\mathbb{Z}^{+} \times \mathbb{Z}^{+}\) is countable

(a) Show that the function \(f : \mathbb{Z}^{+} \times \mathbb{Z}^{+} \to \mathbb{Z}^{+}\) defined by \(f((a,b)) = 2^a \cdot 4^b\) is not one-to-one.

Consider \((3,1)\) and \((1,2)\) in \(\mathbb{Z}^{+} \times \mathbb{Z}^{+}\). \(f((3,1)) = 2^3 \cdot 4^1 = 32\) and \(f((1,2)) = 2^1 \cdot 4^2 = 32\), so \(f((3,1)) = f((1,2))\) but \((3,1) \neq (1,2)\), so \(f\) is not one-to-one.

(b) Show that the function \(f : \mathbb{Z}^{+} \times \mathbb{Z}^{+} \to \mathbb{Z}^{+}\) defined by \(f((a,b)) = 3^a \cdot 5^b\) is one-to-one.

Let \((a,b), (c,d) \in \mathbb{Z}^{+} \times \mathbb{Z}^{+}\) and suppose \(f((a,b)) = f((c,d))\). Then \(3^a 5^b = 3^c 5^d\). By the unique prime factorisation theorem, we have \(a = c\) and \(b = d\). Hence \((a,b) = (c,d)\). So \(f\) is one-to-one.

Figure 4: Why \(2^a \cdot 4^b\) collides and \(3^a \cdot 5^b\) does not, on the pairs with \(a \leq 5\) and \(b \leq 3\). Left: \(2^a 4^b = 2^{a+2b}\) depends only on \(a + 2b\), so every pair on one dashed line gets the same value — \((3,1)\) and \((1,2)\) both give \(2^5 = 32\). Right: \(3^a 5^b\) keeps the two exponents on different primes, and unique factorisation reads both back off the product, so every pair gets its own value.

  1. is the negation of one-to-one, so it needs one witness pair. One way to find it is \(2^a \cdot 4^b = 2^{a + 2b}\): any two pairs with the same \(a + 2b\) collide. (b) is the universal statement, so it is a general argument from \(f((a,b)) = f((c,d))\), and the unique factorisation theorem does all the work. 4 is a power of 2, so both exponents land on the same prime, and that is the whole reason (a) fails.

(c) Show that the set \(\mathbb{Z}^{+} \times \mathbb{Z}^{+}\) is countable. (Hint: Find an injective function \(f : \mathbb{Z}^{+} \times \mathbb{Z}^{+} \to \mathbb{Z}^{+}\) and an injective function \(g : \mathbb{Z}^{+} \to \mathbb{Z}^{+} \times \mathbb{Z}^{+}\), and apply the Schröder–Bernstein Theorem.) — Not assessed

Proof. By part (b), we have an injective function from \(\mathbb{Z}^{+} \times \mathbb{Z}^{+}\) to \(\mathbb{Z}^{+}\), so \(|\mathbb{Z}^{+} \times \mathbb{Z}^{+}| \leq |\mathbb{Z}^{+}|\).

Consider \(g : \mathbb{Z}^{+} \to \mathbb{Z}^{+} \times \mathbb{Z}^{+}\) defined by \(g(n) = (n,1)\). We can see that \(g\) is a function since for every \(n \in \mathbb{Z}^{+}\) we have \((n,1) \in \mathbb{Z}^{+} \times \mathbb{Z}^{+}\) and each \(n \in \mathbb{Z}^{+}\) maps to a unique element of \(\mathbb{Z}^{+} \times \mathbb{Z}^{+}\).

Suppose \(n_1, n_2 \in \mathbb{Z}^{+}\) and \(g(n_1) = g(n_2)\). Then \((n_1, 1) = (n_2, 1)\) so \(n_1 = n_2\). Hence, \(g\) is injective, and so \(|\mathbb{Z}^{+}| \leq |\mathbb{Z}^{+} \times \mathbb{Z}^{+}|\).

Therefore, by the Schröder–Bernstein Theorem \(|\mathbb{Z}^{+}| = |\mathbb{Z}^{+} \times \mathbb{Z}^{+}|\).

The triple product \(\mathbb{Z}^{+} \times \mathbb{Z}^{+} \times \mathbb{Z}^{+}\) goes the same way with \((a,b,c) \mapsto 2^a 3^b 5^c\) and \(n \mapsto (n,1,1)\). Compare the spiral in 2026-09-14-cardinalities. That was a bijection that had to be drawn and checked; this is two one-line injections and a theorem.

What is assessed. Lecture 22 flags only the \(\mathbb{R}\)-is-uncountable proof and part (c) above as not assessed. The course practice set says of its whole §28 (countable and uncountable sets) that “this content will not be assessed in MATH1061”. The two draw the line in different places. Check with the course before relying on either.

See also