Definition 4.1.1.1.
Two sets \(A\) and \(B\) have the same cardinality, denoted \(\size{A} = \size{B}\) if there is a bijection from \(A\) to \(B\text{.}\)
Subsection 4.1.1 Cardinality
The above lets us state precisely what it means to count something.
Definition 4.1.1.2.
Let \(A\) be a set. If there exists a natural number \(n\) such that there is a bijection \(c \colon A \to \{1, 2, \dots, n\}\) then we call \(A\) finite.
To count the elements of \(A\) means to construct such a bijection \(c\text{.}\) When we have such a bijection \(c\) then \(n=\size{A}\) is the cardinality of \(A\text{.}\)
Recall that the cardinality of a finite set is defined earlier in Definition 2.1.3.1. This definition of counting is exactly what we show children when we teach them to count to answer “how many” type questions, though not in this language. Specifically, we teach them to construct a bijection in order to find the size of a set. For example, imagine teaching a child to count the number of hearts (\(\heartsuit\)) shown below:
\begin{equation*}
\heartsuit \quad \heartsuit \quad \heartsuit \quad
\heartsuit \quad \heartsuit \quad \heartsuit \quad
\heartsuit \quad \heartsuit \quad \heartsuit \quad
\heartsuit \quad \heartsuit \quad \heartsuit \quad \heartsuit \quad
\heartsuit
\end{equation*}
Most likely, you pointed to each heart, one-by-one, and recited: “one, two, three, four, \dots, thirteen, fourteen.” In doing so, you created a bijection between the set of hearts and \(\{1, 2, \dots, 14\}\text{.}\) From this, you cam deduce that there are \(14\) hearts.
Notice that we do not need to have constructed the same bijection in order to get the right number for the cardinality. The key point is that we create a function that is both injective and surjective. Do you see why?
We can generalize the definition for counting and cardinality to include some infinite sets. An infinite set is any set that is does not have a finite cardinality. It turns out, there are different sizes of infinity.
Definition 4.1.1.3.
A countable set is either finite or has the same cardinality as the set of positive integers. An uncountable set is any set that is not countable.
Notice that this gives at least two different “sizes” for infinite sets. Some sets are infinite, but we can count them by constructing a bijection to the positive integers. Other infinite sets are so large that we cannot even construct such a bijection to the positive integers.
Example 4.1.1.4. The set of integers is countable.
The set of integers \(\ZZ\) is a countable set. To show this, we need to construct a bijection from \(\ZZ\) to \(\{1,2,\dots\}\text{.}\) Consider the function \(f \colon \ZZ \to \{1,2,\dots\}\) defined by
\begin{equation*}
f(x) =
\begin{cases}
2x + 1 \amp \text{ if }x\geq 0,\\
-2x \amp \text{ if }x \lt 0.
\end{cases}
\end{equation*}
So \(f(0) = 1\text{,}\) \(f(1) = 3\text{,}\) \(f(3) = 7\text{,}\) \dots, and \(f(-1) = 2\text{,}\) \(f(-2)
= 4\text{,}\) \(f(-3) = 6\text{,}\) \dots. In other words, \(f\) sends the nonnegative integers to the odd integers, and the negative integers are sent to the even integers.
Let’s show that \(f\) is bijective. First, to see that \(f\) is surjective, fix a generic element \(n\) in \(\{1,2,\dots\}\text{.}\) If \(n\) is even, then \(-\frac{n}{2}\) is a negative integer, and so
\begin{equation*}
f(-\frac{n}{2}) = -2(-\frac{n}{2}) = n.
\end{equation*}
If \(n\) is odd, then \(\frac{n - 1}{2}\) is a non-negative integer, and so
\begin{equation*}
f(\frac{n-1}{2}) = 2(\frac{n-1}{2}) + 1 = n.
\end{equation*}
Thus \(f\) is surjective.
To see \(f\) is injective, fix generic integers \(a\) and \(\ah\) such that \(f(a) = f(\ah)\text{.}\) If \(f(a)\) is even, then \(f(\ah)\) is also even, and so both \(a\) and \(\ah\) are negative. Then \(f(a) = -2a\text{,}\) and \(f(\ah) =
-2\ah\text{.}\) Since \(f(a) = f(\ah)\text{,}\) we have \(-2a = -2\ah\) so \(a = \ah\text{.}\) Now suppose \(f(a)\) is odd. Then \(f(\ah)\) is also odd, and so both \(a\) and \(\ah\) are nonnegative. Then \(f(a) = 2a + 1\text{,}\) and \(f(\ah) = 2\ah +
1\text{.}\) Since \(f(a) = f(\ah)\text{,}\) we have \(2a + 1 = 2 \ah + 1\) so \(a =
\ah\text{.}\) Thus \(f\) is injective.
Warning 4.1.1.5.
Example 4.1.1.4 is a bit counterintuitive. It shows that \(\ZZ\) can be put in bijection with a proper subset of itself. In particular,
\begin{equation*}
\ZZ=\{\dots,-3,-2,-1,0,1,2,3,\dots\}
\end{equation*}
has the same size as
\begin{equation*}
\NN=\{1,2,3,\dots\}\text{.}
\end{equation*}
This hints at some of the strange things that can happen with counting infinite sets.
Since the inverse of a bijective function is bijective, we can show an infinite set is countable by constructing a bijection from the set of positive integers to the set. Such a bijection is a sequence that includes all of the elements of \(A\text{,}\) listed with no repeats. In other words, an infinite set is countable if and only if it is possible to list all of the elements in a sequence with no repeats. In fact, we can relax the “no repeats” part, since if we do have a sequence with repeats, we can easily extract a subsequence without repeats.
For example, if we are given the sequence
\begin{equation*}
1, 2, 3, 4, 5, 5, 6, 7, 7, 8, 9, 9, 10, \dots
\end{equation*}
we instead consider the sequence
\begin{equation*}
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, \dots.
\end{equation*}
In Example 4.1.1.4 that shows the set of integers is countable, the sequence that is inverse the bijection given is
\begin{equation*}
0,-1,1,-2,2,-3,3,\dots.
\end{equation*}
Sometimes it is easier to think of a sequence instead of a formula for the function. Since the composition of bijective functions is bijective, to show an infinite set \(A\) is countable it is enough to find a bijection from \(A\) to \(\ZZ\text{.}\) If we have such a bijection, we compose it with the bijection from \(\ZZ\) to \(\{1,2,\dots\}\) given in Example 4.1.1.4 to get the desired bijection from \(A\) to \(\{1,2,\dots\}\text{.}\) Using this idea, it is clear that the set of even integers \(2\ZZ\) is countable, since \(f \colon 2\ZZ \to \ZZ\) given by \(f(x) = \frac{x}{2}\) is a bijection from \(2\ZZ\) to \(\ZZ\text{.}\) A similar argument shows the set of odd integers is countable.
What about the set of rational numbers? Surely there are more rational numbers than integers? It turns out, the set of rational numbers is also countable.
Theorem 4.1.1.6.
The set of rational numbers is countable.
Proof.
It suffices to show the set of positive rational numbers is countable. (Why? Exercise.)
Every positive rational number is the quotient \(\frac{p}{q}\) of two positive integers \(p\) and \(q\text{.}\) We arrange the positive rational numbers by listing those with denominator \(q = 1\) in the first row, those with denominator \(2\) in the second row, and so on. The rational numbers with denominator \(k\) are listed in the \(k\) th row, as shown in Figure 4.1.1.7. From the figure, we create a sequence by looking at the diagonals: list \(\frac{p}{q}\) with \(p + q = 2\text{,}\) followed by those with \(p + q = 3\text{,}\) followed by with \(p + q = 4\text{,}\) and so on as shown in Figure 4.1.1.7. The numbers we keep for the sequence are circled. The uncircled numbers are those we leave out because they are already listed. Because all the positive rational numbers are listed once. we hove show the set of positive integers is countable. The exercise completes the proof by extending this bijection to a bijection from \(\ZZ\) to \(\QQ\text{.}\)
One may start to think that every infinite set is countable. In fact, there are sets that are larger. In 1879, Georg Cantor produced a proof using a technique now known as the Cantor diagonalization argument, that proves the set of real numbers is not countable.
Theorem 4.1.1.8.
The set of real numbers is uncountable.
Proof.
It suffices to prove that the open interval \((0,1)=\{x\given (0\lt x)\land(x\lt 1)\}\) is uncountable. We prove this by contradiction. Suppose the interval \((0,1)\) is countable. Then there exists a bijective function \(c:\NN\to (0,1)\). Write the images of \(c\) as
\begin{align*}
c(1) \amp =0.c_{1,1}c_{1,2}c_{1,3}c_{1,4}c_{1,5}\dots \\
c(2) \amp =0.c_{2,1}c_{2,2}c_{2,3}c_{2,4}c_{2,5}\dots \\
c(3) \amp =0.c_{3,1}c_{3,2}c_{3,3}c_{3,4}c_{3,5}\dots \\
\vdots \amp \quad \quad\vdots
\end{align*}
where for \(i\in\NN\) the decimal expansion of \(c(i)\) is
\begin{equation*}
c(i)=0.c_{i,1}c_{i,2}c_{i,3}c_{i,4}c_{i,5}\dots \text{ with }c_{i,j}\in\{0,1,2,\dots,9\}
\text{ for }j\in\NN.
\end{equation*}
By assumption, the image \(c(\NN)\) of \(c\) contains every real number in the interval \((0,1)\text{.}\) To reach a contradiction, it suffices to produce a real number in the interval \((0,1)\) that is provably not in \(c(\NN)\text{.}\) Consider the number
\begin{equation*}
d = 0.d_{1}d_{2}d_{3}d_{4}d_{5}\dots \in (0,1),
\end{equation*}
where \(d_j\) is defined by
\begin{equation*}
d_j =
\begin{cases}
3 \amp \text{ if }c_{j,j} \neq 3,\\
4 \amp \text{ if }c_{j,j} = 3.
\end{cases}
\end{equation*}
We have that \(d \neq c(1)\text{,}\) since they differ in the first digit after the decimal, \(d_1 \neq c_{1,1}\text{.}\) Similarly, \(d \neq c(2)\text{,}\) since they differ in the second digit after the decimal, \(d_2 \neq c_{2,2}\text{,}\) and so on. In general, \(d\) cannot be equal yo \(c(k)\) since \(d_k \neq c_{k,k}\text{.}\) See the boxed digits below:
\begin{align*}
c(1) \amp =0.\fbox{\(c_{1,1}\)}c_{1,2}c_{1,3}c_{1,4}c_{1,5}\dots \\
c(2) \amp =0.c_{2,1}\fbox{\(c_{2,2}\)}c_{2,3}c_{2,4}c_{2,5}\dots \\
c(3) \amp =0.c_{3,1}c_{3,2}\fbox{\(c_{3,3}\)}c_{3,4}c_{3,5}\dots \\
\vdots \amp \quad \quad\vdots
\end{align*}
In other words, \(d\) is not in the image of \(c\text{.}\) This contradicts the assumption that \(c(\NN)=(0,1)\text{.}\) Thus there is no such bijective function, and hence the interval \((0,1)\) is uncountable. It follows that the set of real numbers is uncountable.
Warning 4.1.1.9.
There is a subtle point that not every real number has a unique decimal representation. For example, \(0.5000\dots\) is the same real number as \(0.4999\dots\text{.}\) We avoid this issue by choosing \(d\) to have digits only involving \(3\) and \(4\) to be sure we are producing a number that has only one representation, so that we can be sure it is not in the sequence.
