Ordered Pairs and Cartesian Products

Why introduce a brand-new kind of pair when sets already exist? Because sets throw away order: ${a, b}$ is the same as ${b, a}$. The instant you want to record "first item then second" — a coordinate, an arrow, a function value, a database row — you need a structure that remembers which slot each element sits in. The ordered pair $(a, b)$ does exactly that. From this one tiny scaffold we build Cartesian products, relations, functions, graphs, even the entire $xy$-plane. Everything in Chapters 4 and 5 depends on getting comfortable with ordered pairs — they are the smallest container that knows about order.

The ordered pair

An ordered pair $(a, b)$ is a mathematical object that records two elements in a specific order. The defining feature is its equality rule:

Order matters: $(1, 2) \neq (2, 1)$ even though ${1, 2} = {2, 1}$ as sets. Internally, Kuratowski showed you can build ordered pairs out of plain sets via $(a, b) := {{a}, {a, b}}$, but for working math you only need the equality rule.

The Cartesian product

The Cartesian product of two sets $A$ and $B$ is the set of all ordered pairs whose first slot lives in $A$ and second slot in $B$:

If $|A| = m$ and $|B| = n$ then $|A \times B| = m \cdot n$: for each of the $m$ first-slot choices there are $n$ second-slot choices. Familiar example: $\mathbb{R} \times \mathbb{R} = \mathbb{R}^2$ is the $xy$-plane. Generalising, $A^n = A \times A \times \cdots \times A$ ($n$ times) is the set of $n$-tuples drawn from $A$.

Useful identities

The Cartesian product is not commutative: in general $A \times B \neq B \times A$ (they are equinumerous but their pairs are reversed). It interacts cleanly with unions, intersections and the empty set:

(The Venn widget above visualises the unions and intersections that feed the Cartesian-product identities; ordered pairs themselves do not Venn-diagram, but the set operations on the right-hand sides of the identities above do.)

Pause and think: If $|A| = 4$ and $|B| = 7$, how many elements live in $A \times B$? In $B \times A$? Are those two sets equal? (Hint: same cardinality, different pairs.)

Try it

• Predict first: list all elements of ${1, 2} \times {x, y, z}$ before you check — you should get exactly $2 \cdot 3 = 6$ pairs.
• If $(2x - 1, y + 3) = (5, 4)$, what are $x$ and $y$? Match components before doing algebra.
• Is $(1, 2) \in {1, 2} \times {1, 2}$? Is $(2, 3)$? Argue from the definition, not from a picture.
• Why is $A \times \emptyset = \emptyset$ no matter what $A$ is? Sketch the proof in one sentence.
• Compare $({1,2} \times {a,b})$ and $({a,b} \times {1,2})$. Do they share any element?

A trap to watch for

Beginners often write ${1, 2} \times {a, b} = {1, 2, a, b}$ or $= {{1, a}, {2, b}, \ldots}$. Both are wrong. The product is a set of ordered pairs, not a flattened union, and the components inside each pair are wrapped in $(,,,)$, not ${,,,}$. The correct answer is ${(1, a), (1, b), (2, a), (2, b)}$. The brace-vs-paren distinction matters: ${a, b} = {b, a}$ but $(a, b) \neq (b, a)$.

What you now know

You can build the Cartesian product of any two sets, count its elements, recognise it inside a SQL join or a type signature, and prove identities involving it via component-level reasoning. In the next section you will see that any subset of a Cartesian product is called a relation — and that gives you the language to talk about every mathematical structure built from "this is connected to that."

References

• Velleman, D. J. (2019). How to Prove It: A Structured Approach (3rd ed.). Cambridge University Press, §4.1.
• Halmos, P. R. (1960). Naive Set Theory. Springer, §6.
• Enderton, H. B. (1977). Elements of Set Theory. Academic Press, ch. 3.
• Date, C. J. (2003). An Introduction to Database Systems (8th ed.). Addison-Wesley, ch. 6 (relational algebra and Cartesian product).
• Hammack, R. (2018). Book of Proof, ch. 8.