Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Equivalence relation
Summary
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 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 they belong to the same equivalence class.
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 "a ≡ b", which are used when is implicit, and variations of "", "a ≡R b", or "" to specify explicitly. Non-equivalence may be written "a ≁ b" or "".
A binary relation on a set is said to be an equivalence relation, if and only if it is reflexive, symmetric and transitive. That is, for all and in
(reflexivity).
if and only if (symmetry).
If and then (transitivity).
together with the relation is called a setoid. The equivalence class of under denoted is defined as
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 . 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 on .)
(symmetry).
(transitivity).
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 .
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 triangles.
"Is congruent to" on the set of all triangles.
Given a natural number , "is congruent to, modulo " on the integers.
Given a function , "has the same under as" on the elements of 's domain .
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Related publications (60)