Countable sets · Computability Theory

A set is countable when its elements can be listed in a sequence indexed by integers. Countable sets are the natural setting of computation: inputs, outputs and programs are finite objects, and there are countably many of them. This lesson characterizes countable sets in several equivalent ways and shows that the sets built from integers by finite means — pairs, tuples, finite sequences, finite sets, rational and algebraic numbers — are all countable. The few uses of the axiom of choice are signaled explicitly.

3.1 Definition and characterizations

Definition 3.1.#

A set $A$ is countably infinite if $|A| = |\nat|$ . It is countable if it is finite or countably infinite, and uncountable otherwise.

A bijection $e : \nat \to A$ is an enumeration without repetition of $A$ , and is often written as a sequence $a_0, a_1, a_2, \dots$ with $a_n = e(n)$ . The basic fact behind all characterizations is that the subsets of $\nat$ are countable.

Lemma 3.2.#

Every infinite set $S \subseteq \nat$ is countably infinite. More precisely, the principal function $p_S : \nat \to S$ defined by

p_S(0) = \min S, \qquad p_S(n+1) = \min \{ s \in S : s > p_S(n) \}

is a strictly increasing bijection, which enumerates $S$ in increasing order.

Proof of Lemma 3.2.

The minima exist. Indeed $S \neq \emptyset$ ; and if $S$ had no element greater than $p_S(n)$ , then $S \subseteq \underline{p_S(n) + 1}$ would be finite, as a subset of a finite set (Exercise 1.15). By construction $p_S$ is strictly increasing, hence injective, and by induction $p_S(n) \geq n$ for all $n$ .

For surjectivity, let $s \in S$ . The values $p_S(0) < p_S(1) < \dots$ are unbounded since $p_S(n) \geq n$ , so there is a least $n$ with $p_S(n) \geq s$ . If $n = 0$ , then $s \geq \min S = p_S(0)$ gives $s = p_S(0)$ . If $n > 0$ , then $p_S(n-1) < s \leq p_S(n)$ , and $p_S(n)$ is by definition the least element of $S$ above $p_S(n-1)$ , so $p_S(n) \leq s$ , hence $s = p_S(n)$ .

Proposition 3.3.#

For every set $A$ , the following are equivalent.

$A$ is countable.
$|A| \leq |\nat|$ : there is an injection from $A$ into $\nat$ .
$A = \emptyset$ , or there is a surjection from $\nat$ onto $A$ .

Proof of Proposition 3.3.

(1 ⇒ 2) A bijection with $\underline n \subseteq \nat$ or with $\nat$ is an injection into $\nat$ .

(2 ⇒ 3) Suppose $A \neq \emptyset$ , fix $a_0 \in A$ , and let $i : A \to \nat$ be an injection. Define $s : \nat \to A$ by $s(n) = a$ if $n = i(a)$ , which determines $a$ uniquely, and $s(n) = a_0$ if $n \notin i(A)$ . Then $s(i(a)) = a$ for every $a$ , so $s$ is surjective.

(3 ⇒ 2) The empty set injects into $\nat$ . If $s : \nat \to A$ is surjective, then $|A| \leq |\nat|$ by Proposition 1.13: the injection sends $a$ to the least $n$ with $s(n) = a$ .

(2 ⇒ 1) If $i : A \to \nat$ is injective, then $A$ is equipotent to $S = i(A) \subseteq \nat$ . If $S$ is finite, so is $A$ . Otherwise $S$ is countably infinite by Lemma 3.2, and so is $A$ .

Characterization 3 is the one used most often: a non-empty set is countable when it can be listed as $a_0, a_1, a_2, \dots$ , repetitions allowed. Removing the repetitions is done by the proof, by keeping only the first occurrence of each element.

Corollary 3.4.#

Every subset of a countable set is countable.
The image of a countable set under any function is countable.

Proof of Corollary 3.4.

If $B \subseteq A$ and $i : A \to \nat$ is injective, the restriction of $i$ to $B$ is injective.
Let $f$ be a function defined on a countable set $A$ . If $A = \emptyset$ , then $f(A) = \emptyset$ . Otherwise, if $s : \nat \to A$ is surjective, then $f \circ s$ is a surjection from $\nat$ onto $f(A)$ .

