6.1: Cartesian Product

We discussed unions and intersections in Section $3.3$. The Cartesian product is another important set operation. Before introducing it, let us recall the notation for an ordered pair.

Notation $6.1.1$.

For any objects $x$ and $y$, mathematicians use $(x, y)$ to denote the ordered pair whose first coordinate is $x$ and whose second coordinate is $y$. It is important to know that the order matters: $(x, y)$ is usually not the same as $(y, x)$. (That is why these are called ordered pairs. Notice that sets are not like this: sets are unordered, so $\{x, y\}$ is always the same as $\{y, x\}$.) It is important to realize that: $$\left(x_{1}, y_{1}\right)=\left(x_{2}, y_{2}\right) \quad \Leftrightarrow \quad x_{1}=x_{2} \text { and } y_{1}=y_{2}$$

Example $6.1.2$.

A special case of the Cartesian product is familiar to all algebra students: recall that $(6.1.3)$ $$\mathbb{R}^{2}=\{(x, y) \mid x \in \mathbb{R}, y \in \mathbb{R}\}$$
is the set of all ordered pairs of real numbers. This is the “coordinate plane” (or “$xy$-plane”) that is used to draw the graphs of functions.

The formula $y = f(x)$ often appears in elementary algebra, and, in that subject, the variables $x$ and $y$ represent real numbers. However, advanced math courses allow $x$ and $y$ to be elements of any sets $A$ and $B$, not just from $\mathbb{R}$. Therefore, it is important to generalize the above example by replacing the two appearances of $\mathbb{R}$ in the right-hand side of Equation $6.1.3$ with arbitrary sets $A$ and $B$:

Definition $6.1.4$.

For any sets $A$ and $B$, we let $$A \times B=\{(a, b) \mid a \in A, b \in B\} .$$
This notation means, for all $x$, that $$x \in A \times B \text { iff } \exists a \in A, \exists b \in B, x=(a, b) .$$
The set $A \times B$ is called the Cartesian product of $A$ and $B$.

Example $6.1.5$.

1. $\mathbb{R} \times \mathbb{R} = \mathbb{R}^{2}$.
2. $\{1,2,3\} \times\{\mathrm{a}, \mathrm{b}\}=\{(1, \mathrm{a}),(1, \mathrm{~b}),(2, \mathrm{a}),(2, \mathrm{~b}),(3, \mathrm{a}),(3, \mathrm{~b})\}$.
3. $\{a, b\} \times\{1,2,3\}=\{(a, 1),(a, 2),(a, 3),(b, 1),(b, 2),(b, 3)\}$.

By comparing (2) and (3), we see that $\times$ is not commutative: $A \times B$ is usually not equal to $B \times A$.

Exercise $6.1.6$.

Specify each set by listing its elements.

1. $\{a, i\} \times\{n, t\}=$
2. $\{\mathrm{Q}, \mathrm{K}\} \times$ {♣, ♦, ♥, ♠} =
3. $\{1,2,3\} \times\{3,4,5\}=$

Remark $6.1.7$.

We will prove in Theorem $9.1.18$ that $$\#(A \times B)=\# A \cdot \# B .$$

In other words: $$\text { cardinality of a Cartesian product is the product of the cardinalities.}$$
For now, let us just give an informal justification:

Suppose $\#A = m$ and $\#B = n$. Then, by listing the elements of these sets, we may write $$A=\left\{a_{1}, a_{2}, a_{3}, \ldots, a_{m}\right\} \quad \text { and } \quad B=\left\{b_{1}, b_{2}, b_{3}, \ldots, b_{n}\right\} .$$
The elements of $A \times B$ are: $$\begin{array}{ccccc} \left(a_{1}, b_{1}\right), & \left(a_{1}, b_{2}\right), & \left(a_{1}, b_{3}\right), & \cdots & \left(a_{1}, b_{n}\right) \\ \left(a_{2}, b_{1}\right), & \left(a_{2}, b_{2}\right), & \left(a_{2}, b_{3}\right), & \cdots & \left(a_{2}, b_{n}\right), \\ \left(a_{3}, b_{1}\right), & \left(a_{3}, b_{2}\right), & \left(a_{3}, b_{3}\right), & \cdots & \left(a_{3}, b_{n}\right), \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ \left(a_{m}, b_{1}\right), & \left(a_{m}, b_{2}\right), & \left(a_{m}, b_{3}\right), & \cdots & \left(a_{m}, b_{n}\right) . \end{array}$$
In this array,

• each row has exactly $n$ elements, and
• there are $m$ rows,

so the number of elements is the product $m n=\# A \cdot \# B .$

