Equivalence Relation

A binary relation $\sim$ on a set $X$ is said to be an equivalence relation, if and only if it is reflexive, symmetric and transitive. That is, for all $a,b$ and $c$ in $X$:

• $a\sim a$ (reflexivity)
• $a\sim b⟺b\sim a$ (symmetry)
• $(a\sim b)\wedge (b\sim c)⟹a\sim c$ (transitivity)

Two elements $a$ and $b$ that are related by an equivalence relation are called equivalent.

Equivalence Classes

Let $R$ be an equivalence relation on a set $A$. The set of all elements that are related to an element $a$ of $A$ is called the equivalence class of $a$. The equivalence class of $a$ with respect to $R$ is denoted by $[a{]}_R$. When only one relation is under consideration, we can delete the subscript $R$ and write $[a]$ for this equivalence class.

Let $R$ be an equivalence relation on a set $A$. These statements for elements $a$ and $b$ of $A$ are equivalent

1. $aRb$
2. $[a]=[b]$
3. $[a]\cap [b]\ne \varnothing$

Let $R$ be an equivalence relation on a set $S$. Then the equivalence classes of $R$ form a partition of $S$. Conversely, given a partition $\{A_i\mid i\in I\}$ of the set $S$, there is an equivalence relation $R$ that has the sets $A_i$, $i\in I$, as its equivalence classes.

Example

For example, we can give a partition of the integers by the equivalence relation congruence modulo