$$\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}}}$$

Another way to obtain a new set from two given sets $$A$$ and $$B$$ is to form ordered pairs. 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 $$\R^n$$. It is the $$n$$-fold Cartesian product of $$\R$$. In special cases, $$\R^2$$ is the $$xy$$-plane, and $$\R^3$$ is the $$xyz$$-space.

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{6}\label{eg:cartprod-06}$$

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; 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$$. Alternatively, we can use $$\Leftrightarrow$$ throughout the argument.

Proof 1

Let $$(u,v)\in A\times(B\cup C)$$. Then $$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$$.

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)$$.

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$$. This means

• $$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$$.

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)$$.

Proof 2

We shall only prove the first equality. Since $\arraygap{1.2} \begin{array}{l@{\;\Leftrightarrow\;}l@{\qquad}l} (u,v)\in A \times(B \cup C) & u\in A \wedge v\in (B\cup C) & \mbox{(defn.~of Cartesian product)} \\ & u\in A \wedge (v\in B \vee v\in C) & \mbox{(defn.~of union)} \\ & (u\in A\wedge v\in B)\vee(u\in A\wedge v\in C) & \mbox{(distributive law)} \\ & (u,v)\in A\times B \vee (u,v)\in A\times C & \mbox{(defn.~of Cartesian product)} \\ & (u,v) \in (A \times B) \cup (A \times C) & \mbox{(defn.~of union)} \end{array}$ we conclude that $$A\times(B\cup C) = (A\times B)\cup(A\times C)$$.

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 [ch:combo]. 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 $$|\wp(A)|=2^n$$.

Proof

Let the elements of $$A$$ be $$a_1,a_2,\ldots,a_n$$. The elements of $$\wp(A)$$ are subsets of $$A$$. Each subset of $$A$$ contains some elements from $$A$$. Associate to each subset $$S$$ of $$A$$ an ordered $$n$$-tuple $$\big(b_1,b_2,\ldots,b_n\big)$$ from $$\{0,1\}^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 $$\wp(A)$$ and the Cartesian product $$\{0,1\}^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 [ch:functions].

## 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|$$.

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$$

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

Consider the sets $$X$$, $$Y$$ and $$Z$$ defined in Problem [ex:cartprod-01]. 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 [ex:cartprod-01], determine $$|X\times Y\times X\times Z|$$.

Exercise$$\PageIndex{4}\label{ex:cartprod-04}$$

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

Exercise$$\PageIndex{5}\label{ex:cartprod-05}$$

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

1. $$X\times\wp(X)$$
2. $$\wp(X)\times\wp(X)$$
3. $$\wp(X\times X)$$

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

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{7}\label{ex:cartprod-07}$$

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{8}\label{ex:cartprod-08}$$

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