Equivalence class

In mathematics, when the elements of some set have a notion of equivalence (formalized as an equivalence relation) defined on them, then one may naturally split the set into equivalence classes. These equivalence classes are constructed so that elements and belong to the same equivalence class if, and only if, they are equivalent.
Formally, given a set and an equivalence relation on , the "equivalence class" of an element in , denoted by formula_1, is the set
of elements which are equivalent to . It may be proven, from the defining properties of equivalence relations, that the equivalence classes form a partition of . This partition—the set of equivalence classes—is sometimes called the quotient set or the quotient space of by , and is denoted by .
When the set has some structure (such as a group operation or a topology) and the equivalence relation is compatible with this structure, the quotient set often inherits a similar structure from its parent set. Examples include quotient spaces in linear algebra, quotient spaces in topology, quotient groups, homogeneous spaces, quotient rings, quotient monoids, and quotient categories.
Notation and formal definition.
An equivalence relation on a set is a binary relation on satisfying the three properties:
The equivalence class of an element is denoted or , and is defined as the set formula_3 of elements that are related to by . The word "class" in the term "equivalence class" does not refer to classes as defined in set theory, however equivalence classes do often turn out to be proper classes.
The set of all equivalence classes in with respect to an equivalence relation is denoted as , and is called modulo (or the quotient set of by ). The surjective map formula_4 from onto , which maps each element to its equivalence class, is called the canonical surjection, or the canonical projection map.
When an element is chosen (often implicitly) in each equivalence class, this defines an injective map called a "section". If this section is denoted by , one has for every equivalence class . The element is called a representative of . Any element of a class may be chosen as a representative of the class, by choosing the section appropriately.
Sometimes, there is a section that is more "natural" than the other ones. In this case, the representatives are called "canonical representatives". For example, in modular arithmetic, consider the equivalence relation on the integers defined as follows: if is a multiple of a given positive integer (called the "modulus"). Each class contains a unique non-negative integer smaller than , and these integers are the canonical representatives. The class and its representative are more or less identified, as is witnessed by the fact that the notation may denote either the class, or its canonical representative (which is the remainder of the division of by ).
Properties.
Every element of is a member of the equivalence class . Every two equivalence classes and are either equal or disjoint. Therefore, the set of all equivalence classes of forms a partition of : every element of belongs to one and only one equivalence class. Conversely, every partition of comes from an equivalence relation in this way, according to which if and only if and belong to the same set of the partition.
It follows from the properties of an equivalence relation that
In other words, if is an equivalence relation on a set , and and are two elements of , then these statements are equivalent:
Graphical representation.
An undirected graph may be associated to any symmetric relation on a set , where the vertices are the elements of , and two vertices and are joined if and only if . Among these graphs are the graphs of equivalence relations; they are characterized as the graphs such that the connected components are cliques.
Invariants.
If is an equivalence relation on , and is a property of elements of such that whenever , is true if is true, then the property is said to be an invariant of , or well-defined under the relation .
A frequent particular case occurs when is a function from to another set ; if whenever , then is said to be "class invariant under" , or simply "invariant under" . This occurs, e.g. in the character theory of finite groups. Some authors use "compatible with " or just "respects " instead of "invariant under ".
Any function itself defines an equivalence relation on according to which if and only if . The equivalence class of is the set of all elements in which get mapped to , i.e. the class is the inverse image of . This equivalence relation is known as the kernel of .
More generally, a function may map equivalent arguments (under an equivalence relation on ) to equivalent values (under an equivalence relation on ). Such a function is a morphism of sets equipped with an equivalence relation.
Quotient space in topology.
In topology, a quotient space is a topological space formed on the set of equivalence classes of an equivalence relation on a topological space, using the original space's topology to create the topology on the set of equivalence classes.
In abstract algebra, congruence relations on the underlying set of an algebra allow the algebra to induce an algebra on the equivalence classes of the relation, called a quotient algebra. In linear algebra, a quotient space is a vector space formed by taking a quotient group, where the quotient homomorphism is a linear map. By extension, in abstract algebra, the term quotient space may be used for quotient modules, quotient rings, quotient groups, or any quotient algebra. However, the use of the term for the more general cases can as often be by analogy with the orbits of a group action.
The orbits of a group action on a set may be called the quotient space of the action on the set, particularly when the orbits of the group action are the right cosets of a subgroup of a group, which arise from the action of the subgroup on the group by left translations, or respectively the left cosets as orbits under right translation.
A normal subgroup of a topological group, acting on the group by translation action, is a quotient space in the senses of topology, abstract algebra, and group actions simultaneously.
Although the term can be used for any equivalence relation's set of equivalence classes, possibly with further structure, the intent of using the term is generally to compare that type of equivalence relation on a set , either to an equivalence relation that induces some structure on the set of equivalence classes from a structure of the same kind on , or to the orbits of a group action. Both the sense of a structure preserved by an equivalence relation, and the study of invariants under group actions, lead to the definition of invariants of equivalence relations given above.