3.5: Cartesian Products of Sets

Given a collection of sets, we can form new sets by taking unions, intersections, complements, and set differences. In this section, we introduce a type of “product" of sets. You have already encountered this concept when you learned to plot points in the plane. You also crossed paths with this notion if you have taken a course in linear algebra.

Definition 3.44. For each $n\in \mathbb{N}$, we define an $n$-tuple to be an ordered list of $n$ elements of the form $(a_1, a_2,\ldots,a_n)$. We refer to $a_i$ as the $i$th component (or coordinate) of $(a_1, a_2,\ldots,a_n)$. Two $n$-tuples $(a_1, a_2,\ldots,a_n)$ and $(b_1, b_2,\ldots,b_n)$ are equal if $a_i=b_i$ for all $1\leq i\leq n$. A $2$-tuple $(a,b)$ is more commonly referred to as an ordered pair while a $3$-tuple $(a,b,c)$ is often called an ordered triple.

Occasionally, other symbols are used to surround the components of an $n$-tuple, such as square brackets “$[\ ]$" or angle brackets “$\langle\ \rangle$". In some programming languages, curly braces “$\{\ \}$" are used to specify arrays. However, we avoid this convention in mathematics since curly braces are the standard notation for sets. The term “tuple" can also occur when discussing other mathematical objects, such as vectors.

We can use the notion of $n$-tuples to construct new sets from existing sets.

Definition 3.45. If $A$ and $B$ are sets, the Cartesian product (or direct product) of $A$ and $B$, denoted $A\times B$ (read as “$A$ times $B$" or “$A$ cross $B$"), is the set of all ordered pairs where the first component is from $A$ and the second component is from $B$. In set-builder notation, we have $$A\times B := \{(a,b)|a\in A, b\in B\}.$$ We similarly define the Cartesian product of $n$ sets, say $A_1, \ldots, A_n$, by $$\prod_{i=1}^{n}A_i := A_1 \times \cdots \times A_n := \{a_1, \ldots , a_n \mid a_j\in A_j \mbox{ for all } 1\leq j\leq n\},$$ where $A_i$ is referred to as the $i$th factor of the Cartesian product. As a special case, the set $$\underbrace{A\times \cdots \times A}_{n\text{ factors}}$$ is often abbreviated as $A^n$.

Cartesian products are named after French philosopher and mathematician René Descartes (1596–1650). Cartesian products will play a prominent role in Chapter 7.

Example 3.46. If $A=\{a,b,c\}$ and $B=\{smiley,frownie\}$, then $$A\times B=\{(a,smiley), (a,frownie),(b,smiley),(b,frownie), (c,smiley),(c,frownie)\}.$$

Example 3.47. The standard two-dimensional plane $\mathbb{R}^2$ and standard three space $\mathbb{R}^{3}$ are familiar examples of Cartesian products. In particular, we have $$\mathbb{R}^2=\mathbb{R}\times \mathbb{R}=\{(x,y)\mid x,y\in \mathbb{R}\}$$ and $$\mathbb{R}^3=\mathbb{R}\times \mathbb{R}\times \mathbb{R}=\{(x,y,z)\mid x,y,z\in \mathbb{R}\}.$$

Example 3.48. Consider the sets $A$ and $B$ from Example 3.46.

1. Find $B\times A$.
2. Find $B\times B$.

Problem 3.49. If $A$ and $B$ are sets, why do you think that $A\times B$ is referred to as a type of “product"? Think about the area model for multiplication of natural numbers.

Problem 3.50. If $A$ and $B$ are both finite sets, then how many elements will $A\times B$ have?

Problem 3.51. Let $A=\{1, 2, 3\}$, $B=\{1,2\}$, and $C=\{1,3\}$. Find $A \times B\times C$.

Problem 3.52. Let $X=[0,1]$ and $Y=\{1\}$. Write each of the following using set-builder notation and then describe the set geometrically (e.g., draw a picture).

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

Problem 3.53. If $A$ is a set, then what is $A\times \emptyset$ equal to?

Problem 3.54. Given sets $A$ and $B$, when will $A\times B$ be equal to $B\times A$?

Problem 3.55. Write $\mathbb{N}\times \mathbb{R}$ using set-builder notation and then describe this set geometrically by interpreting it as a subset of $\mathbb{R}^2$.

We now turn our attention to subsets of Cartesian products.

Theorem 3.56. Let $A$, $B$, $C$, and $D$ be sets. If $A\subseteq C$ and $B\subseteq D$, then $A\times B\subseteq C\times D$.

Problem 3.57. Is it true that if $A\times B\subseteq C\times D$, then $A\subseteq C$ and $B\subseteq D$? Do not forget to think about cases involving the empty set.

Problem 3.58. Is every subset of $C\times D$ of the form $A\times B$, where $A\subseteq C$ and $B\subseteq D$? If so, prove it. If not, find a counterexample.

Problem 3.59. If $A$, $B$, and $C$ are nonempty sets, is $A\times B$ a subset of $A\times B\times C$?

Problem 3.60. Let $A=[2,5]$, $B=[3,7]$, $C=[1,3]$, and $D=[2,4]$. Compute each of the following.

1. $(A\cap B)\times (C\cap D)$
2. $(A\times C)\cap (B\times D)$
3. $(A\cup B)\times (C\cup D)$
4. $(A\times C)\cup (B\times D)$
5. $A\times (B\cap C)$
6. $(A\times B)\cap (A\times C)$
7. $A\times (B\cup C)$
8. $(A\times B)\cup (A\times C)$

Problem 3.63. Let $A$, $B$, $C$, and $D$ be sets. Determine whether each of the following statements is true or false. If a statement is true, prove it. Otherwise, provide a counterexample.

1. $(A\cap B)\times (C\cap D)=(A\times C)\cap (B\times D)$
2. $(A\cup B)\times (C\cup D)=(A\times C)\cup (B\times D)$
3. $A\times (B\cap C)=(A\times B)\cap (A\times C)$
4. $A\times (B\cup C)=(A\times B)\cup (A\times C)$
5. $A\times (B\setminus C) = (A\times B)\setminus (A\times C)$

Problem 3.62 If $A$ and $B$ are sets, conjecture a way to rewrite $(A\times B)^C$ in a way that involves $A^C$ and $B^C$ and then prove your conjecture.