
In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, when the elements of some
set have a notion of equivalence (formalized as an
equivalence relation
In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation.
Each equivalence relation ...
), 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 of an element
in
denoted by
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
In mathematics, a group is a set and an operation that combines any two elements of the set to produce a third element of the set, in such a way that the operation is associative, an identity element exists and every element has an inverse. Thes ...
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 group
A quotient group or factor group is a mathematical group obtained by aggregating similar elements of a larger group using an equivalence relation that preserves some of the group structure (the rest of the structure is "factored" out). For examp ...
s,
homogeneous space
In mathematics, particularly in the theories of Lie groups, algebraic groups and topological groups, a homogeneous space for a group ''G'' is a non-empty manifold or topological space ''X'' on which ''G'' acts transitively. The elements of ' ...
s,
quotient rings,
quotient monoids, and
quotient categories.
Examples
* If
is the set of all cars, and
is the
equivalence relation
In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation.
Each equivalence relation ...
"has the same color as", then one particular equivalence class would consist of all green cars, and
could be naturally identified with the set of all car colors.
* Let
be the set of all rectangles in a plane, and
the equivalence relation "has the same area as", then for each positive real number
there will be an equivalence class of all the rectangles that have area
* Consider the
modulo
In computing, the modulo operation returns the remainder or signed remainder of a division, after one number is divided by another (called the '' modulus'' of the operation).
Given two positive numbers and , modulo (often abbreviated as ) is t ...
2 equivalence relation on the set of
integers,
such that
if and only if their difference
is an
even number
In mathematics, parity is the property of an integer of whether it is even or odd. An integer is even if it is a multiple of two, and odd if it is not.. For example, −4, 0, 82 are even because
\begin
-2 \cdot 2 &= -4 \\
0 \cdot 2 &= 0 \\
41 ...
. 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,
and
ordered pair
In mathematics, an ordered pair (''a'', ''b'') is a pair of objects. The order in which the objects appear in the pair is significant: the ordered pair (''a'', ''b'') is different from the ordered pair (''b'', ''a'') unless ''a'' = ''b''. (In con ...
s of integers
(a, b) with non-zero
b, and define an equivalence relation
\,\sim\, on
X such that
(a, b) \sim (c, d) if and only if
a d = b c, then the equivalence class of the pair
(a, b) can be identified with the
rational number 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.
* If
X consists of all the lines in, say, the
Euclidean plane
In mathematics, the Euclidean plane is a Euclidean space of dimension two. That is, a geometric setting in which two real quantities are required to determine the position of each point ( element of the plane), which includes affine notions of ...
, and
L \sim M means that
L and
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.
Definition and notation
An
equivalence relation
In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation.
Each equivalence relation ...
on a set
X is a
binary relation
In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over Set (mathematics), sets and is a new set of ordered pairs consisting of ele ...
\,\sim\, on
X satisfying the three properties:
*
a \sim a for all
a \in X (
reflexivity),
*
a \sim b implies
b \sim a for all
a, b \in X (
symmetry
Symmetry (from grc, συμμετρία "agreement in dimensions, due proportion, arrangement") in everyday language refers to a sense of harmonious and beautiful proportion and balance. In mathematics, "symmetry" has a more precise definit ...
),
* if
a \sim b and
b \sim c then
a \sim c for all
a, b, c \in X (
transitivity).
The equivalence class of an element
a is often denoted
/math> or , and is defined as the set \ of elements that are related to a by \,\sim. The word "class" in the term "equivalence class" may generally be considered as a synonym of " set", although some equivalence classes are not sets but proper class
Proper may refer to:
Mathematics
* Proper map, in topology, a property of continuous function between topological spaces, if inverse images of compact subsets are compact
* Proper morphism, in algebraic geometry, an analogue of a proper map for ...
es. For example, "being
isomorphic
In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word is ...
" is an equivalence relation on
groups, and the equivalence classes, called
isomorphism classes, are not sets.
The set of all equivalence classes in
X with respect to an equivalence relation
R is denoted as
X / R, and is called
X modulo
In computing, the modulo operation returns the remainder or signed remainder of a division, after one number is divided by another (called the '' modulus'' of the operation).
Given two positive numbers and , modulo (often abbreviated as ) is t ...
R (or the of
X by
R). The
surjective map x \mapsto /math> from X onto X / R, which maps each element to its equivalence class, is called the , or the canonical projection.
Every element of an equivalence class characterizes the class, and may be used to ''represent'' it. When such an element is chosen, it is called a representative of the class. The choice of a representative in each class defines an injection from X / R to . Since its composition with the canonical surjection is the identity of X / R, such an injection is called a section, when using the terminology of category theory
Category theory is a general theory of mathematical structures and their relations that was introduced by Samuel Eilenberg and Saunders Mac Lane in the middle of the 20th century in their foundational work on algebraic topology. Nowadays, cate ...
.
Sometimes, there is a section that is more "natural" than the other ones. In this case, the representatives are called . For example, in
modular arithmetic, for every
integer greater than , the
congruence modulo is an equivalence relation on the integers, for which two integers and are equivalent—in this case, one says ''congruent'' —if divides
a-b; this is denoted
a\equiv b \pmod m. Each class contains a unique non-negative integer smaller than
m, and these integers are the canonical representatives.
The use of representatives for representing classes allows avoiding to consider explicitly classes as sets. In this case, the canonical surjection that maps an element to its class is replaced by the function that maps an element to the representative of its class. In the preceding example, this function is denoted
a \bmod m, and produces the remainder of the
Euclidean division of by .
Properties
Every element
x of
X is a member of the equivalence class
Every two equivalence classes
/math> and /math> are either equal or disjoint. Therefore, 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 comes from an equivalence relation in this way, according to which x \sim y if and only if x and y belong to the same set of the partition.
It follows from the properties of an equivalence relation that
x \sim y if and only if =
In other words, if \,\sim\, is an equivalence relation on a set X, and x and y are two elements of X, then these statements are equivalent:
* x \sim y
* = /math>
* \cap \ne \emptyset.
Graphical representation

An
undirected graph may be associated to any
symmetric relation
A symmetric relation is a type of binary relation. An example is the relation "is equal to", because if ''a'' = ''b'' is true then ''b'' = ''a'' is also true. Formally, a binary relation ''R'' over a set ''X'' is symmetric if:
:\forall a, b \in X( ...
on a set
X, where the vertices are the elements of
X, and two vertices
s and
t are joined if and only if
s \sim t. Among these graphs are the graphs of equivalence relations; they are characterized as the graphs such that the
connected components are
cliques.
[
]
Invariants
If \,\sim\, is an equivalence relation on X, and P(x) is a property of elements of X such that whenever x \sim y, P(x) is true if P(y) is true, then the property P is said to be an invariant
Invariant and invariance may refer to:
Computer science
* Invariant (computer science), an expression whose value doesn't change during program execution
** Loop invariant, a property of a program loop that is true before (and after) each iteratio ...
of \,\sim\,, or well-defined under the relation \,\sim.
A frequent particular case occurs when f is a function from X to another set Y; if f\left(x_1\right) = f\left(x_2\right) whenever x_1 \sim x_2, then f is said to be \,\sim\,, or simply \,\sim. This occurs, for example, in the character theory of finite groups. Some authors use "compatible with \,\sim\," or just "respects \,\sim\," instead of "invariant under \,\sim\,".
Any function f : X \to Y is ''class invariant under'' \,\sim\,, according to which x_1 \sim x_2 if and only if f\left(x_1\right) = f\left(x_2\right). The equivalence class of x is the set of all elements in X which get mapped to f(x), that is, the class /math> is the inverse image of f(x). This equivalence relation is known as the kernel of f.
More generally, a function may map equivalent arguments (under an equivalence relation \sim_X on X) to equivalent values (under an equivalence relation \sim_Y on Y). Such a function is a morphism
In mathematics, particularly in category theory, a morphism is a structure-preserving map from one mathematical structure to another one of the same type. The notion of morphism recurs in much of contemporary mathematics. In set theory, morphisms a ...
of sets equipped with an equivalence relation.
Quotient space in topology
In topology, a quotient space
Quotient space may refer to a quotient set when the sets under consideration are considered as spaces. In particular:
*Quotient space (topology), in case of topological spaces
* Quotient space (linear algebra), in case of vector spaces
*Quotient ...
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 relation
In abstract algebra, a congruence relation (or simply congruence) is an equivalence relation on an algebraic structure (such as a group, ring, or vector space) that is compatible with the structure in the sense that algebraic operations done wi ...
s 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
Quotient space may refer to a quotient set when the sets under consideration are considered as spaces. In particular:
*Quotient space (topology), in case of topological spaces
* Quotient space (linear algebra), in case of vector spaces
*Quotient ...
is a vector space formed by taking a quotient group
A quotient group or factor group is a mathematical group obtained by aggregating similar elements of a larger group using an equivalence relation that preserves some of the group structure (the rest of the structure is "factored" out). For examp ...
, 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 group
A quotient group or factor group is a mathematical group obtained by aggregating similar elements of a larger group using an equivalence relation that preserves some of the group structure (the rest of the structure is "factored" out). For examp ...
s, 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 X, either to an equivalence relation that induces some structure on the set of equivalence classes from a structure of the same kind on 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.
See also
* Equivalence partitioning, a method for devising test sets in software testing based on dividing the possible program inputs into equivalence classes according to the behavior of the program on those inputs
* Homogeneous space
In mathematics, particularly in the theories of Lie groups, algebraic groups and topological groups, a homogeneous space for a group ''G'' is a non-empty manifold or topological space ''X'' on which ''G'' acts transitively. The elements of ' ...
, the quotient space of Lie group
In mathematics, a Lie group (pronounced ) is a group that is also a differentiable manifold. A manifold is a space that locally resembles Euclidean space, whereas groups define the abstract concept of a binary operation along with the additio ...
s
*
*
*
*
Notes
References
*
*
*
*
Further reading
*
*
*
*
*
*
*
*
*
*
*
*
*
*
External links
*
{{Authority control
Algebra
Binary relations
Equivalence (mathematics)
Set theory