Definition of Cardinality

Section 9.1 Definition of Cardinality

We introduce the term cardinality for the number of elements in a set. The video in Figure 9.1.1 gives an intuitive introduction and a formal definition of cardinality. More details follow below.

🔗

Figure 9.1.1. Definition of Cardinality by Matt Farmer and Stephen Steward

🔗

The next example shows the properties that a precise definition of cardinality should have.

🔗

Example 9.1.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.

🔗

Definition 9.1.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.”

🔗

Cardinality should tell us the number of elements in a set. This idea works for sets with finitely many elements, but not for sets with infinitely many elements. We need an approach that works for all sets. First, we define when two sets have the same cardinality. Two sets \(A\) and \(B\) have the same number of elements if we can pair each element in \(A\) with an element in \(B\text{.}\) Each element of \(A\) must be in exactly one pair, and each element of \(B\) must be in exactly one pair. These pairs define an invertible function from \(A\) to \(B\text{.}\) This fact gives our definition of equal cardinality.

🔗

Definition 9.1.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 yet define the cardinality of a set or count its elements. It will be useful when we study the cardinality of infinite sets in the next section.

🔗

Example 9.1.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.1.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}\)

🔗

The table shows that the function \(f\) is invertible. In particular, the inverse \(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.

🔗

In our proof, we could also use the function \(f^{-1}:V\to\Z_5\) or any other invertible function between the two sets. The definition in Definition 9.1.4 only requires that an invertible function exists.

🔗

It is often easier to show that two sets have the same cardinality than to show that they have different cardinalities. To show they have the same cardinality, we can give an invertible function. To show they have different cardinalities, we must prove that no such function exists.

🔗

Example 9.1.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*}

\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{.}\) This 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.1.6 can be also be applied when the sets have more elements.

🔗

Example 9.1.7. \(\N\) and \(\{\mathtt{s},\mathtt{t}\}\) do not have the same cardinality.

We compare the set of natural numbers \(\N=\{1,2,3,\dots\}\) with \(U=\{\mathtt{s},\mathtt{t}\}\text{.}\) To show that they do not have the same cardinality, we show 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(3)\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{.}\) This 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.1.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{.}\)

🔗

Definition 9.1.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 an invertible function from a set to \(\Z_n\) is given, where \(n\in\N\text{,}\) the definition gives the cardinality of the set right away.

🔗

Example 9.1.9. Cardinality of the set \(\A\) of characters.

The function \(C:\A\to\Z_{27}\) given in Figure 8.1.1 is invertible. So \(\#\A=27\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 build an invertible function from the set to \(\Z_n\text{.}\)

🔗

Example 9.1.10. 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.1.8 to show that \(\#B=4\text{.}\) Let \(f:B\to \Z_4\) given by:

\begin{align*} f(\mathtt{m})\amp:=0\\ f(\mathtt{a})\amp:=1\\ f(\mathtt{t})\amp:=2\\ f(\mathtt{h})\amp:=3 \end{align*}

As the function \(f\) is invertible, the cardinality of \(B\) is \(4\text{.}\)

🔗

We revisit the examples from the beginning of this section.

🔗

Example 9.1.11. 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.

\(\#\{\}=0\) by Definition 9.1.3.
🔗

🔗
\(\#\{\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 find the cardinality of the set. Often counting the element suffices.

🔗

Example 9.1.12. 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\)
🔗

🔗
\(\displaystyle \nr{\{ 2,4,6,8,10 \}} = 5\)
🔗

🔗
\(\displaystyle \nr{\{1,2,3,\ldots,500\}} = 500\)
🔗

🔗
\(\displaystyle \nr{\{0,1,2,\ldots,500\}} = 501\)
🔗

🔗
\(\displaystyle \nr{\{0,1,2,\ldots,499\}} = 500\)
🔗

🔗
\(\displaystyle \nr{\Z_7}=\nr{\{0,1,2,3,4,5,6\}}=7\)
🔗

🔗
\(\displaystyle \nr{\Z_7^\otimes}=\nr{\{1,2,3,4,5,6\}}=6\)
🔗

🔗

🔗

Example 9.1.13. Cardinalities of special sets.

We give the cardinality of two more of the sets from Definition 5.4.1. Let \(n \in \mathbb{N}\text{.}\) Then

\(\nr{\Z_n} = \nr{\{0,1,2,\dots,n-1\}} = n\text{,}\) because the identity function \(\id_{\Z_n}\) is invertible.
🔗

🔗
\(\nr{\Z_n^\otimes} = \nr{\{1,2,\dots,n-1\}} = n-1\text{.}\) because the function \(f:\Z_n^\otimes\to\Z_{n-1}\) given by \(f(x)=x-1\) is invertible.
🔗

🔗

🔗

Prev Top Next