## Section9.3Cardinality 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.

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.

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{.}$$

$$\text{Cartesian product}$$

$$\text{ordered pairs}$$

$$\text{an element of}$$

$$\text{and}$$

$$\text{an element of}$$

$$\text{cardinality}$$

$$\text{Cartesian product}$$

We give examples for the number of elements in Cartesian products.

1. For any finite set $$A\text{,}$$ we have that $$\nr{(A\times\emptyset)}=\nr{A}\cdot \nr{\emptyset} = \nr{A}\cdot 0 = 0\text{.}$$

2. 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{.}$$

3. 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.

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*}

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.

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)$$
$$A = \lbrace a,b,c\rbrace$$$$B = \lbrace 1,2,3\rbrace$$ The number of elements in a Cartesian product is simply $$N(A)\cdot N(B)$$ for any sets $$A, B\text{.}$$ Thus, the number of elements in $$A\times B$$ is $$N(A)\cdot N(B) = 3\cdot 3 = 9$$ The Cartesian product $$A\times B$$ is defined as the set of all ordered pairs whose first component is a member of $$A$$ and whose second component is a member of $$B\text{.}$$ More formally, $$A\times B = \lbrace (a,b) \vert a\in A \textbf{ and } b\in B\rbrace$$ Thus, $$A\times B$$ is $$\lbrace (a,1),(a,2),(a,3),(b,1),(b,2),(b,3),(c,1),(c,2),(c,3)\rbrace$$