Ordered Pairs and Cartesian Products

The Cartesian product is the literal foundation on which relations and functions are built: a relation from $A$ to $B$ is defined as any subset of $A\times B$, and a function is a relation satisfying an extra existence-and-uniqueness clause — both concepts are meaningless without first having $A\times B$ available as a genuine set, which is exactly what this article establishes. In Relations as Sets of Ordered Pairs this becomes the starting definition. In computer science, ordered pairs and products underlie the type `A × B` (product types) in typed functional languages, tuple data structures, and relational database theory, where a table is literally a finite subset of a Cartesian product of column domains. In cryptography and coding theory, finite Cartesian products $\{0,1\}^n$ (an $n$-fold product of the two-element set) are the ambient space for bit-strings. In probability and statistics, joint sample spaces for two random variables are modeled as $\Omega_1 \times \Omega_2$, with joint distributions as measures on the product. In topology and analysis, the product topology on $A\times B$ (and more generally on infinite products, via Cardinality and Cardinal Arithmetic-adjacent machinery) is defined using exactly this set, and $\mathbb{R}\times\mathbb{R} = \mathbb{R}^2$ recovers ordinary coordinate geometry as the special case $A=B=\mathbb{R}$.

Ask the tutor: How does the Kuratowski definition of ordered pairs let us define a relation from $A$ to $B$ purely as a subset of $A \times B$?

The unordered pair $\{a,b\}$ throws $a$ and $b$ into a set and forgets which one came first — $\{2,3\}$ and $\{3,2\}$ are literally the same set, since a set is determined solely by its members. To encode order, Kuratowski's trick is to build a set that contains a "marked" singleton alongside the full pair. In $(a,b) = \{\{a\},\{a,b\}\}$, the singleton $\{a\}$ flags $a$ as the distinguished element, while $\{a,b\}$ records both members. Reading the set back, you can tell which element was "first" by finding the element that appears in the smaller piece $\{a\}$ — this is the whole content of the Coordinate Theorem proved below, and the case $a=b$ needs a little extra care, handled in the proof. Once pairs are set up, $A \times B$ is simply the set of every possible pairing of an element of $A$ with an element of $B$, laid out as a rectangular grid when $A, B \subseteq \mathbb{R}$. The picture below shows a small concrete product $A \times B$ with $A=\{1,2,3\}$ (horizontal) and $B=\{x,y\}$ (vertical), alongside the internal Kuratowski structure of a single pair.

This lemma is what allows us to speak of $A \times B$ as an object we can quantify over, take subsets of (relations!), and apply further set operations to — it is not a mere shorthand for an infinite unwritten list.

The case split above is exactly why the naive guess "$(a,b) := \{a,b\}$" fails and why the nested structure $\{\{a\},\{a,b\}\}$ is needed: it is precisely engineered so that when $a=b$ the outer set degenerates to a singleton in a way that still lets us recover $a$, while when $a \ne b$ the asymmetry between the singleton branch and the pair branch pins down which element was first.

Example 1 (computing a concrete Kuratowski pair and unwinding it). Let $A = \{1,2\}$ and $B=\{2,3\}$, both finite sets of natural numbers, and consider the pair $(2,3) \in A\times B$ where the coordinate $2$ happens to be shared with the "wrong" set $B$ as well — a deliberately asymmetric, easily-confused case. By definition,

This is a set with two elements: the singleton $\{2\}$ and the pair-set $\{2,3\}$. Let us verify by hand, using only the Coordinate Theorem, that this is genuinely different from $(3,2) = \{\{3\},\{3,2\}\} = \{\{3\},\{2,3\}\}$. Suppose toward showing they're unequal we directly compare the two representations:

