Skip to main content

PLP: An introduction to mathematical proof

Seçkin Demirbaş, Andrew Rechnitzer

Section 12.2 Denumerable sets

As described above, our intuitive notion of an infinite set (or any infinite thing), is a process that keeps on going. We never get to the end because we can always take another step. What we are really doing when we think of infinity in this way is setting up a bijection between it and the set of natural numbers. There is some infinite process — we start at the beginning (the number 1) and then we take a step \(n \mapsto n+1\text{,}\) and then another step, and another step and, …. This is the first type of infinity that we will encounter — sets that are in bijection with \(\mathbb{N}\text{.}\) We call these sets denumerable because we can think of counting off the elements via the bijection.

Definition 12.2.1.

Let \(A\) be a set.
  • The set \(A\) is called denumerable if there is a bijection \(f: \mathbb{N} \to A\text{.}\)
  • The cardinal number of a denumerable set is denoted \(\aleph_0\) (read “aleph naught” or “aleph null”).
  • The set \(A\) is called countable if it is finite or denumerable.
  • The set \(A\) is uncountable if it is not countable.
Notice that
  • At this stage it is not clear that there is something out there that is “uncountable” — the existence of uncountable sets was highly controversial when Cantor proved it in 1874 176 .
  • There is a bijection from \(\mathbb{N} \) to \(A\) if and only if there is a bijection from \(A\) to \(\mathbb{N}\text{.}\)
  • Finally, a very nice property of denumerable sets is that even though they are infinite, we can still “list out the elements”.
This last point is both very important and also is a little counter-intuitive, so we’ll make it more precise. Consider a denumerable set \(A\text{.}\) By definition there is a bijection \(f: \mathbb{N} \to A\text{.}\) Now we can think of \(f\) as a relation
\begin{align*} f &= \set{(1,f(1)), (2,f(2)), (3,f(3)), \dots }\\ \end{align*}

Hence we can write \(A\) as

\begin{align*} A &= \set{f(1), f(2), f(3), \dots} & \text{or equivalently}\\ A &= \set{a_1, a_2, a_3, \dots} & \text{with } a_i = f(i). \end{align*}
Notice that this list has a couple of special properties.
  • Since \(f\) is injective, our list does not repeat — different indices give different elements of \(A\text{.}\)
  • Also, since \(f\) is surjective, any given element of \(A\) — say \(q\) — is mapped to by some integer \(n_q \in \mathbb{N}\text{.}\) Since \(n_q\) is finite, this means that any given element of \(A\) appears on the list in some finite position.
We can also go backwards — if we can list out the elements of some infinite set \(B\text{,}\) then \(B\) is denumerable. Say we have listed out our elements as \(\set{b_1,b_2,b_3,\dots}\text{,}\) so that
  • the list does not repeat, and
  • any given element of \(B\) appears at some finite position on the list.
Now we can define a function \(g:\mathbb{N} \to B\) by \(g(j) = b_j\text{.}\) That is, just map any natural number to the element at that position in the list. The two conditions we have placed on the list then mean that \(g\) is injective and surjective, so \(g\) is a bijection. Hence \(B\) is denumerable.
Let’s formalise this idea that denumerable means listable in a lemma. The proof is given by the argument above.
Let \(A\) be denumerable. Then, by definition, there exists a bijection \(f: \mathbb{N} \to A\text{.}\) For any \(n \in \mathbb{N}\text{,}\) define the \(n^\mathrm{th}\) element of our list to be \(a_n = f(n)\text{.}\) Then
  • Since \(f\) is injective, we know that for \(j \neq k\text{,}\) \(a_j = f(j) \neq f(k)=a_k\text{.}\) So the items on our list are distinct.
  • Since \(f\) is surjective, we know that for any \(x \in A\) there exists \(n \in \mathbb{N}\) so that \(f(n)=x\text{.}\) Thus the element \(x = a_n\) is the \(n^\mathrm{th}\) item on the list, and so appears at a finite position in the list.
