Equivalence class

An equivalence class is a subset of a set whose elements are all equivalent to each other under a given equivalence relation. This fundamental concept in mathematics, particularly in set theory and abstract algebra, partitions a set into disjoint subsets where every element belongs to exactly one class, grouping objects that are considered "the same" with respect to the relation.

Definition and formal construction

Given a set S and an equivalence relation ~ on S, the equivalence class of an element a in S is the set of all elements in S that are related to a by ~. Formally, it is denoted as [a] = {x ∈ S | x ~ a}. The equivalence relation ~ must satisfy three properties: reflexivity (a ~ a for all a in S), symmetry (if a ~ b then b ~ a), and transitivity (if a ~ b and b ~ c then a ~ c). These properties ensure that the equivalence classes form a partition of S, meaning every element of S is in exactly one equivalence class. The set of all equivalence classes is called the quotient set, denoted S/~.

Examples in mathematics

In modular arithmetic, the equivalence classes are called congruence classes. For example, modulo 5, the equivalence class of 2 contains all integers that leave a remainder of 2 when divided by 5: [2] = {..., -8, -3, 2, 7, 12, ...}. In geometry, the set of all triangles can be partitioned into equivalence classes by the relation "is similar to," where each class contains triangles with the same shape but possibly different sizes. In linear algebra, the kernel of a linear transformation partitions the domain vector space into equivalence classes called cosets, where vectors are equivalent if their difference is in the kernel.

Properties and applications

Equivalence classes exhibit several important properties. They are always non-empty because each element is related to itself. They are either equal or disjoint, meaning any two distinct equivalence classes have no elements in common. The union of all equivalence classes equals the original set. These properties make equivalence classes crucial in defining mathematical structures such as quotient groups, quotient rings, and quotient spaces, where the quotient object inherits structure from the original set. In computer science, equivalence classes are used in algorithm design, particularly in union-find data structures for managing partitions. They also appear in database theory for normalizing data and eliminating redundancy.

Relation to partitions

There is a natural bijection between equivalence relations on a set and partitions of that set. Every equivalence relation induces a partition of the set into its equivalence classes, and conversely, every partition of a set defines an equivalence relation where two elements are related if they belong to the same part of the partition. This correspondence is fundamental in combinatorics and probability, where counting equivalence classes under symmetry relations (such as in Burnside's lemma) is essential for solving enumeration problems.