Relations

⚡ Key Takeaways

A relation from a set $A$ to a set $B$ is any subset of the Cartesian product $A \times B$ — a precise way to encode "is connected to," "is less than," or "is equal to." The key result is that relations on a single set are classified by which of three properties (reflexivity, symmetry, transitivity) they satisfy, yielding equivalence relations (which partition sets) and order relations (which rank them). Relations appear everywhere in mathematics, computer science, and logic. The modern set-theoretic formulation is due to Peirce, Schröder, and Russell in the late 19th and early 20th centuries.

💡 The Core Insight

Everything that connects mathematical objects — equality, order, divisibility, congruence, adjacency — is captured by selecting which pairs belong together. A relation is just a set of ordered pairs. By demanding combinations of three structural properties (reflexive, symmetric, transitive), we carve out the two most important species: equivalence relations (which behave like generalized equality) and partial orders (which behave like generalized $\leq$ ). The miracle is how much mathematics is generated by these three axioms.

DefinitionBinary Relation

Let $A$ and $B$ be sets. A binary relation $R$ from $A$ to $B$ is a subset of the Cartesian product:

1

\quad R \subseteq A \times B = \{(a,b) : a \in A,\ b \in B\}

Derivation hint: The Cartesian product collects every possible ordered pair; a relation simply selects which pairs to keep. We write $a\,R\,b \iff (a,b) \in R$ . When $A = B$ , we call $R$ a relation on $A$ . The domain and range are:

2

\quad \operatorname{dom}(R) = \{a \in A : \exists b,\ (a,b)\in R\}, \qquad \operatorname{ran}(R) = \{b \in B : \exists a,\ (a,b)\in R\}

Derivation hint: Project the pairs in $R$ onto their first and second coordinates respectively.

DefinitionThe Three Structural Properties

A relation $R$ on a set $A$ may satisfy:

3

\quad \textbf{Reflexive:}\quad \forall a \in A,\ \ a\,R\,a

Derivation hint: Every element relates to itself — the diagonal $\Delta_A = \{(a,a)\} \subseteq R$ .

4

\quad \textbf{Symmetric:}\quad \forall a,b \in A,\ \ a\,R\,b \implies b\,R\,a

Derivation hint: The relation is its own inverse, $R = R^{-1}$ , where $R^{-1} = \{(b,a) : (a,b)\in R\}$ .

5

\quad \textbf{Transitive:}\quad \forall a,b,c \in A,\ \ (a\,R\,b \ \wedge\ b\,R\,c) \implies a\,R\,c

Derivation hint: Chains compose — composing $R$ with itself stays inside $R$ , i.e. $R \circ R \subseteq R$ . Two further properties define orderings:

6

\quad \textbf{Antisymmetric:}\quad \forall a,b \in A,\ \ (a\,R\,b \ \wedge\ b\,R\,a) \implies a = b

Derivation hint: Two-way relation can only happen on the diagonal; forbids genuine cycles of length 2.

DefinitionEquivalence Relation and Partial Order

A relation $\sim$ on $A$ is an equivalence relation if it is reflexive, symmetric, and transitive. The equivalence class of $a$ is:

7

\quad [a] = \{x \in A : x \sim a\}

Derivation hint: Collect everything equivalent to $a$ ; symmetry and transitivity make this well-behaved. A relation $\leq$ on $A$ is a partial order if it is reflexive, antisymmetric, and transitive. The pair $(A,\leq)$ is then a partially ordered set (poset).

TheoremFundamental Theorem on Equivalence Relations

Let $\sim$ be an equivalence relation on a set $A$ . Then the equivalence classes form a partition of $A$ : they are nonempty, pairwise disjoint, and their union is $A$ . Conversely, every partition $\mathcal{P}$ of $A$ arises from a unique equivalence relation. This establishes a bijection:

8

\quad \{\text{equivalence relations on } A\} \ \longleftrightarrow\ \{\text{partitions of } A\}

Derivation hint: Map each relation to its set of classes; map each partition to "lies in the same block."

ProofEquivalence Classes Partition the Set

We prove the three partition conditions from the equivalence axioms.

Step 1 — Each class is nonempty and covers $A$ . By reflexivity [3], $a \sim a$ , so $a \in [a]$ . Thus every class contains its representative and is nonempty; moreover every $a \in A$ lies in some class (namely $[a]$ ), so $\bigcup_{a\in A}[a] = A$ .