Now assume such a list exists. Then for any \(n \in \mathbb{N}\) define \(g(n) = a_n \in A\text{.}\) Since the list is infinite this defines a function \(g: \mathbb{N} \to A\text{.}\) Then
  • Let \(x \in A\text{.}\) By assumption, the element \(x\) appears at some finite position in the list. So there is \(n \in \mathbb{N}\) so that \(x = a_n = g(n)\text{.}\) Thus \(g\) is surjective.
  • Since the list does not repeat we can take the items from the \(j^\mathrm{th}\) and \(k^\mathrm{th}\) positions on the list, namely \(a_j, a_k\) with \(j \neq k\text{.}\) Then we know that \(a_j \neq a_k\) which in turn gives \(g(j) \neq g(k)\text{.}\) Thus \(g\) is injective.
Hence there is a bijection \(g: \mathbb{N} \to A\) and so \(A\) is denumerable.
This infinite-but-listable way of looking at denumerable sets makes it much easier to work with them. Especially because, as we have seen with our even numbers example above, infinite sets are very counter-intuitive. Here is counter-intuitive result that is also a very important result.
We will sketch out how to prove this result but leave the formal proof to the reader. It suffices to find a “nice way” to list out all the elements of \(\mathbb{Z}\) (since this nice list is really a bijection). We can’t just do \(\mathbb{Z} = \set{\dots, -2,-1,0,1,2, \dots}\) — which each integer appears on the list, it is not clear that any given integer appears at some finite position in the list. This sort of infinite list is typically called bi-infinite, since it extends to infinity in both direction.
On the other hand, if we write out the integers as
\begin{align*} \mathbb{Z} &= \set{0,1,-1,2,-2,\dots} \end{align*}
then we can see that every integer will appear once, and that any given integer will appear at some finite position in the list. Indeed, this list, carefully described, is a proof of the result.
We can, in this case, make the bijection very explicit in this case and define a function
\begin{align*} f &= \begin{array}{cccccc} 1 & 2 & 3 & 4 & 5 & \cdots\\ \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \downarrow\\ 0 & 1 & -1 & 2 & -2 & \cdots \end{array} \end{align*}
With a bit of juggling this becomes
\begin{align*} f(n) &= \begin{cases} \frac{1-n}{2} & n \mbox{ is odd}\\ \frac{n}{2} & n \mbox{ is even} \end{cases} = \frac{1 + (-1)^n(2n-1)}{4} \end{align*}
It is not hard to show this is bijective — in fact, we’ll make this an exercise.
So again we have produced an example of a strict subset having the same cardinality: \(\mathbb{N} \subset \mathbb{Z}\) but \(|\mathbb{N}| = |\mathbb{Z}|\text{.}\) This is quite general; a subset of a denumerable set is either finite or itself denumerable.
Now this proof is a little fiddly around the edges so we’ll just give a proof sketch. Before we get started with the proof, consider the specific case of \(A\) being the set of positive odd numbers, and \(B\) being the set of odd prime numbers.
On the right-hand side of the figure we’ve drawn the set of odd primes, \(B\text{,}\) and the natural numbers and the bijection \(g\) between them. On the left-hand side we’ve given the set of odd numbers, \(A\) and next to it we’ve drawn the set of natural numbers \(\mathbb{N}\) and the bijection \(f\) between them. Notice that we’ve drawn some edges in red and some in green. The red edges correspond to the elements of \(A\) that are not in \(B\text{,}\) while the green edges correspond to the elements in \(A\) that are in \(B\text{.}\) Notice that the red edges stop, while the green edges trace through a set \(I\) (described in the proof sketch below), and then another copy of \(\mathbb{N}\) and then finally to the set \(B\text{.}\) Keep this picture in mind when you read the proof sketch below.
Let \(B\) be a subset of a denumerable set \(A\text{.}\)
  • If \(B\) is finite then we are done, because a finite set is countable.
  • Assume \(B\) is infinite. There is a bijection \(f: \mathbb{N} \to A\text{,}\) and we can write \(A = \{a_1,a_2,\dots \}\) and \(f(n) = a_n\text{.}\) Now define \(I = \{n \in \mathbb{N} \so a_n \in B\}\) — ie the indices of elements that are in \(B\text{.}\) Notice that \(I \subseteq \mathbb{N}\) and so we can write the indices in order 177 
    Hence we can write the set of these indices as \(I = \set{i_1, i_2, i_3, \dots}\text{.}\) Now define a function \(g: \mathbb{N} \to B\) by
    \begin{align*} g(n) &= a_{i_n} \end{align*}
    That is, for any input number \(n\text{,}\) look up the \(n^\mathrm{th}\) index in \(I\text{,}\) and then return that element of \(A\text{.}\) By construction that is an element of \(B\text{.}\)
    We can trace this though our odd-primes figure above. In that case \(g(3)=7\) because \(i_3 = 4\) and \(f(4)=7\text{.}\) Similarly, \(g(5) = 13\) since \(i_5=7\) and \(f(7)=13\text{.}\)
  • Now that we have this function, we need to prove it is bijective.
    • Injective — Assume that \(g(n)=g(m)\text{,}\) then \(a_{i_n} = a_{i_m}\text{.}\) Since the original function \(f\) is bijective, this implies that \(i_n=i_m\text{.}\) Hence \(n=m\text{.}\)
    • Surjective — Let \(b \in B\text{.}\) Then since \(B \subseteq A\text{,}\) we know \(b\in A\text{.}\) Since \(f\) is surjective, there is some \(n\) so that \(f(n)=a_n=b\text{.}\) Hence \(n \in I\text{.}\) Hence there is some \(1 \leq k \leq n\) so that \(g(k)=a_n=b\text{.}\)
  • Thus there is a bijection from \(\mathbb{N}\) to \(B\text{,}\) and so \(B\) is denumerable.
