$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 4.4: Cartesian Products

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

Another way to obtain a new set from two given sets $$A$$ and $$B$$ is to form ordered pairs.

## Definition: Ordered Pair

An ordered pair $$(x,y)$$ consists of two values $$x$$ and $$y$$. Their order of appearance is important, so we call them first and second elements respectively. Consequently, $$(a,b)\neq (b,a)$$ unless $$a=b$$. In general, $$(a,b)=(c,d)$$ if and only if $$a=c$$ and $$b=d$$.

## Definition: Cartesian Product

The Cartesian product of $$A$$ and $$B$$ is the set

$A \times B = \{ (a,b) \mid a \in A \wedge b \in B \}$

Thus, $$A \times B$$ (read as “$$A$$ cross $$B$$”) contains all the ordered pairs in which the first elements are selected from $$A$$, and the second elements are selected from $$B$$.

Example $$\PageIndex{1}\label{eg:cartprod-01}$$

Let $$A = \{\mbox{John}, \mbox{Jim}, \mbox{Dave}\}$$ and $$B = \{\mbox{Mary}, \mbox{Lucy}\}$$. Determine $$A\times B$$ and $$B\times A$$.

Solution

We find $\displaylines{ A\times B = \{ (\mbox{John},\mbox{Mary}), (\mbox{John},\mbox{Lucy}), (\mbox{Jim}, \mbox{Mary}), (\mbox{Jim}, \mbox{Lucy}), (\mbox{Dave},\mbox{Mary}), (\mbox{Dave},\mbox{Lucy})\}, \cr B\times A = \{ (\mbox{Mary},\mbox{John}), (\mbox{Mary},\mbox{Jim}), (\mbox{Mary},\mbox{Dave}), (\mbox{Lucy},\mbox{John}), (\mbox{Lucy},\mbox{Jim}), (\mbox{Lucy},\mbox{Dave})\}. \cr}$ In general, $$A\times B \neq B\times A$$.

Example $$\PageIndex{2}\label{eg:cartprod-02}$$

Determine $$A \times B$$ and $$A \times A$$:

$$A=\{1,2\}$$ and $$B=\{2,5,6\}$$.

$$A=\{5\}$$ and $$B=\{0,7\}$$.

Solution

(a) We find \begin{aligned} A\times B &=& \{(1,2), (1,5), (1,6), (2,2), (2,5), (2,6)\}, \\ A\times A &=& \{(1,1), (1,2), (2,1), (2,2)\}. \end{aligned} (b) The answers are $$A\times B = \{(5,0), (5,7)\}$$, and $$A\times A = \{(5,5)\}$$.

hands-on exercise $$\PageIndex{1}\label{he:cartprod-01}$$

Let $$A=\{a,b,c,d\}$$ and $$B=\{r,s,t\}$$. Find $$A\times B$$, $$B\times A$$, and $$B\times B$$.

Example $$\PageIndex{3}\label{eg:cartprod-03}$$

Determine $$\wp(\{1,2\}) \times \{3,7\}$$. Be sure to use correct notation.

Solution

For a complicated problem, divide it into smaller tasks and solve each one separately. Then assemble them to form the final answer. In this problem, we first evaluate $\wp(\{1,2\}) = \big\{\emptyset, \{1\}, \{2\}, \{1,2\} \big\}.$ This leads to \begin{aligned} \wp(\{1,2\}) \times \{3,7\} &=& \big\{\emptyset, \{1\}, \{2\}, \{1,2\} \big\} \times \{3,7\} \\ &=& \big\{ (\emptyset,3), (\emptyset,7), (\{1\},3), (\{1\},7), (\{2\},3), (\{2\},7), (\{1,2\},3), (\{1,2\},7) \big\}. \end{aligned} Check to make sure that we have matching left and right parentheses, and matching left and right curly braces.

hands-on exercise $$\PageIndex{2}\label{he:cartprod-02}$$

Find $$\{a,b,c\}\times\wp(\{d\})$$.

Example $$\PageIndex{4}\label{eg:cartprod-04}$$

How could we describe the contents of the Cartesian product $$[1,3] \times \{2,4\}$$? Since $$[1,3]$$ is an infinite set, it is impossible to list all the ordered pairs. We need to use the set-builder notation: $[1,3] \times \{2,4\} = \{ (x,y) \mid 1\leq x\leq3, y=2,4\}.$ We can also write $$[1,3] \times \{2,4\} = \{ (x,2), (x,4) \mid 1\leq x\leq3\}$$.