Step 2 — Classes are equal or disjoint. Suppose $[a] \cap [b] \neq \varnothing$ ; pick $c \in [a]\cap[b]$ . Then $c \sim a$ and $c \sim b$ . By symmetry [4], $a \sim c$ ; combined with $c \sim b$ , transitivity [5] gives $a \sim b$ .

Step 3 — Conclude $[a] = [b]$ . Take any $x \in [a]$ , so $x \sim a$ . Since $a \sim b$ (Step 2), transitivity yields $x \sim b$ , hence $x \in [b]$ . So $[a] \subseteq [b]$ ; by symmetric argument $[b] \subseteq [a]$ . Therefore $[a] = [b]$ .

Step 4 — Disjointness. Contrapositively, if $[a] \neq [b]$ then by Step 3 they cannot intersect, so $[a]\cap[b]=\varnothing$ .

Step 5 — Converse. Given a partition $\mathcal{P}$ , define $a \sim b$ iff $a,b$ lie in the same block. Reflexivity holds since each $a$ is in its own block; symmetry is automatic ("same block" is symmetric); transitivity holds because blocks are disjoint, so sharing a block with $b$ and $b$ sharing with $c$ forces all three into one block. $\blacksquare$

∎

mathematician · Charles Sanders Peirce | 1839–1914

Peirce, an American polymath, developed the algebra of relations in the 1870s–1880s, extending De Morgan's earlier work. He introduced systematic notation for relative operations (composition, converse) and recognized relations as fundamental logical objects rather than derivative of properties. His work, refined by Ernst Schröder, fed directly into Bertrand Russell and Whitehead's Principia Mathematica, where relations became the backbone of the logicist program. Peirce famously argued that relations are irreducible — that genuinely triadic relations cannot be decomposed into dyadic ones, a deep claim in his theory of categories.

🧠 Intuition

Picture a relation as a directed graph: draw a dot for each element, and an arrow $a \to b$ whenever $aRb$ . Then the abstract axioms become pictures you can see:

Reflexive = every dot has a self-loop.
Symmetric = every arrow comes with a reverse arrow (so you may as well draw undirected edges).
Transitive = whenever you can walk $a \to b \to c$ , there's a direct shortcut $a \to c$ .

An equivalence relation is then a graph that breaks into fully-connected clumps — each clump is one equivalence class, an "island of sameness." A partial order is an arrow-diagram with no cycles (drawn as a Hasse diagram, going upward), where transitivity lets us infer indirect comparisons but antisymmetry forbids two distinct elements from sitting at the same level via mutual arrows.

Figure

Relation as a directed graph: a symmetric, reflexive relation breaking into two equivalence classes

ExampleCongruence modulo 5

Given: Define $a \sim b$ on $\mathbb{Z}$ by $a \sim b \iff 5 \mid (a - b)$ (i.e. $a \equiv b \pmod 5$ ). Verify it is an equivalence relation and list the classes.

Step 1 — Reflexive: $5 \mid (a-a) = 0$ since $0 = 5\cdot 0$ . ✓

Step 2 — Symmetric: If $5 \mid (a-b)$ , write $a-b = 5k$ . Then $b - a = 5(-k)$ , so $5 \mid (b-a)$ . ✓

Step 3 — Transitive: If $a - b = 5k$ and $b - c = 5m$ , then $a - c = (a-b)+(b-c) = 5(k+m)$ , so $5 \mid (a-c)$ . ✓

Step 4 — Classes: Each integer is equivalent to its remainder on division by 5. There are exactly 5 classes:

9

\quad [0],[1],[2],[3],[4], \qquad [r] = \{\,5q + r : q \in \mathbb{Z}\,\}

Derivation hint: The Division Algorithm gives a unique remainder $r \in \{0,1,2,3,4\}$ for each integer.

Answer: $\boxed{\ \sim\ \text{is an equivalence relation with } 5 \text{ classes, } \mathbb{Z}/5\mathbb{Z} = \{[0],[1],[2],[3],[4]\}\ }$

ExampleDivisibility as a partial order

Given: On the set $A = \{1,2,3,4,6,12\}$ (divisors of 12) define $a \mid b$ (" $a$ divides $b$ "). Show it is a partial order and find maximal/minimal elements.

Step 1 — Reflexive: $a \mid a$ since $a = a \cdot 1$ . ✓

Step 2 — Antisymmetric: If $a \mid b$ and $b \mid a$ with $a,b > 0$ , then $a \leq b$ and $b \leq a$ , forcing $a = b$ . ✓

Step 3 — Transitive: If $b = a k$ and $c = b m$ , then $c = a(km)$ , so $a \mid c$ . ✓

