Ordered pairs and Cartesian products

To talk about relations such as "$x$ is less than $y$" or "$P$ lies on the line $y = 2x$", we need a way to write a pair of objects in which order matters. The set $\{2, 3\}$ does not distinguish first from second. The ordered pair $(2, 3)$ does.

Definitions

An ordered pair $(a, b)$ is a pair of objects where $a$ is the first coordinate (or first component) and $b$ is the second coordinate.

Equality. Two ordered pairs are equal iff their first coordinates match and their second coordinates match: $(a, b) = (c, d) \iff a = c \ \text{and}\ b = d.$

In particular, $(2, 3) \ne (3, 2)$ , order matters.

Given two sets $A$ and $B$, the Cartesian product of $A$ and $B$ is $A \times B = \{(a, b) : a \in A,\ b \in B\}.$ We read $A \times B$ as "A cross B". If either $A$ or $B$ is empty, $A \times B = \varnothing$.

We similarly define $A \times B \times C = \{(a, b, c) : a \in A, b \in B, c \in C\}$ , ordered triples.

Size of the Cartesian product

Theorem. If $A$ and $B$ are finite sets, $|A \times B| = |A| \cdot |B|$.

Proof. Each element of $A \times B$ is a pair $(a, b)$. There are $|A|$ choices for $a$ and, independently, $|B|$ choices for $b$. By the multiplication principle, the total number of pairs is $|A| \cdot |B|$. $\qed$

Cartesian plane

When $A = B = \mathbb{R}$, we get $\mathbb{R} \times \mathbb{R} = \mathbb{R}^2 = \{(x, y) : x, y \in \mathbb{R}\}.$ This is the Cartesian plane , every point of which is described by an ordered pair $(x, y)$ of real numbers. The coordinate axes and the four quadrants you learned in geometry are nothing but a picture of $\mathbb{R}^2$.

Standard identities

For all sets $A, B, C$:

• $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 \varnothing = \varnothing$.
• If $A \subseteq B$, then $A \times C \subseteq B \times C$ for any $C$.

These follow by checking ordered-pair-by-ordered-pair. For instance, $(x, y) \in A \times (B \cup C) \iff x \in A$ and $y \in B \cup C \iff x \in A$ and ($y \in B$ or $y \in C$) $\iff (x, y) \in A \times B$ or $(x, y) \in A \times C \iff (x, y) \in (A \times B) \cup (A \times C)$.

Worked examples

Example 1. If $A = \{1, 2\}$ and $B = \{a, b, c\}$, list $A \times B$ and $B \times A$ and find their sizes.

$A \times B = \{(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)\}$, $|A \times B| = 6$.

$B \times A = \{(a, 1), (a, 2), (b, 1), (b, 2), (c, 1), (c, 2)\}$, $|B \times A| = 6$.

The two have the same size but are different sets ($(1, a) \in A \times B$ but $(1, a) \notin B \times A$).

Example 2. If $(x + 1, y - 2) = (3, 1)$, find $x$ and $y$.

Matching coordinates: $x + 1 = 3 \Rightarrow x = 2$; $y - 2 = 1 \Rightarrow y = 3$.

Example 3. Let $A = \{x \in \mathbb{R} : 0 < x < 1\}$ and $B = \{1, 2, 3\}$. Describe $A \times B$.

$A \times B$ is the union of three horizontal segments in the plane: $\{(x, 1) : 0 < x < 1\}$, $\{(x, 2) : 0 < x < 1\}$, $\{(x, 3) : 0 < x < 1\}$.

Example 4. If $|A| = 3$ and $|A \times B| = 12$, find $|B|$.

$|A \times B| = |A| \cdot |B|$ gives $12 = 3 \cdot |B|$, so $|B| = 4$.

Example 5 (harder). Show $A \times B = B \times A \iff A = B$ or one of them is empty.

If $A = B$ then $A \times B = A \times A = B \times A$. If $A = \varnothing$ or $B = \varnothing$, both products are $\varnothing$.

Conversely, suppose $A \ne \varnothing$, $B \ne \varnothing$, and $A \times B = B \times A$. Pick $a \in A, b \in B$. Then $(a, b) \in A \times B = B \times A$, forcing $a \in B$ and $b \in A$. Hence $A \subseteq B$ and $B \subseteq A$, so $A = B$. $\qed$

Try it yourself

1. Find $(x, y)$ if $(2x - 1, y + 3) = (5, -2)$.
2. List $A \times B$ for $A = \{1, 2, 3\}$, $B = \{a\}$. What is $|A \times B|$?
3. Find $|A \times B|$ if $|A| = 7$, $|B| = 5$.
4. If $A \times B$ has $9$ elements and contains $(1, 2)$ and $(2, 4)$, find $A$ and $B$ (given $|A| = |B|$).
5. Let $A = \{1, 2\}$. List all elements of $A \times A \times A$.
6. Show $(A \cup B) \times C = (A \times C) \cup (B \times C)$.
7. If $A = \{1, 2\}, B = \{3, 4\}, C = \{2, 5\}$, find $A \times (B \cap C)$ and $(A \times B) \cap (A \times C)$.
8. Plot $A \times B$ on graph paper for $A = \{1, 2, 3\}$ and $B = \{2, 4\}$.
9. If $(x + y, x - y) = (5, 1)$, find $x, y$.
10. Verify $A \times \varnothing = \varnothing \times A = \varnothing$.
11. If $A = \{x \in \mathbb{R} : 1 \le x \le 2\}$ and $B = \{y \in \mathbb{R} : 0 \le y \le 3\}$, describe $A \times B$ geometrically.
12. Show that for sets $A, B$, $A \times B = B \times A$ does not in general hold.

Pitfalls / Tricks

• $(a, b) \ne \{a, b\}$. The ordered pair is not the same as the unordered set.
• In general $A \times B \ne B \times A$ even though $|A \times B| = |B \times A|$.
• $A \times \varnothing = \varnothing$: any product with the empty set is empty.
• Insight. Cartesian products are how you encode several pieces of information at once. A pair $(x, y)$ stores two numbers; a triple $(x, y, z)$ stores three. Multi-dimensional thinking starts here.