Equivalence class

In mathematics, given a set X and an equivalence relation ~ on X, the equivalence class of an element a in X is the subset of all elements in X which are equivalent to a:

[a] = { x in X | x ~ a }

The notion of equivalence classes is useful for constructing sets out of already constructed ones. The set of all equivalence classes in X given an equivalence relation ~ is usually denoted as X / ~ and called the quotient set of X by ~. This operation can be thought of (very informally indeed) as the act of "dividing" the input set by the equivalence relation, hence both the name "quotient", and the notation, which are both reminiscent of division.

In cases where X has some additional structure preserved under ~, the quotient becomes an object of the same type in a natural fashion; the map that sends a to [a] is then an epimorphism. See congruence relation.

Examples

If X is the set of all cars, and ~ is the equivalence relation of "having the same color", then one particular equivalence class consists of all green cars. X / ~ could be naturally identified with the set of all car colors.
Consider the "modulo 2" equivalence relation on the set of integers: x~y if and only if x-y is even. This relation gives rise to exactly two equivalence classes: [0] consisting of all even numbers, and [1] consisting of all odd numbers.
The rational numbers can be constructed as the set of equivalence classes of ordered pairs of integers (a,b) with b not zero, where the equivalence relation is defined by

(a,b) ~ (c,d) if and only if ad = bc.

Here the equivalence class of the pair (a,b) can be identified with rational number a/b.

Any function f : X → Y defines an equivalence relation on X by x ~ y iff f(x) = f(y). The equivalence class of x is the set of all elements in X which get mapped to f(x), i.e. the class [x] is the inverse image of f(x). This equivalence relation is known as the kernel of f.
Given a group G and a subgroup H, we can define an equivalence relation on G by x ~ y iff xy^-1 ∈ H. The equivalence classes are known as right cosets of H in G. If H is a normal subgroup, then the set of all cosets is itself a group in a natural way.
Every group can be partitioned into equivalence classes called conjugacy classes.
The homotopy class of a continuous map f is the equivalence class of all maps homotopic to f.
In natural language processing, an equivalence class is a set of all references to a single person, place, thing, or event, either real or conceptual. For example, in the sentence "GE shareholders will vote for a successor to the company's outgoing CEO Jack Welch", GE and the company are synonomous, and thus constitute one equivalence class. There are separate equivalence classes for GE shareholders and Jack Welch.

Properties

Because of the properties of an equivalence relation it holds that a is in [a] and that any two equivalence classes are either equal or disjoint. It follows that the set of all equivalence classes of X forms a partition of X: every element of X belongs to one and only one equivalence class. Conversely every partition of X also defines an equivalence relation over X.

It also follows from the properties of an equivalence relation that

a ~ b if and only if [a] = [b].

If ~ is an equivalence relation on X, and P(x) is a property of elements of x, such that whenever x ~ y, P(x) is true iff P(y) is true, then the property P is said to be a class invariant under the relation ~. A frequent particular case occurs when f is a function from X to another set Y; if x ~ y implies f(x) = f(y) then f is said to be a class invariant under ~, or simply invariant under ~. This occurs, e.g. in the character theory of finite groups. The latter case with the function f can be expressed by a commutative triangle. See also invariant.