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 }
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.
Table of contents |
2 Properties 3 Related topics |
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 pairs of integers (a,b) with b not zero, where the equivalence relation is defined by
- Any function f : X → Y defines an equivalence relation an 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].
- a ~ b if and only if [a] = [b].
Related topics
- equivalence relation
- partition
- first isomorphism theorem
- congruence relation
- rational numbers
- homotopy theory
- up to
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.