Relations — Equivalence Relations and Partial Orders

A relation on a set is a collection of ordered pairs; two special kinds dominate mathematics. An equivalence relation (reflexive, symmetric, transitive) partitions a set into disjoint classes of "interchangeable" elements, while a partial order (reflexive, antisymmetric, transitive) arranges elements into a hierarchy of "comparability." They appear everywhere from modular arithmetic and quotient constructions to scheduling, dependency graphs, and lattice theory. Studied systematically since the late 19th century (Dedekind, Peirce, Cantor).

A binary relation $R$ on a set $A$ is any subset of the Cartesian product $A \times A$ ; we write $a R b$ to mean $(a, b) \in R$ . From this minimal definition, imposing combinations of three properties — reflexivity, symmetry/antisymmetry, and transitivity — produces the two most important structured relations in mathematics. An equivalence relation generalizes equality: it groups elements into equivalence classes that form a partition, and this correspondence between equivalence relations and partitions is exact (one of the cleanest bijections in all of mathematics). A partial order generalizes "less than or equal to": it lets us compare some elements while leaving others incomparable, which is exactly what is needed to model dependency, containment, and divisibility. The surprising fact: every finite partial order can be drawn as a Hasse diagram and is determined entirely by its covering relation, so an apparently infinite list of comparisons collapses to a finite skeleton.

The Core Insight

Three atomic properties — reflexive, symmetric/antisymmetric, transitive — recombine into two fundamentally different worlds. Keep symmetry and you get sameness (equivalence → partitions → quotients). Replace symmetry with antisymmetry and you get ranking (partial order → hierarchies → lattices). The single property they share, transitivity, is what makes both "behave like" the relations they generalize (equality and ≤).

Formal Statement

Binary Relation and Its Properties

A binary relation on a set $A$ is a subset $R \subseteq A \times A$ . We write $a \sim b$ or $a \leq b$ depending on context.

R \subseteq A \times A, a R b ⟺ (a, b) \in R

⟳A relation is literally just the set of pairs that "stand in the relation"; everything else is a property this set may or may not have.

The four fundamental properties, for all $a, b, c \in A$ :

Reflexive: \forall a (a R a)

⟳every element relates to itself; the diagonal

Δ = {(a, a) : a \in A}

is contained in

R

Symmetric: \forall a, b (a R b \Rightarrow b R a)

⟳the pair set is closed under swapping coordinates, i.e.

R = R^{- 1}

Antisymmetric: \forall a, b ((a R b \land b R a) \Rightarrow a = b)

⟳the only way two elements can relate both ways is if they are identical;

R \cap R^{- 1} \subseteq Δ

Transitive: \forall a, b, c ((a R b \land b R c) \Rightarrow a R c)

⟳chains collapse to a single link; in relational-composition terms

R \circ R \subseteq R

Equivalence Relation

A relation $\sim$ on $A$ is an equivalence relation if it is reflexive [2], symmetric [3], and transitive [5]. For $a \in A$ , its equivalence class is

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

⟳collect all elements indistinguishable from

a

under

\sim

; this set is the basic building block.

The set of all equivalence classes is the quotient set:

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

⟳take the collection of distinct classes; each appears once even if many representatives generate it.

Partition

A partition of $A$ is a collection $P$ of nonempty subsets (blocks) of $A$ such that every element lies in exactly one block:

B \in P ⋃ B = A and B_{i} \cap B_{j} = \emptyset (B_{i} \neq = B_{j})

⟳the blocks cover everything (union is

A

) and never overlap (pairwise disjoint), so each element has a unique home.

Fundamental Theorem of Equivalence Relations

There is a bijection between the set of equivalence relations on $A$ and the set of partitions of $A$ . Given $\sim$ , the family of equivalence classes $A / \sim$ is a partition; conversely, given a partition $P$ , the relation " $a \sim b$ iff $a, b$ lie in the same block" is an equivalence relation. These constructions are mutually inverse.

Partial Order, Poset, Total Order

A relation $\leq$ on $A$ is a partial order if it is reflexive [2], antisymmetric [4], and transitive [5]. The pair $(A, \leq)$ is a partially ordered set (poset). Two elements are comparable if $a \leq b$ or $b \leq a$ ; otherwise incomparable (written $a ∥ b$ ). A partial order in which every pair is comparable is a total (or linear) order:

