Relations

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.

A relation $R$ from $A$ to $B$ is formally a subset of $A \times B$ ; we write $a R b$ (or $(a, b) \in R$ ) to mean " $a$ stands in relation $R$ to $b$ ." This deceptively simple definition unifies an enormous range of mathematical concepts — functions, orderings, equivalences, and graphs are all special kinds of relations. Why it matters: relations are the connective tissue of mathematics, providing the language in which we say how objects relate rather than merely what they are. A surprising fact is that the seemingly different notions of "equality up to some criterion" (equivalence) and "partitioning a set into disjoint pieces" are literally the same thing — there is a perfect bijection between equivalence relations on a set and partitions of it.

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.

Formal Statement

Binary Relation

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

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

⟳The Cartesian product collects every possible ordered pair; a relation simply selects which pairs to keep.

We write $a R b ⟺ (a, b) \in R$ . When $A = B$ , we call $R$ a relation on $A$ . The domain and range are:

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

⟳Project the pairs in

R

onto their first and second coordinates respectively.

The Three Structural Properties

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

Reflexive: \forall a \in A, a R a

⟳Every element relates to itself — the diagonal

Δ_{A} = {(a, a)} \subseteq R

Symmetric: \forall a, b \in A, a R b ⟹ b R a

⟳The relation is its own inverse,

R = R^{- 1}

, where

R^{- 1} = {(b, a) : (a, b) \in R}

Transitive: \forall a, b, c \in A, (a R b \land b R c) ⟹ a R c

⟳Chains compose — composing

R

with itself stays inside

R

, i.e.

R \circ R \subseteq R

Two further properties define orderings:

Antisymmetric: \forall a, b \in A, (a R b \land b R a) ⟹ a = b

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

Equivalence 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:

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

⟳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).

Fundamental 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 $P$ of $A$ arises from a unique equivalence relation. This establishes a bijection:

{equivalence relations on A} ⟷ {partitions of A}

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

Why It Holds

Equivalence 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

⋃_{a \in A} [a] = A

. Step 2 — Classes are equal or disjoint. Suppose

[a] \cap [b] \neq = \emptyset

; 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] = \emptyset

. Step 5 — Converse. Given a partition

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.

■

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.

Building Intuition

Picture a relation as a directed graph: draw a dot for each element, and an arrow $a \to b$ whenever $a R b$ . 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.

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

Worked Examples

Congruence modulo 5

Given: Define

a \sim b

Z

a \sim b ⟺ 5 ∣ (a - b)

(i.e.

a \equiv b (mod 5)

). Verify it is an equivalence relation and list the classes. Step 1 — Reflexive:

5 ∣ (a - a) = 0

since

0 = 5 \cdot 0

. ✓ Step 2 — Symmetric: If

5 ∣ (a - b)

, write

a - b = 5 k

. Then

b - a = 5 (- k)

, so

5 ∣ (b - a)

. ✓ Step 3 — Transitive: If

a - b = 5 k

and

b - c = 5 m

, then

a - c = (a - b) + (b - c) = 5 (k + m)

, so

5 ∣ (a - c)

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

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

⟳The Division Algorithm gives a unique remainder

r \in {0, 1, 2, 3, 4}

for each integer.

Answer:

\sim is an equivalence relation with 5 classes, Z /5 Z = {[0], [1], [2], [3], [4]}

Divisibility as a partial order

Given: On the set

A = {1, 2, 3, 4, 6, 12}

(divisors of 12) define

a ∣ b

a

divides

b

"). Show it is a partial order and find maximal/minimal elements. Step 1 — Reflexive:

a ∣ a

since

a = a \cdot 1

. ✓ Step 2 — Antisymmetric: If

a ∣ b

and

b ∣ a

with

a, b > 0

, then

a \leq b

and

b \leq a

, forcing

a = b

. ✓ Step 3 — Transitive: If

b = ak

and

c = bm

, then

c = a (k m)

, so

a ∣ c

. ✓ Step 4 — Extremes: The least element is

1

(divides all); the greatest is

12

(divisible by all in

A

). Comparable chains include

1 ∣ 2 ∣ 4 ∣ 12

and

1 ∣ 3 ∣ 6 ∣ 12

, but

4

and

6

are incomparable (

4 ∤ 6

and

6 ∤ 4

) — confirming it is partial, not total. Answer:

(A, ∣) is a poset; min = 1, max = 12, with {4, 6} incomparable

Common Misconceptions

Symmetry + Transitivity does NOT imply Reflexivity. A common false "proof": if

a R b

then by symmetry

b R a

, and by transitivity

a R a

. The flaw: this only forces

a R a

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.

Symmetric + 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) \in / 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.

Connections

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 $Z / n 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 $Rel$ .

Real-World Applications

Databases (Relational Model). E.F. Codd's relational database model represents every table as a relation (a subset of a Cartesian product of column domains); SQL queries are operations in relational algebra (join, projection, selection).
Modular Arithmetic & Cryptography. Congruence relations $a \equiv b (mod n)$ underpin RSA encryption, hash functions, and checksums (ISBN, credit-card Luhn checks).
Sorting & Scheduling. Partial orders model task dependencies; topological sorting of a poset schedules jobs respecting prerequisites (build systems like Make, project management with PERT charts).
Type Systems & Subtyping. In programming languages, the subtype relation (Cat <: Animal) is a partial order that compilers traverse for type checking.
Equivalence in Quotient Constructions. Building the rationals $Q$ from pairs of integers, or the real numbers from Cauchy sequences, uses equivalence relations to identify "the same" object.
Social Network Analysis. "Friendship" is a symmetric relation; "follows" is a general directed relation — graph algorithms compute connected components (equivalence classes) and influence rankings.
Equivalence Checking in Hardware. Verifying two circuits compute the same function uses equivalence relations on Boolean expressions and BDD-based comparison.

Historical Development

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.

Subtleties & Limits

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.

Relations

The Core Insight

Formal Statement

Binary Relation

The Three Structural Properties

Equivalence Relation and Partial Order

Fundamental Theorem on Equivalence Relations

Why It Holds

Equivalence Classes Partition the Set

Charles Sanders Peirce | 1839–1914

Building Intuition

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

Worked Examples

Congruence modulo 5

Divisibility as a partial order

Common Misconceptions

Symmetric + Transitive ≠ Equivalence

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also

Before this

Where this leads