Equivalence class

Properties

For a set ${\displaystyle X}$ with an equivalence relation ${\displaystyle \sim }$, every element ${\displaystyle x}$ of ${\displaystyle X}$ is a member of the equivalence class ${\displaystyle [x]}$ by reflexivity (${\displaystyle a\sim a}$ for all ${\displaystyle a\in X}$). Every two equivalence classes ${\displaystyle [x]}$ and ${\displaystyle [y]}$ are either equal if ${\displaystyle x\sim y}$, or disjoint otherwise. Therefore, the set of all equivalence classes of ${\displaystyle X}$ forms a partition of ${\displaystyle X}$: every element ${\displaystyle x}$ of ${\displaystyle X}$ belongs to one and only one equivalence class.

Conversely, for a set ${\displaystyle X}$, every partition comes from an equivalence relation in this way, and different relations give different partitions. Thus ${\displaystyle x\sim y}$ if and only if ${\displaystyle x}$ and ${\displaystyle y}$ belong to the same set of the partition.

It follows from the properties in the previous section that if ${\displaystyle \sim }$ is an equivalence relation on a set ${\displaystyle X,}$ and ${\displaystyle x}$ and ${\displaystyle y}$ are two elements of ${\displaystyle X,}$ the following statements are equivalent:

• ${\displaystyle x\sim y}$,
• ${\displaystyle [x]=[y]}$, and
• ${\displaystyle [x]\cap [y]\ne \mathrm{\varnothing }.}$

Examples

• Let ${\displaystyle X}$ be the set of all rectangles in a plane, and ${\displaystyle \sim }$ the equivalence relation "has the same area as", then for each positive real number ${\displaystyle A,}$ there will be an equivalence class of all the rectangles that have area ${\displaystyle A.}$
  • For example, the rectangles with side lengths 2 by 4 and 1 by 8 both have the area 8. Although they differ, in shape, they are equivalent under the relation "has the same area" so they are in the same equivalence class.
• Consider the modulo 2 equivalence relation on the set of integers, ${\displaystyle \mathbb{Z},}$ such that ${\displaystyle x\sim y}$ if and only if their difference ${\displaystyle x-y}$ is an even number. This relation gives rise to exactly two equivalence classes: one class consists of all even numbers, and the other class consists of all odd numbers. Using square brackets around one member of the class to denote an equivalence class under this relation, ${\displaystyle [7],[9],}$ and ${\displaystyle [1]}$ all represent the same element of ${\displaystyle \mathbb{Z}/\sim .}$
  • Congruence modulo 3 on the set of integers can be examined to demonstrate this. Under this equivalence relation,

[0] = {..., -9, -6, -3, 0, 3, 6, 9,...}

[1] = {..., -8, -5, -2, 1, 4, 7, 10,...}

[2] = {..., -7, -4, -1, 2, 5, 8, 11,...}

Each value in ${\displaystyle \mathbb{Z}}$ belongs to only one of the classes where elements 0, 1 and 2 are the canonical representatives of their classes.

• Let ${\displaystyle X}$ be the set of ordered pairs of integers ${\displaystyle (a,b)}$ with non-zero ${\displaystyle b,}$ and define an equivalence relation ${\displaystyle \sim }$ on ${\displaystyle X}$ such that ${\displaystyle (a,b)\sim (c,d)}$ if and only if ${\displaystyle ad=bc,}$ then the equivalence class of the pair ${\displaystyle (a,b)}$ can be identified with the rational number ${\displaystyle a/b,}$ 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.
  • The ordered pairs ${\displaystyle (1,2),(2,4)}$ and ${\displaystyle (3,6)}$serve as an example of this. These pairs belong to the same equivalence class as each ${\displaystyle (a,b)}$ pairing represents the rational number ⁠1/2⁠.
• If ${\displaystyle X}$ consists of all the lines in the Euclidean plane, and ${\displaystyle L\sim M}$ means that ${\displaystyle L}$ and ${\displaystyle M}$ are parallel lines, then the set of lines that are parallel to each other form an equivalence class, as long as a line is considered parallel to itself. In this situation, each equivalence class determines a point at infinity.
  • In the Cartesian plane, the lines ${\displaystyle y=2x-3}$ and ${\displaystyle y=2x+1}$ have the same slope—and are parallel—so they belong to the same equivalence class.
• For any set ${\displaystyle X}$, the relation ${\displaystyle x\sim y⟺x=y}$ is an equivalence relation in which every equivalence class is a set consisting of a single element.
  • If ${\displaystyle X}$ = ${\displaystyle \{1,2,3\}}$, then the equivalence classes are ${\displaystyle [1],[2],}$ and ${\displaystyle [3]}$ as no two distinct elements are considered equivalent under the equality relation.

Graphical representation

An undirected graph may be associated to any symmetric relation on a set ${\displaystyle X,}$ where the vertices are the elements of ${\displaystyle X,}$ and two vertices ${\displaystyle s}$ and ${\displaystyle t}$ are joined if and only if ${\displaystyle s\sim t.}$ Among these graphs are the graphs of equivalence relations. These graphs, called cluster graphs, are characterized as the graphs such that the connected components are cliques.

Invariants

If ${\displaystyle \sim }$ is an equivalence relation on ${\displaystyle X,}$ and ${\displaystyle P(x)}$ is a property of elements of ${\displaystyle X}$ such that whenever ${\displaystyle x\sim y,}$ ${\displaystyle P(x)}$ is true if ${\displaystyle P(y)}$ is true, then the property ${\displaystyle P}$ is said to be an invariant of ${\displaystyle \sim ,}$ or well-defined under the relation ${\displaystyle \sim .}$

A frequent particular case occurs when ${\displaystyle f}$ is a function from ${\displaystyle X}$ to another set ${\displaystyle Y}$; if ${\displaystyle f\left(x_1\right)=f\left(x_2\right)}$ whenever ${\displaystyle x_1\sim x_2,}$ then ${\displaystyle f}$ is said to be class invariant under ${\displaystyle \sim ,}$ or simply invariant under ${\displaystyle \sim .}$ This occurs, for example, in the character theory of finite groups. Some authors use "compatible with ${\displaystyle \sim }$" or just "respects ${\displaystyle \sim }$" instead of "invariant under ${\displaystyle \sim }$".

Any function ${\displaystyle f:X\to Y}$ is class invariant under ${\displaystyle \sim ,}$ according to which ${\displaystyle x_1\sim x_2}$ if and only if ${\displaystyle f\left(x_1\right)=f\left(x_2\right).}$ The equivalence class of ${\displaystyle x}$ is the set of all elements in ${\displaystyle X}$ which get mapped to ${\displaystyle f(x),}$ that is, the class ${\displaystyle [x]}$ is the inverse image of ${\displaystyle f(x).}$ This equivalence relation is known as the kernel of ${\displaystyle f.}$

More generally, a function may map equivalent arguments (under an equivalence relation ${\displaystyle {\sim }_X}$ on ${\displaystyle X}$) to equivalent values (under an equivalence relation ${\displaystyle {\sim }_Y}$ on ${\displaystyle Y}$). 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 ${\displaystyle X,}$ either to an equivalence relation that induces some structure on the set of equivalence classes from a structure of the same kind on ${\displaystyle X,}$ 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.