The Size of Sets

Reading preferences

Optional display controls need JavaScript. All reading content and navigation work without it.

How to use Read

This page follows the source chapter in ordinary reading order. Equations remain native MathML so compatible screen readers and braille systems can navigate their internal structure. Each small source link returns to the exact source line.

Introduction

When Georg Cantor developed set theory in the 1870s, one of his aims was to make palatable the idea of an infinite collection—an actual infinity, as the medievals would say. A key part of this was his treatment of the size of different sets. If $a$ source 16, $b$ source 16 and $c$ source 16 are all distinct, then the set ${a, b, c}$ source 17 is intuitively larger than ${a, b}$ source 18. But what about infinite sets? Are they all as large as each other? It turns out that they are not.

The first important idea here is that of an enumeration. We can list every finite set by listing all its elements. For some infinite sets, we can also list all their elements if we allow the list itself to be infinite. Such sets are called enumerable. Cantor's surprising result, which we will fully understand by the end of this chapter, was that some infinite sets are not enumerable.

Enumerations and Enumerable Sets

Definition: Informal enumeration

Informally, an enumeration of a set $A$ source 28 is a list (possibly infinite) of elements of $A$ source 29 such that every element of $A$ source 29 appears on the list at some finite position. If $A$ source 30 has an enumeration, then $A$ source 31 is said to be enumerable.

source 27

Explanation

A couple of points about enumerations:

We count as enumerations only lists which have a beginning and in which every element other than the first has a single element immediately preceding it. In other words, there are only finitely many elements between the first element of the list and any other element. In particular, this means that every element of an enumeration has a finite position: the first element has position $1$ source 43, the second position $2$ source 43, etc.
We can have different enumerations of the same set $A$ source 44 which differ by the order in which the elements appear: $4$ source 45, $1$ source 45, $25$ source 46, $16$ source 46, $9$ source 46 enumerates the (set of the) first five square numbers just as well as $1$ source 47, $4$ source 47, $9$ source 47, $16$ source 47, $25$ source 47 does.
Redundant enumerations are still enumerations: $1$ source 48, $1$ source 48, $2$ source 48, $2$ source 49, $3$ source 49, $3$ source 49, … enumerates the same set as $1$ source 49, $2$ source 49, $3$ source 50, … does.
Order and redundancy do matter when we specify an enumeration: we can enumerate the positive integers beginning with $1$ source 53, $2$ source 53, $3$ source 53, $1$ source 53, …, but the pattern is easier to see when enumerated in the standard way as $1$ source 54, $2$ source 54, $3$ source 54, $4$ source 54, …
Enumerations must have a beginning: …, $3$ source 55, $2$ source 55, $1$ source 55 is not an enumeration of the positive integers because it has no first element. To see how this follows from the informal definition, ask yourself, “at what position in the list does the number 76 appear?”
The following is not an enumeration of the positive integers: $1$ source 61, $3$ source 61, $5$ source 61, …, $2$ source 61, $4$ source 61, $6$ source 61, … The problem is that the even numbers occur at places $\infty + 1$ source 62, $\infty + 2$ source 62, $\infty + 3$ source 62, rather than at finite positions.
The empty set is enumerable: it is enumerated by the empty list!

Proposition: Removing repetitions from an enumeration

If $A$ source 69 has an enumeration, it has an enumeration without repetitions.

source 68

Proof

Suppose $A$ source 74 has an enumeration $x_{1}$ source 74, $x_{2}$ source 74, … in which each $x_{i}$ source 75 is an element of $A$ source 75. We can remove repetitions from an enumeration by removing repeated elements. For instance, we can turn the enumeration into a new one in which we list $x_{i}$ source 77 if it is a element of $A$ source 78 that is not among $x_{1}$ source 78, …, $x_{i - 1}$ source 79 or remove $x_{i}$ source 79 from the list if it already appears among $x_{1}$ source 80, …, $x_{i - 1}$ source 80.

End of proof.

The last argument shows that in order to get a good handle on enumerations and enumerable sets and to prove things about them, we need a more precise definition. The following provides it.

Definition: Enumeration as a surjection from the positive integers

An enumeration of a set $A \neq \emptyset$ source 88 is any surjective function $f : Z^{+} \to A$ source 89.

source 87

Explanation

Let's convince ourselves that the formal definition and the informal definition using a possibly infinite list are equivalent. First, any surjective function from $Z^{+}$ source 95 to a set $A$ source 95 enumerates $A$ source 95. Such a function determines an enumeration as defined informally above: the list $f (1)$ source 97, $f (2)$ source 97, $f (3)$ source 97, …. Since $f$ source 97 is surjective, every element of $A$ source 98 is guaranteed to be the value of $f (n)$ source 98 for some $n \in Z^{+}$ source 99. Hence, every element of $A$ source 99 appears at some finite position in the list. Since the function may not be injective, the list may be redundant, but that is acceptable (as noted above).

On the other hand, given a list that enumerates all elements of $A$ source 105, we can define a surjective function $f : Z^{+} \to A$ source 105 by letting $f (n)$ source 106 be the $n$ source 106th element of the list, or the final element of the list if there is no $n$ source 107th element. The only case where this does not produce a surjective function is when $A$ source 108 is empty, and hence the list is empty. So, every non-empty list determines a surjective function $f : Z^{+} \to A$ source 110.

Definition: Enumerable sets

A set $A$ source 115 is enumerable iff it is empty or has an enumeration.

source 113

Example: Enumerating the positive integers and natural numbers

A function enumerating the positive integers ( $Z^{+}$ source 119) is simply the identity function given by $f (n) = n$ source 120. A function enumerating the natural numbers $N$ source 121 is the function $g (n) = n - 1$ source 121.

source 118

Example: Enumerating positive even and odd integers

The functions $f : Z^{+} \to Z^{+}$ source 125 and $g : Z^{+} \to Z^{+}$ source 125 given by $\begin{matrix} f (n) & = 2 n and \\ g (n) & = 2 n - 1 \end{matrix}$ source 127 enumerate the even positive integers and the odd positive integers, respectively. However, neither function is an enumeration of $Z^{+}$ source 133, since neither is surjective.

source 124

Exercise: Enumerating the positive square numbers

Define an enumeration of the positive squares $1$ source 137, $4$ source 137, $9$ source 137, $16$ source 137, …

source 136

Example: Alternating enumeration of the integers from positive inputs