Let’s generalise our result above positive even numbers being in bijection with the naturals; we’ll also do Galileo’s paradox the same way. Using the above theorem we don’t have to establish explicit bijections, we just need to show that they are infinite subsets of a denumerable set.
Let \(k \in \mathbb{N}\text{.}\) Then above sets all subsets of \(\mathbb{Z}\text{.}\) Hence by the previous theorem they are countable. All of the sets are infinite, so they must be denumerable.
One can show that the union of denumerable sets is denumerable and that the Cartesian product is too.
It suffices to find a bijection from \(\mathbb{N}\) to \(A\times B\text{.}\) Since \(A\) and \(B\) are denumerable we can write \(A = \set{a_1,a_2,\dots}\) and \(B = \set{b_1,b_2,\dots}\text{.}\) Construct the following (infinite) table
\begin{align*} \begin{array}{c|cccc} & b_1 & b_2 & b_3 & \dots\\ \hline a_1 & (a_1,b_1) & (a_1,b_2) & (a_1,b_3) & \dots\\ a_2 & (a_2,b_1) & (a_2,b_2) & (a_2,b_3) & \dots\\ a_3 & (a_3,b_1) & (a_3,b_2) & (a_3,b_3) & \dots\\ \vdots & \vdots & \vdots & \vdots & \ddots \end{array} \end{align*}
We form the function \(f: \mathbb{N} \to A \times B\) by sweeping successive diagonals \(\swarrow \; \swarrow \; \cdots \text{.}\)
\begin{align*} f(1) &= (a_1,b_1)\\ f(2) &= (a_1,b_2) & f(3) &= (a_2,b_1)\\ f(4) &= (a_1,b_3) & f(5) &= (a_2,b_2) & f(6) &= (a_3,b_1)\\ f(7) &= (a_1,b_4) & f(8) &= (a_2,b_3) & f(9) &= (a_3,b_2) & f(10) &= (a_4,b_1) \end{align*}
and so forth. Since any given ordered pair is reached eventually (ie after a finite number of diagonal sweeps of finite length), the function is surjective. Since we never repeat an ordered pair, the function is injective. Thus \(f\) is bijective.
Notice that if we tried to list out the elements by reading out each column (or each row), then the resulting function would not be surjective — it would take an infinite time to reach the second column. Hence the preimage under that function of an element in the second column would not be a natural number.
Very similarly we arrive at the following very counter-intuitive result
Form the following table of positive rationals
\begin{align*} \begin{array}{c|cccc} & 1 & 2 & 3 & \dots\\ \hline 1 & 1/1 & 1/2 & 1/3 & \dots\\ 2 & 2/1 & 2/2 & 2/3 & \dots\\ 3 & 3/1 & 3/2 & 3/3 & \dots\\ \vdots & \vdots & \vdots & \vdots & \ddots \end{array} \end{align*}
List things out in the same sweeping diagonal order \(\swarrow \; \swarrow \; \cdots \) we used previously:
\begin{align*} \begin{array}{ccccc} \frac{1}{1}, \\[1ex] \frac{1}{2}, & \frac{2}{2}, \\[1ex] \frac{1}{3}, & \frac{2}{2}, & \frac{3}{1}, \\[1ex] \frac{1}{4}, & \frac{2}{3}, & \frac{3}{2}, & \frac{4}{1}, \\[1ex] \frac{1}{5}, & \frac{2}{4}, & \frac{3}{3}, & \frac{4}{2}, & \frac{5}{1},\\ \vdots \end{array} \end{align*}
This list gives a surjective function, since any given positive rational number would appear at some finite positive position on the list. For example, we have \(f(1)=\frac{1}{1}, f(2)=\frac{1}{2}, f(5)=\frac{2}{2}\text{,}\) and so on. However, the list repeats rationals, so it is not injective.
Thankfully this is quite easy to fix, we can simply skip those rationals that have already appeared 178 :
\begin{align*} \begin{array}{ccccc} \frac{1}{1}, & \\[1ex] \frac{1}{2}, & \frac{2}{1}, \\[1ex] \frac{1}{3}, & \cdot & \frac{3}{1}, \\[1ex] \frac{1}{4}, & \frac{2}{3}, & \frac{3}{2}, & \frac{4}{1}, \\[1ex] \frac{1}{5}, & \cdot & \cdot & \cdot & \frac{5}{1}, \end{array} \end{align*}
where we have used a dot to indicate a fraction we have skipped. Define \(f: \mathbb{N} \to \mathbb{Q}^+\) by \(f(n)\) is the nth term of the list. So \(f(1)=\frac{1}{1}, f(3)=\frac{2}{1}, f(5)=\frac{3}{1}, f(7)=\frac{2}{3}\) and so on.
Since every positive rational number appears on the list (at some finite position), \(f\) is surjective. Since no number is repeated, \(f\) is injective. Thus \(f\) is bijective and so \(|\mathbb{N}| = \mathbb{Q}^+\text{.}\)
We can also prove this result using our previous theorem, by constructing a bijection from \(\mathbb{Q}^+\) to an infinite subset of \(\mathbb{N}\times\mathbb{N}\text{.}\)
Recall that we can write any \(q \in \mathbb{Q}^+\) uniquely as \(\frac{a}{b}\) where \(a,b\) are natural numbers with no common divisors. Then we can define \(f:\mathbb{Q}^+ \to \mathbb{N}\times\mathbb{N}\) by
\begin{align*} f(q) \amp= (a,b) \amp \text{where } q=\frac{a}{b} \end{align*}
and \(a,b \in \mathbb{N}\) with no common divisors. We claim that this function is an injection.
Let \(p,q \in \mathbb{Q}^+\) so that \(p \neq q\text{.}\) Now if \(f(p)=f(q)=(a,b)\) we must have \(p=q=\frac{a}{b}\text{.}\) Thus we must have \(f(p) \neq f(q)\text{.}\)
The injection \(f\) can be specialised to a bijection \(\hat{f}: \mathbb{Q} \to \mathrm{rng}(f)\) by reducing its codomain to exactly the range of \(f\text{.}\) Since \(\mathrm{rng}(f)\) is an infinite subset of \(\mathbb{N}\times\mathbb{N}\text{,}\) it must be denumerable. Hence \(\mathbb{Q}^+\) is denumerable.
Now say that the above order gives
\begin{gather*} \mathbb{Q}^+ = \set{q_1,q_2,q_3,\dots}\\ \mathbb{Q}^- = \set{-q_1,-q_2,-q_3,\dots} \end{gather*}
Then we can write
\begin{align*} \mathbb{Q} &= \set{0} \cup \mathbb{Q}^+ \cup \mathbb{Q}^-\\ &= \set{0, q_1, -q_1, q_2, -q_2, \dots} \end{align*}
And so by using this sneaky way of listing the rationals, we get
This is really weird. While the natural numbers and the integers feel very similar; there are nice discrete unit steps between numbers. The rational numbers, however, appear to be very different objects. Most striking being that they are dense — between any two rationals we can find another rational number. But despite that, the rationals are the same size as the integers!
The trick we used above to prove this corollary is a good one and can be extended to a more general result:
  • The intersection \(A \cap B \subseteq A\text{,}\) so if \(A\) is finite then so is the intersection. While if \(A\) is denumerable, then our previous theorem tells us that all its subsets are countable. So we are done.
  • Now consider the union. Since \(A,B\) are countable, we can list out their elements as
    \begin{align*} A &= \set{a_1,a_2,a_3,\dots} & B &= \set{b_1,b_2,b_3,\dots} & \end{align*}
    Assume, for the moment that \(A\cap B = \es\text{.}\)
    • If both \(A,B\) are finite then their union is finite.
    • If both \(A,B\) are infinite, then write the union as
      \begin{align*} A \cup B &= \set{a_1, b_1, a_2, b_2, a_3, b_3, \dots} \end{align*}
      This listing of the elements of the union demonstrates that the union is denumerable.
    • If one of \(A,B\) is finite, but the other infinite, then we can write
      \begin{align*} A \cup B &= \set{a_1, b_1, a_2, b_2, a_3, b_3, \dots, a_n, b_n, a_{n+1}, a_{n+2}, a_{n+3}, \dots} & \text{ or}\\ A \cup B &= \set{a_1, b_1, a_2, b_2, a_3, b_3, \dots, a_\ell, b_\ell, b_{\ell+1}, b_{\ell+2}, b_{\ell+3}, \dots} \end{align*}
      depending on which of \(A,B\) are finite. This demonstrates that the union is denumerable.
    Thus the union of two disjoint countable sets is countable.
    Now assume that \(A \cap B \neq \es\text{,}\) then write \(C = B - A\text{,}\) so that
    \begin{equation*} C \subseteq B \qquad A \cap C = \es \qquad A\cup C = A \cup B. \end{equation*}
    These are quite straight-forward to prove:
    • If \(x \in C\) then \(x \in B-A\) and so \(x \in B\text{.}\)
    • Let \(x \in A\text{.}\) Then we must have that \(x \not\in B-A\text{,}\) and thus \(x \not\in C\text{.}\) Hence \(A\cap C\) must be empty.
    • Since \(C = B-A = B \cap \bar{A}\text{,}\) we have
      \begin{equation*} A \cup C = A \cup (B \cap \bar{A}) = (A \cup B) \cap (A \cup \bar{A}) = (A \cup B) \cap U = A \cup B \end{equation*}
      where \(U\) denotes the universal set.
    Now, since \(B\) is countable we know that \(C\) is countable. The reasoning used for disjoint sets above, then shows that \(A \cup C\) is countable, and thus \(A\cup B\) is countable.
It first appeared in an article called “On a Property of the Collection of All Real Algebraic Numbers”. He did not use his famous diagonal-argument (we do it a little later in the text); that argument appeared 17 years later in a 1891 paper titled “On an elementary question of the theory of manifolds.”
This bit actually requires a bit of thought — one can use the well-ordering principle to find the smallest thing in the set \(I\) and call it \(i_1\text{.}\)Then remove that from the set and find the next smallest, call it \(i_2\text{.}\) etc etc.
Notice that we do not have to be able to do this efficiently, we just need to be able to do it! Mind you, it is not too hard to work out that a given ratio \(\frac{a}{b}\) has already appeared on the list when \(a,b\) have a common divisor.
<Prev^TopNext>