4.4: Cartesian Products
 Page ID
 8405
\( \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:cartprod01}\)
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:cartprod02}\)
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)\}\).
handson exercise \(\PageIndex{1}\label{he:cartprod01}\)
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:cartprod03}\)
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.
handson exercise \(\PageIndex{2}\label{he:cartprod02}\)
Find \(\{a,b,c\}\times\wp(\{d\})\).
Example \(\PageIndex{4}\label{eg:cartprod04}\)
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 setbuilder 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\}\).
handson exercise \(\PageIndex{3}\label{HE:cartprod03}\)
Describe, using the setbuilder 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:cartprod05}\)
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.
handson exercise \(\PageIndex{5}\label{he:cartprod04}\)
Let \(A=\{1,2\}\), \(B=\{a,b\}\), and \(C=\{r,s,t\}\). Find \(A\times B\times C\).
Example \(\PageIndex{6}\label{eg:cartprod06}\)
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 onetoone 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 onetoone 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\cdotB\).
Exercise\(\PageIndex{1}\label{ex:cartprod01}\)
Let \(X=\{2,2\}\), \(Y=\{0,4\}\) and \(Z=\{3,0,3\}\). Evaluate the following Cartesian products.
 \(X\times Y\)
 \(X\times Z\)
 \(Z\times Y\times Y\)
Exercise\(\PageIndex{2}\label{ex:cartprod02}\)
Consider the sets \(X\), \(Y\) and \(Z\) defined in Problem [ex:cartprod01]. Evaluate the following Cartesian products.
 \(X\times Y\times Z\)
 \((X\times Y)\times Z\)
 \(X\times (Y\times Z)\)
Exercise\(\PageIndex{3}\label{ex:cartprod03}\)
Without listing all the elements of \(X\times Y\times X\times Z\), where \(X\), \(Y\), and \(Z\) are defined in Problem [ex:cartprod01], determine \(X\times Y\times X\times Z\).
Exercise\(\PageIndex{4}\label{ex:cartprod04}\)
Determine \(\wp(\wp(\wp(\{1,2\})))\).
Exercise\(\PageIndex{5}\label{ex:cartprod05}\)
Consider the set \(X=\{2,2\}\). Evaluate the following Cartesian products.
 \(X\times\wp(X)\)
 \(\wp(X)\times\wp(X)\)
 \(\wp(X\times X)\)
Exercise\(\PageIndex{6}\label{ex:cartprod06}\)
Let \(A\) and \(B\) be arbitrary nonempty sets.
 Under what condition does \(A\times B = B\times A\)?
 Under what condition is \((A\times B)\cap(B\times A)\) empty?
Exercise\(\PageIndex{7}\label{ex:cartprod07}\)
Let \(A\), \(B\), and \(C\) be any three sets. Prove that
 \(A\times(B\cap C) = (A\times B)\cap (A\times C)\)
 \(A\times(B  C) = (A\times B)  (A\times C)\)
Exercise\(\PageIndex{8}\label{ex:cartprod08}\)
Let \(A\), \(B\), and \(C\) be any three sets. Prove that if \(A\subseteq B\), then \(A\times C \subseteq B\times C\).