Equivalence Relations

Why we need a special kind of “sameness”

In mathematics and computer science, we constantly treat different objects as interchangeable.

• •Two integers might be “the same” if they have the same remainder mod 5.
• •Two strings might be “the same” if they differ only by capitalization.
• •Two graphs might be “the same” if they are isomorphic.

In each case, we’re not claiming the objects are literally equal. We’re defining a notion of equivalence.

An equivalence relation is the cleanest way to do this because it guarantees that “equivalent” behaves like a consistent grouping rule.

Definition (with the three rules)

Let S be a set and let ~ be a binary relation on S (so ~ ⊆ S × S). We say ~ is an equivalence relation if it satisfies:

1. 1)Reflexive: ∀a ∈ S, a ~ a.
2. 2)Symmetric: ∀a, b ∈ S, if a ~ b then b ~ a.
3. 3)Transitive: ∀a, b, c ∈ S, if a ~ b and b ~ c then a ~ c.

These rules are not arbitrary; they’re exactly what you need for “equivalent” to produce stable groups.

Intuition: what each property is protecting

Think of drawing a graph where each element of S is a node, and you draw an (undirected) edge between a and b when a ~ b.

• •Reflexive means every node has a “self-connection” (often implicit). It prevents an element from being excluded from its own group.
• •Symmetric means edges have no direction. If a is considered equivalent to b, b must be equivalent to a.
• •Transitive means connectivity “closes”: if a is connected to b and b to c, then a and c must be connected too. This is what forces groups to become cliques/connected components rather than messy overlaps.

A tiny non-example to see what goes wrong

Let S = {1, 2, 3} and define a relation R = {(1,2), (2,1), (2,3), (3,2)}.

• •Symmetric? Yes.
• •Reflexive? No (missing (1,1), (2,2), (3,3)).
• •Transitive? Not necessarily: we have 1 R 2 and 2 R 3, but not 1 R 3.

If you tried to “group by R,” you’d feel the problem: 1 is grouped with 2, and 2 with 3, but 1 is not grouped with 3. That violates the idea of an equivalence class being a coherent bucket.

Notation you’ll see constantly

• •Write a ~ b to mean “a is equivalent to b.”
• •When ~ is understood, we define the equivalence class of a as:

This set [a] is “everything that belongs in the same bucket as a.”

Why equivalence classes matter

Equivalence relations are useful because they let you replace complicated objects with their class label.

• •In modular arithmetic, you often care only about the remainder, not the exact integer.
• •In compiler optimization, you might identify expressions that are equivalent under rewriting rules.

Equivalence classes are the units you actually manipulate.

Definition: equivalence class of an element

Given an equivalence relation ~ on S and an element a ∈ S:

Two key facts follow from the equivalence properties.

Fact A: Every element is in its own class

Because ~ is reflexive, a ~ a, so a ∈ [a].

This is small but important: no class is empty, and no element “falls out” of the grouping.

Fact B: Two classes are either disjoint or identical

This is the central structural rule of equivalence classes.

For any a, b ∈ S, either [a] = [b] or [a] ∩ [b] = ∅.

Proof (showing the work)

Assume [a] ∩ [b] ≠ ∅. Then there exists some x such that x ∈ [a] and x ∈ [b].

By definition of class:

• •x ∈ [a] ⇒ x ~ a
• •x ∈ [b] ⇒ x ~ b

Now use symmetry and transitivity to connect a to b:

1. 1)x ~ a ⇒ (by symmetry) a ~ x
2. 2)a ~ x and x ~ b ⇒ (by transitivity) a ~ b

Now show [a] ⊆ [b]. Take any y ∈ [a]. Then y ~ a.

Since a ~ b, transitivity gives:

• •y ~ a and a ~ b ⇒ y ~ b

So y ∈ [b]. Hence [a] ⊆ [b].

Similarly, show [b] ⊆ [a] (swap roles), so [a] = [b].

So if they overlap at all, they must be the same class.

Small diagram/table (for when interactive visuals aren’t available)

Imagine S split into “blocks,” each block is a class:

And the structural rule is:

[a] and [b] either:
  (1) don’t touch at all, or
  (2) are exactly the same block

This is what makes equivalence classes behave like well-defined buckets.

Example snapshot: integers mod 4

Let S = ℤ and define a ~ b if a and b have the same remainder mod 4 (i.e., 4 | (a − b)).

Then there are exactly four equivalence classes:

• •[0] = {..., -8, -4, 0, 4, 8, ...}
• •[1] = {..., -7, -3, 1, 5, 9, ...}
• •[2] = {..., -6, -2, 2, 6, 10, ...}
• •[3] = {..., -5, -1, 3, 7, 11, ...}

Notice how:

• •every integer belongs to exactly one of these,
• •the classes don’t overlap,
• •but each class has infinitely many elements.

Why this correspondence is the whole point

Equivalence relations can feel abstract: sets of ordered pairs with three properties.

Partitions are much more concrete: “split the set into non-overlapping groups.”

The key theorem is that these are the same idea expressed in two different languages:

• •An equivalence relation induces a partition into equivalence classes.
• •A partition defines an equivalence relation by “same block.”

This is the conceptual bridge you want to internalize.

From an equivalence relation to a partition

Let ~ be an equivalence relation on S.

