equivalence relation

Equivalence relation

$R\subseteq A\times A$ is an equivalence relation on $A$ if it is:

• reflexive, i.e. $\forall x\in A:xRx$ (every element is related to itself … a = a)
• symmetric, i.e. $\forall x,y\in A:xRy⟹yRx$
• transitive, i.e. $\forall x,y,z\in A:xRy\wedge yRz⟹xRz$

The relationship in the example above is not an equivalence relation (3 would need a self-loop and 1,3 would need to be connected symmetrically).

Equivalence relations

Let $A$ be any set, $xRy:⟺x=y$ → “Equality relation” on $A$ (the resulting set is the diagonal of the cartesian product).

Let $A$ be any set, $\forall x,y\in A:xRy$ → “Universal relation” on $A$ (the resulting set is the entire cartesian product).
The equality relation can also be though of as partitioning each different element into its own set, and the universal relation as a single set containing all elements.

Let $A=\mathbb{Z},m\in {\mathbb{Z}}^{+},aRb:⟺a\equiv b\mathrm{mod}m$
$\forall a\in \mathbb{Z}:a\equiv a\mathrm{mod}m$, since $m\mid \underset{0}{\underbrace{a-a}}$, since $\exists x\in \mathbb{Z},0=mx$ (reflexive: $✓$)
$\forall a,b\in \mathbb{Z}:a\equiv b\mathrm{mod}m⟹b\equiv a\mathrm{mod}m$
$a\equiv b\mathrm{mod}m⟺m\mid b-a⟺\exists x\in \mathbb{Z}:mx=b-a$
$⟹m(-x)=a-b⟺b\equiv a\mathrm{mod}m$ (symmetric: $✓$)
$\forall a,b,c\in \mathbb{Z}:a\equiv b\mathrm{mod}m,b\equiv c\mathrm{mod}m⟹\underset{\text{z.z.: }m\mid c-a}{\underbrace{a\equiv c\mathrm{mod}m}}$
$a\equiv \mathrm{mod}m⟺\exists x:mx=b-a$
$b\equiv c\mathrm{mod}m⟺\exists y:my=c-b$
$⟹m(x+y)=c-a$ (transitive $✓$)

Equivalence Relations ↔ Partitions

Every equivalence relation induces a partition and every partition induces an equivalence relation:

Equivalence Relation → Partition:
Given equivalence relation $R$ on $A$, the equivalence classes $[x{]}_R=\{y\in A\mid xRy\}$ form a partition. Properties of $R$ ensure partition properties: reflexivity means blocks are non-empty ($x\in [x{]}_R$), symmetry and transitivity ensure blocks are disjoint ($[x{]}_R=[y{]}_R$ or $[x{]}_R\cap [y{]}_R=\varnothing$), and together they guarantee blocks cover $A$ (${\bigcup }_{x\in A}[x{]}_R=A$).

Partition → Equivalence Relation:
Given partition $\{A_i\mid i\in I\}$ of $A$, define $xRy:⟺\exists i\in I:x,y\in A_i$. Partition properties ensure equivalence relation properties: non-empty blocks give reflexivity, disjoint blocks give symmetry, and covering gives transitivity.

Like sorting items into boxes: Each item goes in exactly one box (partition), and two items are related if they’re in the same box (equivalence relation).

Link to original