4.4: Cartesian Products
- Page ID
- 23275
\( \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}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)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.
- \(X\times Y\)
- \(X\times Z\)
- \(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.
- \(X\times Y\times Z\)
- \((X\times Y)\times Z\)
- \(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)
- Answer
-
(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.
- \(X\times\mathscr{P}(X)\)
- \(\mathscr{P}(X)\times\mathscr{P}(X)\)
- \(\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.
- Under what condition does \(A\times B = B\times A\)?
- 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
- \(A\times(B\cap C) = (A\times B)\cap (A\times C)\)
- \(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\).