Relations as Sets of Ordered Pairs

The relation-as-set-of-pairs viewpoint underlies enormous swaths of mathematics and computer science. In pure mathematics it is the immediate precursor to Properties of Relations (reflexivity, symmetry, transitivity), to equivalence relations and quotient constructions, and to partial and total orders that structure everything from cardinal arithmetic to lattice theory. It is also the precursor to Functions as Special Relations: a function $f: A \to B$ is defined as a relation $R \subseteq A\times B$ satisfying $\operatorname{dom}(R) = A$ together with a uniqueness clause (for each $a$, at most one $b$ with $aRb$) — so functions are a special case, not a separate primitive notion. In computer science, relational databases are literally implementations of finite relations: a database table is a finite subset of a Cartesian product of column domains, and relational algebra (joins, projections, selections) is set-theoretic manipulation of these subsets. Graph theory identifies a directed graph with a relation on its vertex set. In logic and model theory, relational structures (models of a first-order language) interpret relation symbols as exactly such subsets of Cartesian powers of a domain. In cryptography and complexity theory, one-way functions, hard relations, and NP-relations are formalized as subsets of pairs $(x,y)$ satisfying a checkable condition, directly generalizing this definition to computational contexts. In statistics and probability, a joint distribution can be viewed as living on a relation-like structure — the support of a joint random pair is a subset of a product space, echoing the same set-of-pairs idea underlying correlation and dependence between variables.

Ask the tutor: How does adding the properties of reflexivity, symmetry, and transitivity to a relation on a set lead to the definition of an equivalence relation and equivalence classes?

Think of $A \times B$ as a grid: rows indexed by elements of $A$, columns indexed by elements of $B$. Every possible ordered pair $(a,b)$ is one cell of this grid. A relation $R$ is a choice of some cells to "shade in" — nothing about why those cells are chosen matters to the mathematics; only the resulting shaded set matters. The domain is the set of rows containing at least one shaded cell; the range is the set of columns containing at least one shaded cell. This grid picture immediately explains several facts that otherwise feel mysterious. Two relations described by completely different English sentences are the same relation if they shade exactly the same cells. A relation need not touch every row or every column — hence domain and range can be strictly smaller than $A$ and $B$. And since a relation is just a subset of a set with $|A|\cdot|B|$ elements, counting relations is counting subsets: there are exactly $2^{|A||B|}$ of them when $A, B$ are finite.

Example 1 (an explicit small relation with domain and range strictly smaller than $A$, $B$). Let $A = \{1, 2, 3, 4, 5\}$ and $B = \{p, q, r\}$. Define

Checking $R$ is genuinely a relation from $A$ to $B$: each listed pair has first coordinate in $A$ and second coordinate in $B$, so indeed $R \subseteq A \times B$. Domain. An element $a \in A$ belongs to $\operatorname{dom}(R)$ iff some pair in $R$ has $a$ as first coordinate. Scanning $R$: first coordinates appearing are $1$ (twice) and $3$ (twice). Elements $2, 4, 5 \in A$ never appear as a first coordinate. Hence

Range. Second coordinates appearing in $R$ are $p, q, r$ — in fact all three elements of $B$ occur (namely $p$ from $(1,p)$, $q$ from $(1,q)$ or $(3,q)$, and $r$ from $(3,r)$). Hence

Reading off $aRb$ statements. By definition $1\,R\,p$ (since $(1,p)\in R$), $1\,R\,q$, $3\,R\,q$, $3\,R\,r$, while $2 \not R\, p$ (since $(2,p) \notin R$), and indeed $2$ is unrelated by $R$ to every element of $B$, consistent with $2 \notin \operatorname{dom}(R)$. Cardinality check. Here $|A|=5$, $|B|=3$, so by the Theorem there are $2^{15} = 32768$ relations from $A$ to $B$ in total; $R$, with $4$ pairs, is just one particular subset among these $32768$, namely one of the $\binom{15}{4} = 1365$ subsets of size exactly $4$.

Example 2 (a relation defined by a condition, converted into explicit pair form). Let $A = \{2,3,4,5,6\}$ and $B = \{4,5,6,7,8,9\}$, and define the "divides" relation

Here $a \mid b$ means $b = ka$ for some integer $k$ — this is the rule used to decide membership, but $R$ itself is the resulting set of pairs, not the rule. We compute $R$ explicitly by checking each $a \in A$ against each $b \in B$:

• $a=2$: divides $4,6,8$ among $B$. Pairs: $(2,4),(2,6),(2,8)$.
• $a=3$: divides $6,9$ among $B$. Pairs: $(3,6),(3,9)$.
• $a=4$: divides $4,8$ among $B$. Pairs: $(4,4),(4,8)$.
• $a=5$: divides none of $4,5,6,7,8,9$ that are multiples of $5$ within $B$ — check: $5 \mid 5$ is true since $5 = 1\cdot 5$! Recheck: $5$ divides $5$. Pair: $(5,5)$.
• $a=6$: divides $6$ among $B$ (does $6$ divide $12$? not in $B$). Pair: $(6,6)$.

So

This has $9$ ordered pairs. Domain. First coordinates occurring: $2,3,4,5,6$ — every element of $A$ occurs (each $a$ divides itself, and $a \in B$ for $a \in \{4,5,6\}$, while $2,3$ divide larger elements of $B$). Hence

Range. Second coordinates occurring: $4,6,8$ (from $a=2$), $6,9$ (from $a=3$), $4,8$ (from $a=4$), $5$ (from $a=5$), $6$ (from $a=6$). Collecting distinct values: $\{4,5,6,8,9\}$. Note $7$ never appears — indeed no $a \in A$ divides $7$, since $7$ is prime and none of $2,3,4,5,6$ equal $1$ or $7$. Hence

because $7 \in B \setminus \operatorname{ran}(R)$. Infix notation in use. We may write $2\,R\,8$ (true, since $2 \mid 8$) and $3 \not R\, 8$ (false, since $3 \nmid 8$); both are just restatements of $(2,8) \in R$ and $(3,8) \notin R$ respectively.

The rigorous reduction of "relation" to "set of ordered pairs" is a product of the broader foundational program that reduced essentially all mathematical objects to pure sets, carried out especially through the work of Felix Hausdorff, Kazimierz Kuratowski, and Norbert Wiener on the set-theoretic definition of the ordered pair itself, combined with the systematic set-theoretic treatment of functions and relations that crystallized in the early-to-mid twentieth century. Kuratowski's 1921 definition of the ordered pair, $(a,b) := \{\{a\},\{a,b\}\}$, made it possible to define $A \times B$ purely as a set built from $A$ and $B$, and once that was in hand, "relation" could be defined with no further primitives — simply as a subset of $A \times B$.