Skip to main content

Section 9.1 Definition of Cardinality

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.1 we give a intuitive introduction and a formal definition of cardinality. More details can be found below.

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

We discuss possible cardinalities of some sets.

  1. The empty set \(\{\}\) contains no elements, so its cardinality should be \(0\text{.}\)

  2. The set \(\{\mathtt{m}\}\) contains one element, namely the character \(\mathtt{m}\text{,}\) so its cardinality should be \(1\text{.}\)

  3. 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{.}\)

  4. 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.”

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.

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 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. If 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.5.

Let \(A\) be a set.

The set \(A\) is called finite when \(A=\{\}\) or that there exists \(n\in\N\) and an invertible function \(f:A\to\Z_n\text{.}\)

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{.}\)”

Read Definition 9.1.4 and Definition 9.1.5 once more and complete the definition in the checkpoint.

When an invertible function from a set to \(\Z_n\) where \(m\in\N\) is given the cardinality of the set immediately follows from the definition.

The function \(C:\A\to\Z_{27}\) from given in Table 8.1.1 is invertible. Thus \(\#\A=27\text{.}\)

In Checkpoint 9.1.8 determine the cardinality of a set when an invertible function from a set to \(\Z_n\) where \(m\in\N\) is given.

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{.}\)

Let \(B=\{\mathtt{m},\mathtt{a},\mathtt{t},\mathtt{h}\}\text{.}\) We count \(4\) elements and now apply Definition 9.1.5 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{.}\)

In Checkpoint 9.1.10 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.

We revisit the examples from the beginning of this section.

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.

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

  2. \(\#\{\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\}\)).

  3. \(\#\{\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{.}\)

  4. \(\#\{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.

We give the cardinality of some other sets.

  1. \(\nr{\{\}}=0\)

  2. \(\nr{\{1,2,3,4\}}=4\)

  3. \(\nr{\{x\mid x\in\N \mbox{ and } x\lt 100\}} = 99\)

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

  5. \(\nr{\{1,2,3,\ldots,500\}} = 500\)

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

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

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

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

  2. \(\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.