Totality: \forall a, b (a \leq b \lor b \leq a)

⟳add the demand that no two elements are incomparable; this upgrades a partial order to a chain.

The strict order associated with $\leq$ is $a < b ⟺ (a \leq b \land a \neq = b)$ , which is irreflexive and transitive.

Covering Relation and Hasse Diagram

In a poset $(A, \leq)$ , element $b$ covers $a$ (written $a ⋖ b$ ) if $a < b$ and no $c$ satisfies $a < c < b$ :

a ⋖ b ⟺ a < b \land \neg\exists c (a < c < b)

⟳

b

sits immediately above

a

with nothing in between; this is the "next step up."

A Hasse diagram draws elements as dots, places $b$ above $a$ whenever $a ⋖ b$ , and joins them by a line. The full order is recovered by transitivity, so only covers are drawn.

Why It Holds / Derivation

Equivalence Classes Form a Partition

Let $\sim$ be an equivalence relation on $A$ . We verify the two partition conditions [8].

Step 1 — Every element is covered. By reflexivity [2],

a \sim a

, so

a \in [a]

. Hence each

a

lies in at least one class and

⋃_{a} [a] = A

. Each class is nonempty (it contains its own generator). Step 2 — Classes are equal or disjoint. Suppose

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

; pick

c

in the intersection, so

c \sim a

and

c \sim b

. By symmetry [3],

a \sim c

. Take any

x \in [a]

, i.e.

x \sim a

. Then by transitivity [5]:

x \sim a

a \sim c

give

x \sim c

; and

x \sim c

c \sim b

give

x \sim b

, so

x \in [b]

. Thus

[a] \subseteq [b]

, and by symmetry of the argument

[b] \subseteq [a]

, giving

[a] = [b]

. Step 3 — Conclusion. Either two classes coincide or are disjoint; combined with Step 1,

A / \sim

is a partition. The inverse direction (a partition induces an equivalence relation) is checked directly: "same block" is trivially reflexive, symmetric, and transitive.

■

A Finite Poset Is Determined by Its Covering Relation

Let $(A, \leq)$ be a finite poset and let $⋖$ be its covering relation [10]. We claim $a \leq b$ iff there is a chain $a = x_{0} ⋖ x_{1} ⋖ \dots ⋖ x_{n} = b$ (with $n = 0$ allowed, meaning $a = b$ ).

Step 1 — Chains imply order. Each

x_{i} ⋖ x_{i + 1}

gives

x_{i} < x_{i + 1} \leq x_{i + 1}

, and by transitivity [5] applied repeatedly

a \leq b

. Step 2 — Order implies a chain (finiteness used here). Suppose

a < b

. If

a ⋖ b

we are done. Otherwise there exists

c

with

a < c < b

. The strict order is a strict partial order, so consider the finite set

{c : a < c < b}

; pick a minimal such

c

to make

a ⋖ c

, and recurse on

c < b

. Finiteness guarantees the process terminates, producing a covering chain. Step 3 — Conclusion. The full relation

\leq

is the reflexive-transitive closure of

⋖

, so the Hasse diagram (which records exactly

⋖

) loses no information.

■

Step 2 genuinely needs finiteness. In $(Q, \leq)$ the covering relation is empty — between any two rationals lies a third — so $Q$ has no Hasse diagram and cannot be reconstructed from covers. Dense orders are the canonical exception.

Richard Dedekind | 1831–1916

Dedekind brought ordered structures and equivalence into the foundations of mathematics. His Dedekind cuts (1872) construct the real numbers using a partition of the rationals into two ordered blocks — a partial-order idea at the heart of analysis. In Was sind und was sollen die Zahlen? (1888) he treated mappings, chains, and the precursors of equivalence classes with new rigor. The notion of a lattice — a poset with meets and joins — traces to his work on ideals and modules (Dualgruppen), later rediscovered and named by Birkhoff. Charles S. Peirce and Ernst Schröder independently developed the algebra of relations in the same era, and Cantor's cardinality theory rests squarely on the equivalence relation "is in bijection with."

Building Intuition

Think of an equivalence relation as a pair of "blurry glasses": elements that look the same through them get lumped together. Modular arithmetic mod 12 is a clock — 3 o'clock and 15 o'clock are the same point, so $Z /12 Z$ has just twelve classes. The quotient set $A / \sim$ is what you see after putting on the glasses: you've thrown away distinctions you decided don't matter.

