Relations — Equivalence Relations and Partial Orders

⚡ Key Takeaways

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

💡 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 ≤).

DefinitionBinary 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 \le b$ depending on context.

1

\quad R \subseteq A \times A, \qquad a\,R\,b \iff (a,b) \in R

Derivation hint: 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$ :

2

\quad \textbf{Reflexive:}\quad \forall a\,(a\,R\,a)

Derivation hint: every element relates to itself; the diagonal $\Delta = \{(a,a) : a\in A\}$ is contained in $R$ .

3

\quad \textbf{Symmetric:}\quad \forall a,b\,(a\,R\,b \Rightarrow b\,R\,a)

Derivation hint: the pair set is closed under swapping coordinates, i.e. $R = R^{-1}$ .

4

\quad \textbf{Antisymmetric:}\quad \forall a,b\,\big((a\,R\,b \wedge b\,R\,a) \Rightarrow a=b\big)

Derivation hint: the only way two elements can relate both ways is if they are identical; $R \cap R^{-1} \subseteq \Delta$ .

5

\quad \textbf{Transitive:}\quad \forall a,b,c\,\big((a\,R\,b \wedge b\,R\,c) \Rightarrow a\,R\,c\big)

Derivation hint: chains collapse to a single link; in relational-composition terms $R \circ R \subseteq R$ .

DefinitionEquivalence 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

6

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

Derivation hint: 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:

7

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

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

DefinitionPartition

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

8

\quad \bigcup_{B\in\mathcal{P}} B = A \quad\text{and}\quad B_i \cap B_j = \varnothing \ \ (B_i \ne B_j)

Derivation hint: the blocks cover everything (union is $A$ ) and never overlap (pairwise disjoint), so each element has a unique home.

TheoremFundamental 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 $\mathcal{P}$ , the relation " $a \sim b$ iff $a,b$ lie in the same block" is an equivalence relation. These constructions are mutually inverse.

DefinitionPartial Order, Poset, Total Order

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

9

\quad \textbf{Totality:}\quad \forall a,b\,(a\le b \ \vee\ b\le a)

Derivation hint: add the demand that no two elements are incomparable; this upgrades a partial order to a chain. The strict order associated with $\le$ is $a < b \iff (a\le b \wedge a\ne b)$ , which is irreflexive and transitive.

DefinitionCovering Relation and Hasse Diagram

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

10

\quad a \lessdot b \iff a<b \ \wedge\ \neg\exists c\,(a<c<b)

Derivation hint: $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 \lessdot b$ , and joins them by a line. The full order is recovered by transitivity, so only covers are drawn.

ProofEquivalence 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 $\bigcup_{a} [a] = A$ . Each class is nonempty (it contains its own generator).

Step 2 — Classes are equal or disjoint. Suppose $[a] \cap [b] \neq \varnothing$ ; 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. $\blacksquare$

∎

ProofA Finite Poset Is Determined by Its Covering Relation

Let $(A,\le)$ be a finite poset and let $\lessdot$ be its covering relation [10]. We claim $a \le b$ iff there is a chain $a = x_0 \lessdot x_1 \lessdot \cdots \lessdot x_n = b$ (with $n=0$ allowed, meaning $a=b$ ).

Step 1 — Chains imply order. Each $x_i \lessdot x_{i+1}$ gives $x_i < x_{i+1} \le x_{i+1}$ , and by transitivity [5] applied repeatedly $a \le b$ .

Step 2 — Order implies a chain (finiteness used here). Suppose $a < b$ . If $a \lessdot 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 \lessdot c$ , and recurse on $c < b$ . Finiteness guarantees the process terminates, producing a covering chain.

Step 3 — Conclusion. The full relation $\le$ is the reflexive-transitive closure of $\lessdot$ , so the Hasse diagram (which records exactly $\lessdot$ ) loses no information. $\blacksquare$

∎

⚠️ Common mistake

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

mathematician · 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."

🧠 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 $\mathbb{Z}/12\mathbb{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."

Figure

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

ExampleCongruence Modulo 5 — Counting Classes

Given: the relation on $\mathbb{Z}$ defined by $a \sim b \iff 5 \mid (a-b)$ .

Step 1 — Verify it is an equivalence relation.

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

Step 2 — Identify the classes. Every integer leaves remainder $0,1,2,3,$ or $4$ on division by 5. Two integers are related iff they share a remainder. So:

0

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

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

\boxed{\ \mathbb{Z}/5\mathbb{Z} = \{[0],[1],[2],[3],[4]\}, \quad |\mathbb{Z}/5\mathbb{Z}| = 5\ }

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

Given: $A=\{1,2,3,4,6,12\}$ with $a \le b \iff a \mid b$ (divides).

Step 1 — Confirm it is a partial order. Reflexive ( $a\mid a$ ), antisymmetric (if $a\mid b$ and $b\mid a$ with positive integers then $a=b$ ), transitive ( $a\mid b$ , $b\mid c \Rightarrow a\mid c$ ). ✓ It is not total: $2 \parallel 3$ (neither divides the other).

Step 2 — Find covers. $1\lessdot 2$ , $1\lessdot 3$ , $2\lessdot 4$ , $2\lessdot 6$ , $3\lessdot 6$ , $4\lessdot 12$ , $6\lessdot 12$ . (Note $1 \not\lessdot 4$ because $1<2<4$ .)

Step 3 — Identify special elements.

Least element (bottom): $1$ , since $1\mid x$ for all $x$ .
Greatest element (top): $12$ , since $x \mid 12$ for all $x$ .
Meet (greatest lower bound) of $4$ and $6$ : $\gcd(4,6)=2$ .
Join (least upper bound) of $4$ and $6$ : $\operatorname{lcm}(4,6)=12$ .

\boxed{\ \text{bottom}=1,\ \text{top}=12,\ \ 4\wedge 6 = 2,\ \ 4\vee 6 = 12\ }

This poset is in fact a lattice: every pair has a meet ( $\gcd$ ) and join ( $\operatorname{lcm}$ ).

⚠️ Common mistake

Reflexivity is not automatic — and the empty relation is a trap. The relation $R=\varnothing$ 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.

⚠️ Common mistake

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.

Counterexample

"Has the same first name as" looks like an order but isn't, and "is a friend of" isn't transitive. The relation $a \le b \iff 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\le b$ and $b\le 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.

connection

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.

🔬 Where this appears

⏳ History

- 1872 — Richard Dedekind constructs the reals via cuts, partitioning

\mathbb{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.

open-problem

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- $\ge 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 $\mathbb{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.

Relations — Equivalence Relations and Partial Orders

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also