# 4.6.1: Cardinality

- Page ID
- 10902

In counting, as it is learned in childhood, the set {1, 2, 3, . . . , *n*} is used as a typical set that contains *n *elements. In mathematics and computer science, it has become more common to start counting with zero instead of with one, so we define the following sets to use as our basis for counting:

*\(N_{0}=\varnothing\)*, a set with 0 elements

\(N_{1}=\{0\}\), a set with 1 element

\(N_{2}=\{0,1\}\), a set with 2 elements

\(N_{3}=\{0,1,2\}\), a set with 3 elements

\(N_{4}=\{0,1,2,3\}\), a set with 4 elements

and so on. In general, \(N_{n}=\{0,1,2, \ldots, n-1\}\) for each \(n \in \mathbb{N} .\) For each natural number \(n, N_{n}\) is a set with \(n\) elements. Note that if \(n \neq m,\) then there is no one-to-one correspondence between \(N_{n}\) and \(N_{m} .\) This is obvious, but like many obvious things is not all that easy to prove rigorously, and we omit the argument here.

Theorem 4.6.

For each \(n \in \mathbb{N},\) let \(N_{n}\) be the set \(N_{n}=\{0,1, \ldots, n-1\} .\) If \(n \neq m,\) then there is no bijective function from \(N_{m}\) to \(N_{n}\).

We can now make the following definitions:

Definition4.3.

A set A is said to be finite if there is a one-to-one correspondence between \(A\) and \(N_{n}\) for some natural number \(n .\) We then say that \(n\) is the **cardinality** of \(A .\) The notation |A| is used to indicate the cardinality of A. That is, if A is a finite set, then|A| is the natural number n such that there is a one-to-one correspondence between A and \(N_{n} .\) In layman's terms: \(|A|\) is the number items in \(A .\) A set that is not finite is said to be infinite. That is, a set B is infinite if for every n ∈ N, there is no one-to-one correspondence between \(B\) and \(N_{n}\).

Fortunately, we don’t always have to count every element in a set individually to determine its cardinality. Consider, for example, the set *A *× *B*, where *A *and *B *are finite sets. If we already know |*A*| and |*B*|, then we can determine |*A *× *B*| by computation, without explicit counting of elements. In fact, |*A *× *B*| = |*A*| · |*B*|. The cardinality of the cross product *A *× *B *can be computed by multiplying the cardinality of *A *by the cardinality of *B*. To see why this is true, think of how you might count the elements of *A** *× *B*. You could put the elements into piles, where all the ordered pairs in a pile have the same first coordinate. There are as many piles as there are elements of *A*, and each pile contains as many ordered pairs as there are elements of *B*. That is, there are |*A*| piles, with |*B*| items in each. By the definition of multiplication, the total number of items in all the piles is |*A*| · |*B*|. A similar result holds for the cross product of more that two finite sets. For example, |*A *× *B *× *C*| = |*A*| · |*B*| · |*C*|.

It’s also easy to compute |*A *∪ *B*| in the case where *A *and *B *are disjoint finite sets. (Recall that two sets *A *and *B *are said to be disjoint if they have no members in common, that is, if *A *∩ *B *= ∅.) Suppose |*A*| = *n *and |*B*| = *m*. If we wanted to count the elements of *A *∪ *B*, we could use the *n *numbers from 0 to *n *− 1 to count the elements of *A *and then use the *m *numbers from *n *to *n*+*m*−1 to count the elements of *B*. This amounts to a one-to-one correspondence between \(A \cup B\) and the set \(N_{n+m} .\) We see that \(|A \cup B|=n+m\) That is, for disjoint finite sets *A *and *B*, |*A *∪ *B*| = |*A*| + |*B*|.

What about *A *∪ *B*, where *A *and *B *are not disjoint? We have to be careful not to count the elements of *A *∩ *B *twice. After counting the elements of *A*, there are only |*B*| − |*A *∩ *B*| new elements in *B *that still need to be counted. So we see that for any two finite sets *A *and *B*, |*A *∪ *B*| = |*A*| + |*B*| − |*A *∩ *B*|.

What about the number of subsets of a finite set *A*? What is the relationship between|*A*| and |P(*A*)|? The answer is provided by the following theorem.

Theorem 4.7.

A finite set with cardinality \(n\) has \(2^{n}\) subsets.

Proof. Let \(P(n)\) be the statement "Any set with cardinality \(n\) has \(2^{n}\) subsets". We will use induction to show that *P*(*n*) is true for all *n *∈ *N*.

Base case: For \(n=0, P(n)\) is the statement that a set with cardinality 0 has \(2^{0}\) subsets. The only set with 0 elements is the empty set. The empty set has exactly 1 subset, namely itself. Since \(2^{0}=1, P(0)\) is true.

Inductive case: Let *k *be an arbitrary element of N, and assume that *P*(*k*) is true. That is, assume that any set with cardinality \(k\) has \(2^{k}\) elements. (This is the induction hypothesis.) We must show that *P*(*k *+ 1) follows from this assumption. That is, using the assumption that any set with cardinality *k *has 2*k *subsets, we must show that any set with cardinality \(k+1\) has \(2^{k+1}\) subsets.

