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 ...
, an equivalence relation is a
binary relation that is
reflexive,
symmetric and
transitive. The
equipollence
In mathematics, two sets or classes ''A'' and ''B'' are equinumerous if there exists a one-to-one correspondence (or bijection) between them, that is, if there exists a function from ''A'' to ''B'' such that for every element ''y'' of ''B'', t ...
relation between line segments in geometry is a common example of an equivalence relation.
Each equivalence relation provides a
partition of the underlying set into disjoint
equivalence classes. Two elements of the given set are equivalent to each other
if and only if
In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false.
The connective is bic ...
they belong to the same equivalence class.
Notation
Various notations are used in the literature to denote that two elements
and
of a set are equivalent with respect to an equivalence relation
the most common are "
" and "", which are used when
is implicit, and variations of "
", "", or "
" to specify
explicitly. Non-equivalence may be written "" or "
".
Definition
A
binary relation on a set
is said to be an equivalence relation,
if and only if
In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false.
The connective is bic ...
it is reflexive, symmetric and transitive. That is, for all
and
in
*
(
reflexivity).
*
if and only if
(
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 definiti ...
).
* If
and
then
(
transitivity).
together with the relation
is called a
setoid. The
equivalence class of
under
denoted
is defined as
Alternative definition using relational algebra
In
relational algebra, if
and
are relations, then the
composite relation is defined so that
if and only if there is a
such that
and
.
[Sometimes the composition is instead written as , or as ; in both cases, is the first relation that is applied. See the article on Composition of relations for more information.] This definition is a generalisation of the definition of
functional composition. The defining properties of an equivalence relation
on a set
can then be reformulated as follows:
*
. (
reflexivity). (Here,
denotes the
identity function
Graph of the identity function on the real numbers
In mathematics, an identity function, also called an identity relation, identity map or identity transformation, is a function that always returns the value that was used as its argument, un ...
on
.)
*
(
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 definiti ...
).
*
(
transitivity).
Examples
Simple example
On the set
, the relation
is an equivalence relation. The following sets are equivalence classes of this relation:
The set of all equivalence classes for
is
This set is a
partition of the set
with respect to
.
Equivalence relations
The following relations are all equivalence relations:
* "Is equal to" on the set of numbers. For example,
is equal to
* "Has the same birthday as" on the set of all people.
* "Is
similar to" on the set of all
triangle
A triangle is a polygon with three edges and three vertices. It is one of the basic shapes in geometry. A triangle with vertices ''A'', ''B'', and ''C'' is denoted \triangle ABC.
In Euclidean geometry, any three points, when non- colline ...
s.
* "Is
congruent to" on the set of all
triangle
A triangle is a polygon with three edges and three vertices. It is one of the basic shapes in geometry. A triangle with vertices ''A'', ''B'', and ''C'' is denoted \triangle ABC.
In Euclidean geometry, any three points, when non- colline ...
s.
* Given a natural number
, "is congruent to,
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 ...
" on the
integers.
* Given a
function , "has the same
image
An image is a visual representation of something. It can be two-dimensional, three-dimensional, or somehow otherwise feed into the visual system to convey information. An image can be an artifact, such as a photograph or other two-dimensio ...
under
as" on the elements of
's
domain
Domain may refer to:
Mathematics
*Domain of a function, the set of input values for which the (total) function is defined
** Domain of definition of a partial function
** Natural domain of a partial function
**Domain of holomorphy of a function
* ...
. For example,
and
have the same image under
, viz.
.
* "Has the same absolute value as" on the set of real numbers
* "Has the same cosine as" on the set of all angles.
Relations that are not equivalences
* The relation "≥" between real numbers is reflexive and transitive, but not symmetric. For example, 7 ≥ 5 but not 5 ≥ 7.
* The relation "has a
common factor
In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers ''x'', ''y'', the greatest common divisor of ''x'' and ''y'' is ...
greater than 1 with" between
natural numbers greater than 1, is reflexive and symmetric, but not transitive. For example, the natural numbers 2 and 6 have a common factor greater than 1, and 6 and 3 have a common factor greater than 1, but 2 and 3 do not have a common factor greater than 1.
* The
empty relation
In mathematics, a homogeneous relation (also called endorelation) over a set ''X'' is a binary relation over ''X'' and itself, i.e. it is a subset of the Cartesian product . This is commonly phrased as "a relation on ''X''" or "a (binary) relation ...
''R'' (defined so that ''aRb'' is never true) on a set ''X'' is
vacuously symmetric and transitive; however, it is not reflexive (unless ''X'' itself is empty).
* The relation "is approximately equal to" between real numbers, even if more precisely defined, is not an equivalence relation, because although reflexive and symmetric, it is not transitive, since multiple small changes can accumulate to become a big change. However, if the approximation is defined asymptotically, for example by saying that two functions ''f'' and ''g'' are approximately equal near some point if the limit of ''f − g'' is 0 at that point, then this defines an equivalence relation.
Connections to other relations
*A
partial order
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary ...
is a relation that is reflexive, , and transitive.
*
Equality is both an equivalence relation and a partial order. Equality is also the only relation on a set that is reflexive, symmetric and antisymmetric. In
algebraic expression In mathematics, an algebraic expression is an expression built up from integer constants, variables, and the algebraic operations (addition, subtraction, multiplication, division and exponentiation by an exponent that is a rational number). ...
s, equal variables may be
substituted
A substitution reaction (also known as single displacement reaction or single substitution reaction) is a chemical reaction during which one functional group in a chemical compound is replaced by another functional group. Substitution reactions ar ...
for one another, a facility that is not available for equivalence related variables. The equivalence classes of an equivalence relation can substitute for one another, but not individuals within a class.
*A
strict partial order is irreflexive, transitive, and
asymmetric.
*A
partial equivalence relation
In mathematics, a partial equivalence relation (often abbreviated as PER, in older literature also called restricted equivalence relation) is a homogeneous binary relation that is symmetric and transitive. If the relation is also reflexive, the ...
is transitive and symmetric. Such a relation is reflexive
if and only if
In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false.
The connective is bic ...
it is
total, that is, if for all
there exists some
[''If:'' Given let hold using totality, then by symmetry, hence by transitivity. — ''Only if:'' Given choose then by reflexivity.] Therefore, an equivalence relation may be alternatively defined as a symmetric, transitive, and total relation.
*A
ternary equivalence relation In mathematics, a ternary equivalence relation is a kind of ternary relation analogous to a binary equivalence relation. A ternary equivalence relation is symmetric, reflexive, and transitive. The classic example is the relation of collinearity a ...
is a ternary analogue to the usual (binary) equivalence relation.
*A reflexive and symmetric relation is a
dependency relation (if finite), and a
tolerance relation if infinite.
*A
preorder is reflexive and transitive.
*A
congruence relation is an equivalence relation whose domain
is also the underlying set for an
algebraic structure, and which respects the additional structure. In general, congruence relations play the role of
kernels of homomorphisms, and the quotient of a structure by a congruence relation can be formed. In many important cases, congruence relations have an alternative representation as substructures of the structure on which they are defined (e.g., the congruence relations on groups correspond to the
normal subgroups).
*Any equivalence relation is the negation of an
apartness relation, though the converse statement only holds in
classical mathematics (as opposed to
constructive mathematics), since it is equivalent to the
law of excluded middle.
*Each relation that is both reflexive and left (or right)
Euclidean is also an equivalence relation.
Well-definedness under an equivalence relation
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
well-defined or a under the relation
A frequent particular case occurs when
is a function from
to another set
if
implies
then
is said to be a for
a
or simply
This occurs, e.g. in the character theory of finite groups. The latter case with the function
can be expressed by a commutative triangle. See also
invariant. Some authors use "compatible with
" or just "respects
" instead of "invariant under
".
More generally, a function may map equivalent arguments (under an equivalence relation
) to equivalent values (under an equivalence relation
). Such a function is known as a morphism from
to
Equivalence class, quotient set, partition
Let
Some definitions:
Equivalence class
A subset ''Y'' of ''X'' such that
holds for all ''a'' and ''b'' in ''Y'', and never for ''a'' in ''Y'' and ''b'' outside ''Y'', is called an equivalence class of ''X'' by ~. Let
denote the equivalence class to which ''a'' belongs. All elements of ''X'' equivalent to each other are also elements of the same equivalence class.
Quotient set
The set of all equivalence classes of ''X'' by ~, denoted
is the quotient set of ''X'' by ~. If ''X'' is a
topological space
In mathematics, a topological space is, roughly speaking, a geometrical space in which closeness is defined but cannot necessarily be measured by a numeric distance. More specifically, a topological space is a set whose elements are called poin ...
, there is a natural way of transforming
into a topological space; see
quotient space for the details.
Projection
The projection of
is the function
defined by