3.2 The smallest infinity

Proposition 3.5.#

Every infinite set $A$ satisfies $|\nat| \leq |A|$ .

Proof of Proposition 3.5.

We define an injection $a : \nat \to A$ by induction. Pick $a_0 \in A$ , which exists since $\emptyset$ is finite. Having chosen pairwise distinct $a_0, \dots, a_n$ , the set $\{a_0, \dots, a_n\}$ is finite, so it is not $A$ ; pick $a_{n+1} \in A \setminus \{a_0, \dots, a_n\}$ . The elements $a_n$ are pairwise distinct by construction.

This proof makes infinitely many arbitrary choices, one at each step, each depending on the previous ones. It uses the axiom of dependent choice, a weak form of the axiom of choice, and cannot be carried out in ZF alone: it is consistent with ZF that some infinite set of real numbers has no countably infinite subset (we admit this result of Cohen; a proof is in Jech’s monograph on the axiom of choice). When $A$ comes with an injection into $\nat$ or with a linear order in which every non-empty subset has a least element, one can take $a_{n+1}$ to be the least element of $A \setminus \{a_0, \dots, a_n\}$ , and no choice is needed; this is what Lemma 3.2 does.

Corollary 3.6.#

An infinite set is countable if and only if it is equipotent to each of its infinite subsets.

Proof of Corollary 3.6.

If $A$ is countably infinite and $B \subseteq A$ is infinite, then $B$ is countable by Corollary 3.4, and infinite, so $|B| = |\nat| = |A|$ . Conversely, if $A$ is infinite and equipotent to each of its infinite subsets, then by Proposition 3.5 it has a subset $a(\nat)$ equipotent to $\nat$ , and $|A| = |a(\nat)| = |\nat|$ .

3.3 Pairs and tuples

Proposition 3.7.#

The set $\nat \times \nat$ is countably infinite. An explicit bijection is Cantor’s pairing function

\langle x, y \rangle = \frac{(x+y)(x+y+1)}{2} + y.

The pairs

(x, y)

with

x + y \leq 4

, labeled by

\langle x, y \rangle

. The enumeration follows each diagonal upwards, then jumps to the next diagonal.

Proof of Proposition 3.7.

List the pairs diagonal by diagonal: first those with $x + y = 0$ , then those with $x + y = 1$ , and so on, each diagonal in order of increasing $y$ :

(0,0),\ (1,0),\ (0,1),\ (2,0),\ (1,1),\ (0,2),\ (3,0),\ \dots

The diagonal $x + y = k$ contains the $k + 1$ pairs $(k, 0), (k-1, 1), \dots, (0, k)$ , so the diagonals before it contain $1 + 2 + \dots + k = k(k+1)/2$ pairs, and $(x, y)$ is at position $k(k+1)/2 + y$ with $k = x + y$ . Every pair lies on exactly one diagonal and appears once on it, so the listing is a bijection between $\nat \times \nat$ and $\nat$ , and the position of $(x, y)$ is $\langle x, y \rangle$ .

The function and its inverses are studied as computable functions in the course on models of computation (Proposition 1.4 of “Algorithms and partial functions”).

Corollary 3.8.#

If $A$ and $B$ are countable, so is $A \times B$ .
For every $k \geq 1$ , $\nat^k$ is countably infinite.

Proof of Corollary 3.8.

If $i : A \to \nat$ and $j : B \to \nat$ are injections, then $(a, b) \mapsto \langle i(a), j(b) \rangle$ is an injection of $A \times B$ into $\nat$ .
By induction on $k$ , identifying $\nat^{k+1}$ with $\nat^k \times \nat$ ; the set is infinite since $\nat$ injects into it.

Explicitly, a bijection $\nat^k \to \nat$ is obtained by iterating the pairing function: $\langle x_1, \dots, x_{k+1} \rangle = \langle \langle x_1, \dots, x_k \rangle, x_{k+1} \rangle$ .

Example 3.9.#