Let \(A\) be an arbitrary set with cardinality \(k+1 .\) We must show that \(|\mathcal{P}(A)|=2^{k+1}\) \. Since |*A*| > 0, *A *contains at least one element. Let *x *be some element of *A*, and let*B** *= *A *∖ {*x*}. The cardinality of *B *is *k*, so we have by the induction hypothesis that \(|\mathcal{P}(B)|=2^{k} .\) Now, we can divide the subsets of \(A\) into two classes: subsets of \(A\) that do not contain *x *and subsets of *A *that do contain *x*. Let *Y *be the collection of subsets of*A** *that do not contain *x*, and let *X *be the collection of subsets of *A *that do contain *x*. *X *and *Y *are disjoint, since it is impossible for a given subset of *A *both to contain and to not contain *x*. It follows that |P(*A*)| = |*X *∪ *Y*| = |*X*| + |*Y*|.

Now, a member of *Y *is a subset of *A *that does not contain *x*. But that is exactly the same as saying that a member of *Y *is a subset of *B*. So *Y *= P(*B*), which we know contains \(2^{k}\) members. As for \(X,\) there is a one-to-one correspondence between \(\mathcal{P}(B)\) and *X*. Namely, the function *f *: P(*B*) → *X *defined by *f *(*C*) = *C *∪ {*x*} is a bijective function. (The proof of this is left as an exercise.) From this, it follows that \(|X|=|\mathcal{P}(B)|=2^{k}\) Putting these facts together, we see that \(|\mathcal{P}(A)|=|X|+|Y|=2^{k}+2^{k}=2 \cdot 2^{k}=2^{k+1}\) This completes the proof that *P*(*k*) → *P*(*k *+ 1).

We have seen that the notation \(A^{B}\) represents the set of all functions from \(B\) to \(A\) Suppose \(A\) and \(B\) are finite, and that \(|A|=n\) and \(|B|=m .\) Then \(\left|A^{B}\right|=n^{m}=|A|^{B |}\). (This fact is one of the reasons why the notation \(A^{B}\) is reasonable.) One way to see this is to note that there is a one-to-one correspondence between \(A^{B}\) and a cross product *A*×*A*×···*A*, where the number of terms in the cross product is *m*. (This will be shown in one of the exercises at the end of this section.) It follows that ����*\(\left|A^{B}\right|=|A| \cdot|A| \cdots|A|=\) n *· *n *· · · *n*, where the factor *n *occurs *m *times in the product. This product is, by definition, \(n^{m}\)

This discussion about computing cardinalities is summarized in the following theorem:

Theorem 4.8.

Let *A *and *B *be finite sets. Then

• |*A*×*B*|=|*A*|·|*B*|.

• |*A*∪*B*| = |*A*|+|*B*|−|*A*∩*B*|.

• If *A *and *B *are disjoint then|*A*∪*B*|=|*A*|+|*B*|.

\(\bullet\left|A^{B}\right|=|A|^{B |}\)

\(\bullet|\mathcal{P}(A)|=2^{|A|}\)

When it comes to counting and computing cardinalities, this theorem is only the be- ginning of the story. There is an entire large and deep branch of mathematics known as combinatorics that is devoted mostly to the problem of counting. But the theorem is already enough to answer many questions about cardinalities.

For example, suppose that |*A*| = *n *and |*B*| = *m*. We can form the set P(*A *× *B*), which

consists of all subsets of *A *× *B*. Using the theorem, we can compute that |P(*A *× *B*)| =\(2^{|A \times B|}=2^{|A| \cdot|B|}=2^{n m}\). If we assume that *A *and *B *are disjoint, then we can compute that \(\left|A^{A \cup B}\right|=|A|^{|A \cup B|}=n^{n+m}\).

To be more concrete, let *X *= {*a*,*b*,*c*,*d*,*e*} and let *Y *= {*c*,*d*,*e*, *f*} where *a*,*b*, *c*, *d*, *e*, and *f *are distinct. Then |*X*×*Y*| = 5·4 = 20 while |*X*∪*Y*| = \(5+4-|\{c, d, e\}|=6\) and \(\left|X^{Y}\right|=5^{4}=625\)

We can also answer some simple practical questions. Suppose that in a restaurant you can

choose one appetizer and one main course. What is the number of possible meals? If *A*is the set of possible appetizers and *C *is the set of possible main courses, then your meal is an ordered pair belonging to the set *A *× *C*. The number of possible meals is |*A *× *C*|, which is the product of the number of appetizers and the number of main courses.

Or suppose that four different prizes are to be awarded, and that the set of people who are eligible for the prizes is *A*. Suppose that |*A*| = *n*. How many different ways are there to award the prizes? One way to answer this question is to view a way of awarding the prizes as a function from the set of prizes to the set of people. Then, if *P *is the set of prizes, the number of different ways of awarding the prizes is \(\left|A^{P}\right| .\) since \(|P|=4\) and \(|A|=n,\) this is \(n^{4} .\) Another way to look at it is to note that the people who win the prizes form an ordered tuple (*a*, *b*, *c*, *d*), which is an element of *A *× *A *× *A *× *A*. So the number of different ways of awarding the prizes is |*A *× *A *× *A *× *A*|, which is |*A*| · |*A*| · |*A*| · |*A*|. This is\(|A|^{4},\) or \(n^{4}\), the same answer we got before.