We introduce the terminology for speaking about the number of elements in a set, called the cardinality of the set. In the video in Figure 9.1 we give a intuitive introduction and a formal definition of cardinality. More details can be found below.
Figure9.1.Definition of Cardinality by Matt Farmer and Stephen Steward
In the example below we illustrate the properties that we would want a precise definition of cardinality to have.
Example9.2.What should the cardinalities of sets be ?
We discuss possible cardinalities of some sets.
The empty set \(\{\}\) contains no elements, so its cardinality should be \(0\text{.}\)
The set \(\{\mathtt{m}\}\) contains one element, namely the character \(\mathtt{m}\text{,}\) so its cardinality should be \(1\text{.}\)
The set \(\{\mathtt{m},\mathtt{a}\}\) contains two (distinct) elements, namely the characters \(\mathtt{m}\) and \(\mathtt{a}\text{,}\) so its cardinality should be \(2\text{.}\)
The set \(\{1,2,3,4,5\}\) contains five (distinct) elements, namely the numbers \(1\text{,}\)\(2\text{,}\)\(3\text{,}\)\(4\text{,}\) and \(5\text{,}\) so its cardinality should be \(5\text{.}\)
We start with a definition of the cardinality of the empty set.
Definition9.3.
The cardinality of the empty set \(\{\}\) is \(0\text{.}\)
We write \(\#\{\}=0\) which is read as “the cardinality of the empty set is zero” or “the number of elements in the empty set is zero.”
We have the idea that cardinality should be the number of elements in a set. This works for sets with finitely many elements, but fails for sets with infinitely many elements. We approach cardinality in a way that works for all sets. First we define when we consider two sets to have the same cardinality. Certainly two sets \(A\) and \(B\) have the same number of elements if we can pair each element in \(A\) with an element in \(B\) such that each element of \(A\) is in exactly one pair and each element of \(B\) is in exactly one pair. These pairs define an invertible function from \(A\) to \(B\text{.}\) This observation yields our definition of equality of cardinality.
Definition9.4.
Let \(A\) and \(B\) be non-empty sets. The sets \(A\) and \(B\) have the same cardinality means that there is an invertible function \(f:A\to B\text{.}\)
This definition does not specify what we mean by the cardinality of a set and does not talk about the number of elements in a set. This will come in handy, when we consider the cardinality of infinite sets in the next section.
Example9.5.\(\{0,1,2,3,4\}\) and \(\{\mathtt{a},\mathtt{e},\mathtt{i},\mathtt{o},\mathtt{u}\}\) have the same cardinality.
We show that the two sets \(\Z_5=\{0,1,2,3,4\}\) and \(V=\{\mathtt{a},\mathtt{e},\mathtt{i},\mathtt{o},\mathtt{u}\}\) have the same cardinality.
To show that \(\Z_5\) and \(V\text{,}\) by Definition 9.4, we need to find an invertible function \(f:\Z_5\to V\text{.}\) Consider the function \(f:\Z_5\to V\) given by:
\(x\)
\(0\)
\(1\)
\(2\)
\(3\)
\(4\)
\(f(x)\)
\(\mathtt{a}\)
\(\mathtt{e}\)
\(\mathtt{i}\)
\(\mathtt{o}\)
\(\mathtt{u}\)
Inspecting the table we see that the function \(f\) is invertible. In particular, the inverse of \(f^{-1}\) of \(f\) is given by:
\(y\)
\(\mathtt{a}\)
\(\mathtt{e}\)
\(\mathtt{i}\)
\(\mathtt{o}\)
\(\mathtt{u}\)
\(f^{-1}(y)\)
\(0\)
\(1\)
\(2\)
\(3\)
\(4\)
By presenting an invertible function \(f:\Z_5\to V\) we have proven that the sets \(\Z_5\) and \(V\) have the same cardinality.
Note that in our proof we could also have used the function \(f^{-1}:V\to\Z_5\) or any other invertible function between the two functions, since Definition 9.4 only requires the existence of any invertible function.
Often it is easier to show that two sets have the same cardinality than showing that they do not have the same cardinality, because it is easier to proof the existence of such a function by simply presenting on than proving that there is no such function.
Example9.6.\(\{0,1,2\}\) and \(\{\mathtt{s},\mathtt{t}\}\) do not have the same cardinality.
We show that the two sets \(\Z_3=\{0,1,2\}\) and \(U=\{\mathtt{s},\mathtt{t}\}\) do not have the same cardinality by showing that there is no invertible function from \(\Z_3\) to \(U\text{.}\)
Let \(f:\Z_3\to U\text{.}\) Then \(f(0)\in U\) and \(f(1)\in U\) and \(f(2)\in U\text{.}\) As we want \(f\) to be invertible no two of \(f(0)\) and \(f(1)\) and \(f(2)\) can be the same. As \(U\) only contains the elements \(\mathtt{s}\) and \(\mathtt{t}\) this is impossible. Namely if \(f(0)\ne f(1)\) we either have
\begin{equation*}
f(0)=\mathtt{s}\text{ and }f(1)=\mathtt{t}
\end{equation*}
or
\begin{equation*}
f(0)=\mathtt{t}\text{ and }f(1)=\mathtt{s}
\end{equation*}
Since the codomain \(U\) only contains \(\mathtt{s}\) and \(\mathtt{t}\) the image \(f(2)\) has to be either \(\mathtt{s}\) and \(\mathtt{t}\text{,}\) which means that we must have either \(f(2)=f(0)\) or \(f(2)=f(1)\text{.}\) This means that \(f\) cannot be invertible.
The principle used in Example 9.6 can be also be applied when the sets have more elements.
Example9.7.\(\N\) and \(\{\mathtt{s},\mathtt{t}\}\) do not have the same cardinality.
We show that the set of natural numbers \(\N=\{1,2,3,\dots\}\) and \(U=\{\mathtt{s},\mathtt{t}\}\) do not have the same cardinality by showing that there is no invertible function from \(\N\) to \(U\text{.}\)
Let \(f:\N\to U\text{.}\) Then \(f(1)\in U\) and \(f(2)\in U\) and \(f(2)\in U\) and so on. As we want \(f\) to be invertible no two of \(f(1)\) and \(f(2)\) and \(f(3)\) and so on can be the same. As \(U\) only contains the elements \(\mathtt{s}\) and \(\mathtt{t}\) this is impossible. Namely if \(f(1)\ne f(2)\) we either have
\(f(1)=\mathtt{s}\) and \(f(2)=\mathtt{t}\) or
\(f(1)=\mathtt{t}\) and \(f(2)=\mathtt{s}\)
Since the codomain \(U\) only contains \(\mathtt{s}\) and \(\mathtt{t}\) the image \(f(3)\) has to be either \(\mathtt{s}\) and \(\mathtt{t}\text{,}\) which means that we must have either \(f(3)=f(1)\) or \(f(3)=f(2)\text{.}\) This means that \(f\) cannot be invertible.
If, in Definition 9.4 the set \(B\) can be chosen as one of the sets \(\Z_n\text{,}\) we use this to define the cardinality of the set \(A\text{.}\)
Definition9.8.
Let \(A\) be a set. If there is \(n\in \N\) such that \(A\) and \(\Z_n\) have the same cardinality, we say that the cardinality of \(A\) is \(n\) and write \(\#A=n\text{.}\)
We read \(\#A=n\) as “the cardinality of \(A\) is \(n\)” or “the number of elements of \(A\) is \(n\text{.}\)”
When we follow the definition of cardinality to show that a set has a certain cardinality, we use a backwards approach. Using our intuition of cardinality we count the number of elements in the set. Assume that we have counted \(n\) elements. To prove that the cardinality of the set is \(n\) we construct an invertible function from the set to \(\Z_n\text{.}\)
Example9.12.Cardinality of \(\{\mathtt{m},\mathtt{a},\mathtt{t},\mathtt{h}\}\).
Let \(B=\{\mathtt{m},\mathtt{a},\mathtt{t},\mathtt{h}\}\text{.}\) We count \(4\) elements and now apply Definition 9.8 to show that \(\#B=4\text{.}\) Let \(f:B\to \Z_4\) given by:
As the function \(f\) is invertible, the cardinality of \(B\) is \(4\text{.}\)
In Checkpoint 9.13 find \(n\in\N\) such that there is an invertible function from \(\{0,1,2,\dots,n\}\) to a given set and use this information to determine the cardinality of that set.
Checkpoint9.13.Find cardinality.
Let \(Z=\lbrace 24,25,26,\dots,32\rbrace\text{.}\)
We revisit the examples from the beginning of this section.
Example9.14.Applying the definition of cardinality.
We give the cardinalities of some sets. In all but the first example we list an invertible function whose existence gives the cardinality of the set. This function in most cases is not unique, we only need to know that such a function exists.
\(\#\{\mathtt{m}\}=1\text{,}\) because the function \(f:\{\mathtt{m}\}\to\Z_1\) given by \(f(\mathtt{m})=0\) is invertible (recall that \(\ZZ_1=\{0\}\)).
\(\#\{\mathtt{m},\mathtt{a}\}=2\text{,}\) because the function \(f:\{\mathtt{m},\mathtt{a}\}\to\Z_2\) given by \(f(\mathtt{m})=0\) and \(f(\mathtt{a})=1\) is invertible.
Note that we can use any invertible function from \(\{\mathtt{m},\mathtt{a}\}\) to \(\Z_2\) to show that \(\#\{\mathtt{m},\mathtt{a}\}=2\text{.}\) In this case there is only one other invertible function, namely \(g:\{\mathtt{m},\mathtt{a}\}\to\Z_2\) given by \(g(\mathtt{m})=1\) and \(g(\mathtt{a})=0\text{.}\)
\(\#\{1,2,3,4,5\}=5\text{,}\) because the function \(f:\{1,2,3,4,5\}\to\Z_5\) given by \(f(1)=0\text{,}\)\(f(2)=1\text{,}\)\(f(3)=2\text{,}\)\(f(4)=3\text{,}\) and \(f(5)=4\) is invertible.
Note that we can use any invertible function from \(\{1,2,3,4,5\}\) to \(\Z_5\) to show that \(\#\{1,2,3,4,5\}=5\text{.}\) For example, \(g:\{1,2,3,4,5\}\to\Z_5\) given by \(f(1)=1\text{,}\)\(f(2)=2\text{,}\)\(f(3)=3\text{,}\)\(f(4)=4\text{,}\) and \(f(5)=0\text{.}\)
In practice, for many sets, we do not need to find such an invertible function \(f\) to determine the cardinality of the set. Often counting the element suffices.
Example9.15.Cardinalities of some sets.
We give the cardinality of some other sets.
\(\displaystyle \nr{\{\}}=0\)
\(\displaystyle \nr{\{1,2,3,4\}}=4\)
\(\displaystyle \nr{\{x\mid x\in\N \text{ and } x\lt 100\}} = 99\)
