Theorem 9.30.
Let \(A\) and \(B\) be finite sets. Then, \(\nr{(A\times B)}=\nr{A}\cdot \nr{B}\text{.}\)
Section 9.3 Cardinality of Cartesian Products
Recall that by Definition 6.12 the Cartesian of two sets consists of all ordered pairs whose first entry is in the first set and whose second entry is in the second set. In the video in Figure 9.29 we give overview over the remainder of the section and give first examples.
We continue our discussion of Cartesian products with the formula for the cardinality of a Cartesian product in terms of the cardinalities of the sets from which it is constructed.
Proof.
Let \(a \in A\text{.}\) The number of pairs of the form \((a,b)\) where \(b\in B\) is \(\nr{B}\text{.}\) Since there are \(\nr{B}\) choices for \(b\) for each of the \(\nr{A}\) choices for \(a\in A\) the number of elements in \(A\times B\) is \(\nr{A}\cdot \nr{B}\text{.}\)
In Checkpoint 9.31 complete the definition of a Cartesian product and a restatement of Theorem 9.30.
Checkpoint 9.31. Cardinality of Cartesian products.
Complete the following:
Let \(A\) and \(B\) be sets.
The
- select
- intersection
- union
- difference
- sum
- Cartesian product
- complement
of the sets \(A\) and \(B\text{,}\) denoted by \(A\times B\text{,}\) is the set of all
- select
- unordered pairs
- ordered pairs
- sets
- numbers
\(a,b\) where \(a\) is
- select
- related to
- an element of
- a subsets of
- not related to
- not an element of
- a proper subset of
- equal to
- not equal to
the set \(A\)
- select
- and
- or
\(b\) is
- select
- related to
- an element of
- a subsets of
- not related to
- not an element of
- a proper subset of
- equal to
- not equal to
the set \(B\text{.}\)
The
- select
- weight
- volume
- size
- length
- area
- cardinality
of the
- select
- intersection
- union
- difference
- sum
- Cartesian product
- complement
of \(A\) and \(B\) is \(\#A\cdot \#B\text{.}\)
We give examples for the number of elements in Cartesian products.
Example 9.32. Cardinality of a Cartesian products.
- For any finite set \(A\text{,}\) we have that \(\nr{(A\times\emptyset)}=\nr{A}\cdot \nr{\emptyset} = \nr{A}\cdot 0 = 0\text{.}\)
- Let \(A=\{-4,-3,-2,-1,0,1,2,3,4\}\text{.}\) Then, \(\nr{(A\times A)}=\nr{A}\cdot \nr{A}=9\cdot 9=81\text{.}\)
- Let \(A=\{0,1,2\}\) and \(B=\{0,1,2,3,4\}\text{.}\) Then, \(\nr{(A\times B)}=\nr{A}\cdot \nr{B}=3\cdot 5=15\text{.}\)
Knowing the cardinality of a Cartesian product helps us to verify that we have listed all of the elements of the Cartesian product. The following example demonstrates this by revisiting the Cartesian products introduced in Example 6.14.
Example 9.33. The cardinality of a Cartesian product and its elements.
Let \(A = \set{0,1}\text{,}\) and let \(B = \set{4,5,6}\text{.}\) Then, \(\nr{A} = 2\) and \(\nr{B} = 3\text{.}\) By Theorem 9.30,
\begin{equation*}
\nr{(A \times B)} = \nr{A} \cdot \nr{B} = 2 \cdot 3 = 6
\end{equation*}
and
\begin{equation*}
\nr{(B \times A)} = \nr{B} \cdot \nr{A} = 3 \cdot 2 = 6.
\end{equation*}
Writing \(A \times B\) and \(B \times A\) in roster form we get
\begin{equation*}
A \times B = \set{(0, 4), (0, 5), (0, 6), (1, 4), (1, 5), (1, 6)}\text{,}
\end{equation*}
and
\begin{equation*}
B \times A = \set{(4, 0), (4, 1), (5, 0), (5, 1), (6, 0), (6,1)}\text{.}
\end{equation*}
Notice that there are, in fact, \(6\) elements in \(A \times B\) and in \(B \times A\text{,}\) so we may say with confidence that we listed all of the elements in those Cartesian products.
In Checkpoint 9.34 compute the number of elements of a Cartesian product of two sets and list the number of the elements in the set.
Checkpoint 9.34. Cardinality and elements on a Cartesian product.
Let \(A = \lbrace a,b,c\rbrace\text{,}\) \(B = \lbrace 1,2,3\rbrace\)
How many elements are in \(A\times B\text{?}\)
Give \(A\times B\) in roster form.
\(A\times B= \lbrace\)\(\rbrace\)
[Note: Enter your answer as a comma-separated list. Pairs should be denoted with parentheses.]