hands-on exercise $$\PageIndex{3}\label{HE:cartprod-03}$$

Describe, using the set-builder notation, the Cartesian product $$[1,3] \times [2,4]$$.

Cartesian products can be extended to more than two sets. Instead of ordered pairs, we need ordered $$n$$-tuples. The $$n$$-fold Cartesian product of $$n$$ sets $$A_1, A_2, \ldots, A_n$$ is the set

$A_1 \times A_2 \times \cdots \times A_n = \{(a_1,a_2,\ldots,a_n) \mid a_i \in A_i \mbox{ for each } i, 1 \leq i \leq n \}$

In particular, when $$A_i=A$$ for all $$i$$, we abbreviate the Cartesian product as $$A^n$$.

Example $$\PageIndex{5}\label{eg:cartprod-05}$$

The $$n$$-dimensional space is denoted $$\mathbb{R}^n$$. It is the $$n$$-fold Cartesian product of $$\mathbb{R}$$. In special cases, $$\mathbb{R}^2$$ is the $$xy$$-plane, and $$\mathbb{R}^3$$ is the $$xyz$$-space.

Example $$\PageIndex{6}$$

If $$D = \{1,2\}$$ then $$D^3=D \times D \times D =$$

Solution

$$\big\{(1,1,1), (1,1,2),(1,2,2),(1,2,1),(2,1,1),(2,1,2),(2,2,2),(2,2,1) \big\}$$

hands-on exercise $$\PageIndex{5}\label{he:cartprod-04}$$

Let $$A=\{1,2\}$$, $$B=\{a,b\}$$, and $$C=\{r,s,t\}$$. Find $$A\times B\times C$$.

Example $$\PageIndex{7}\label{eg:cartprod-07}$$

From a technical standpoint, $$(A \times B) \times C$$ is different from $$A \times B \times C$$. Can you explain why? Can you discuss the difference, if any, between $$(A \times B) \times C$$ and $$A \times (B \times C)$$? For instance, give some specific examples of the elements in $$(A \times B)\times C$$ and $$A \times (B \times C)$$ to illustrate their differences.

Solution

The elements of $$(A\times B)\times C$$ are ordered pairs in which the first coordinates are themselves ordered pairs. A typical element in $$(A\times B)\times C$$ takes the form of $\big((a,b),c\big).$ The elements in $$A\times B\times C$$ are ordered triples of the form $(a,b,c).$ Since their elements look different, it is clear that $$(A\times B)\times C \neq A\times B\times C$$. Likewise, a typical element in $$A\times (B\times C)$$ looks like $\big(a,(b,c)\big).$ Therefore, $$(A\times B)\times C \neq A\times(B\times C)$$, and $$A\times (B\times C)\neq A\times B\times C$$.

## Theorem $$\PageIndex{1}$$

For any sets $$A$$, $$B$$, and $$C$$, we have \begin{aligned} A \times (B \cup C) &=& (A \times B) \cup (A \times C), \\ A \times (B \cap C) &=& (A \times B) \cap (A \times C), \\ A \times (B - C) &=& (A \times B) - (A \times C).\end{aligned}

Remark

How would we show that the two sets $$S$$ and $$T$$ are equal? We need to show that $x\in S \Leftrightarrow x\in T.$ The complication in this problem is that both $$S$$ and $$T$$ are Cartesian products, so $$x$$ takes on a special form, namely, that of an ordered pair. Consider the first identity as an example

$$A \times (B\cup C)=(A \times B) \cup (A \times C)$$.

We need to show that $(u,v)\in A \times (B \cup C) \Leftrightarrow (u,v)\in (A \times B) \cup (A \times C).$

We prove this in two steps: first showing $$\Rightarrow$$, then $$\Leftarrow$$, which is equivalent to first showing $$\subseteq$$, then $$\supseteq$$.

Proof

Let $$(u,v)\in A\times(B\cup C)$$. Then by definition of Cartesian Product,  $$u\in A$$, and $$v\in B\cup C$$.

The definition of union implies that $$v\in B$$ or $$v\in C$$. Thus far, we have found

• $$u\in A$$ and $$v\in B$$, or
• $$u\in A$$ and $$v\in C$$.

By definition of Cartesian Product, this is equivalent to

• $$(u,v)\in A\times B$$, or
• $$(u,v)\in A\times C$$.