The first has $\{2\}$ as a member; does the second? The second's members are $\{3\}$ and $\{2,3\}$. Is $\{2\} = \{3\}$? No, since $2 \ne 3$ (as elements) means these singletons have different unique elements. Is $\{2\} = \{2,3\}$? No, since $3 \in \{2,3\}$ but $3 \notin \{2\}$ (as $3 \ne 2$). So $\{2\}$ is a member of the first set but not the second, hence the two outer sets are unequal by extensionality: $(2,3) \ne (3,2)$. This matches the Coordinate Theorem's prediction directly: $(2,3)=(3,2)$ would require $2=3$ (comparing first coordinates), which is false, so the theorem guarantees inequality without any set manipulation — the hand computation above is simply that guarantee unpacked. Now let us list $A \times B$ in full, to see the "grid," including the coincidence that $2$ appears in both $A$ and $B$:

Each of these four is a distinct Kuratowski set:

Note $(2,2)$ collapses to the singleton $\{\{2\}\}$, exactly as in Case 1 of the Coordinate Theorem's proof — this is the only pair here with equal coordinates, and it is the only one whose Kuratowski set has just one element rather than two. Compare with $B \times A = \{2,3\}\times\{1,2\} = \{(2,1),(2,2),(3,1),(3,2)\}$; the two products share the single element $(2,2)$ but are otherwise disjoint as sets of pairs, illustrating Theorem 7 above: since $A\ne B$ (as $1\in A\setminus B$), we must have $A\times B \ne B\times A$, which indeed holds since e.g. $(1,2) \in A\times B$ but $(1,2)\notin B\times A$ (as $1 \notin B$, so no pair in $B\times A$ has first coordinate $1$).

Example 2 (an infinite, asymmetric product and a subtlety about "diagonal" elements). Let $A = \mathbb{N} = \{0,1,2,\dots\}$ and $B = \{0,1\}$. Consider $A \times B$, an infinite set of ordered pairs — this models, for instance, the graph of a function $\mathbb{N} \to \{0,1\}$ once we restrict to pairs forming a valid function, foreshadowing Relations as Sets of Ordered Pairs. We compute a specific pair with a repeated numeral to stress-test the definition: take $a=1 \in A$ and $b=1 \in B$ (the same natural number $1$ used in two different roles, as an element of $A$ and as an element of $B$). Then

using that $\{1,1\}=\{1\}$ as sets (repetition in listing notation does not create new elements). So $(1,1)$ is a singleton set containing a singleton set. Contrast this with $(1,0) = \{\{1\},\{1,0\}\}$, which has two distinct elements since $\{1\}\ne\{1,0\}$ (because $0 \in \{1,0\}$ but $0\notin\{1\}$). Now here is the subtlety: is $(1,1) \in A\times B$ actually equal to the number $1$, or to the singleton $\{1\}$, under some encodings of natural numbers as sets (e.g. the von Neumann encoding where $1 := \{0\}$, $2:=\{0,1\}$, etc.)? This is worth checking carefully because a careless reader might worry the Kuratowski pair collides with a "coincidental" von Neumann numeral. Under the von Neumann encoding, $0 := \varnothing$ and $1 := \{\varnothing\} = \{0\}$. Then $\{1\} = \{\{0\}\}$, a set whose unique element is itself a singleton (namely $1$). So $(1,1) = \{\{1\}\} = \{\{\{0\}\}\}$, while the numeral $2 := \{0,1\} = \{\varnothing, \{\varnothing\}\}$, a two-element set. These are visibly different sets (one has one element, the other has two), so no collision occurs — but the exercise shows why one must always unwind definitions explicitly rather than trust intuition when several set-theoretic constructions ($\mathbb{N}$ as von Neumann ordinals, and $(a,b)$ as Kuratowski pairs) are stacked together. This is exactly the kind of verification the Coordinate Theorem is designed to make routine: no matter what $a$ and $b$ "secretly" are as sets, $(a,b)=(c,d)$ reduces purely to $a=c \wedge b=d$, so no accidental collision between differently-motivated set constructions can ever corrupt the coordinate-recovery property.