Equivalence class explained

In mathematics, given a set and an equivalence relation on, the equivalence class of an element in is the subset of all elements in which are equivalent to . Equivalence classes among elements of a structure are often used to produce a smaller structure whose elements are the classes, distilling a relationship every element of the class shares with at least one other element of another class. This is known as modding out by the class. The class may assume the identity of one of the original elements, as when fractions are put in reduced form.

Notation and formal definition

An equivalence relation is a binary relation satisfying three properties:

• For every element in, (reflexivity),
• For every two elements and in, if, then (symmetry), and
• For every three elements,, and in, if and, then (transitivity).

The equivalence class of an element is denoted and may be defined as the set

[a]=\{x\inX\mida\simx\}

of elements that are related to by . The alternative notation can be used to denote the equivalence class of the element specifically with respect to the equivalence relation . This is said to be the -equivalence class of .

The set of all equivalence classes in given an equivalence relation is denoted as and called the quotient set of by . Each equivalence relation has a canonical projection map, the surjective function from to given by .

Analogy with division

This operation can be thought of (very informally) 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 is finite and the equivalence classes are all equinumerous, then the number of equivalence classes in can be calculated by dividing the number of elements in by the number of elements in each equivalence class. The quotient set may be thought of as the set with all the equivalent points identified.

Examples

• If 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. could be naturally identified with the set of all car colors.
• Consider the modulo 2 equivalence relation on the set of integers: if and only if their difference is an even number. This relation gives rise to exactly two equivalence classes: one class consisting of all even numbers, and the other consisting of all odd numbers. Under this relation,, and all represent the same element of .
• Let be the set of ordered pairs of integers with not zero, and define an equivalence relation on according to which if and only if . Then the equivalence class of the pair can be identified with the rational number, and this equivalence relation and its equivalence classes can be used to give a formal definition of the set of rational numbers. The same construction can be generalized to the field of fractions of any integral domain.

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

if and only if .

In other words, if is an equivalence relation on a set, and and are two elements of, then these statements are equivalent:

x\simy

[x]=[y]

[x]\cap[y]\ne\emptyset

.

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 a morphism for, a 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 known as a morphism from to .