# 3.6.1: Cardinality

In counting, as it is learned in childhood, the set {1, 2, 3, . . . , n} is used as a typical set that contains 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 × B, where and are finite sets. If we already know |A| and |B|, then we can determine |× B| by computation, without explicit counting of elements. In fact, |× B| = |A| · |B|. The cardinality of the cross product × can be computed by multiplying the cardinality of 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, |× × C| = |A| · |B| · |C|.

It’s also easy to compute |∪ B| in the case where and are disjoint finite sets. (Recall that two sets and are said to be disjoint if they have no members in common, that is, if ∩ = ∅.) Suppose |A| = and |B| = m. If we wanted to count the elements of ∪ B, we could use the numbers from 0 to − 1 to count the elements of and then use the numbers from 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 and B, |∪ B| = |A| + |B|.

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

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 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(+ 1) follows from this assumption. That is, using the assumption that any set with cardinality has 2subsets, 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, contains at least one element. Let be some element of A, and letB ∖ {x}. The cardinality of 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 and subsets of that do contain x. Let be the collection of subsets ofA that do not contain x, and let be the collection of subsets of that do contain xand are disjoint, since it is impossible for a given subset of both to contain and to not contain x. It follows that |P(A)| = |∪ Y| = |X| + |Y|.

Now, a member of is a subset of that does not contain x. But that is exactly the same as saying that a member of is a subset of B. So = 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 : P(B) → defined by (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(+ 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, where the factor occurs 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 and be finite sets. Then
• |A×B|=|A|·|B|.
• |AB| = |A|+|B|−|AB|.
• If and are disjoint then|AB|=|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| = and |B| = m. We can form the set P(× B), which

consists of all subsets of × B. Using the theorem, we can compute that |P(× B)| =$$2^{|A \times B|}=2^{|A| \cdot|B|}=2^{n m}$$. If we assume that and 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 = {a,b,c,d,e} and let = {c,d,ef} where a,bcde, and are distinct. Then |X×Y| = 5·4 = 20 while |XY| = $$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 Ais the set of possible appetizers and is the set of possible main courses, then your meal is an ordered pair belonging to the set × C. The number of possible meals is |× 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 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 (abcd), which is an element of × × × A. So the number of different ways of awarding the prizes is |× × × A|, which is |A| · |A| · |A| · |A|. This is$$|A|^{4},$$ or $$n^{4}$$, the same answer we got before.