Cartesian Products and Relations

When order mat­ters#

A point on a graph, a seat marked "row, col­umn" in a cin­ema hall: in both, the order of the two entries mat­ters, and $(2, 5)$ is not the same as $(5, 2)$. Pairs like these build the Carte­sian prod­uct of two sets, and a rela­tion turns out to be noth­ing more than a col­lec­tion of such pairs. We will define ordered pairs and Carte­sian prod­ucts, count them, and then describe rela­tions in ros­ter form, set-builder form and arrow dia­grams, along with their domain, codomain and range. All of this is the ground­work for func­tions in the next les­son.

Ordered pairs and Carte­sian prod­ucts#

Two ordered pairs are equal only when they match entry by entry: $(a, b) = (c, d)$ exactly when $a = c$ and $b = d$. So $(x - 2, y + 3) = (4, -1)$ gives $x = 6$ and $y = -4$.

The Carte­sian prod­uct col­lects every pos­si­ble pair: $A \times B = \{(a, b) : a \in A, b \in B\}$. For $A = \{1, 2\}$ and $B = \{x, y, z\}$:

$$A \times B = \{(1, x), (1, y), (1, z), (2, x), (2, y), (2, z)\}$$

Every ele­ment of the first set pairs with every ele­ment of the sec­ond, so $n(A \times B) = n(A) \cdot n(B)$. Watch the order, though: $A \times B \ne B \times A$ unless $A = B$ (or one of them is empty). You have been using a Carte­sian prod­uct for years with­out the name: $\mathbf{R} \times \mathbf{R}$ is the coor­di­nate plane, and $\mathbf{R} \times \mathbf{R} \times \mathbf{R}$ is space.

Rela­tions#

Out of all the pos­si­ble pairs, a rule usu­ally picks out only some. That selec­tion is a rela­tion: a rela­tion from $A$ to $B$ is any sub­set $R$ of $A \times B$. We write $(a, b) \in R$ or $a \, R \, b$, and call $b$ the image of $a$.

• Domain: the set of first ele­ments of pairs in $R$.
• Codomain: the whole of $B$.
• Range: the set of sec­ond ele­ments actu­ally used, which is a sub­set of the codomain.

Count­ing rela­tions. The same in-or-out argu­ment you used for sub­sets works here. $A \times B$ has $n(A) \, n(B)$ pairs, and each one is either in the rela­tion or out, so there are $2^{n(A) n(B)}$ rela­tions from $A$ to $B$. With $n(A) = 2$ and $n(B) = 3$, that is already $2^6 = 64$.

Prac­tice ques­tions#

1. Find $x$ and $y$: $(2x + 1, y - 3) = (7, 5)$; $\displaystyle (\tfrac{x}{3} + 1, y - \tfrac{2}{3}) = (\tfrac{5}{3}, \tfrac{1}{3})$.
2. $A = \{-1, 1\}$, $B = \{0, 2, 4\}$. Write $A \times B$ and $B \times A$. Are they equal?
3. $A$ has $4$ ele­ments and $B$ has $3$. How many ele­ments in $A \times B$? How many rela­tions from $A$ to $B$?
4. $A \times A$ has $9$ ele­ments, two of which are $(2, 5)$ and $(5, 7)$. Find $A$ and the remain­ing ele­ments.
5. $A = \{1, 2\}$, $B = \{1, 2, 3, 4\}$, $C = \{5, 6\}$, $D = \{5, 6, 7, 8\}$. Ver­ify $A \times C \subset B \times D$.
6. On $A = \{1, 2, 3, \ldots, 12\}$ define $R = \{(a, b) : b = 2a - 1\}$. Write $R$ in ros­ter form; find its domain and range.
7. $R = \{(x, x^3) : x \text{ a prime less than } 8\}$. Write $R$ and its range.
8. From an arrow dia­gram with $1 \to 4$, $2 \to 5$, $3 \to 4$, $3 \to 6$: write $R$, domain and range.
9. On $\mathbf{Z}$, $R = \{(a, b) : a - b \text{ is a multiple of } 3\}$. Is $(7, 1) \in R$? $(5, -1)$? $(2, 6)$?
10. True or false: if $(a, b) \in A \times B$ and $(b, c) \in B \times C$ then $(a, c) \in A \times C$.

Answers#