4.5 Equivalence relations

Definition of equivalence relations

An equivalence relation is a way of saying when two elements of a set can be treated as "the same" for a particular purpose. You encounter this idea constantly in math: two fractions representing the same number, two shapes with the same angles, two integers with the same remainder. The relation formalizes what "sameness" means in each context.

For a relation $R$ on a set $S$ to qualify as an equivalence relation, it must satisfy three properties simultaneously. If even one fails, it's not an equivalence relation.

Properties of equivalence relations

Reflexivity: Every element is related to itself.

$\forall a \in S, \; aRa$

Think of it this way: anything should be "the same as" itself under any reasonable notion of sameness.

Symmetry: If $a$ is related to $b$, then $b$ is related to $a$.

$\forall a, b \in S, \; aRb \implies bRa$

The relationship goes both directions. If $a$ has the same birthday as $b$, then $b$ has the same birthday as $a$.

Transitivity: If $a$ is related to $b$ and $b$ is related to $c$, then $a$ is related to $c$.

$\forall a, b, c \in S, \; (aRb \land bRc) \implies aRc$

Sameness "chains together." If $a \equiv b$ and $b \equiv c$, then $a \equiv c$.

When all three hold, the relation partitions the set into non-overlapping groups of equivalent elements.

Examples of equivalence relations

• Equality ($=$) on any set. The most basic equivalence relation.
• Congruence modulo $n$ on the integers. Two integers are equivalent if they leave the same remainder when divided by $n$. For example, $7 \equiv 2 \pmod{5}$ because both leave remainder 2.
• Similarity of geometric shapes. Two triangles are similar if they have the same angles, regardless of size.
• "Has the same birthday as" on a set of people. This satisfies all three properties: you share a birthday with yourself (reflexive), if you share one with someone they share one with you (symmetric), and the relation chains (transitive).
• Parallelism among lines in Euclidean geometry. Parallel lines share the same slope (or are both vertical). Note: each line is considered parallel to itself for this to work as an equivalence relation.

Equivalence classes

Once you have an equivalence relation on a set, it naturally groups elements together. Each group is called an equivalence class.

Formation of equivalence classes

For an element $a$ in set $S$, its equivalence class $[a]$ is the set of all elements related to $a$:

$[a] = \{x \in S \mid xRa\}$

Every element in $[a]$ is related to every other element in $[a]$. Any member of the class can serve as its representative. For instance, under congruence mod 3, the class $[0] = \{\ldots, -6, -3, 0, 3, 6, \ldots\}$ could equally be written as $[3]$ or $[-6]$.

Properties of equivalence classes

• Disjoint: No element belongs to more than one equivalence class. If $[a]$ and $[b]$ share even one element, then $[a] = [b]$.
• Exhaustive: The union of all equivalence classes equals the entire set $S$. Every element lands somewhere.
• Internally connected: All elements within a single class are related to each other.
• The collection of all equivalence classes forms a partition of $S$.

Note: equivalence classes do not necessarily have equal sizes. Under congruence mod 2 on $\{1, 2, 3, 4, 5\}$, the class of even numbers has 2 elements and the class of odd numbers has 3.

Partitions

A partition of a set $S$ is a collection of non-empty subsets of $S$ such that every element of $S$ belongs to exactly one subset. The subsets don't overlap, and together they cover everything.

Relationship to equivalence relations

There's a perfect correspondence between equivalence relations and partitions:

