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