Here are some examples of proofs involving Cartesian products.

Example $6.1.8$.

If $A$ and $B$ are nonempty sets, and $A \times B = B \times A$, then $A = B$.

Solution

PROOF.

Assume $A$ and $B$ are nonempty sets, such that $A \times B = B \times A$. It suffices to show $A \subset B$ and $B \subset A$. By symmetry, we need only show $A \subset B$.

Let $a_{0}$ be an arbitrary element of $A$. Since $B$ is nonempty, there exists some $b_{0} \in B$. Then $$\left(a_{0}, b_{0}\right) \in A \times B=B \times A=\{(b, a) \mid b \in B, a \in A\} ,$$
so there exist $b \in B$ and $a \in A$, such that $\left(a_{0}, b_{0}\right)=(b, a)$. Therefore, $a_{0} = b$ (and $b_{0} = a$, but we do not need that fact). Hence $a_{0} = b \in B$.

Example $6.1.9$.

If $B$ is disjoint from $C$, then $A \times B$ is disjoint from $A \times C$.

Solution

PROOF.

We prove the contrapositive: Assume $A \times B$ is not disjoint from $A \times C$, and we will show $B$ is not disjoint from $C$.

By assumption, the intersection of $A \times B$ and $A \times C$ is not empty, so we may choose some $$x \in(A \times B) \cap(A \times C) .$$
Then:

• Since $x \in A \times B$, there exist $a_{1} \in A$ and $b \in B$, such that $x=\left(a_{1}, b\right)$.
• Since $x \in A \times C$, there exist $a_{2} \in A$ and $c \in C$, such that $x = (a_{2}, c)$.

Hence $\left(a_{1}, b\right)=x=\left(a_{2}, c\right)$, so $b = c$. Now $b \in B$ and $b = c \in C$, so $b \in B \cap C$. Therefore $B \cap C \neq \varnothing$, so, as desired, $B$ and $C$ are not disjoint.

Remark $6.1.10$.

When reading the proof above, you may have noticed that the variable $x$ (a single letter) was used to represent an ordered pair $(a, b)$. There is nothing wrong with this, because the ordered pair is a single object, and a variable can represent any mathematical object at all, whether it is an element of a set, or an entire set, or a function, or an ordered pair, or something else.

Example $6.1.11$.

Assume $A$, $B$, and $C$ are sets. Prove $A \times (B \cup C) = (A \times B) \cup (A \times C)$.

Solution

PROOF.

($\subset$) Given $x \in(A \times B) \cup(A \times C)$, we have $x \in A \times B$ or $x \in A \times C$. By symmetry, we may assume $x \in A \times B$, so $x = (a, b)$ for some $a \in A$ and $b \in B$. Note that $b \in B \cup C$, so we have $a \in A$ and $b \in B \cup C$. Therefore $$x=(a, b) \in A \times(B \cup C)$$
Since $x$ is an arbitrary element of $(A \times B) \cup (A \times C)$, this implies $(A \times B) \cup(A \times C) \subset A \times(B \cup C)$.

($\subset$) Given $(a, x) \in A \times(B \cup C),$, we have $a \in A$, and either $x \in B$ or $x \in C$. By symmetry, we may assume $x \in B$. Then $(a, x) \in A \times B \subset(A \times B) \cup(A \times C)$, so $(a, x) \in(A \times B) \cup(A \times C)$. Since $(a, x)$ is an arbitrary element of $A \times (B \cup C)$, this implies $A \times(B \cup C) \subset(A \times B) \cup(A \times C)$.

Exercise $6.1.12$.

1. Suppose $A$, $B$, and $C$ are sets.
   1. Show that if $B \subset C$, then $A \times B \subset A \times C$.
   2. Show that if $A \times B = A \times C$, and $A \neq \varnothing$, then $B = C$.
2. Suppose $A$ is a set.
   1. Show $A \times \varnothing=\varnothing$.
   2. Show $A \times A=\varnothing$ if and only if $A=\varnothing$.
3. To say that $\times$ is distributive over $\cup$ means that, for all sets $A$, $B$, and $C$, we have $$A \times(B \cup C)=(A \times B) \cup(A \times C) \quad \text { and } \quad(B \cup C) \times A=(B \times A) \cup(C \times A) .$$
   The first equation was established in Example $6.1.11$. Complete the proof that $\times$ is distributive over $\cup$ by proving the second equation.
4. Show that $\times$ is distributive over $\cap$. That is, for all sets $A$, $B$, and $C$, we have
   1. $A \times(B \cap C)=(A \times B) \cap(A \times C)$, and
   2. $(B \cap C) \times A=(B \times A) \cap(C \times A)$.