$$\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 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 4.4: Cartesian Products

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\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 \|}$$ $$\newcommand{\inner}{\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 \|}$$ $$\newcommand{\inner}{\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. 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 \} \nonumber$

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} \nonumber$ In general, $$A\times B \neq B\times A$$.

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

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

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

(a) We find $\begin{array}{r c l} 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{array} \nonumber$

(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\}. \nonumber$ This leads to $\begin{array}{r c l} \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{array} \nonumber$ 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\}. \nonumber$ 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 \} \nonumber$

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.

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). \nonumber$ The elements in $$A\times B\times C$$ are ordered triples of the form $(a,b,c). \nonumber$ 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). \nonumber$ 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{array}{r c l} 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{array} \nonumber$

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

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

This is equivalent to

1. $$(u,v)\in A\times B$$, or
2. $$(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

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

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

1. $$u\in A$$, and
2. $$v\in B$$ or $$v\in C$$;

which is equivalent to

1. $$u\in A$$, and
2. $$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 $\begin{array}{r l l} (u,v) \in A \times (B \cup C) & \Leftrightarrow u \in A \wedge v \in (B \cup C) & (\text{defn. of Cartesian product}) \\ & \Leftrightarrow u \in A \wedge (v \in B \vee v \in C) & (\text{defn. of union}) \\ & \Leftrightarrow (u \in A \wedge v \in B) \vee (u \in A \wedge v \in C) & (\text{distributive law}) \\ & \Leftrightarrow (u, v) \in A \times B \vee (u, v) \in A \times C & (\text{defn. of Cartesian product}) \\ & \Leftrightarrow (u,v) \in (A \times B) \cup (A \times C) & (\text{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 8. 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} \nonumber$ 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 6.

## 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 the previous exercise. 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 the first exercise, 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$$.

4.4: Cartesian Products is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by Harris Kwong (OpenSUNY) .