A partial order is a "depends-on" or "is-bigger-than" arrow, but with the honest admission that some things just can't be compared. Subsets of a set under $\subseteq$ : ${1, 2}$ and ${2, 3}$ are incomparable — neither contains the other — yet both sit below ${1, 2, 3}$ . The Hasse diagram is the picture of this hierarchy with all redundant arrows erased. The crucial mental switch: symmetry says "both directions are the same," antisymmetry says "both directions can only happen if you're standing still."

Equivalence partition (left) vs. partial order Hasse diagram (right). The gold curve encloses one equivalence class; gold edges trace a covering chain.

Worked Examples

Congruence Modulo 5 — Counting Classes

Given: the relation on

Z

defined by

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

. Step 1 — Verify it is an equivalence relation.

Reflexive: $5 ∣ (a - a) = 0$ . ✓
Symmetric: if $5 ∣ (a - b)$ then $5 ∣ - (a - b) = (b - a)$ . ✓
Transitive: if $5 ∣ (a - b)$ and $5 ∣ (b - c)$ then $5 ∣ (a - b) + (b - c) = (a - c)$ . ✓

Step 2 — Identify the classes. Every integer leaves remainder

0, 1, 2, 3,

4

on division by 5. Two integers are related iff they share a remainder. So:

= {\dots, - 5, 0, 5, 10, \dots}, [1] = {\dots, - 4, 1, 6, \dots}, \dots, [4] .

Step 3 — Count. There are exactly 5 distinct classes.

Z /5 Z = {[0], [1], [2], [3], [4]}, ∣ Z /5 Z ∣ = 5

Divisibility Poset on {1,2,3,4,6,12} — Bounds

Given:

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

with

a \leq b ⟺ a ∣ b

(divides). Step 1 — Confirm it is a partial order. Reflexive (

a ∣ a

), antisymmetric (if

a ∣ b

and

b ∣ a

with positive integers then

a = b

), transitive (

a ∣ b

b ∣ c \Rightarrow a ∣ c

). ✓ It is not total:

2 ∥ 3

(neither divides the other). Step 2 — Find covers.

1 ⋖ 2

1 ⋖ 3

2 ⋖ 4

2 ⋖ 6

3 ⋖ 6

4 ⋖ 12

6 ⋖ 12

. (Note

1 \neq ⋖ 4

because

1 < 2 < 4

.) Step 3 — Identify special elements.

Least element (bottom): $1$ , since $1 ∣ x$ for all $x$ .
Greatest element (top): $12$ , since $x ∣ 12$ for all $x$ .
Meet (greatest lower bound) of $4$ and $6$ : $g cd (4, 6) = 2$ .
Join (least upper bound) of $4$ and $6$ : $lcm (4, 6) = 12$ .

bottom = 1, top = 12, 4 \land 6 = 2, 4 \lor 6 = 12

This poset is in fact a lattice: every pair has a meet ( $g cd$ ) and join ( $lcm$ ).

Common Misconceptions

Reflexivity is not automatic — and the empty relation is a trap. The relation

R = \emptyset

on a nonempty set

A

is vacuously symmetric and transitive, but it is not reflexive (no

a R a

). So it is not an equivalence relation. Likewise, "symmetric + transitive ⟹ reflexive" is a famous fallacy: the bogus proof says "

a \sim b \Rightarrow b \sim a \Rightarrow a \sim a

," but it silently assumes every

a

relates to some

b

. If

a

is isolated,

a \sim a

can fail. Antisymmetry ≠ asymmetry, and "not symmetric" ≠ "antisymmetric." Antisymmetry [4] permits

a R a

(the diagonal is allowed); asymmetry forbids it entirely. A relation can be both symmetric and antisymmetric — namely any subset of the diagonal, e.g. equality itself. Do not assume the two properties are opposites. "Has the same first name as" looks like an order but isn't, and "is a friend of" isn't transitive. The relation

a \leq b ⟺ a

is at least as tall as

b

on a set of people is reflexive and transitive but generally not antisymmetric: two different people of equal height satisfy

a \leq b

and

b \leq a

without

a = b

. So it is a preorder, not a partial order — to fix it you must pass to the quotient by "equal height."