Thus, $$(u,v)\in (A\times B)\cup(A\times C)$$. This proves that $$A\times(B\cup C) \subseteq (A\times B)\cup(A\times C)$$, by definition of subset.

Next, let $$(u,v)\in (A\times B)\cup(A\times C)$$. Then $$(u,v)\in A\times B$$, or $$(u,v)\in A\times C$$ by definition of union.

This means, by definition of Cartesian Product,

• $$u\in A$$ and $$v\in B$$, or
• $$u\in A$$ and $$v\in C$$.

Both conditions require $$u\in A$$, so we can rewrite them as

• $$u\in A$$, and
• $$v\in B$$ or $$v\in C$$;

which is equivalent to

• $$u\in A$$, and
• $$v\in B\cup C$$ by definition of union.

Thus, $$(u,v)\in A\times(B\cup C)$$. We have proved that $$(A\times B) \cup(A\times C) \subseteq A\times(B\cup C)$$. Together with $$A\times (B\cup C) \subseteq (A\times B)\cup(A\times C)$$ that we have proved earlier, we conclude that $$A\times(B\cup C) = (A\times B)\cup (A\times C)$$, by definition of Set Equality.

Theorem $$\PageIndex{2}\label{cartprodcard}$$

If $$A$$ and $$B$$ are finite sets, with $$|A|=m$$ and $$|B|=n$$, then $$|A\times B| = mn$$.

Proof

The elements of $$A\times B$$ are ordered pairs of the form $$(a,b)$$, where $$a\in A$$, and $$b\in B$$. There are $$m$$ choices of $$a$$. For each fixed $$a$$, we can form the ordered pair $$(a,b)$$ in $$n$$ ways, because there are $$n$$ choices for $$b$$. Together, the ordered pairs $$(a,b)$$ can be formed in $$mn$$ ways.

The argument we used in the proof is called multiplication principle. We shall study it again in Chapter 7. In brief, it says that if a job can be completed in several steps, then the number of ways to finish the job is the product of the number of ways to finish each step.

Corallary $$\PageIndex{3}$$

If $$A_1,A_2,\ldots,A_n$$ are finite sets, then $$|A_1\times A_2\times \cdots\times A_n| = |A_1| \cdot |A_2|\,\cdots\, |A_n|$$.

Corollary $$\PageIndex{4}$$

If $$A$$ is a finite set with $$|A|=n$$, then $$|\mathscr{P}(A)|=2^n$$.

Proof

Let the elements of $$A$$ be $$a_1,a_2,\ldots,a_n$$. The elements of $$\mathscr{P}(A)$$ are subsets of $$A$$. Each subset of $$A$$ contains some elements from $$A$$. Let $$B = \{0,1\}$$, so $$B^n$$ is $$B \times B \times B \times B \times \ldots$$ n times. $$B^n$$ is the set of all possible n-tupples (or strings) with 1s and 0s.  Associate to each subset $$S$$ of $$A$$ an ordered $$n$$-tuple $$\big(b_1,b_2,\ldots,b_n\big)$$ from $$B^n$$ such that $b_i = \cases{ 0 & if a_i\notin S, \cr 1 & if a_i\in S. \cr}$ The value of the $$i$$th element in this ordered $$n$$-tuple indicates whether the subset $$S$$ contains the element $$a_i$$. It is clear that the subsets of $$A$$ are in one-to-one correspondence with the $$n$$-tuples. This means the power set $$\mathscr{P}(A)$$ and the Cartesian product $$B^n$$ have the same cardinality. Since there are $$2^n$$ ordered $$n$$-tuples, we conclude that there are $$2^n$$ subsets as well.

This idea of one-to-one correspondence is a very important concept in mathematics. We shall study it again in Chapter 5.

## Summary and Review

• The Cartesian product of two sets $$A$$ and $$B$$, denoted $$A\times B$$, consists of ordered pairs of the form $$(a,b)$$, where $$a$$ comes from $$A$$, and $$b$$ comes from $$B$$.
• Since ordered pairs are involved, $$A\times B$$ usually is not equal to $$B\times A$$.
• The notion of ordered pairs can be extended analogously to ordered $$n$$-tuples, thereby yielding an $$n$$-fold Cartesian product.
• If $$A$$ and $$B$$ are finite sets, then $$|A\times B| = |A|\cdot|B|$$.

## Exercises