$\mathbb Z$ is countably infinite: $z \mapsto 2z$ for $z \geq 0$ and $z \mapsto -2z - 1$ for $z < 0$ is a bijection $\mathbb Z \to \nat$ .
$\mathbb Q$ is countably infinite. The map $(p, q) \mapsto p/(q+1)$ is a surjection from $\mathbb Z \times \nat$ , a countable set by the corollary, onto $\mathbb Q$ , so $\mathbb Q$ is countable by Corollary 3.4; it is infinite since it contains $\nat$ .

3.4 Unions

Proposition 3.10.#

Let $(A_n)_{n \in \nat}$ be a sequence of sets, and let $(s_n)_{n \in \nat}$ be a sequence of functions such that each $s_n : \nat \to A_n$ is surjective. Then $\bigcup_n A_n$ is countable. In particular, a finite union of countable sets is countable.

Proof of Proposition 3.10.

The map $\langle n, m \rangle \mapsto s_n(m)$ is a surjection from $\nat$ onto $\bigcup_n A_n$ : every element of $A_n$ is some $s_n(m)$ . For a finite union $A_0 \cup \dots \cup A_k$ of non-empty countable sets, fix surjections $s_0, \dots, s_k$ and let $A_n = A_k$ and $s_n = s_k$ for $n > k$ , which does not change the union; the empty sets can be discarded beforehand.

The hypothesis provides the enumerations $s_n$ along with the sets. The statement “a countable union of countable sets is countable”, without given enumerations, requires choosing one enumeration of each $A_n$ among infinitely many possibilities. It is a consequence of the axiom of countable choice, and it is not provable in ZF: Feferman and Lévy showed that it is consistent with ZF that $\mathbb R$ is a countable union of countable sets. We admit this result. In practice, as in the examples below, the sets come with natural enumerations, and the proposition applies directly.

3.5 Finite strings and finite sets

An alphabet is a set $\Sigma$ , whose elements are called letters. A string of length $k$ over $\Sigma$ is a finite sequence $w = a_1 a_2 \cdots a_k$ of letters, that is, a function $\{1, \dots, k\} \to \Sigma$ ; the string of length $0$ is the empty string $\varepsilon$ . The set of strings over $\Sigma$ is written $\Sigma^*$ .

Proposition 3.11.#

If $\Sigma$ is countable, then $\Sigma^*$ is countable. It is countably infinite if $\Sigma \neq \emptyset$ .

Proof of Proposition 3.11.

Let $i : \Sigma \to \nat$ be an injection, and $p_1 = 2, p_2 = 3, p_3 = 5, \dots$ the primes. The map

a_1 a_2 \cdots a_k \;\mapsto\; p_1^{\,i(a_1) + 1}\, p_2^{\,i(a_2) + 1} \cdots p_k^{\,i(a_k) + 1}

sends $\varepsilon$ to $1$ and is injective by uniqueness of prime factorization: the code determines $k$ , as the number of its distinct prime factors, and each $i(a_j)$ , hence each $a_j$ . If $a \in \Sigma$ , the strings $a, aa, aaa, \dots$ are pairwise distinct, so $\Sigma^*$ is infinite.

The exponents are shifted by one so that the code determines the length: without the shift, strings of letters $a$ with $i(a) = 0$ would all be coded by $1$ .

Corollary 3.12.#

The set $\mathcal P_{\mathrm{fin}}(\nat)$ of finite subsets of $\nat$ is countably infinite. An explicit bijection with $\nat$ is $F \mapsto \sum_{n \in F} 2^n$ .

Proof of Corollary 3.12.

Every integer has a unique binary expansion, and a finite set $F$ is exactly the set of positions of the digits $1$ in the binary expansion of $\sum_{n \in F} 2^n$ .

Example 3.13.#

