Equivalence Relations

College Depth 7 in the knowledge graph I know this Set as goal
Unlocks 2666 downstream topics
relations equivalence partitions

Core Idea

An equivalence relation is reflexive, symmetric, and transitive. Every equivalence relation partitions its domain into equivalence classes of mutually related elements, formalizing the notion of 'sameness' for a given property.

Explainer

You already know what a binary relation is — a set of ordered pairs that records which elements are related to which. An equivalence relation is a special kind of binary relation that formalizes the intuitive idea of "sameness under some criterion." The three defining properties — reflexive, symmetric, and transitive — are precisely what any reasonable notion of sameness must satisfy.

Reflexivity says every element is related to itself (a ~ a). Symmetry says the relation works in both directions (if a ~ b, then b ~ a). Transitivity says the relation is consistent across chains (if a ~ b and b ~ c, then a ~ c). Intuitively: you're the same as yourself, sameness is mutual, and chains of sameness compose. Geometric congruence satisfies all three. Equality satisfies all three. "Has the same remainder when divided by 3" satisfies all three — and this last example is modular arithmetic in disguise, a sign of how pervasive equivalence relations are.

The most important consequence of these three properties together is the partition theorem: every equivalence relation on a set S partitions S into equivalence classes — non-overlapping groups where every element belongs to exactly one group. The equivalence class of a, written [a], is the set {x : x ~ a}. Two elements are in the same class if and only if they are related. This is why mathematicians use equivalence relations so extensively: when you want to treat "indistinguishable" things as the same object, you quotient by an equivalence relation and work with classes instead of individual elements. Rational numbers are defined this way (pairs of integers under the equivalence (a, b) ~ (c, d) iff ad = bc).

A common pitfall is assuming that any two of the three properties imply the third. They do not. The relation ≤ on real numbers is reflexive and transitive but not symmetric — it is a partial order, not an equivalence relation. Admiration between people may be symmetric but rarely reflexive or transitive. When verifying whether a relation is an equivalence relation, always check each property separately, either by proving it holds or constructing a counterexample to show it fails.

Practice Questions 3 questions

Prerequisite Chain

Longest path: 8 steps · 12 total prerequisite topics

Prerequisites (1)

Leads To (17)