Equivalence Relations

Definition

A relation is an equivalence relation iff it is reflexive, symmetric and transitive. $\sim$ is commonly used to denote an equivalence relation (it replaces $R$ in $aRb$, so $a\sim b$) This is the same as a partition, but from a different perspective

Equivalence Class

The equivalence class of an element is the component of the partition that contains the element e.g. Partition $\mathcal{C}=\{\{1,2,3\},\{4\}\}$, the equivalence class of $1$, denoted $[1]$ is $\{1,2,3\}$ Formally, Suppose $A$ is a set and $\sim$ is an equivalence relation on $A$. For each $a\in A$, the equivalence class of $a$, denoted $[a]$, called the class of $a$ for short, is the set of all elements $x\in A$ such that $a$ is $\sim$-related to $x$. Symbolically, $[a{]}_{\sim }=\{x\in A:a\sim x\}$

Lemma Rel.1 Equivalence Classes

Let $\sim$ be a equivalence relation on a set $A$. The following are equivalent for all $x,y\in A$.

• $x\sim y$
• $[x]=[y]$
• $[x]\cap [y]\ne \varnothing$

Set of equivalence classes

For set $A$ and equivalence relation $\sim$ on $A$, the set of all equivalence classes with respect to $\sim$ is denoted $A/\sim$ (“the quotient of $A$ by $\sim$“) $A/\sim =\{[x{]}_{\sim }:x\in A\}$ This is a partition of $A$ (Theorem Rel.2)

Theorem Rel.2

Equivalence classes form a partition Let $\sim$ be an equivalence relation on set $A$, then $A/\sim$ is a partition of $A$

Common Example

Congruence Relations are examples of equivalence relations.