equivalence relation


An equivalence relationMathworldPlanetmath on a set S is a relationMathworldPlanetmathPlanetmath that is:

ReflexiveMathworldPlanetmathPlanetmath.

aa for all aS.

Symmetric.

Whenever ab, then ba.

TransitiveMathworldPlanetmathPlanetmathPlanetmathPlanetmath.

If ab and bc then ac.

If a and b are related this way we say that they are equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath under . If aS, then the set of all elements of S that are equivalent to a is called the equivalence classMathworldPlanetmath of a. The set of all equivalence classes under is written S/.

An equivalence relation on a set induces a partition on it. Conversely, any partition induces an equivalence relation. Equivalence relations are important, because often the set S can be ’transformed’ into another set (quotient spaceMathworldPlanetmath) by considering each equivalence class as a single unit.

Two examples of equivalence relations:

1. Consider the set of integers and take a positive integer m. Then m induces an equivalence relation by ab when m divides b-a (that is, a and b leave the same remainder when divided by m).

2. Take a group (G,) and a subgroupMathworldPlanetmathPlanetmath H. Define ab whenever ab-1H. That defines an equivalence relation. Here equivalence classes are called cosets.

Title equivalence relation
Canonical name EquivalenceRelation
Date of creation 2013-03-22 11:48:27
Last modified on 2013-03-22 11:48:27
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 15
Author CWoo (3771)
Entry type Definition
Classification msc 06-00
Classification msc 03D20
Related topic QuotientGroup
Related topic EquivalenceClass
Related topic Equivalent
Related topic EquivalenceRelation
Related topic Partition
Related topic MathbbZ_n
Defines equivalent
Defines equivalence class