The relation " $a$ knows $b$ " on a social network is reflexive and symmetric but not transitive (your friend's friend need not be your friend), so it is a tolerance/dependency relation, not an equivalence relation. To force an equivalence you take the transitive closure, yielding connected components.

Connections

Equivalence relations are the engine behind every quotient construction: Quotient Groups ( $G / N$ ), Quotient Topology, quotient rings, and Cardinality and Bijections (where "same size" is the equivalence "is in bijection with"). The First Isomorphism Theorem is precisely the statement that a homomorphism's kernel-equivalence quotient is isomorphic to its image. Partial orders generalize into Lattice Theory (posets with meets and joins) and underlie Order Topology and Zorn's Lemma, the order-theoretic form of the Axiom of Choice. Both relation types are instances of the general theory of Binary Relations and Their Composition, and the strict-order/total-order distinction connects directly to Well-Ordering and Ordinals. Graph-theoretically, an equivalence relation is a disjoint union of complete graphs, while a (strict) partial order is exactly a transitively closed Directed Acyclic Graphs.

Real-World Applications

Modular arithmetic & cryptography — Congruence mod $n$ (an equivalence relation) defines $Z / n Z$ , the backbone of RSA, Diffie–Hellman, hashing, and error-correcting codes.
Task scheduling / build systems — make, Bazel, and CI pipelines model file/task dependencies as a partial order (a DAG); a valid build order is a topological sort, i.e. a linear extension of the poset.
Version control & distributed systems — Git commit history and vector clocks in distributed databases use partial orders to capture "happened-before" causality (Lamport's relation), where concurrent events are incomparable.
Database query optimization & type systems — Subtype relations in programming languages (Cat <: Animal) form a partial order; type checkers compute meets/joins in this lattice. SQL GROUP BY partitions rows by an equivalence relation.
Clustering & image segmentation — Connected-components labeling and union–find partition pixels/data points into equivalence classes; the union–find data structure maintains a dynamic equivalence relation in near-constant time.
Decision theory & rankings — Preference relations are partial orders (allowing "indifferent" or "incomparable" outcomes); Pareto optimality is defined via the product partial order on outcome vectors.
Voting & social choice — Arrow's theorem concerns aggregating individual total/partial orders into a collective ranking, with sharp impossibility limits.

Historical Development

1872 — Richard Dedekind constructs the reals via cuts, partitioning $Q$ into ordered blocks — an order-theoretic foundation for analysis.
1870s–80s — Charles S. Peirce develops the algebra of relations, formalizing composition, converse, and relational properties.
1883 — Georg Cantor bases cardinality on the equivalence relation "is in bijection with," and ordinality on order types of well-orders.
1888 — Dedekind's Was sind und was sollen die Zahlen? rigorously treats mappings and chains, prefiguring equivalence classes.
1890s — Ernst Schröder's Vorlesungen über die Algebra der Logik systematizes the calculus of relations.
1914 — Felix Hausdorff develops ordered and partially ordered sets in his foundational set-theory text, introducing modern poset language.
1928–1933 — Helmut Hasse popularizes the diagrammatic representation now called the Hasse diagram in number-theory lectures.
1933–1940 — Garrett Birkhoff founds modern lattice theory, unifying posets, Boolean algebras, and order structures; his Lattice Theory (1940) becomes the standard reference.
1978 — Leslie Lamport formalizes the "happened-before" partial order for distributed systems, a landmark application in computer science.

Subtleties & Limits

Several deep issues lurk beneath this elementary surface. (1) Counting: the number of partitions of an $n$ -element set is the Bell number $B_{n}$ , but the number of distinct partial orders (and posets up to isomorphism) on $n$ elements has no known closed form and grows wildly — these are computed only for small $n$ . (2) Dimension theory: every finite poset embeds into a product of chains; the minimum number of chains needed is the poset's order dimension, and recognizing dimension- $\geq 3$ posets is NP-complete, with many extremal questions open. (3) Choice-dependence: the claim "every set can be well-ordered" and "every partial order extends to a total order" require the Axiom of Choice / Zorn's Lemma; without it these can fail, exposing the foundational sensitivity of order theory. (4) Infinite & dense orders: dense linear orders (like $Q$ ) have no covering relation, so Hasse diagrams and finite combinatorial methods break down, and the model theory of such orders (Cantor's back-and-forth theorem and beyond) remains a rich research area.