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: Euclid, Greek mathematician, 3rd century BC, as imagined by by Raphael in this detail from The School of Athens. ... In mathematics, a set can be thought of as any collection of distinct things considered as a whole. ... In mathematics, an equivalence relation, denoted by an infix ~, is a binary relation on a set X that is reflexive, symmetric, and transitive. ... A is a subset of B, and B is a superset of A. In mathematics, especially in set theory, the terms, subset, superset and proper (or strict) subset or superset are used to describe the relation, called inclusion, of one set being contained inside another set. ...

[a] = { x ∈ 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. One way in which the quotient set resembles division is that if X is finite and the equivalence classes are all equinumerous, then the order of X/~ is the quotient of the order of X by the order of an equivalence class. The quotient set is to be thought of as the set X with all the equivalent points identified. Two sets A and B are said to be equinumerous if they have the same cardinality, i. ...

For any equivalence relation, there is a canonical projection map π from X to X/~ given by π(x) = [x]. This map is always surjective. In cases where X has some additional structure, one considers equivalence relations which preserve that structure. Then one says that that structure is well-defined, and the quotient set inherits the structure to become an object of the same category in a natural fashion; the map that sends a to [a] is then an epimorphism in that category. See congruence relation. In mathematics, a surjective function (or onto function or surjection) is a function with the property that all possible output values of the function are generated when the input ranges over all the values in the domain. ... In mathematics, the term well-defined is used to specify that a certain concept (a function, a property, a relation, etc. ... In mathematics, categories allow one to formalize notions involving abstract structure and processes which preserve structure. ... In mathematics and related technical fields, the term map or mapping is often a synonym for function. ... In category theory an epimorphism (also called an epic morphism or an epi) is a morphism f : X → Y which is right-cancellable in the following sense: g1 o f = g2 o f implies g1 = g2 for all morphisms g1, g2 : Y → Z. Epimorphisms are analogues of surjective functions, but... In mathematics and especially in abstract algebra, a congruence relation or simply congruence is an equivalence relation that is compatible with some algebraic operation(s). ...

Examples

• If X is the set of all cars, and ~ is the equivalence relation "has the same color as", 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 Z 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. Under this relation [7] [9] and [1] all represent the same element of Z / ~.
• 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₁ ~ x₂ if and only if f(x₁) = f(x₂). 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 if and only if xy ^-1 ∈ H. The equivalence classes are known as right cosets of H in G; one of them is H itself. They all have the same number of elements (or cardinality in the case of an infinite H). 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 synonymous, and thus constitute one equivalence class. There are separate equivalence classes for GE shareholders and Jack Welch.

Modular arithmetic (sometimes called modulo arithmetic) is a system of arithmetic for integers, where numbers wrap around after they reach a certain value — the modulus. ... The integers are commonly denoted by the above symbol. ... In mathematics, the parity of an object refers to whether it is even or odd. ... In mathematics, a rational number (commonly called a fraction) is a ratio or quotient of two integers, usually written as the vulgar fraction a/b, where b is not zero. ... Partial plot of a function f. ... It has been suggested that this article or section be merged with Logical biconditional. ... In mathematics, the image of an element x in a set X under the function f : X → Y, denoted by f(x), is the unique y in Y that is associated with x. ... In mathematics, the kernel of a function f may be taken to be either the equivalence relation on the functions domain that roughly expresses the idea of equivalent as far as the function f can tell, or the corresponding partition of the domain. ... This picture illustrates how the hours in a clock form a group. ... In group theory, given a group G under a binary operation *, we say that some subset H of G is a subgroup of G if H also forms a group under the operation *. More precisely, H is a subgroup of G if the restriction of * to H is a group... In mathematics, if G is a group, H a subgroup of G, and g an element of G, then gH = { gh : h an element of H } is a left coset of H in G, and Hg = { hg : h an element of H } is a right coset of H in G... In mathematics, the cardinality of a set is a measure of the number of elements of the set. There are two approaches to cardinality – one which compares sets directly using bijections, injections, and surjections, and another which uses cardinal numbers. ... Infinity is a word carrying a number of different meanings in mathematics, philosophy, theology and everyday life. ... In mathematics, a normal subgroup N of a group G is a subgroup invariant under conjugation; that is, for each element n in N and each g in G, the element g−1ng is still in N. The statement N is a normal subgroup of G is written: . There are... In mathematics, especially group theory, the elements of any group may be partitioned into conjugacy classes; members of the same conjugacy class share many properties, and study of conjugacy classes of non-abelian groups reveals many important features of their structure. ... The two bold paths shown above are homotopic relative to their endpoints. ... In mathematics, a continuous function is a function for which, intuitively, small changes in the input result in small changes in the output. ... Natural language processing (NLP) is a subfield of artificial intelligence and linguistics. ...

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. In mathematics, two sets are said to be disjoint if they have no element in common. ... A partition of U into 6 blocks: a Venn diagram representation. ...

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 if P(y) is true, then the property P is said to be well-defined or a class invariant under the relation ~. A frequent particular case occurs when f is a function from X to another set Y; if x₁ ~ x₂ implies f(x₁) = f(x₂) 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. In mathematics, the term well-defined is used to specify that a certain concept (a function, a property, a relation, etc. ... In mathematics, an invariant is something that does not change under a set of transformations. ...

Some authors use "compatible with ~" or just "respects ~" instead of "invariant under ~".

See also

• first isomorphism theorem
• up to
• character equivalence class
• In music see octave equivalency, transpositional equivalency, inversional equivalency, enharmonic equivalency. Musical set theory takes advantage of all of these, to varying degrees, while other theories take more or less advantage of a selection.
• In computing a form of testing is based on equivalence partitions, which are based on equivalence classes.