Section 9.3 Cardinality of Cartesian Products
Recall from Definition 6.2.2 that the Cartesian product of two sets contains all ordered pairs whose first entry is in the first set and whose second entry is in the second set. The video in Figure 9.3.1 gives an overview of the rest of the section and gives the first examples.
We now give a formula for the cardinality of a Cartesian product. The formula uses the cardinalities of the sets that form the product.
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{.}\)
We give examples for the number of elements in Cartesian products.
Example 9.3.3. 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{.}\)
The cardinality of a Cartesian product helps us check whether we have listed all its elements. The next example shows this by returning to the Cartesian products from Example 6.2.3.
Example 9.3.4. 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.3.2,
\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*}
There are exactly \(6\) elements in \(A \times B\) and in \(B \times A\text{.}\) Therefore, the lists contain every element of both Cartesian products.
