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

Find $(x, y)$ if $(2x - 1, y + 3) = (5, -2)$ .
List $A \times B$ for $A = \{1, 2, 3\}$ , $B = \{a\}$ . What is $|A \times B|$ ?
Find $|A \times B|$ if $|A| = 7$ , $|B| = 5$ .
If $A \times B$ has $9$ elements and contains $(1, 2)$ and $(2, 4)$ , find $A$ and $B$ (given $|A| = |B|$ ).
Let $A = \{1, 2\}$ . List all elements of $A \times A \times A$ .
Show $(A \cup B) \times C = (A \times C) \cup (B \times C)$ .
If $A = \{1, 2\}, B = \{3, 4\}, C = \{2, 5\}$ , find $A \times (B \cap C)$ and $(A \times B) \cap (A \times C)$ .
Plot $A \times B$ on graph paper for $A = \{1, 2, 3\}$ and $B = \{2, 4\}$ .
If $(x + y, x - y) = (5, 1)$ , find $x, y$ .
Verify $A \times \varnothing = \varnothing \times A = \varnothing$ .
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.
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.