Equivalence relation

An equivalence relation is a binary relation that is reflexive, symmetric, and transitive, and it partitions a set into disjoint equivalence classes where all elements in a class are considered equivalent under the relation.

Definition and properties

An equivalence relation on a set \( S \) is a binary relation \( \sim \) that satisfies three fundamental properties for all elements \( a, b, c \in S \). First, reflexivity requires that every element is related to itself: \( a \sim a \). Second, symmetry dictates that if \( a \sim b \), then \( b \sim a \). Third, transitivity ensures that if \( a \sim b \) and \( b \sim c \), then \( a \sim c \). These properties collectively allow the relation to group elements into classes where all members are mutually related. Common examples include equality of numbers, geometric congruence, and logical equivalence. The properties ensure that the relation behaves in a consistent and predictable manner, forming the foundation for many mathematical constructions.

Equivalence classes

Given an equivalence relation \( \sim \) on a set \( S \), the equivalence class of an element \( a \in S \) is the set \( [a] = \{ x \in S \mid x \sim a \} \). This class contains all elements that are equivalent to \( a \). The set of all equivalence classes, denoted \( S / \sim \), forms a partition of \( S \), meaning every element of \( S \) belongs to exactly one equivalence class. For instance, in modular arithmetic, the equivalence relation "congruence modulo \( n \)" partitions the integers into \( n \) classes, such as the residue classes modulo 3: \( [0], [1], [2] \). Equivalence classes are fundamental in quotient structures, where they allow the construction of new sets by "gluing together" equivalent elements.

Examples in mathematics

Equivalence relations appear throughout mathematics. In set theory, the relation of having the same cardinality partitions sets into classes based on size. In geometry, congruence of triangles is an equivalence relation that groups triangles with identical shape and size. In algebra, the relation of being isomorphic groups partitions the class of all groups into isomorphism classes. Another key example is the relation of parallelism among lines in affine geometry, where lines are equivalent if they are parallel or coincident. These examples illustrate how equivalence relations simplify complex systems by identifying objects that share essential properties, enabling mathematicians to study representatives from each class rather than every individual element.

Construction and applications

Equivalence relations can be constructed from functions or other relations. If \( f: S \to T \) is a function, the relation defined by \( a \sim b \) if and only if \( f(a) = f(b) \) is an equivalence relation, whose classes are the fibers of \( f \). In topology, equivalence relations are used to form quotient spaces by identifying points, such as in the construction of the circle from a line segment. In computer science, they underpin data types that abstract away implementation details, like in type theory where types represent equivalence classes of values. Applications also include database theory, where they help in normalizing data, and in logic, where they model semantic equivalence. The versatility of equivalence relations makes them a cornerstone in both pure and applied disciplines.