Equivalence Relation

Overview

A binary relation $R$ on set $A$ is an equivalence relation on $A$ iff it is reflexive on $A$ , symmetric, and transitive. In other words, an equivalence relation is a symmetric preorder.

An equivalence relation is usually denoted with the $\sim$ symbol.

Equivalence Classes

The set $[x]_{R}$ is defined by $[x]_{R} = {t ∣ x R t}$ . If $R$ is an equivalence relation and $x \in fld R$ , then $[x]_{R}$ is called the equivalence class of $x$ (modulo $R$ ). If the relation $R$ is fixed by the context, we just write $[x]$ .

Partitions

A partition $Π$ of a set $A$ is a set of nonempty subsets of $A$ that is disjoint and exhaustive.

If $Π$ is a partition of set $A$ , then the following relation $R$ is an equivalence relation:

x R y ⟺ (\exists B \in Π, x \in B \land y \in B)

Quotient Sets

If $R$ is an equivalence relation on $A$ , then the quotient set " $A$ modulo $R$ " is defined as

A / R = {[x]_{R} ∣ x \in A} .

The canonical map (or natural map) $ϕ : A \to A / R$ is given by $ϕ (x) = [x]_{R}$ . Note that $A / R$ , the set of all equivalence classes, is a partition of $A$ .

Equivalence Kernel

Let $F : A \to B$ . Define equivalence relation $\sim$ as

x \sim y ⟺ f (x) = f (y)

Relation $\sim$ is called the (equivalence) kernel of $f$ . The partition induced by $\sim$ on $A$ is called the coimage of $f$ (denoted $coim f$ ).

The fiber of an element $y$ under $F$ is $F^{- 1} [[{y}]]$ , i.e. the preimage of singleton set ${y}$ . Therefore the fibers of elements $y \in F [[A]]$ under $F$ are the equivalence classes of $\sim$ .