• Every equivalence relation on $S$ produces a unique partition (its equivalence classes).
• Every partition of $S$ defines a unique equivalence relation (declare two elements related if and only if they're in the same subset).

This two-way connection means you can always move between the two perspectives. Sometimes it's easier to define the partition directly, and other times it's easier to define the relation and let the classes fall out.

Properties of partitions

• Each element of $S$ belongs to exactly one subset (block) of the partition.
• The union of all blocks equals $S$.
• Any two distinct blocks have empty intersection: if $A \neq B$, then $A \cap B = \emptyset$.
• The number of blocks equals the number of equivalence classes.
• A refinement of a partition splits some blocks into smaller pieces, corresponding to a "finer" (more discriminating) equivalence relation.

Quotient sets

The quotient set collects all the equivalence classes into a single set. It's the result of "collapsing" each equivalence class down to a single point.

Construction of quotient sets

The quotient set of $S$ by the equivalence relation $R$ is written:

$S/R = \{[a] \mid a \in S\}$

Each element of $S/R$ is an entire equivalence class, not an individual element of $S$. For example, $\mathbb{Z}/\equiv_3$ (the integers mod 3) has exactly three elements: $[0], [1], [2]$.

To construct a quotient set:

1. Identify the equivalence relation $R$ on $S$.
2. Determine the equivalence classes by grouping related elements.
3. Collect these classes into a set. That set is $S/R$.

Applications of quotient sets

• Modular arithmetic: $\mathbb{Z}/n\mathbb{Z}$ treats integers as equivalent if they differ by a multiple of $n$, giving you a finite number system to work with.
• Constructing new structures: In algebra, factor groups (quotient groups) are built this way.
• State reduction: In computer science, minimizing a finite automaton involves collapsing equivalent states into a quotient structure.
• Rational numbers: $\mathbb{Q}$ can be constructed as a quotient set of pairs of integers, where $\frac{a}{b} \sim \frac{c}{d}$ whenever $ad = bc$.

Equivalence relation proofs

Proving that a relation is (or isn't) an equivalence relation is a standard exercise that builds proof-writing skills. The structure is always the same: check all three properties.

Proving reflexivity, symmetry, transitivity

To prove a relation $R$ on a set $S$ is an equivalence relation, you need three separate arguments:

1. Reflexivity: Pick an arbitrary $a \in S$. Show that $aRa$ holds using the definition of $R$.
2. Symmetry: Assume $aRb$ for arbitrary $a, b \in S$. Show that $bRa$ follows.
3. Transitivity: Assume $aRb$ and $bRc$ for arbitrary $a, b, c \in S$. Show that $aRc$ follows.

Worked example: Prove that congruence mod 3 is an equivalence relation on $\mathbb{Z}$.

Define $aRb$ to mean $3 \mid (a - b)$.

• Reflexivity: $a - a = 0 = 3 \cdot 0$, so $3 \mid (a - a)$. Thus $aRa$.
• Symmetry: If $3 \mid (a - b)$, then $a - b = 3k$ for some integer $k$. So $b - a = 3(-k)$, meaning $3 \mid (b - a)$. Thus $bRa$.
• Transitivity: If $3 \mid (a - b)$ and $3 \mid (b - c)$, then $a - b = 3k$ and $b - c = 3m$. Adding: $a - c = 3(k + m)$, so $3 \mid (a - c)$. Thus $aRc$.

Disproving equivalence relations

To show a relation is not an equivalence relation, you only need one counterexample violating one property:

• Reflexivity fails: Find an element $a$ where $aRa$ doesn't hold.
• Symmetry fails: Find $a, b$ where $aRb$ but not $bRa$.
• Transitivity fails: Find $a, b, c$ where $aRb$ and $bRc$ but not $aRc$.

For example, "is a friend of" on a set of people might fail transitivity: Alice is friends with Bob, Bob is friends with Carol, but Alice and Carol might not be friends.

Equivalence relations in mathematics

Number theory applications

• Congruence modulo $n$ partitions $\mathbb{Z}$ into $n$ equivalence classes based on remainders. This is the foundation of modular arithmetic and appears throughout number theory and cryptography.
• Rational number equivalence treats fractions as equivalent when they reduce to the same value: $\frac{1}{2} \sim \frac{2}{4} \sim \frac{3}{6}$.
• Equivalence of quadratic residues modulo a prime groups integers by whether they're perfect squares in that modular system.

Geometry applications

• Congruence of figures: same size and shape (related by rigid motions).
• Similarity of figures: same shape, possibly different sizes (related by rigid motions plus scaling).
• Parallelism of lines groups lines by direction.
• Equivalence under transformations: Points that map to each other under a group of symmetries (rotations, reflections) form equivalence classes called orbits.

Equivalence relations in computer science

Hashing and equivalence

Hash functions map elements into buckets, and elements landing in the same bucket form a kind of equivalence class. Collision resolution handles the case where distinct elements end up in the same class. Locality-sensitive hashing intentionally groups similar items together, using a notion of approximate equivalence.

State equivalence in automata

When minimizing a finite automaton, you identify states that produce identical output behavior for all possible inputs. These equivalent states get merged, producing the smallest automaton that recognizes the same language. Hopcroft's algorithm does this efficiently by iteratively refining equivalence classes of states.

Bisimulation in process calculi extends this idea: two processes are bisimilar (behaviorally equivalent) if they can simulate each other step by step.

Equivalence vs other relations

Equivalence vs partial order

The key distinction: equivalence relations group elements as "the same," while partial orders rank elements as "less than or equal to." A partial order's antisymmetry means if $aRb$ and $bRa$, then $a = b$, which is the opposite of what symmetry does.

Equivalence vs congruence

A congruence relation is an equivalence relation that also respects algebraic operations. For example, congruence mod $n$ isn't just an equivalence relation on $\mathbb{Z}$; it's compatible with addition and multiplication:

• If $a \equiv b \pmod{n}$ and $c \equiv d \pmod{n}$, then $a + c \equiv b + d \pmod{n}$.

This compatibility is what allows you to do arithmetic in the quotient set $\mathbb{Z}/n\mathbb{Z}$. A general equivalence relation doesn't guarantee this, so you can't always define operations on the quotient set.

Computational aspects

Algorithms for equivalence checking

The Union-Find (disjoint set) data structure is the go-to tool for managing equivalence classes computationally. It supports two operations:

1. Find: Determine which equivalence class an element belongs to.
2. Union: Merge two equivalence classes when you learn two elements are related.

With path compression and union by rank optimizations, both operations run in nearly constant amortized time ($O(\alpha(n))$, where $\alpha$ is the inverse Ackermann function, which grows incredibly slowly).

Other relevant algorithms include Hopcroft's algorithm for DFA minimization and graph-based approaches for finding equivalence classes in networks.

Complexity considerations

• Union-Find with optimizations gives near-constant time per operation, making it practical for very large sets.
• Equivalence checking can often be reduced to graph reachability: two elements are equivalent if and only if there's a path between them.
• There are space-time tradeoffs between storing all equivalence classes explicitly versus computing membership on the fly.
• Some equivalence problems are computationally hard. Graph isomorphism (determining whether two graphs are "the same" up to relabeling) is a famous example whose exact complexity class remains an open question.