The function $f (n) = (- 1)^{n} ⌈ \frac{(n - 1)}{2} ⌉$ source 141 (where $⌈ x ⌉$ source 142 denotes the ceiling function, which rounds $x$ source 143 up to the nearest integer) enumerates the set of integers $Z$ source 144. Notice how $f$ source 144 generates the values of $Z$ source 144 by “hopping” back and forth between positive and negative integers: $\begin{array}{ccccccccccccccc} f (1) & f (2) & f (3) & f (4) & f (5) & f (6) & f (7) & \dots \\ - ⌈ \frac{0}{2} ⌉ & ⌈ \frac{1}{2} ⌉ & - ⌈ \frac{2}{2} ⌉ & ⌈ \frac{3}{2} ⌉ & - ⌈ \frac{4}{2} ⌉ & ⌈ \frac{5}{2} ⌉ & - ⌈ \frac{6}{2} ⌉ & \dots \\ 0 & 1 & - 1 & 2 & - 2 & 3 & \dots \end{array}$ source 146 You can also think of $f$ source 154 as defined by cases as follows: $f (n) = {\begin{matrix} 0 & if n = 1 \\ n / 2 & if n is even \\ - (n - 1) / 2 & if n is odd and > 1 \end{matrix}$ source 155

source 140

Exercise: Union of two enumerable sets using positive-integer enumerations

Show that if $A$ source 165 and $B$ source 165 are enumerable, so is $A \cup B$ source 165. To do this, suppose there are surjective functions $f : Z^{+} \to A$ source 166 and $g : Z^{+} \to B$ source 167, and define a surjective function $h : Z^{+} \to A \cup B$ source 168 and prove that it is surjective. Also consider the cases where $A$ source 169 or $B = \emptyset$ source 169.

source 164

Exercise: Enumerable subsets of enumerable sets

Show that if $B \subseteq A$ source 173 and $A$ source 173 is enumerable, so is $B$ source 173. To do this, suppose there is a surjective function $f : Z^{+} \to A$ source 174. Define a surjective function $g : Z^{+} \to B$ source 175 and prove that it is surjective. What happens if $B = \emptyset$ source 176?

source 172

Exercise: Finite unions of enumerable sets using induction

Show by induction on $n$ source 180 that if $A_{1}$ source 180, $A_{2}$ source 180, …, $A_{n}$ source 180 are all enumerable, so is $A_{1} \cup \dots \cup A_{n}$ source 181. You may assume the fact that if two sets $A$ source 182 and $B$ source 182 are enumerable, so is $A \cup B$ source 182.

source 179

Although it is perhaps more natural when listing the elements of a set to start counting from the $1$ source 187st element, mathematicians like to use the natural numbers $N$ source 188 for counting things. They talk about the $0$ source 189th, $1$ source 189st, $2$ source 189nd, and so on, elements of a list. Correspondingly, we can define an enumeration as a surjective function from $N$ source 191 to $A$ source 191. Of course, the two definitions are equivalent.

Proposition: Shifting enumerations between positive and natural indices

There is a surjection $f : Z^{+} \to A$ source 195 iff there is a surjection $g : N \to A$ source 196.

source 194

Proof

Given a surjection $f : Z^{+} \to A$ source 200, we can define $g (n) = f (n + 1)$ source 200 for all $n \in N$ source 201. It is easy to see that $g : N \to A$ source 201 is surjective. Conversely, given a surjection $g : N \to A$ source 202, define $f (n) = g (n - 1)$ source 203.

End of proof.

This gives us the following result:

Corollary: Enumerable sets via surjections from the natural numbers

A set $A$ source 209 is enumerable iff it is empty or there is a surjective function $f : N \to A$ source 210.

source 208

We discussed above that a list of elements of a set $A$ source 213 can be turned into a list without repetitions. This is also true for enumerations, but a bit harder to formulate and prove rigorously. Any function $f : Z^{+} \to A$ source 216 must be defined for all $n \in Z^{+}$ source 216. If there are only finitely many elements in $A$ source 217 then we clearly cannot have a function defined on the infinitely many elements of $Z^{+}$ source 219 that takes as values all the elements of $A$ source 220 but never takes the same value twice. In that case, i.e., in the case where the list without repetitions is finite, we must choose a different domain for $f$ source 222, one with only finitely many elements. Not having repetitions means that $f$ source 223 must be injective. Since it is also surjective, we are looking for a bijection between some finite set ${1, \dots, n}$ source 225 or $Z^{+}$ source 225 and $A$ source 225.

Proposition: Replacing a surjective enumeration by a bijective one

If $f : Z^{+} \to A$ source 228 is surjective (i.e., an enumeration of $A$ source 229), there is a bijection $g : Z \to A$ source 229 where $Z$ source 229 is either $Z^{+}$ source 230 or ${1, \dots, n}$ source 230 for some $n \in Z^{+}$ source 230.

source 227

Proof

We define the function $g$ source 234 recursively: Let $g (1) = f (1)$ source 234. If $g (i)$ source 234 has already been defined, let $g (i + 1)$ source 235 be the first value of $f (1)$ source 235, $f (2)$ source 236, … not already among $g (1)$ source 236, …, $g (i)$ source 236, if there is one. If $A$ source 237 has just $n$ source 237 elements, then $g (1)$ source 237, …, $g (n)$ source 237 are all defined, and so we have defined a function $g : {1, \dots, n} \to A$ source 238. If $A$ source 239 has infinitely many elements, then for any $i$ source 239 there must be a element of $A$ source 240 in the enumeration $f (1)$ source 240, $f (2)$ source 240, …, which is not already among $g (1)$ source 241, …, $g (i)$ source 241. In this case we have defined a function $g : Z^{+} \to A$ source 242.

The function $g$ source 244 is surjective, since any element of $A$ source 244 is among $f (1)$ source 245, $f (2)$ source 245, … (since $f$ source 245 is surjective) and so will eventually be a value of $g (i)$ source 246 for some $i$ source 246. It is also injective, since if there were $j < i$ source 247 such that $g (j) = g (i)$ source 247, then $g (i)$ source 248 would already be among $g (1)$ source 248, …, $g (i - 1)$ source 248, contrary to how we defined $g$ source 249.

End of proof.

Corollary: Enumerable sets via bijections from natural initial segments

A set $A$ source 253 is enumerable iff it is empty or there is a bijection $f : N \to A$ source 254 where either $N = N$ source 254 or $N = {0, \dots, n}$ source 254 for some $n \in N$ source 255.

source 252

Proof

$A$ source 259 is enumerable iff $A$ source 259 is empty or there is a surjective $f : Z^{+} \to A$ source 260. By Proposition: Replacing a surjective enumeration by a bijective one, the latter holds iff there is a bijective function $f : Z \to A$ source 261 where $Z = Z^{+}$ source 261 or $Z = {1, \dots, n}$ source 262 for some $n \in Z^{+}$ source 262. By the same argument as in the proof of Proposition: Shifting enumerations between positive and natural indices, that in turn is the case iff there is a bijection $g : N \to A$ source 264 where either $N = N$ source 265 or $N = {0, \dots, n - 1}$ source 265.

End of proof.

Exercise: Injective and surjective characterizations of enumerability

According to Definition: Enumerable sets, a set $A$ source 269 is enumerable iff $A = \emptyset$ source 270 or there is a surjective $f : Z^{+} \to A$ source 270. It is also possible to define “enumerable set” precisely by: a set is enumerable iff there is a injective function $g : A \to Z^{+}$ source 273. Show that the definitions are equivalent, i.e., show that there is a injective function $g : A \to Z^{+}$ source 275 iff either $A = \emptyset$ source 275 or there is a surjective $f : Z^{+} \to A$ source 276.

source 268

Cantor's Zig-Zag Method

Explanation

We've already considered some “easy” enumerations. Now we will consider something a bit harder. Consider the set of pairs of natural numbers, which we defined in Pairs, Tuples, Cartesian Products thus: $N \times N = {⟨ n, m ⟩ : n, m \in N}$ source 18 We can organize these ordered pairs into an array, like so: $\begin{array}{cccccccccccccccccccccc} 0 & 1 & 2 & 3 & \dots \\ 0 & ⟨ 0, 0 ⟩ & ⟨ 0, 1 ⟩ & ⟨ 0, 2 ⟩ & ⟨ 0, 3 ⟩ & \dots \\ 1 & ⟨ 1, 0 ⟩ & ⟨ 1, 1 ⟩ & ⟨ 1, 2 ⟩ & ⟨ 1, 3 ⟩ & \dots \\ 2 & ⟨ 2, 0 ⟩ & ⟨ 2, 1 ⟩ & ⟨ 2, 2 ⟩ & ⟨ 2, 3 ⟩ & \dots \\ 3 & ⟨ 3, 0 ⟩ & ⟨ 3, 1 ⟩ & ⟨ 3, 2 ⟩ & ⟨ 3, 3 ⟩ & \dots \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋱ \end{array}$ source 22 Clearly, every ordered pair in $N \times N$ source 37 will appear exactly once in the array. In particular, $⟨ n, m ⟩$ source 38 will appear in the $n$ source 39th row and $m$ source 39th column. But how do we organize the elements of such an array into a “one-dimensional” list? The pattern in the array below demonstrates one way to do this (although of course there are many other options): $\begin{array}{cccccccccccccccccccccccccc} 0 & 1 & 2 & 3 & 4 & \dots \\ 0 & 0 & 1 & 3 & 6 & 10 & \dots \\ 1 & 2 & 4 & 7 & 11 & \dots & \dots \\ 2 & 5 & 8 & 12 & \dots & \dots & \dots \\ 3 & 9 & 13 & \dots & \dots & \dots & \dots \\ 4 & 14 & \dots & \dots & \dots & \dots & \dots \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & \dots & ⋱ \end{array}$ source 42 This pattern is called Cantor's zig-zag method. It enumerates $N \times N$ source 60 as follows: $⟨ 0, 0 ⟩, ⟨ 0, 1 ⟩, ⟨ 1, 0 ⟩, ⟨ 0, 2 ⟩, ⟨ 1, 1 ⟩, ⟨ 2, 0 ⟩, ⟨ 0, 3 ⟩, ⟨ 1, 2 ⟩, ⟨ 2, 1 ⟩, ⟨ 3, 0 ⟩, \dots$ source 61 And this establishes the following:

Proposition: Enumerability of pairs of natural numbers

$N \times N$ source 69 is enumerable.

source 68

Proof

Let $f : N \to N \times N$ source 73 take each $k \in N$ source 73 to the tuple $⟨ n, m ⟩ \in N \times N$ source 74 such that $k$ source 74 is the value of the $n$ source 75th row and $m$ source 75th column in Cantor's zig-zag array.

End of proof.

Explanation

This technique also generalises rather nicely. For example, we can use it to enumerate the set of ordered triples of natural numbers, i.e.: $N \times N \times N = {⟨ n, m, k ⟩ : n, m, k \in N}$ source 81 We think of $N \times N \times N$ source 84 as the Cartesian product of $N \times N$ source 85 with $N$ source 85, that is, $N^{3} = (N \times N) \times N = {⟨ ⟨ n, m ⟩, k ⟩ : n, m, k \in N}$ source 86 and thus we can enumerate $N^{3}$ source 91 with an array by labelling one axis with the enumeration of $N$ source 92, and the other axis with the enumeration of $N^{2}$ source 93: $\begin{array}{cccccccccccccccccccccc} 0 & 1 & 2 & 3 & \dots \\ ⟨ 0, 0 ⟩ & ⟨ 0, 0, 0 ⟩ & ⟨ 0, 0, 1 ⟩ & ⟨ 0, 0, 2 ⟩ & ⟨ 0, 0, 3 ⟩ & \dots \\ ⟨ 0, 1 ⟩ & ⟨ 0, 1, 0 ⟩ & ⟨ 0, 1, 1 ⟩ & ⟨ 0, 1, 2 ⟩ & ⟨ 0, 1, 3 ⟩ & \dots \\ ⟨ 1, 0 ⟩ & ⟨ 1, 0, 0 ⟩ & ⟨ 1, 0, 1 ⟩ & ⟨ 1, 0, 2 ⟩ & ⟨ 1, 0, 3 ⟩ & \dots \\ ⟨ 0, 2 ⟩ & ⟨ 0, 2, 0 ⟩ & ⟨ 0, 2, 1 ⟩ & ⟨ 0, 2, 2 ⟩ & ⟨ 0, 2, 3 ⟩ & \dots \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋱ \end{array}$ source 94 Thus, by using a method like Cantor's zig-zag method, we may similarly obtain an enumeration of $N^{3}$ source 110. And we can keep going, obtaining enumerations of $N^{n}$ source 111 for any natural number $n$ source 111. So, we have:

Proposition: Enumerability of finite powers of the natural numbers

$N^{n}$ source 115 is enumerable, for every $n \in N$ source 115.

source 114

Exercise: Enumerability of finite powers of the positive integers

Show that $(Z^{+})^{n}$ source 119 is enumerable, for every $n \in N$ source 119.

source 118

Exercise: Enumerability of all finite positive-integer sequences

Show that $(Z^{+})^{*}$ source 123 is enumerable. You may assume Exercise: Enumerability of finite powers of the positive integers.

source 122

Pairing Functions and Codes

Explanation

Cantor's zig-zag method makes the enumerability of $N^{n}$ source 13 visually evident. But let us focus on our array depicting $N^{2}$ source 14. Following the zig-zag line in the array and counting the places, we can check that $⟨ 1, 2 ⟩$ source 16 is associated with the number $7$ source 16. However, it would be nice if we could compute this more directly. That is, it would be nice to have to hand the inverse of the zig-zag enumeration, $g : N^{2} \to N$ source 19, such that $g (⟨ 0, 0 ⟩) = 0, g (⟨ 0, 1 ⟩) = 1, g (⟨ 1, 0 ⟩) = 2, \dots, g (⟨ 1, 2 ⟩) = 7, \dots$ source 20 This would enable us to calculate exactly where $⟨ n, m ⟩$ source 26 will occur in our enumeration.

In fact, we can define $g$ source 29 directly by making two observations. First: if the $n$ source 30th row and $m$ source 30th column contains value $v$ source 30, then the $(n + 1)$ source 31st row and $(m - 1)$ source 31st column contains value $v + 1$ source 31. Second: the first row of our enumeration consists of the triangular numbers, starting with $0$ source 33, $1$ source 33, $3$ source 33, $6$ source 33, etc. The $k$ source 33th triangular number is the sum of the natural numbers $< k$ source 34, which can be computed as $k (k + 1) / 2$ source 35. Putting these two observations together, consider this function: $g (n, m) = \frac{(n + m + 1) (n + m)}{2} + n$ source 37 We often just write $g (n, m)$ source 40 rather that $g (⟨ n, m ⟩)$ source 40, since it is easier on the eyes. This tells you first to determine the $(n + m)^{th}$ source 42 triangle number, and then add $n$ source 42 to it. And it populates the array in exactly the way we would like. So in particular, the pair $⟨ 1, 2 ⟩$ source 44 is sent to $\frac{4 \times 3}{2} + 1 = 7$ source 44.

This function $g$ source 47 is the inverse of an enumeration of a set of pairs. Such functions are called pairing functions.

Definition: Arithmetic pairing functions and codes

A function $f : A \times B \to N$ source 52 is an arithmetical pairing function if $f$ source 53 is injective. We also say that $f$ source 53 encodes $A \times B$ source 54, and that $f (x, y)$ source 54 is the code for $⟨ x, y ⟩$ source 55.

source 51

Exercise: Enumerating the nonnegative rational numbers

Give an enumeration of the set of all non-negative rational numbers.

source 66

Exercise: Enumerability of all rational numbers

Show that $Q$ source 71 is enumerable. Recall that any rational number can be written as a fraction $z / m$ source 72 with $z \in Z$ source 72, $m \in N^{+}$ source 72.

source 70

Exercise: Enumerating finite binary strings

Define an enumeration of $B^{*}$ source 76.

source 75

Exercise: Enumerability of finite-arity truth functions

Recall from your introductory logic course that each possible truth table expresses a truth function. In other words, the truth functions are all functions from $B^{k} \to B$ source 82 for some $k$ source 82. Prove that the set of all truth functions is enumerable.

source 79

Exercise: Enumerability of finite subsets of an enumerable set

Show that the set of all finite subsets of an arbitrary infinite enumerable set is enumerable.

source 86

Exercise: Enumerability of finite and cofinite subsets of the natural numbers

A subset of $N$ source 92 is said to be cofinite iff it is the complement of a finite set $N$ source 93; that is, $A \subseteq N$ source 93 is cofinite iff $N ∖ A$ source 94 is finite. Let $I$ source 94 be the set whose elements are exactly the finite and cofinite subsets of $N$ source 95. Show that $I$ source 96 is enumerable.

source 91

Exercise: Countable unions of enumerable sets

Show that the enumerable union of enumerable sets is enumerable. That is, whenever $A_{1}$ source 101, $A_{2}$ source 101, … are sets, and each $A_{i}$ source 102 is enumerable, then the union ${⋃_{i = 1}}^{\infty} A_{i}$ source 102 of all of them is also enumerable. [NB: this is hard!]

source 99

Exercise: Inverting a pairing function to enumerate its product

Let $f : A \times B \to N$ source 107 be an arbitrary pairing function. Show that the inverse of $f$ source 108 is an enumeration of $A \times B$ source 108.

source 106

Exercise: Encoding triples of natural numbers

Specify a function that encodes $N^{3}$ source 112.

source 111

An Alternative Pairing Function

Explanation

There are other enumerations of $N^{2}$ source 14 that make it easier to figure out what their inverses are. Here is one. Instead of visualizing the enumeration in an array, start with the list of positive integers associated with (initially) empty spaces. Imagine filling these spaces successively with pairs $⟨ n, m ⟩$ source 18 as follows. Starting with the pairs that have $0$ source 19 in the first place (i.e., pairs $⟨ 0, m ⟩$ source 20), put the first (i.e., $⟨ 0, 0 ⟩$ source 20) in the first empty place, then skip an empty space, put the second (i.e., $⟨ 0, 2 ⟩$ source 21) in the next empty place, skip one again, and so forth. The (incomplete) beginning of our enumeration now looks like this $\begin{array}{ccccccccccccccccccccccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & \dots \\ ⟨ 0, 0 ⟩ & ⟨ 0, 1 ⟩ & ⟨ 0, 2 ⟩ & ⟨ 0, 3 ⟩ & ⟨ 0, 4 ⟩ & \dots \end{array}$ source 24 Repeat this with pairs $⟨ 1, m ⟩$ source 30 for the place that still remain empty, again skipping every other empty place: $\begin{array}{ccccccccccccccccccccccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & \dots \\ ⟨ 0, 0 ⟩ & ⟨ 1, 0 ⟩ & ⟨ 0, 1 ⟩ & ⟨ 0, 2 ⟩ & ⟨ 1, 1 ⟩ & ⟨ 0, 3 ⟩ & ⟨ 0, 4 ⟩ & ⟨ 1, 2 ⟩ & \dots \end{array}$ source 32 Enter pairs $⟨ 2, m ⟩$ source 39, $⟨ 2, m ⟩$ source 39, etc., in the same way. Our completed enumeration thus starts like this: $\begin{array}{cccccccccccccccccccccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & \dots \\ ⟨ 0, 0 ⟩ & ⟨ 1, 0 ⟩ & ⟨ 0, 1 ⟩ & ⟨ 2, 0 ⟩ & ⟨ 0, 2 ⟩ & ⟨ 1, 1 ⟩ & ⟨ 0, 3 ⟩ & ⟨ 3, 0 ⟩ & ⟨ 0, 4 ⟩ & ⟨ 1, 2 ⟩ & \dots \end{array}$ source 41 If we number the cells in the array above according to this enumeration, we will not find a neat zig-zag line, but this arrangement: $\begin{array}{ccccccccccccccccccccccccccccccc} 0 & 1 & 2 & 3 & 4 & 5 & \dots \\ 0 & 1 & 3 & 5 & 7 & 9 & 11 & \dots \\ 1 & 2 & 6 & 10 & 14 & 18 & \dots & \dots \\ 2 & 4 & 12 & 20 & 28 & \dots & \dots & \dots \\ 3 & 8 & 24 & 40 & \dots & \dots & \dots & \dots \\ 4 & 16 & 48 & \dots & \dots & \dots & \dots & \dots \\ 5 & 32 & \dots & \dots & \dots & \dots & \dots & \dots \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋱ \end{array}$ source 51 We can see that the pairs in row $0$ source 70 are in the odd numbered places of our enumeration, i.e., pair $⟨ 0, m ⟩$ source 71 is in place $2 m + 1$ source 71; pairs in the second row, $⟨ 1, m ⟩$ source 72, are in places whose number is the double of an odd number, specifically, $2 \cdot (2 m + 1)$ source 73; pairs in the third row, $⟨ 2, m ⟩$ source 74, are in places whose number is four times an odd number, $4 \cdot (2 m + 1)$ source 75; and so on. The factors of $(2 m + 1)$ source 75 for each row, $1$ source 76, $2$ source 76, $4$ source 76, $8$ source 76, …, are exactly the powers of $2$ source 76: $1 = 2^{0}$ source 77, $2 = 2^{1}$ source 77, $4 = 2^{2}$ source 77, $8 = 2^{3}$ source 77, … In fact, the relevant exponent is always the first member of the pair in question. Thus, for pair $⟨ n, m ⟩$ source 79 the factor is $2^{n}$ source 79. This gives us the general formula: $2^{n} \cdot (2 m + 1)$ source 80. However, this is a mapping of pairs to positive integers, i.e., $⟨ 0, 0 ⟩$ source 81 has position $1$ source 82. If we want to begin at position $0$ source 82 we must subtract $1$ source 82 from the result. This gives us:

Example: Pairing natural numbers by powers of two

The function $h : N^{2} \to N$ source 87 given by $h (n, m) = 2^{n} (2 m + 1) - 1$ source 88 is a pairing function for the set of pairs of natural numbers $N^{2}$ source 91.

source 86

Sometimes it is enough to encode pairs of natural numbers $N^{2}$ source 102 without requiring that the encoding is surjective. Such encodings have inverses that are only partial functions.

Example: Injective pair encoding by prime powers

The function $j : N^{2} \to N^{+}$ source 107 given by $j (n, m) = 2^{n} 3^{m}$ source 108 is a injective function $N^{2} \to N$ source 111.

source 106

Nonenumerable Sets

Some sets, such as the set $Z^{+}$ source 20 of positive integers, are infinite. So far we've seen examples of infinite sets which were all enumerable. However, there are also infinite sets which do not have this property. Such sets are called nonenumerable.

First of all, it is perhaps already surprising that there are nonenumerable sets. For any enumerable set $A$ source 26 there is a surjective function $f : Z^{+} \to A$ source 27. If a set is nonenumerable there is no such function. That is, no function mapping the infinitely many elements of $Z^{+}$ source 29 to $A$ source 29 can exhaust all of $A$ source 30. So there are “more” elements of $A$ source 30 than the infinitely many positive integers.

How would one prove that a set is nonenumerable? You have to show that no such surjective function can exist. Equivalently, you have to show that the elements of $A$ source 35 cannot be enumerated in a one way infinite list. The best way to do this is to show that every list of elements of $A$ source 37 must leave at least one element out; or that no function $f : Z^{+} \to A$ source 38 can be surjective. We can do this using Cantor's diagonal method. Given a list of elements of $A$ source 40, say, $x_{1}$ source 40, $x_{2}$ source 40, …, we construct another element of $A$ source 40 which, by its construction, cannot possibly be on that list.

Our first example is the set $B^{ω}$ source 43 of all infinite, non-gappy sequences of $0$ source 44's and $1$ source 44's.

Theorem: Non-enumerability of positive-indexed infinite binary sequences

$B^{ω}$ source 48 is nonenumerable.

source 46

Proof

Suppose, by way of contradiction, that $B^{ω}$ source 52 is enumerable, i.e., suppose that there is a list $s_{1}$ source 53, $s_{2}$ source 53, $s_{3}$ source 54, $s_{4}$ source 54, … of all elements of $B^{ω}$ source 54. Each of these $s_{i}$ source 55 is itself an infinite sequence of $0$ source 55's and $1$ source 55's. Let's call the $j$ source 56-th element of the $i$ source 56-th sequence in this list $s_{i} (j)$ source 57. Then the $i$ source 57-th sequence $s_{i}$ source 57 is $s_{i} (1), s_{i} (2), s_{i} (3), \dots$ source 58

We may arrange this list, and the elements of each sequence $s_{i}$ source 62 in it, in an array: $\begin{array}{ccccccccccc} 1 & 2 & 3 & 4 & \dots \\ 1 & s_{1} (1) & s_{1} (2) & s_{1} (3) & s_{1} (4) & \dots \\ 2 & s_{2} (1) & s_{2} (2) & s_{2} (3) & s_{2} (4) & \dots \\ 3 & s_{3} (1) & s_{3} (2) & s_{3} (3) & s_{3} (4) & \dots \\ 4 & s_{4} (1) & s_{4} (2) & s_{4} (3) & s_{4} (4) & \dots \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋱ \end{array}$ source 64 The labels down the side give the number of the sequence in the list $s_{1}$ source 75, $s_{2}$ source 75, …; the numbers across the top label the elements of the individual sequences. For instance, $s_{1} (1)$ source 76 is a name for whatever number, a $0$ source 77 or a $1$ source 77, is the first element in the sequence $s_{1}$ source 78, and so on.

Now we construct an infinite sequence, $\bar{s}$ source 80, of $0$ source 80's and $1$ source 81's which cannot possibly be on this list. The definition of $\bar{s}$ source 82 will depend on the list $s_{1}$ source 82, $s_{2}$ source 82, …. Any infinite list of infinite sequences of $0$ source 83's and $1$ source 83's gives rise to an infinite sequence $\bar{s}$ source 84 which is guaranteed to not appear on the list.

To define $\bar{s}$ source 87, we specify what all its elements are, i.e., we specify $\bar{s} (n)$ source 88 for all $n \in Z^{+}$ source 88. We do this by reading down the diagonal of the array above (hence the name “diagonal method”) and then changing every $1$ source 90 to a $0$ source 90 and every $0$ source 91 to a $1$ source 91. More abstractly, we define $\bar{s} (n)$ source 91 to be $0$ source 91 or $1$ source 92 according to whether the $n$ source 92-th element of the diagonal, $s_{n} (n)$ source 93, is $1$ source 93 or $0$ source 93. $\bar{s} (n) = {\begin{matrix} 1 & if s_{n} (n) = 0 \\ 0 & if s_{n} (n) = 1 . \end{matrix}$ source 94 If you like formulas better than definitions by cases, you could also define $\bar{s} (n) = 1 - s_{n} (n)$ source 102.

Clearly $\bar{s}$ source 104 is an infinite sequence of $0$ source 104's and $1$ source 105's, since it is just the mirror sequence to the sequence of $0$ source 105's and $1$ source 106's that appear on the diagonal of our array. So $\bar{s}$ source 106 is a element of $B^{ω}$ source 107. But it cannot be on the list $s_{1}$ source 107, $s_{2}$ source 108, … Why not?

It can't be the first sequence in the list, $s_{1}$ source 110, because it differs from $s_{1}$ source 111 in the first element. Whatever $s_{1} (1)$ source 111 is, we defined $\bar{s} (1)$ source 112 to be the opposite. It can't be the second sequence in the list, because $\bar{s}$ source 113 differs from $s_{2}$ source 113 in the second element: if $s_{2} (2)$ source 114 is $0$ source 114, $\bar{s} (2)$ source 114 is $1$ source 114, and vice versa. And so on.

More precisely: if $\bar{s}$ source 117 were on the list, there would be some $k$ source 118 so that $\bar{s} = s_{k}$ source 118. Two sequences are identical iff they agree at every place, i.e., for any $n$ source 119, $\bar{s} (n) = s_{k} (n)$ source 119. So in particular, taking $n = k$ source 120 as a special case, $\bar{s} (k) = s_{k} (k)$ source 121 would have to hold. $s_{k} (k)$ source 121 is either $0$ source 122 or $1$ source 122. If it is $0$ source 122 then $\bar{s} (k)$ source 122 must be $1$ source 122—that's how we defined $\bar{s}$ source 123. But if $s_{k} (k) = 1$ source 123 then, again because of the way we defined $\bar{s}$ source 124, $\bar{s} (k) = 0$ source 124. In either case $\bar{s} (k) \neq s_{k} (k)$ source 125.

We started by assuming that there is a list of elements of $B^{ω}$ source 128, $s_{1}$ source 128, $s_{2}$ source 128, … From this list we constructed a sequence $\bar{s}$ source 129 which we proved cannot be on the list. But it definitely is a sequence of $0$ source 130's and $1$ source 130's if all the $s_{i}$ source 130 are sequences of $0$ source 131's and $1$ source 131's, i.e., $\bar{s} \in B^{ω}$ source 131. This shows in particular that there can be no list of all elements of $B^{ω}$ source 133, since for any such list we could also construct a sequence $\bar{s}$ source 134 guaranteed to not be on the list, so the assumption that there is a list of all sequences in $B^{ω}$ source 136 leads to a contradiction.

End of proof.

Theorem: Non-enumerability of the power set of the positive integers

$℘ (Z^{+})$ source 149 is not enumerable.

source 147

Proof

We proceed in the same way, by showing that for every list of subsets of $Z^{+}$ source 154 there is a subset of $Z^{+}$ source 154 which cannot be on the list. Suppose the following is a given list of subsets of $Z^{+}$ source 155: $Z_{1}, Z_{2}, Z_{3}, \dots$ source 156 We now define a set $\bar{Z}$ source 159 such that for any $n \in Z^{+}$ source 159, $n \in \bar{Z}$ source 160 iff $n \notin Z_{n}$ source 160: $\bar{Z} = {n \in Z^{+} : n \notin Z_{n}}$ source 161 $\bar{Z}$ source 164 is clearly a set of positive integers, since by assumption each $Z_{n}$ source 165 is, and thus $\bar{Z} \in ℘ (Z^{+})$ source 165. But $\bar{Z}$ source 166 cannot be on the list. To show this, we'll establish that for each $k \in Z^{+}$ source 167, $\bar{Z} \neq Z_{k}$ source 167.

So let $k \in Z^{+}$ source 170 be arbitrary. We've defined $\bar{Z}$ source 170 so that for any $n \in Z^{+}$ source 171, $n \in \bar{Z}$ source 171 iff $n \notin Z_{n}$ source 171. In particular, taking $n = k$ source 172, $k \in \bar{Z}$ source 172 iff $k \notin Z_{k}$ source 172. But this shows that $\bar{Z} \neq Z_{k}$ source 173, since $k$ source 173 is a element of one but not the other, and so $\bar{Z}$ source 174 and $Z_{k}$ source 174 have different elements. Since $k$ source 175 was arbitrary, $\bar{Z}$ source 175 is not on the list $Z_{1}$ source 176, $Z_{2}$ source 176, …

End of proof.

Explanation

The preceding proof did not mention a diagonal, but you can think of it as involving a diagonal if you picture it this way: Imagine the sets $Z_{1}$ source 182, $Z_{2}$ source 182, …, written in an array, where each element $j \in Z_{i}$ source 183 is listed in the $j$ source 183-th column. Say the first four sets on that list are ${1, 2, 3, \dots}$ source 184, ${2, 4, 6, \dots}$ source 184, ${1, 2, 5}$ source 185, and ${3, 4, 5, \dots}$ source 185. Then the array would begin with $\begin{array}{rcccrrrrrrr} Z_{1} = { & 1, & 2, & 3, & 4, & 5, & 6, & \dots} \\ Z_{2} = { & 2, & 4, & 6, & \dots} \\ Z_{3} = { & 1, & 2, & 5 & } \\ Z_{4} = { & 3, & 4, & 5, & 6, & \dots} \\ ⋮ & ⋱ \end{array}$ source 186 Then $\bar{Z}$ source 195 is the set obtained by going down the diagonal, leaving out any numbers that appear along the diagonal and include those $j$ source 197 where the array has a gap in the $j$ source 197-th row/column. In the above case, we would leave out $1$ source 198 and $2$ source 198, include $3$ source 198, leave out $4$ source 199, etc.

Exercise: Diagonal proof for the power set of the natural numbers

Show that $℘ (N)$ source 203 is nonenumerable by a diagonal argument.

source 202

Exercise: Diagonal proof for functions on the positive integers

Show that the set of functions $f : Z^{+} \to Z^{+}$ source 207 is nonenumerable by an explicit diagonal argument. That is, show that if $f_{1}$ source 209, $f_{2}$ source 209, …, is a list of functions and each $f_{i} : Z^{+} \to Z^{+}$ source 209, then there is some $\bar{f} : Z^{+} \to Z^{+}$ source 210 not on this list.

source 206

Reduction

We showed $℘ (Z^{+})$ source 20 to be nonenumerable by a diagonalization argument. We already had a proof that $B^{ω}$ source 21, the set of all infinite sequences of $0$ source 22s and $1$ source 22s, is nonenumerable. Here's another way we can prove that $℘ (Z^{+})$ source 23 is nonenumerable: Show that if $℘ (Z^{+})$ source 24 is enumerable then $B^{ω}$ source 24 is also enumerable. Since we know $B^{ω}$ source 25 is not enumerable, $℘ (Z^{+})$ source 26 can't be either. This is called reducing one problem to another—in this case, we reduce the problem of enumerating $B^{ω}$ source 28 to the problem of enumerating $℘ (Z^{+})$ source 29. A solution to the latter—an enumeration of $℘ (Z^{+})$ source 30—would yield a solution to the former—an enumeration of $B^{ω}$ source 31.

How do we reduce the problem of enumerating a set $B$ source 33 to that of enumerating a set $A$ source 34? We provide a way of turning an enumeration of $A$ source 35 into an enumeration of $B$ source 35. The easiest way to do that is to define a surjective function $f : A \to B$ source 36. If $x_{1}$ source 36, $x_{2}$ source 36, … enumerates $A$ source 37, then $f (x_{1})$ source 37, $f (x_{2})$ source 37, … would enumerate $B$ source 38. In our case, we are looking for a surjective function $f : ℘ (Z^{+}) \to B^{ω}$ source 39.

Exercise: Reduction along an injection with positive-integer enumerations

Show that if there is an injective function $g : B \to A$ source 42, and $B$ source 43 is nonenumerable, then so is $A$ source 43. Do this by showing how you can use $g$ source 44 to turn an enumeration of $A$ source 44 into one of $B$ source 44.

source 41

Proof of Theorem: Non-enumerability of the power set of the positive integers by reduction

Suppose that $℘ (Z^{+})$ source 48 were enumerable, and thus that there is an enumeration of it, $Z_{1}$ source 49, $Z_{2}$ source 49, $Z_{3}$ source 49, …

Define the function $f : ℘ (Z^{+}) \to B^{ω}$ source 51 by letting $f (Z)$ source 52 be the sequence $s_{k}$ source 52 such that $s_{k} (n) = 1$ source 52 iff $n \in Z$ source 52, and $s_{k} (n) = 0$ source 53 otherwise. This clearly defines a function, since whenever $Z \subseteq Z^{+}$ source 54, any $n \in Z^{+}$ source 54 either is a element of $Z$ source 55 or isn't. For instance, the set $2 Z^{+} = {2, 4, 6, \dots}$ source 55 of positive even numbers gets mapped to the sequence $010101 \dots$ source 57, the empty set gets mapped to $0000 \dots$ source 57 and the set $Z^{+}$ source 58 itself to $1111 \dots$ source 58.

It also is surjective: Every sequence of $0$ source 60s and $1$ source 60s corresponds to some set of positive integers, namely the one which has as its members those integers corresponding to the places where the sequence has $1$ source 63s. More precisely, suppose $s \in B^{ω}$ source 63. Define $Z \subseteq Z^{+}$ source 63 by: $Z = {n \in Z^{+} : s (n) = 1}$ source 65 Then $f (Z) = s$ source 68, as can be verified by consulting the definition of $f$ source 69.

Now consider the list $f (Z_{1}), f (Z_{2}), f (Z_{3}), \dots$ source 72 Since $f$ source 75 is surjective, every member of $B^{ω}$ source 75 must appear as a value of $f$ source 76 for some argument, and so must appear on the list. This list must therefore enumerate all of $B^{ω}$ source 77.

So if $℘ (Z^{+})$ source 79 were enumerable, $B^{ω}$ source 79 would be enumerable. But $B^{ω}$ source 80 is nonenumerable (Theorem: Non-enumerability of positive-indexed infinite binary sequences). Hence $℘ (Z^{+})$ source 81 is nonenumerable.

End of proof.

Explanation

It is easy to be confused about the direction the reduction goes in. For instance, a surjective function $g : B^{ω} \to B$ source 87 does not establish that $B$ source 88 is nonenumerable. (Consider $g : B^{ω} \to B$ source 88 defined by $g (s) = s (1)$ source 89, the function that maps a sequence of $0$ source 90's and $1$ source 90's to its first element. It is surjective, because some sequences start with $0$ source 91 and some start with $1$ source 92. But $B$ source 92 is finite.) Note also that the function $f$ source 92 must be surjective, or otherwise the argument does not go through: $f (x_{1})$ source 94, $f (x_{2})$ source 94, … would then not be guaranteed to include all the elements of $B$ source 95. For instance, $h (n) = {\underset{⏟}{000 \dots 0}}_{n 0's}$ source 96 defines a function $h : Z^{+} \to B^{ω}$ source 99, but $Z^{+}$ source 100 is enumerable.

Exercise: Non-enumerability of sets of positive-integer pairs

Show that the set of all sets of pairs of positive integers is nonenumerable by a reduction argument.

source 103

Exercise: Functions on the natural numbers by positive-indexed reduction

Show that the set $X$ source 109 of all functions $f : N \to N$ source 109 is nonenumerable by a reduction argument (Hint: give a surjective function from $X$ source 111 to $B^{ω}$ source 111.)

source 108

Exercise: Infinite natural-number sequences by positive-indexed reduction

Show that $N^{ω}$ source 115, the set of infinite sequences of natural numbers, is nonenumerable by a reduction argument.

source 114

Exercise: Total and partial zero-valued functions

Let $P$ source 120 be the set of functions from the set of positive integers to the set ${0}$ source 121, and let $Q$ source 121 be the set of partial functions from the set of positive integers to the set ${0}$ source 122. Show that $P$ source 123 is enumerable and $Q$ source 123 is not. (Hint: reduce the problem of enumerating $B^{ω}$ source 124 to enumerating $Q$ source 124).

source 119

Exercise: Binary surjections from the positive integers

Let $S$ source 128 be the set of all surjective functions from the set of positive integers to the set {0,1}, i.e., $S$ source 129 consists of all surjective $f : Z^{+} \to B$ source 130. Show that $S$ source 130 is nonenumerable.

source 127

Exercise: Real numbers by positive-indexed reduction

Show that the set $R$ source 135 of all real numbers is nonenumerable.

source 134

Equinumerosity

We have an intuitive notion of “size” of sets, which works fine for finite sets. But what about infinite sets? If we want to come up with a formal way of comparing the sizes of two sets of any size, it is a good idea to start by defining when sets are the same size. Here is Frege:

If a waiter wants to be sure that he has laid exactly as many knives as plates on the table, he does not need to count either of them, if he simply lays a knife to the right of each plate, so that every knife on the table lies to the right of some plate. The plates and knives are thus uniquely correlated to each other, and indeed through that same spatial relationship. (Gottlob Frege, 1884, §70)

The insight of this passage can be brought out through a formal definition:

Definition: Equinumerous sets

$A$ source 30 is equinumerous with $B$ source 30, written $A \approx B$ source 30, iff there is a bijection $f : A \to B$ source 31.

source 29

Proposition: Equinumerosity as an equivalence relation

Equinumerosity is an equivalence relation.

source 34

Proof

We must show that equinumerosity is reflexive, symmetric, and transitive. Let $A, B$ source 40, and $C$ source 40 be sets.

Reflexivity. The identity map ${Id}_{A} : A \to A$ source 42, where ${Id}_{A} (x) = x$ source 43 for all $x \in A$ source 43, is a bijection. So $A \approx A$ source 44.

Symmetry. Suppose $A \approx B$ source 46, i.e., there is a bijection $f : A \to B$ source 47. Since $f$ source 47 is bijective, its inverse $f^{- 1}$ source 48 exists and is also bijective. Hence, $f^{- 1} : B \to A$ source 49 is a bijection, so $B \approx A$ source 49.

Transitivity. Suppose that $A \approx B$ source 51 and $B \approx C$ source 51, i.e., there are bijections $f : A \to B$ source 52 and $g : B \to C$ source 52. Then the composition $g \circ f : A \to C$ source 53 is bijective, so that $A \approx C$ source 54.

End of proof.

Proposition: Preservation of enumerability under equinumerosity

If $A \approx B$ source 58, then $A$ source 58 is enumerable if and only if $B$ source 59 is.

source 57

Proof

Suppose $A \approx B$ source 69, so there is some bijection $f : A \to B$ source 69, and suppose that $A$ source 70 is enumerable.

Then either $A = \emptyset$ source 72 or there is a surjective function $g : Z^{+} \to A$ source 73. If $A = \emptyset$ source 73, then $B = \emptyset$ source 73 also (otherwise there would be a element $y \in B$ source 74 but no $x \in A$ source 74 with $g (x) = y$ source 75). If, on the other hand, $g : Z^{+} \to A$ source 75 is surjective, then $f \circ g : Z^{+} \to B$ source 76 is surjective. To see this, let $y \in B$ source 77. Since $f$ source 77 is surjective, there is an $x \in A$ source 78 such that $f (x) = y$ source 78. Since $g$ source 79 is surjective, there is an $n \in Z^{+}$ source 79 such that $g (n) = x$ source 79. Hence, $(f \circ g) (n) = f (g (n)) = f (x) = y$ source 81 and thus $f \circ g$ source 84 is surjective. We have that $f \circ g$ source 84 is an enumeration of $B$ source 85, and so $B$ source 85 is enumerable.

If $B$ source 96 is enumerable, we obtain that $A$ source 96 is enumerable by repeating the argument with the bijection $f^{- 1} : B \to A$ source 97 instead of $f$ source 98.

End of proof.

Exercise: Equinumerosity of disjoint unions

Show that if $A \approx C$ source 102 and $B \approx D$ source 102, and $A \cap B = C \cap D = \emptyset$ source 102, then $A \cup B \approx C \cup D$ source 103.

source 101

Exercise: Infinite enumerable sets and the natural numbers

Show that if $A$ source 107 is infinite and enumerable, then $A \approx N$ source 108.

source 106

Sets of Different Sizes, and Cantor's Theorem

Definition: Cardinality comparison by injection

$A$ source 27 is no larger than $B$ source 27, written $A ≼ B$ source 27, iff there is a injection $f : A \to B$ source 28.

source 26

It is clear that this is a reflexive and transitive relation, but that it is not symmetric (this is left as an exercise). We can also introduce a notion, which states that one set is (strictly) smaller than another.

Definition: Strict cardinal inequality

$A$ source 37 is smaller than $B$ source 37, written $A ≺ B$ source 37, iff there is a injection $f : A \to B$ source 38 but no bijection $g : A \to B$ source 38, i.e., $A ≼ B$ source 39 and $A ≉ B$ source 39.

source 36

It is clear that this relation is irreflexive and transitive. (This is left as an exercise.) Using this notation, we can say that a set $A$ source 44 is enumerable iff $A ≼ N$ source 44, and that $A$ source 45 is nonenumerable iff $N ≺ A$ source 45. This allows us to restate

Theorem: Non-enumerability of the power set of the natural numbers as the observation that $N ≺ ℘ (N)$ source 50. In fact, Georg Cantor (1892) proved that this last point is perfectly general:

Theorem: Cantor's theorem on power sets

$A ≺ ℘ (A)$ source 57, for any set $A$ source 57.

source 56

Proof

The map $f (x) = {x}$ source 61 is a injection $f : A \to ℘ (A)$ source 61, since if $x \neq y$ source 62, then also ${x} \neq {y}$ source 62 by extensionality, and so $f (x) \neq f (y)$ source 63. So we have that $A ≼ ℘ (A)$ source 63.

We will now show that there cannot be a surjective function $g : A \to ℘ (A)$ source 71, let alone a bijective one, and hence that $A ≉ ℘ (A)$ source 73. For suppose that $g : A \to ℘ (A)$ source 73. Since $g$ source 74 is total, every $x \in A$ source 74 is mapped to a subset $g (x) \subseteq A$ source 74. We can show that $g$ source 75 cannot be surjective. To do this, we define a subset $\bar{A} \subseteq A$ source 76 which by definition cannot be in the range of $g$ source 77. Let $\bar{A} = {x \in A : x \notin g (x)} .$ source 78 Since $g (x)$ source 81 is defined for all $x \in A$ source 81, $\bar{A}$ source 81 is clearly a well-defined subset of $A$ source 82. But, it cannot be in the range of $g$ source 83. Let $x \in A$ source 83 be arbitrary, we will show that $\bar{A} \neq g (x)$ source 83. If $x \in g (x)$ source 84, then it does not satisfy $x \notin g (x)$ source 84, and so by the definition of $\bar{A}$ source 85, we have $x \notin \bar{A}$ source 85. If $x \in \bar{A}$ source 86, it must satisfy the defining property of $\bar{A}$ source 87, i.e., $x \in A$ source 87 and $x \notin g (x)$ source 87. Since $x$ source 88 was arbitrary, this shows that for each $x \in \bar{A}$ source 88, $x \in g (x)$ source 89 iff $x \notin \bar{A}$ source 89, and so $g (x) \neq \bar{A}$ source 90. In other words, $\bar{A}$ source 90 cannot be in the range of $g$ source 91, contradicting the assumption that $g$ source 91 is surjective.

End of proof.

Explanation

It's instructive to compare the proof of Theorem: Cantor's theorem on power sets to that of Theorem: Non-enumerability of the power set of the positive integers. There we showed that for any list $Z_{1}$ source 111, $Z_{2}$ source 111, …, of subsets of $Z^{+}$ source 111 one can construct a set $\bar{Z}$ source 112 of numbers guaranteed not to be on the list. It was guaranteed not to be on the list because, for every $n \in Z^{+}$ source 113, $n \in Z_{n}$ source 114 iff $n \notin \bar{Z}$ source 114. This way, there is always some number that is a element of one of $Z_{n}$ source 115 or $\bar{Z}$ source 116 but not the other. We follow the same idea here, except the indices $n$ source 117 are now elements of $A$ source 117 instead of $Z^{+}$ source 118. The set $\bar{A}$ source 118 is defined so that it is different from $g (x)$ source 119 for each $x \in A$ source 119, because $x \in g (x)$ source 119 iff $x \notin \bar{A}$ source 120. Again, there is always a element of $A$ source 120 which is a element of one of $g (x)$ source 121 and $\bar{A}$ source 121 but not the other. And just as $\bar{Z}$ source 122 therefore cannot be on the list $Z_{1}$ source 123, $Z_{2}$ source 123, …, $\bar{A}$ source 123 cannot be in the range of $g$ source 124.

It's instructive to compare the proof of Theorem: Cantor's theorem on power sets to that of Theorem: Non-enumerability of the power set of the natural numbers. There we showed that for any list $N_{0}$ source 129, $N_{1}$ source 129, $N_{2}$ source 129, …, of subsets of $N$ source 129 we can construct a set $D$ source 130 of numbers guaranteed not to be on the list. It was guaranteed not to be on the list because $n \in N_{n}$ source 131 iff $n \notin D$ source 131, for every $n \in N$ source 132. We follow the same idea here, except the indices $n$ source 133 are now elements of $A$ source 133 rather than of $N$ source 133. The set $D$ source 134 is defined so that it is different from $g (x)$ source 134 for each $x \in A$ source 134, because $x \in g (x)$ source 135 iff $x \notin D$ source 135.

The proof is also worth comparing with the proof of Russell's Paradox, Russell's Paradox. Indeed, Cantor's Theorem was the inspiration for Russell's own paradox.

Exercise: No injection from a power set into its base set

Show that there cannot be a injection $g : ℘ (A) \to A$ source 143, for any set $A$ source 144. Hint: Suppose $g : ℘ (A) \to A$ source 144 is injective. Consider $D = {g (B) : B \subseteq A and g (B) \notin B}$ source 145. Let $x = g (D)$ source 146. Use the fact that $g$ source 146 is injective to derive a contradiction.

source 142

The Notion of Size, and Schröder-Bernstein

Theorem: Schröder-Bernstein theorem

If $A ≼ B$ source 25 and $B ≼ A$ source 25, then $A \approx B$ source 26.

source 23

Explanation

In other words, if there is a injection from $A$ source 30 to $B$ source 30, and a injection from $B$ source 31 to $A$ source 31, then there is a bijection from $A$ source 31 to $B$ source 32.

This result, however, is really rather difficult to prove. Indeed, although Cantor stated the result, others proved it. Note: For more on the history, see e.g., Michael Potter (2004), pp. 165–6.

For now, you can (and must) take it on trust.

Fortunately, Schröder-Bernstein is correct, and it vindicates our thinking of the relations we defined, i.e., $A \approx B$ source 46 and $A ≼ B$ source 46, as having something to do with “size”. Moreover, Schröder-Bernstein is very useful. It can be difficult to think of a bijection between two equinumerous sets. The Schröder-Bernstein Theorem allows us to break the comparison down into cases so we only have to think of a injection from the first to the second, and vice-versa.

Enumerations and Enumerable Sets

We can specify finite set is by simply enumerating its elements. We do this when we define a set like so: $A = {a_{1}, a_{2}, \dots, a_{n}} .$ source 23 Assuming that the elements $a_{1}$ source 26, …, $a_{n}$ source 26 are all distinct, this gives us a bijection between $A$ source 27 and the first $n$ source 27 natural numbers $0$ source 28, …, $n - 1$ source 28. Conversely, since every finite set has only finitely many elements, every finite set can be put into such a correspondence. In other words, if $A$ source 30 is finite, there is a bijection between $A$ source 31 and ${0, \dots, n - 1}$ source 31, where $n$ source 31 is the number of elements of $A$ source 32.

If we allow for certain kinds of infinite sets, then we will also allow some infinite sets to be enumerated. We can make this precise by saying that an infinite set is enumerated by a bijection between it and all of $N$ source 37.

Definition: Set-theoretic enumeration

An enumeration of a set $A$ source 40 is a bijection whose range is $A$ source 41 and whose domain is either an initial set of natural numbers ${0, 1, \dots, n}$ source 41 or the entire set of natural numbers $N$ source 42.

source 39

Definition: Enumerable and nonenumerable sets in the set-theoretic presentation

A set $A$ source 59 is enumerable iff either $A = \emptyset$ source 59 or there is an enumeration of $A$ source 60. We say that $A$ source 60 is nonenumerable iff $A$ source 60 is not enumerable.

source 57

Example: Enumerating natural and positive natural numbers

A function enumerating the natural numbers is simply the identity function ${Id}_{N} : N \to N$ source 71 given by ${Id}_{N} (n) = n$ source 71. A function enumerating the positive natural numbers, $N^{+} = N ∖ {0}$ source 72, is the function $g (n) = n + 1$ source 73, i.e., the successor function.

source 69

Exercise: Injective and surjective tests for set-theoretic enumerability

Show that a set $A$ source 78 is enumerable iff either $A = \emptyset$ source 78 or there is a surjection $f : N \to A$ source 79. Show that $A$ source 79 is enumerable iff there is a injection $g : A \to N$ source 80.

source 77

Example: Enumerating even and odd natural numbers

The functions $f : N \to N$ source 84 and $g : N \to N$ source 84 given by $\begin{matrix} f (n) & = 2 n and \\ g (n) & = 2 n + 1 \end{matrix}$ source 86 respectively enumerate the even natural numbers and the odd natural numbers. But neither is surjective, so neither is an enumeration of $N$ source 92.

source 83

Exercise: Enumerating square numbers from natural inputs

Define an enumeration of the square numbers $1$ source 96, $4$ source 96, $9$ source 96, $16$ source 96, …

source 95

Example: Alternating enumeration of the integers from natural inputs

Let $⌈ x ⌉$ source 100 be the ceiling function, which rounds $x$ source 100 up to the nearest integer. Then the function $f : N \to Z$ source 101 given by: $f (n) = (- 1)^{n} ⌈ \frac{n}{2} ⌉$ source 103 enumerates the set of integers $Z$ source 107 as follows: $\begin{array}{ccccccccccccccc} f (0) & f (1) & f (2) & f (3) & f (4) & f (5) & f (6) & \dots \\ ⌈ \frac{0}{2} ⌉ & - ⌈ \frac{1}{2} ⌉ & ⌈ \frac{2}{2} ⌉ & - ⌈ \frac{3}{2} ⌉ & ⌈ \frac{4}{2} ⌉ & - ⌈ \frac{5}{2} ⌉ & ⌈ \frac{6}{2} ⌉ & \dots \\ 0 & - 1 & 1 & - 2 & 2 & - 3 & 3 & \dots \end{array}$ source 108 Notice how $f$ source 115 generates the values of $Z$ source 115 by “hopping” back and forth between positive and negative integers. You can also think of $f$ source 117 as defined by cases as follows: $f (n) = {\begin{matrix} \frac{n}{2} & if n is even \\ - \frac{n + 1}{2} & if n is odd \end{matrix}$ source 118

source 99

Exercise: Union of two enumerable sets in the set-theoretic presentation

Show that if $A$ source 127 and $B$ source 127 are enumerable, so is $A \cup B$ source 127.

source 126

Exercise: Finite unions in the set-theoretic presentation

Show by induction on $n$ source 131 that if $A_{1}$ source 131, $A_{2}$ source 131, …, $A_{n}$ source 131 are all enumerable, so is $A_{1} \cup \dots \cup A_{n}$ source 132.

source 130

Nonenumerable Sets

Explanation

The set $N$ source 21 of natural numbers is infinite. It is also trivially enumerable. But the remarkable fact is that there are nonenumerable sets, i.e., sets which are not enumerable (see Definition: Enumerable and nonenumerable sets in the set-theoretic presentation).

This might be surprising. After all, to say that $A$ source 26 is nonenumerable is to say that there is no bijection $f : N \to A$ source 27; that is, no function mapping the infinitely many elements of $N$ source 29 to $A$ source 29 exhausts all of $A$ source 29. So if $A$ source 29 is nonenumerable, there are “more” elements of $A$ source 30 than there are natural numbers.

To prove that a set is nonenumerable, you have to show that no appropriate bijection can exist. The best way to do this is to show that every attempt to enumerate elements of $A$ source 35 must leave at least one element out; this shows that no function $f : N \to A$ source 36 is surjective. And a general strategy for establishing this is to use Cantor's diagonal method. Given a list of elements of $A$ source 39, say, $x_{1}$ source 39, $x_{2}$ source 39, …, we construct another element of $A$ source 40 which, by its construction, cannot possibly be on that list.

But all of this is best understood by example. So, our first example is the set $B^{ω}$ source 44 of all infinite strings of $0$ source 44's and $1$ source 44's. (The ` $B$ source 45' stands for binary, and we can just think of it as the two-element set ${0, 1}$ source 47.)

Theorem: Non-enumerability of zero-indexed infinite binary strings

$B^{ω}$ source 58 is nonenumerable.

source 56

Proof

Consider any enumeration of a subset of $B^{ω}$ source 62. So we have some list $s_{0}$ source 63, $s_{1}$ source 63, $s_{2}$ source 63, … where every $s_{n}$ source 63 is an infinite string of $0$ source 64's and $1$ source 64's. Let $s_{n} (m)$ source 64 be the $n$ source 64th digit of the $m$ source 65th string in this list. So we can now think of our list as an array, where $s_{n} (m)$ source 66 is placed at the $n$ source 66th row and $m$ source 66th column: $\begin{array}{ccccccccccc} 0 & 1 & 2 & 3 & \dots \\ 0 & s_{0} (0) & s_{0} (1) & s_{0} (2) & s_{0} (3) & \dots \\ 1 & s_{1} (0) & s_{1} (1) & s_{1} (2) & s_{1} (3) & \dots \\ 2 & s_{2} (0) & s_{2} (1) & s_{2} (2) & s_{2} (3) & \dots \\ 3 & s_{3} (0) & s_{3} (1) & s_{3} (2) & s_{3} (3) & \dots \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋱ \end{array}$ source 67 We will now construct an infinite string, $d$ source 77, of $0$ source 77's and $1$ source 77's which is not on this list. We will do this by specifying each of its entries, i.e., we specify $d (n)$ source 79 for all $n \in N$ source 79. Intuitively, we do this by reading down the diagonal of the array above (hence the name “diagonal method”) and then changing every $1$ source 81 to a $0$ source 81 and every $1$ source 82 to a $0$ source 82. More abstractly, we define $d (n)$ source 82 to be $0$ source 82 or $1$ source 82 according to whether the $n$ source 83-th element of the diagonal, $s_{n} (n)$ source 83, is $1$ source 84 or $0$ source 84, that is: $d (n) = {\begin{matrix} 1 & if s_{n} (n) = 0 \\ 0 & if s_{n} (n) = 1 \end{matrix}$ source 85 Clearly $d \in B^{ω}$ source 92, since it is an infinite string of $0$ source 92's and $1$ source 93's. But we have constructed $d$ source 93 so that $d (n) \neq s_{n} (n)$ source 93 for any $n \in N$ source 94. That is, $d$ source 94 differs from $s_{n}$ source 94 in its $n$ source 94th entry. So $d \neq s_{n}$ source 95 for any $n \in N$ source 95. So $d$ source 95 cannot be on the list $s_{0}$ source 96, $s_{1}$ source 96, $s_{2}$ source 96, …

We have shown, given an arbitrary enumeration of some subset of $B^{ω}$ source 100, that it will omit some element of $B^{ω}$ source 100. So there is no enumeration of the set $B^{ω}$ source 101, i.e., $B^{ω}$ source 101 is nonenumerable.

End of proof.

Theorem: Non-enumerability of the power set of the natural numbers

$℘ (N)$ source 115 is not enumerable.

source 113

Proof

We proceed in the same way, by showing that every list of subsets of $N$ source 120 omits some subset of $N$ source 120. So, suppose that we have some list $N_{0}, N_{1}, N_{2}, \dots$ source 121 of subsets of $N$ source 121. We define a set $D$ source 121 as follows: $n \in D$ source 122 iff $n \notin N_{n}$ source 122: $D = {n \in N : n \notin N_{n}}$ source 123 Clearly $D \subseteq N$ source 126. But $D$ source 126 cannot be on the list. After all, by construction $n \in D$ source 127 iff $n \notin N_{n}$ source 127, so that $D \neq N_{n}$ source 127 for any $n \in N$ source 128.

End of proof.

Explanation

The preceding proof did not mention a diagonal. Still, you can think of it as involving a diagonal if you picture it this way: Imagine the sets $N_{0}$ source 134, $N_{1}$ source 134, …, written in an array, where we write $N_{n}$ source 134 on the $n$ source 135th row by writing $m$ source 135 in the $m$ source 135th column iff if $m \in N_{n}$ source 135. For example, say the first four sets on that list are ${0, 1, 2, \dots}$ source 137, ${1, 3, 5, \dots}$ source 137, ${0, 1, 4}$ source 137, and ${2, 3, 4, \dots}$ source 138; then our array would begin with $\begin{array}{rcccrrrrrrr} N_{0} = { & 0, & 1, & 2, & \dots} \\ N_{1} = { & 1, & 3, & 5, & \dots} \\ N_{2} = { & 0, & 1, & 4 & } \\ N_{3} = { & 2, & 3, & 4, & \dots} \\ ⋮ & ⋱ \end{array}$ source 139 Then $D$ source 148 is the set obtained by going down the diagonal, placing $n \in D$ source 148 iff $n$ source 149 is not on the diagonal. So in the above case, we would leave out $0$ source 150 and $1$ source 150, we would include $2$ source 150, we would leave out $3$ source 151, etc.

Exercise: Diagonal proof for functions on the natural numbers

Show that the set of all functions $f : N \to N$ source 155 is nonenumerable by an explicit diagonal argument. That is, show that if $f_{1}$ source 157, $f_{2}$ source 157, …, is a list of functions and each $f_{i} : N \to N$ source 157, then there is some $g : N \to N$ source 158 not on this list.

source 154

Reduction

We proved that $B^{ω}$ source 20 is nonenumerable by a diagonalization argument. We used a similar diagonalization argument to show that $℘ (N)$ source 22 is nonenumerable. But here's another way we can prove that $℘ (N)$ source 23 is nonenumerable: show that if $℘ (N)$ source 24 is enumerable then $B^{ω}$ source 24 is also enumerable. Since we know $B^{ω}$ source 25 is nonenumerable, it will follow that $℘ (N)$ source 26 is too.

This is called reducing one problem to another. In this case, we reduce the problem of enumerating $B^{ω}$ source 29 to the problem of enumerating $℘ (N)$ source 30. A solution to the latter—an enumeration of $℘ (N)$ source 31—would yield a solution to the former—an enumeration of $B^{ω}$ source 32.

To reduce the problem of enumerating a set $B$ source 34 to that of enumerating a set $A$ source 35, we provide a way of turning an enumeration of $A$ source 35 into an enumeration of $B$ source 36. The easiest way to do that is to define a surjection $f : A \to B$ source 37. If $x_{1}$ source 37, $x_{2}$ source 37, … enumerates $A$ source 38, then $f (x_{1})$ source 38, $f (x_{2})$ source 38, … would enumerate $B$ source 38. In our case, we are looking for a surjection $f : ℘ (N) \to B^{ω}$ source 39.

Exercise: Reduction along an injection with natural-number enumerations

Show that if there is an injective function $g : B \to A$ source 43, and $B$ source 44 is nonenumerable, then so is $A$ source 44. Do this by showing how you can use $g$ source 45 to turn an enumeration of $A$ source 45 into one of $B$ source 45.

source 42

Proof of Theorem: Non-enumerability of the power set of the natural numbers by reduction

For a reduction, suppose that $℘ (N)$ source 49 is enumerable, and thus that there is an enumeration of it, $N_{1}$ source 50, $N_{2}$ source 50, $N_{3}$ source 50, …

Define the function $f : ℘ (N) \to B^{ω}$ source 52 by letting $f (N)$ source 53 be the string $s_{k}$ source 53 such that $s_{k} (n) = 1$ source 53 iff $n \in N$ source 53, and $s_{k} (n) = 0$ source 54 otherwise.

This clearly defines a function, since whenever $N \subseteq N$ source 56, any $n \in N$ source 57 either is a element of $N$ source 57 or isn't. For instance, the set $2 N = {2 n : n \in N} = {0, 2, 4, 6, \dots}$ source 58 of even naturals gets mapped to the string $1010101 \dots$ source 59; $\emptyset$ source 60 gets mapped to $0000 \dots$ source 60; $N$ source 60 gets mapped to $1111 \dots$ source 61.

It is also surjective: every string of $0$ source 63s and $1$ source 63s corresponds to some set of natural numbers, namely the one which has as its members those natural numbers corresponding to the places where the string contains a $1$ source 66s. More precisely, if $s \in B^{ω}$ source 66, then define $N \subseteq N$ source 66 by: $N = {n \in N : s (n) = 1}$ source 68 Then $f (N) = s$ source 71, as can be verified by consulting the definition of $f$ source 72.

Now consider the list $f (N_{1}), f (N_{2}), f (N_{3}), \dots$ source 75 Since $f$ source 78 is surjective, every member of $B^{ω}$ source 78 must appear as a value of $f$ source 79 for some argument, and so must appear on the list. This list must therefore enumerate all of $B^{ω}$ source 80.

So if $℘ (N)$ source 82 were enumerable, $B^{ω}$ source 82 would be enumerable. But $B^{ω}$ source 83 is nonenumerable (Theorem: Non-enumerability of zero-indexed infinite binary strings). Hence $℘ (N)$ source 84 is nonenumerable.

End of proof.

Exercise: Functions on the natural numbers by zero-indexed reduction

Show that the set $X$ source 107 of all functions $f : N \to N$ source 107 is nonenumerable by a reduction argument (Hint: give a surjective function from $X$ source 109 to $B^{ω}$ source 109.)

source 106

Exercise: Sets of natural-number pairs by reduction

Show that the set of all sets of pairs of natural numbers, i.e., $℘ (N \times N)$ source 114, is nonenumerable by a reduction argument.

source 112

Exercise: Infinite natural-number sequences by zero-indexed reduction

Show that $N^{ω}$ source 119, the set of infinite sequences of natural numbers, is nonenumerable by a reduction argument.

source 118

Exercise: Binary surjections from the natural numbers

Let $S$ source 131 be the set of all surjections from $N$ source 131 to the set ${0, 1}$ source 132, i.e., $S$ source 132 consists of all surjections $f : N \to B$ source 132. Show that $S$ source 133 is nonenumerable.

source 130

Exercise: Real numbers by zero-indexed reduction

Show that the set $R$ source 137 of all real numbers is nonenumerable.

source 136