A real number is algebraic if it is a root of a non-zero polynomial with integer coefficients. The set of real algebraic numbers is countable. Indeed, a polynomial $c_0 + c_1 X + \dots + c_d X^d$ is determined by the string $c_0 c_1 \cdots c_d$ over the countable alphabet $\mathbb Z$ , so there is a surjection $n \mapsto P_n$ from $\nat$ onto the non-zero polynomials, by Proposition 3.11. A non-zero polynomial $P_n$ has at most $\deg P_n$ real roots; list them in increasing order as $r_{n,0} < \dots < r_{n,k-1}$ , and let $r_{n,m} = r_{n,k-1}$ for $m \geq k$ (if $P_n$ has no real root, let $r_{n,m} = 0$ , which is algebraic). Then $\langle n, m \rangle \mapsto r_{n,m}$ is a surjection onto the real algebraic numbers. The ordering of the roots replaces an arbitrary choice of enumeration of each finite set of roots.

The computational consequence of Proposition 3.11 is the starting point of the last lesson: programs, in any programming language, are strings over a finite alphabet, so there are countably many of them, and countably many computable functions.

3.6 Exercises

Exercise 3.14 ★.

Let $s : \nat \to A$ be a surjection onto an infinite set $A$ . Construct an explicit bijection between $\nat$ and $A$ , without appealing to Proposition 3.5.

Solution

Let $S = \{ n : s(n) \neq s(m) \text{ for all } m < n \}$ be the set of positions of first occurrences. The restriction of $s$ to $S$ is a bijection from $S$ onto $A$ : it is surjective, since each $a \in A$ has a least $n$ with $s(n) = a$ , and this $n$ is in $S$ ; it is injective, since two first occurrences of the same element would be equal. $S$ is infinite since $A$ is. So $s \circ p_S : \nat \to A$ is a bijection, where $p_S$ is the principal function of Lemma 3.2.

Exercise 3.15 ★.

Show that the set of eventually periodic sequences $X : \nat \to \{0, 1\}$ is countable. (A sequence is eventually periodic if there are $n_0$ and $p \geq 1$ such that $X(n + p) = X(n)$ for all $n \geq n_0$ .)

Solution

An eventually periodic sequence is determined by two strings $u$ and $v$ over $\{0, 1\}$ , with $v$ non-empty: its first $n_0$ values $u$ , followed by $v$ repeated forever. So there is a surjection from a subset of $\{0, 1\}^* \times \{0, 1\}^*$ , which is countable by Proposition 3.11 and Corollary 3.8, onto the set of eventually periodic sequences, which is therefore countable by Corollary 3.4.

Exercise 3.16 ★★.#

Show that a set $A$ is infinite if and only if it is equipotent to a proper subset of itself. Which direction uses the axiom of choice?

Solution

If $A$ is finite, it is not equipotent to a proper subset, by Corollary 1.10. Conversely, if $A$ is infinite, let $a : \nat \to A$ be an injection, given by Proposition 3.5. The map $h$ defined by $h(a_n) = a_{n+1}$ and $h(x) = x$ for $x \notin a(\nat)$ is a bijection from $A$ onto $A \setminus \{a_0\}$ . Only the second direction uses choice, through Proposition 3.5.

Exercise 3.17 ★★.

A real number is transcendental if it is not algebraic. Show that every non-empty open interval contains a transcendental number, admitting that intervals are uncountable (this is proved in the next lessons).

Solution

An open interval $(a, b)$ with $a < b$ is uncountable, while the algebraic numbers form a countable set by Example 3.13. If $(a, b)$ contained only algebraic numbers, it would be countable, by Corollary 3.4.

3.7 Notes and references

The countability of the algebraic numbers is the first result of Cantor’s paper of 1874, which also proves, by a different argument than the diagonal one, that the real numbers are not countable; together, the two results give a new proof of the existence of transcendental numbers, first established by Liouville in 1844. The consistency of ” $\mathbb R$ is a countable union of countable sets” with ZF is due to Feferman and Lévy (1963); a proof is in Jech’s monograph on the axiom of choice.

G. Cantor, Über eine Eigenschaft des Inbegriffes aller reellen algebraischen Zahlen, Journal für die reine und angewandte Mathematik 77 (1874), 258–262.
T. Jech, The Axiom of Choice, North-Holland, 1973.
K. Hrbacek and T. Jech, Introduction to Set Theory, 3rd edition, Marcel Dekker, 1999.