Exercise $$\PageIndex{1}\label{ex:cartprod-01}$$

Let $$X=\{-2,2\}$$, $$Y=\{0,4\}$$ and $$Z=\{-3,0,3\}$$. Evaluate the following Cartesian products.

1. $$X\times Y$$
2. $$X\times Z$$
3. $$Z\times Y\times Y$$

Solution

(a) $$\{(-2,0), (-2,4), (2,0), (2,4)\}$$

(b) $$\{(-2,-3), (-2,0), (-2,3), (2,-3), (2,0), (2,3)\}$$

Exercise $$\PageIndex{2}\label{ex:cartprod-02}$$

Consider the sets $$X$$, $$Y$$ and $$Z$$ defined in Problem 1. Evaluate the following Cartesian products.

1. $$X\times Y\times Z$$
2. $$(X\times Y)\times Z$$
3. $$X\times (Y\times Z)$$

Exercise $$\PageIndex{3}\label{ex:cartprod-03}$$

Without listing all the elements of $$X\times Y\times X\times Z$$, where $$X$$, $$Y$$, and $$Z$$ are defined in Problem 1, determine $$|X\times Y\times X\times Z|$$.

Solution

$$2\cdot2\cdot2\cdot3 = 24$$.

Exercise $$\PageIndex{4}$$

Let $$A=\{1,2,3\}$$ and $$B=\{5,6\}$$.

(a) $$|A\times B| =$$

(b) True or False?

(b1) $$(1,6) \in A \times B$$

(b2) $$(5,2) \in A \times B$$

(b3) $$A \subseteq A \times B$$

(b4) $$\big\{(1,5), (2,6) \big\} \subseteq A \times B$$

(b5) $$(3,3) \in A \times B$$

(b6) $$(2,5) \in A \times B$$

(b7) $$(1,5) \subseteq A \times B$$

(b8)  $$\big\{(5,2), (6,1), (6,3) \big\} \subseteq B \times A$$

Exercise $$\PageIndex{5}$$

Which of the following are elements of the Cartesian product $$[1,3] \times \{2,4\}$$?  (see Example 4.4)

Note: assume ( , ) indicates ordered pairs, not intervals;  [  ,  ] does indicate a closed interval.

(a) (1,2)        (b) (4,4)       (c) (4,3)      (d) (2,4)    (e) (1.7, 4)    (f) [2,3]

(g) (0.7, 4)    (h) (2.7, 4)    (i) (3, 4)     (j) (1.5, 2)    (k) (3,3)       (l)  (2.981, 2)

(a) YES   $$(1,2) \in [1,3] \times \{2,4\}$$   (b) No   (c) No (d) YES  (e) YES   (f) No
(g) No     (h)  YES    (i)  YES      (j)  YES    (k)  No   (l) YES

Exercise $$\PageIndex{6}\label{ex:cartprod-06}$$

Determine $$|\mathscr{P}(\mathscr{P}(\mathscr{P}(\{1,2\})))|$$.

Exercise $$\PageIndex{7}\label{ex:cartprod-07}$$

Consider the set $$X=\{-2,2\}$$. Evaluate the following Cartesian products.

1. $$X\times\mathscr{P}(X)$$
2. $$\mathscr{P}(X)\times\mathscr{P}(X)$$
3. $$\mathscr{P}(X\times X)$$
Solution

(a) $$\{(-2,\emptyset),(-2,\{-2\}),(-2,\{2\}),(-2,\{-2,2\}), ( 2,\emptyset),( 2,\{-2\}),( 2,\{2\}),( 2,\{-2,2\})\}$$

Exercise $$\PageIndex{8}\label{ex:cartprod-08}$$

Let $$A$$ and $$B$$ be arbitrary nonempty sets.

1. Under what condition does $$A\times B = B\times A$$?
2. Under what condition is $$(A\times B)\cap(B\times A)$$ empty?

Exercise $$\PageIndex{9}\label{ex:cartprod-09}$$

Let $$A$$, $$B$$, and $$C$$ be any three sets. Prove that

1. $$A\times(B\cap C) = (A\times B)\cap (A\times C)$$
2. $$A\times(B - C) = (A\times B) - (A\times C)$$

Exercise $$\PageIndex{10}\label{ex:cartprod-10}$$

Let $$A$$, $$B$$, and $$C$$ be any three sets. Prove that if $$A\subseteq B$$, then $$A\times C \subseteq B\times C$$.