Section 9.3 Cardinality of Cartesian Products
Recall that by Definition 6.2.2 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.3.1 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.
Theorem 9.3.2.
Let \(A\) and \(B\) be finite sets. Then, \(\nr{(A\times B)}=\nr{A}\cdot \nr{B}\text{.}\)
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.3.3 complete the definition of a Cartesian product and a restatement of Theorem 9.3.2.
Checkpoint 9.3.3. Cardinality of Cartesian products.
Complete the following:
Let \(A\) and \(B\) be sets.
The
select
intersection
union
difference
sum
Cartesian product
complement
select
unordered pairs
ordered pairs
sets
numbers
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
select
and
or
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
select
weight
volume
size
length
area
cardinality
select
intersection
union
difference
sum
Cartesian product
complement
We give examples for the number of elements in Cartesian products.
Example 9.3.4. 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.2.4.
Example 9.3.5. 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,
and
Writing \(A \times B\) and \(B \times A\) in roster form we get
and
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.3.6 compute the number of elements of a Cartesian product of two sets and list the number of the elements in the set.
Checkpoint 9.3.6. 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.]
\(9\)
\(\left(\text{a}, 1\right), \left(\text{a}, 2\right), \left(\text{a}, 3\right), \left(\text{b}, 1\right), \left(\text{b}, 2\right), \left(\text{b}, 3\right), \left(\text{c}, 1\right), \left(\text{c}, 2\right), \left(\text{c}, 3\right)\)