In mathematics an equivalence relation is a binary relation on a set that formalizes a notion of sameness or indistinguishability for the objects of that set. Informally, an equivalence relation groups elements that should be treated as equivalent for some purpose. Formally, a relation R on a set X is an equivalence relation if it satisfies three properties at once: reflexivity, symmetry and transitivity. These properties are usually studied in elementary set theory and discrete mathematics; see a general introduction to mathematics and to the concept of a binary relation.

Formal definition and immediate consequences

Let X be a set and R a subset of X×X. The relation R is reflexive if every x in X satisfies x R x. It is symmetric if whenever x R y then y R x. It is transitive if whenever x R y and y R z then x R z. These three conditions together ensure that R behaves like a consistent equivalence notion: each element is equivalent to itself, equivalence passes both ways, and it propagates along chains. For further discussion of the individual properties see entries on symmetry and transitivity.

Given an equivalence relation R on X and an element a in X, the equivalence class of a, denoted [a], is the subset of X consisting of all elements related to a. Equivalence classes are either identical or disjoint: any two classes are either the same set or have empty intersection. The family of all equivalence classes forms a partition of X, and conversely any partition of X determines an equivalence relation (two elements are equivalent exactly when they lie in the same block). For background on this correspondence see partitions.

It is common to denote the set of all equivalence classes by X/~ or X/R. There is a natural surjection, often called the canonical projection or quotient map, from X to X/~ which sends each element to its class. This projection has the universal property in many algebraic and categorical contexts: maps defined on X that are constant on each class factor uniquely through the quotient.

Examples

Examples illustrate why equivalence relations are pervasive:

  1. Congruence modulo n on the integers: two integers are equivalent if their difference is divisible by n. The equivalence classes are the residue classes modulo n, central to number theory and modular arithmetic.
  2. Equality of shapes up to rigid motion: two geometric figures are equivalent if one can be moved without stretching to coincide with the other; this notion underlies congruence in geometry.
  3. Same species in a population: classifying animals by species is an intuitive example — two animals are equivalent when they belong to the same species. See a simple animal-species illustration here and an explanatory note here.
  4. Kernel of a function: given a function f:X→Y, define x~y when f(x)=f(y). This is an equivalence relation, and its classes are the fibres of f; this construction explains many algebraic quotients.

Equivalence relations also arise when some property is required to hold almost everywhere: for example, two functions may be declared equivalent if they agree except on a set of measure zero. Such relations are fundamental in functional analysis and measure theory.

Quotients and algebraic constructions

Forming the set of equivalence classes (the quotient) is an essential step in many mathematical constructions. In algebra, quotient groups, rings, and modules are obtained by declaring two elements equivalent when their difference lies in a fixed normal subgroup or ideal; in topology, quotient spaces are built by identifying points according to an equivalence relation and equipping the set of classes with the quotient topology. These quotient constructions systematically reduce complexity by collapsing equivalent items to single entities.

The process of passing to a quotient is subject to natural constraints: additional structure on X (such as an algebraic operation or a topology) often induces structure on the quotient only when the equivalence relation is compatible with that structure. In group theory this compatibility is captured by the notion of a normal subgroup; in topology the equivalence relation should be such that the quotient map is continuous with appropriate properties.

Practical uses and computational aspects

In computer science equivalence relations appear in state minimization for finite automata, in union–find algorithms that maintain a partition efficiently, and in type systems and program analysis where one must identify equivalent program states or types. Efficient data structures exploit the partition nature of equivalence relations: instead of storing pairwise relations, one represents blocks and a representative element for each block.

For further reading and elementary exercises, standard textbooks on set theory, abstract algebra and topology develop the theory of equivalence relations alongside partitions and quotient constructions. Overview articles and lecture notes provide worked examples and applications; see a compact overview of equivalence classes here.

In summary, equivalence relations give a concise formal way to express that certain differences between objects are to be ignored. They underlie many classification schemes across mathematics, permit formation of quotient objects that simplify problems, and connect directly to the combinatorial notion of partitions and to practical algorithms for grouping and identification.