Define the collection of all equivalence classes:

(As a set, this automatically removes duplicates, because if [a] = [b] they appear only once in \(\mathcal{P}\).)

Claim: 𝒫 is a partition of S

A partition of S is a collection of nonempty subsets (called blocks) such that:

1. 1)Every block is nonempty.
2. 2)Blocks are pairwise disjoint.
3. 3)The union of all blocks is S.

Check each:

1) Nonempty: For any a, a ∈ [a] (reflexive), so [a] ≠ ∅.

2) Disjointness: For any a, b, either [a] = [b] or [a] ∩ [b] = ∅ (proved earlier). So distinct blocks are disjoint.

3) Covers S: For any x ∈ S, x ∈ [x]. So every element is in some block. Thus ⋃_{C∈𝒫} C = S.

So equivalence classes form a partition.

From a partition to an equivalence relation

Now go the other way.

Suppose you start with a partition 𝒫 of S. That means 𝒫 is a set of blocks {B₁, B₂, ..., } such that each element of S belongs to exactly one block.

Define a relation ~ by:

a ~ b iff a and b are in the same block of 𝒫.

Claim: ~ is an equivalence relation

Check the properties:

• •Reflexive: a is in the same block as itself ⇒ a ~ a.
• •Symmetric: if a and b are in the same block, then b and a are in the same block ⇒ b ~ a.
• •Transitive: if a and b are in the same block, and b and c are in the same block, then all three are in that one block (because b can’t be in two blocks). Hence a and c are in the same block ⇒ a ~ c.

So any partition gives an equivalence relation.

Why this is a bijection (one-to-one correspondence)

These two constructions are inverses:

• •Start with ~, build its classes 𝒫. Then define “same block” from 𝒫. You get back exactly ~.
• •Start with partition 𝒫, define ~ as “same block.” Then take classes [a]. You get back the original blocks.

This is why equivalence relations are best understood visually as partitions.

Visualization guidance (for an interactive canvas)

If you’re building or using a visualization, here’s the mental model to reinforce partition ⇔ relation.

View A: Partition blocks

• •Show elements as dots.
• •Surround each equivalence class with a shaded region (a block).
• •Clicking an element highlights its entire block.

View B: Relation edges

• •Same dots, but now draw an undirected edge between any pair (a,b) with a ~ b.
• •In a true equivalence relation, each block becomes a clique (all-to-all connections), or at least a clearly separated connected component if you treat self-loops as implicit.

Crucial interaction: toggle + highlight the theorem

1. 1)Toggle from blocks → edges.
2. 2)Click element a:

• •In block view, highlight block [a].
• •In edge view, highlight all vertices connected within that block.

3. 3)Click element b:

• •If b is in [a], the highlight is identical.
• •Otherwise, the highlight is disjoint.

This directly demonstrates “either disjoint or identical.”

A concrete micro-demo you can picture

Let S = {1,2,3,4,5,6} and partition it as:

• •B₁ = {1,4}
• •B₂ = {2,3,6}
• •B₃ = {5}

Block view shows three regions.

Edge view would show:

• •edges between 1 and 4,
• •edges among 2,3,6 (a triangle),
• •no edges for 5 besides (5,5) if you include self-loops.

No edges ever connect between blocks. That’s the partition boundary showing up as “no relation.”

1) Modular arithmetic (grouping integers by remainder)

This is the canonical example because it’s both practical and rigorous.

Define, for a fixed n ≥ 1:

Read it as: “a is equivalent to b if their difference is divisible by n.”

This creates n equivalence classes, often written as:

These classes are exactly the integers grouped by remainder. This is the foundation of working in ℤₙ.

2) Converting “messy equality” into clean computation

In programming, you frequently define a custom equality notion:

• •case-insensitive string equality
• •equality up to whitespace normalization
• •geometric points equal up to rounding tolerance (careful: tolerance-based relations are often not transitive!)

Equivalence relations tell you what properties must hold if you want to safely:

• •deduplicate items (e.g., store one representative per class)
• •use hash-based structures (hashing typically assumes an equivalence relation)

3) Data structure connection: Disjoint Set Union (Union-Find)

Union-Find maintains a partition of elements into disjoint sets, supporting:

• •find(x): return a representative of x’s class
• •union(a,b): merge the classes containing a and b

This is exactly “maintain equivalence classes under merges.”

Even if you don’t yet know Union-Find, equivalence relations explain what the structure is tracking: a partition.

4) Mathematics connection: quotient sets

Given an equivalence relation ~ on S, the set of equivalence classes is written:

Read “S mod ~” or “S quotient ~.”

This is how you build new objects:

• •integers mod n: ℤ/≡ₙ
• •rational numbers as equivalence classes of integer pairs (a,b) with b≠0 under (a,b) ~ (c,d) iff ad = bc

The pattern: define an equivalence relation capturing “same value,” then treat each class as a single new element.

5) Design warning: not every ‘similarity’ is equivalence

In ML and graphics, you might say two items are “similar” if distance ≤ ε.

That relation is often:

• •reflexive (distance(a,a)=0)
• •symmetric (distance(a,b)=distance(b,a))
• •not transitive (a close to b, b close to c, but a not close to c)

So it does not partition cleanly into equivalence classes. That’s a common reason clustering behaves differently from equivalence-class grouping.