Definition 6.2.1.
Two sets \(A\) and \(B\) have the same cardinality if there is a one-to-one, onto map from \(A\) to \(B\text{.}\) We call a one-to-one, onto map a one-to-one correspondence from \(A\) to \(B\text{.}\)
Section 6.2 Cardinality
In this section we will explore what it means for a set to be infinite and whether infinite sets such as the integers, the rational numbers, and the real numbers have the same “size”.
First, start with finite sets. The size of a finite set is the number of elements in the set. It may seem simple to determine the size of a set by just counting the elements. But suppose I have a bag of candy and a class of students. I could decide if I have enough candy by just counting the pieces and the students and seeing if I have more candy or students. But suppose I have a lot of candy and a lot of students. It might be faster just to start passing out the candy to the students. If I run out of candy, I have more students; if I run out of students, I have more candy. We will use this idea of matching up objects in two sets to define the size of a set and to decide which set is bigger.
We will use \(|A|\) to denote the cardinality if a set \(A\text{.}\)
Example 6.2.2. Finite Cardinality.
Let \(A=\{1, 2, 3, 4\}\text{.}\) Then \(|A|=4\text{.}\) Let \(B=\{2k : 1\leq k\leq 4, k\in \mathbb{Z}\}\text{.}\) Then \(|B|=4\text{.}\)
Activity 6.2.1. Sets of a Given Cardinality.
Give a set for each of the following cardinalities: 5, 1, 0.Two finite sets have the same cardinality if they have the same number of elements. But what about infinite sets?
Example 6.2.3. Cardinality of the Even Integers.
Let \(E\) be the set of even integers, \(E=\{2k : k\in \mathbb{Z}\}\text{.}\) Consider the map \(f:\mathbb{Z}\rightarrow E\) given by \(f(n)=2n\text{.}\) You can check that \(f\) is one-to-one and onto \(E\text{.}\) Thus, \(f\) gives us a one-to-one correspondence between the integers and the even integers. Hence, they have the same cardinailty.
Is Example 6.2.3 surprising? On one hand, it may seem surprising since the even integers is a proper subset of the integers, so it may seem like there are “more” integers then even integers (maybe even twice as many!). On the other hand, both sets have infinitely many elements, so since they both have infinite “size,” it may seem reasonable that the two sets have the same size. The idea behind the definition of cardinality is that the map gives us a way to match up elements in the two sets. Since they can be matched up exactly, the two sets must have the same size, or cardinality.
Definition 6.2.4.
A set is countably infinite if it has the same cardinailty as \(\mathbb{Z}^+\text{.}\) A set is countable if it is finite or countably infinite. Otherwise, a set is uncountable.
For the sake of notational simplicity in this section, we will use \(\mathbb{N}\) for the set of natural numbers, \(\{1, 2, 3, \ldots\}\text{,}\) rather than \(\mathbb{Z}^+\text{.}\) Thus, an infinite set is countable if it has the same cardinality as \(\mathbb{N}\text{.}\)
Example 6.2.5. The Integers are Countable.
To show \(|\mathbb{N}|=|\mathbb{Z}|\text{,}\) we need to find a way to match each integer with a natural number. Although we may be able to find an explicit formula, we do not need to. We just need a clear process for demonstrating a way to pair integers with natural numbers so that every integer gets assigned to a natural number, and no integers are assigned to the same natural number. We can see that we can't just assign \(n\in \mathbb{N}\) to \(n\in \mathbb{Z}\text{,}\) as we would never be able to assign the negative integers to a natural number. So we need to pick our correspondence more carefully. Consider the following “listing” of integers:
\begin{equation*}
0, 1, -1, 2, -2, 3, -3, \ldots
\end{equation*}
We can now assign each integer to its place in the list:
| \(\mathbb{N}\text{:}\) 1 | 2 | 3 | 4 | 5 | 6 | 7 | ... |
| \(\mathbb{Z}\text{:}\) 0 | 1 | -1 | 2 | -2 | 3 | -3 | ... |
Since there is a one-to-one correspondence between the natural numbers and the integers, \(|\mathbb{N}|=|\mathbb{Z}|\text{,}\) and \(\mathbb{Z}\) is countable.
Theorem 6.2.6.
Consider sets \(A, B\text{,}\) and the relation given by \((A, B)\in R\) if an only if \(|A|=|B|\text{.}\) In other words, we say two sets are related if they have the same cardinality. Then \(R\) is an equivalence relation.We leave it as an exercise to prove the cardinality relation is reflexive, symmetric, and transitive, and hence, and equivalence relation.
Theorem 6.2.6 is important, as we can now use it directly to show the set of even integers, \(E\text{,}\) is countable. Since \(|E|=|\mathbb{Z}|=|\mathbb{N}|\text{,}\) we have \(|E|=|\mathbb{N}|\text{.}\) Thus we can say \(E\) is countable without needing to find a specific correspondence between \(E\) and \(\mathbb{N}\text{.}\)
So what about the set of rational numbers, \(\mathbb{Q}\text{?}\) To show it is countable, we need to find a one-to-one correspondence with \(\mathbb{N}\text{.}\) As we saw in Example 6.2.5 is that it is enough to find a way to list the rational numbers. However, one of the properties of the rational numbers that makes this challenging is that between any two rational numbers, \(a, b\text{,}\) there is another rational number. We proved this in Example 5.1.2 by showing the average, \(\frac{a+b}{2}\) is between \(a\) and \(b\text{.}\) But since the average is also rational, there is another rational number between \(a\) and \(\frac{a+b}{2}\text{,}\) and so on. Thus, in fact, between any two rational numbers there are infinitely many rational numbers. So it would seem the rationals might be “larger” than \(\mathbb{N}\text{.}\)
Example 6.2.7. The Positive Rational Numbers are Countable.
To show the rational numbers are countable, we need to rely on a clever way to list them. To simplify our proof, we first just show the positive rational numbers are countable. Recall a number is rational if it can be written as \(\frac{a}{b}\) with \(a, b\in \mathbb{Z}, b\neq 0\text{.}\) Since we just want positive rational numbers, we can assume \(a, b\in \mathbb{Z}^+\text{.}\) Now we make a table with columns for \(b=1, 2, 3, \ldots\) and rows for \(a=1, 2, 3\ldots\text{,}\) and the corresponding fraction \(\frac{a}{b}\) as entries.
| \(\frac{1}{1}\) | \(\frac{1}{2}\) | \(\frac{1}{3}\) | \(\frac{1}{4}\) | \(\frac{1}{5}\) | ... |
| \(\frac{2}{1}\) | \(\frac{2}{2}\) | \(\frac{2}{3}\) | \(\frac{2}{4}\) | \(\frac{2}{5}\) | ... |
| \(\frac{3}{1}\) | \(\frac{3}{2}\) | \(\frac{3}{3}\) | \(\frac{3}{4}\) | \(\frac{3}{5}\) | ... |
| \(\frac{4}{1}\) | \(\frac{4}{2}\) | \(\frac{4}{3}\) | \(\frac{4}{4}\) | \(\frac{4}{5}\) | ... |
| \(\frac{5}{1}\) | \(\frac{5}{2}\) | \(\frac{5}{3}\) | \(\frac{5}{4}\) | \(\frac{5}{5}\) | ... |
| ... | ... | ... | ... | ... | ... |
We can see that the table contains every positive rational number, though many are repeated. For example, \(1=1/1=2/2=3/3\text{,}\) etc. If we start trying to make our list of rational numbers by starting at \(1/1\) and just moving along the row, we we never make it to row 2, since there are infinitely many elements in row 1. Similarly, if we start at \(1/1\) and move down the column, we will never make it to column 2. So instead we are going to make a serpentine pattern through the table, as follows:
- start in the upper left corner with \(\frac{1}{1}\text{,}\)
- move right to \(\frac{1}{2}\text{,}\)
- move diagonally down to \(\frac{2}{1}\text{,}\)
- move down to \(\frac{3}{1}\text{,}\)
- move diagonally up to \(\frac{2}{2}\text{,}\) and then \(\frac{1}{3}\text{,}\)
- repeat the process, moving right one, then diagonally down to the first column,
- then move down one and then diagonally up to the first row.
The pattern can be seen in the following figure.
As you trace through the diagonal pattern, you will see that you will be able to include every element of the table, eventually. Since we don't actually want to count repeated rational numbers, we could just skip any numbers that we have already included.
Since it is possible to list the elements in one-to-one correspondence with \(\mathbb{N}\text{,}\) the positive rational numbers are countable and \(|\mathbb{Q}^+|=|\mathbb{N}|\text{.}\)
Activity 6.2.2. Extending to All Rational Numbers.
Extend the argument used in Example 6.2.7 to include all of the rational numbers. Can you adjust the table to include 0? Can you adjust it to include the negative rational numbers?
We have seen that \(|\mathbb{Q}|=|\mathbb{Z}|=|\mathbb{N}|\text{,}\) so maybe every infinite set really does have the same size. Are there any sets that are uncountable?
Theorem 6.2.9.
The interval \([0, 1]\) of real numbers is uncountable.Before proving the theorem, we will explore the main idea of the proof in the following activity.
Activity 6.2.3. Unlistable Elements.
To get an understanding of the construction used in the proof of Theorem 6.2.9, we will look at a very specific example.
(a)
Consider the following list of numbers:
\begin{equation*}
0.1112345
\end{equation*}
\begin{equation*}
0.00083576
\end{equation*}
\begin{equation*}
0.99999999
\end{equation*}
\begin{equation*}
0.12000000
\end{equation*}
Now, construct a new number, \(d=0.d_1d_2d_3\ldots\text{,}\) where we change the \(i\)th digit after the decimal in the \(i\)th number in the list and use the new number in the \(i\)th position of \(d\text{.}\) For example, the first digit in \(0.1112345\) is a 1, so make that a new number, like 2. The second digit in \(0.00083576\) is 0, make that a 2. Now \(d=0.22\ldots\text{.}\)
Give an example of \(d\) by changing the \(i\)th digit of each number in the list.
(b)
We need some better notation for our list and our new number \(d\text{.}\) We will use a double subscript, \(a_{ij}\) where \(i\) represents which number in the list and \(j\) represents the decimal position. For example, from our above list
\begin{equation*}
0.1112345=0.a_{11}a_{12}a_{13}\ldots
\end{equation*}
\begin{equation*}
0.00083576=0.a_{21}a_{22}a_{23}\ldots
\end{equation*}
\begin{equation*}
0.99999999=0.a_{31}a_{32}a_{33}\ldots
\end{equation*}
What digit is \(a_{24}\text{?}\) How about \(a_{42}?\)
(c)
Now define our new number \(d=0.d_1d_2d_3\ldots\) by \(d_i=1\) if \(a_{ii}\neq 1\text{;}\) otherwise, \(d_i=2\text{.}\) Find \(d\) for the list in (a).
(d)
Make your own list of at least 6 decimals between 0 and 1, each with at least 6 decimal places and find the corresponding \(d\text{,}\) using the rule in (c).
(e)
Explain why your \(d\) must be different from every decimal on your list.
The key idea explored in Activity 6.2.3 is that if we create a list of decimals, \(0.a_{i1}a_{i2}a_{i3}\ldots\) then by changing the digit in the \(a_{ii}\) position, we will always get a decimal that is not on our list, as it will differ from each number on the list by at least one digit.
Example 6.2.10. Finding \(d\).
To clarify the process further, here is an example of finding \(d\) for a specific list. Given a list of \(0.a_{i1}a_{i2}a_{i3}\ldots\text{,}\) find \(d=d_1d_2d_3\ldots\text{,}\) using the rule
\begin{equation*}
d_1=\begin{cases}
1 & \text{ if } a_{ii}\neq 1;\\
2 & \text{ if } a_{ii}=1.
\end{cases}
\end{equation*}
Find \(d\) for the following list.
\begin{equation*}
0.{\color{blue}{1}}38756645
\end{equation*}
\begin{equation*}
0.1{\color{blue}{1}}1111111
\end{equation*}
\begin{equation*}
0.99{\color{blue}{9}}999999
\end{equation*}
\begin{equation*}
0.010{\color{blue}{1}}01010
\end{equation*}
\begin{equation*}
0.1231{\color{blue}{2}}3123
\end{equation*}
\begin{equation*}
0.98765{\color{blue}{4}}321
\end{equation*}
\begin{equation*}
0.223355{\color{blue}{7}}70
\end{equation*}
\begin{equation*}
0.1230000{\color{blue}{0}}0
\end{equation*}
Note, the blue digits are the ones we are considering for \(d\text{.}\) Since \(a_{11}=1, d_1=2\text{.}\) Since \(a_{22}=1, d_2=2\text{.}\) Since \(a_{33}=9, d_3=1\text{.}\) Continuing in this way, we get \(d=0.22121111\text{.}\) Clearly, \(d\) differs from each decimal on the list.
One last idea before beginning the proof, make sure you understand that every real number in \([0, 1]\) can be represented by a decimal of the form \(0.a_{i1}a_{i2}a_{i3}\ldots\) with infinitely many decimal places. This should be clear if the decimal is repeating or nonterminating, nonrepeating. If the decimal is terminating, we can just add infinitely many 0's. We also note that \(0=0.000000000\ldots\) and \(1=0.99999999\ldots\) (see Section 3.2 for how to prove this).
Now that we have a way to write a list of numbers in \([0, 1]\) as decimals, and we have a understanding of a way to construct a new number not on our list, we are ready to prove Theorem 6.2.9.
Proof.
We will prove this by contradiction. Assume \([0, 1]\) is countable. That means there is a one-to-one correspondence between \(\mathbb{N}\) and \([0, 1]\text{.}\) We don't need to know what it is, just that it exists. Since there is a one-to-one correspondence, there is a way to list the elements of \([0, 1]\text{.}\) First, note that every real number has a decimal representation, and since our elements are less than or equal to one, each real number can be represented by \(0.a_{i1}a_{i2}a_{i3}\ldots\text{.}\) Thus, we can write our list as
\begin{equation*}
b_1=0.a_{11}a_{12}a_{13}\ldots
\end{equation*}
\begin{equation*}
b_2=0.a_{21}a_{22}a_{23}\ldots
\end{equation*}
\begin{equation*}
b_3=0.a_{31}a_{32}a_{33}\ldots
\end{equation*}
\begin{equation*}
\vdots
\end{equation*}
Since we assumed we had a listing of every real number in \([0, 1]\text{,}\) every such decimal must be on our list.
Now define
\begin{equation*}
d_1=\begin{cases}
1 & \text{ if } a_{ii}\neq 1;\\
2 & \text{ if } a_{ii}=1.
\end{cases}
\end{equation*}
We can see that for every \(n\text{,}\) \(d\neq b_n\) since it differs in the \(n\)th decimal place. Thus \(d\) is not on our list. This is a contradiction since we assumed we were able to include every real number in \([0, 1]\) on our list. Hence, \([0, 1]\) is not countable.
We finally have an infinite set that has a different cardinality from \(\mathbb{N}\text{.}\) Since \([0, 1]\) is a subset of \(\mathbb{R}\text{,}\) that means \(\mathbb{R}\) is uncountable, too.
Exercises Exercises
1.
Prove the set of perfect squares, \(S=\{n^2 : n\in \mathbb{Z}\}\text{,}\) has the same cardinaility as \(\mathbb{N}\) by finding a one-to-one correspondence from \(\mathbb{N}\) to \(S\text{.}\)
2.
Prove Theorem 6.2.6, that the cardinality relation is an equivalence relation.
3.
Show that the intervals \([0, 1]\) and \([3, 6]\) have the same cardinality by finding a one-to-one correspondence between the sets.
Hint.
Can you find a line segment whose inputs are \([0, 1]\) and outputs are \([3, 6]\text{?}\) Then show your line is one-to-one and onto.
4.
Assume \(a, b, c, d\in \mathbb{R}\) with \(a < b\) and \(c < d\text{.}\) Show that the intervals \([a, b]\) and \([c, d]\) have the same cardinality by finding a one-to-one correspondence between the sets.
Hint.
Can you find a line segment whose inputs are \([a, b]\) and outputs are \([c, d]\text{?}\) Then show your line is one-to-one and onto.
5.
Let \(A\) and \(B\) be countable sets. Prove \(A\cup B\) is countable.
6.
Determine if the following are true or false. Justify your answer.
- A finite union of countable sets, \(\bigcup_{i=1}^{n}A_i\text{,}\) is countable.
- A countable union of countable sets, \(\bigcup_{i=1}^{\infty}A_i\text{,}\) is countable.
- The union of a countable set and an uncountable set in uncountable.
- The set of irrational numbers is countable.
- The set of prime numbers is countable.
