equivalence relation

An equivalence relation $\sim$ on a set $S$ is a relation that is:

Reflexive.: $a\sim a$ for all $a\in S$ .
Symmetric.: Whenever $a\sim b$ , then $b\sim a$ .
Transitive.: If $a\sim b$ and $b\sim c$ then $a\sim c$ .

If $a$ and $b$ are related this way we say that they are equivalent under $\sim$ . If $a\in S$ , then the set of all elements of $S$ that are equivalent to $a$ is called the equivalence class of $a$ . The set of all equivalence classes under $\sim$ is written $S/\sim$ .

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 space) by considering each equivalence class as a single unit.

Two examples of equivalence relations:

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

2. Take a group $(G,\cdot)$ and a subgroup $H$ . Define $a\sim b$ whenever $ab^{-1}\in H$ . 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