Step 4 — Extremes: The least element is $1$ (divides all); the greatest is $12$ (divisible by all in $A$ ). Comparable chains include $1 \mid 2 \mid 4 \mid 12$ and $1 \mid 3 \mid 6 \mid 12$ , but $4$ and $6$ are incomparable ( $4 \nmid 6$ and $6 \nmid 4$ ) — confirming it is partial, not total.

Answer: $\boxed{\ (A,\mid)\ \text{is a poset; min}=1,\ \max=12,\ \text{with } \{4,6\}\ \text{incomparable}\ }$

⚠️ Common mistake

Symmetry + Transitivity does NOT imply Reflexivity. A common false "proof": if $aRb$ then by symmetry $bRa$ , and by transitivity $aRa$ . The flaw: this only forces $aRa$ for elements that relate to something. An element related to nothing never gets a self-loop, so the relation can fail reflexivity. Reflexivity must be checked independently. Also beware: "antisymmetric" is not the negation of "symmetric." A relation can be both (e.g. equality $=$ ), neither, or one without the other. Antisymmetric means mutual arrows only occur on the diagonal.

CounterexampleSymmetric + Transitive ≠ Equivalence

On $A = \{1,2,3\}$ take $R = \{(1,1),(2,2),(1,2),(2,1)\}$ . Check: it is symmetric (every pair has its reverse) and transitive (the only chains stay within $\{1,2\}$ ). But it is not reflexive because $(3,3) \notin R$ — the element $3$ is related to nothing, so it gets no self-loop. Hence $R$ is not an equivalence relation despite having two of the three properties, decisively refuting the "derivation" of reflexivity in the warning above.

connection

Relations sit at the crossroads of nearly every undergraduate subject. A Function is precisely a relation $R \subseteq A \times B$ in which every $a \in A$ relates to exactly one $b$ — functions are "single-valued, total" relations. Equivalence Relations manufacture Quotient Sets, the engine behind constructing $\mathbb{Z}/n\mathbb{Z}$ , quotient groups, and quotient topological spaces. Partial Orders generalize to Lattices and underlie Order Theory and domain theory in semantics. In Graph Theory, a relation on a finite set is a directed graph, and symmetric relations are undirected graphs. The algebra of relations (composition, converse, intersection) forms a Relation Algebra, connecting to Boolean Algebra and category theory, where relations form a category $\mathbf{Rel}$ .

🔬 Where this appears

⏳ History

- 1847 — Augustus De Morgan publishes early work on the logic of relations, noting Aristotelian syllogistics cannot handle "is greater than."

- 1860s–1880s — Charles S. Peirce develops a full algebra of relatives, introducing notation for converse and relative product (composition).

- 1870 — Richard Dedekind uses equivalence-class-like constructions (cuts) to build the real numbers, an early implicit use of equivalence relations.

- 1890s — Ernst Schröder systematizes the algebra of relations in his Vorlesungen über die Algebra der Logik.

- 1895–1897 — Georg Cantor's set theory provides the ordered-pair and Cartesian-product machinery relations require.

- 1910–1913 — Russell and Whitehead's Principia Mathematica make relations central to logicism, defining them as classes of ordered pairs.

- 1921 — Kazimierz Kuratowski gives the now-standard set-theoretic definition of the ordered pair

(a,b) = \{\{a\},\{a,b\}\}

, grounding relations purely in set theory.

- 1940s — Alfred Tarski revives and axiomatizes relation algebra as an abstract algebraic structure.

- 1970 — Edgar F. Codd publishes "A Relational Model of Data for Large Shared Data Banks," translating relation theory into the foundation of modern databases.

open-problem

The set-theoretic reduction of relations is clean for binary relations, but $n$ -ary relations and the question of whether all relations reduce to binary ones is philosophically loaded — Peirce insisted that genuine triadic relations (like " $a$ gives $b$ to $c$ ") are irreducible to dyadic compositions, a claim with no purely formal resolution. On the algorithmic side, deciding whether the transitive closure of an infinite relation is itself definable, or whether a finitely-axiomatized first-order theory of relations is decidable, connects to deep undecidability results: Tarski's relation algebra is not finitely axiomatizable in a strong sense (Monk, 1964), and many problems about representable relation algebras remain open. In order theory, characterizing which partial orders extend to total orders (always possible by the Szpilrajn extension theorem, but requiring the Axiom of Choice for infinite sets) shows that even basic facts about relations depend on foundational choices.

Formal Statement

Why It Holds

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also