Equivalence Relations

A relation $R$ is an equivalence relation if it is reflex, symmetric and transitive. To show that the relation $R$ is an equivalence relation, we can write instead of $aRb$, $a \equiv b$ or $a \sim b$ if the relation is clear and $a$ is related to $b$. If the relation is not clear, we can write $a \equiv_R b$ or $a \sim_R b$.

Therefore we know that a relation $R$ is an equivalence relation if it satisfies the following properties:

• $\forall a \in A, a \equiv_R a$ (reflexive)
• $\forall a, b \in A, a \equiv_R b \implies b \equiv_R a$ (symmetric)
• $\forall a, b, c \in A, a \equiv_R b \land b \equiv_R c \implies a \equiv_R c$ (transitive)

This makes sense if we think of we compare it to our normal understandin of "equivalence":

• We say that two things that are the same are equivalent to each other (reflexive).
• If something is equivalent to something else, then that something else is equivalent to the first thing (symmetric).
• If something is equivalent to something else, and that something else is equivalent to another thing, then the first thing is equivalent to the other thing (transitive).

Equivalence Classes

Given an equivalence relation $R$ on a set $A$, the equivalence class is a subset of $A$ that contains all the elements that are equivalent to a given element $a \in A$. The equivalence class of $a$ is denoted by $[a]$ if the relation is clear, or $[a]_R$ if the relation is not clear. More formally, the equivalence class of $a$ is defined as:

Because of the reflexive, symmetric and transitive properties of the equivalence relation, the equivalence classes partition the set $A$ into subsets that must either be equal or disjoint. So for any elements $a, b \in A$:

• If $a \equiv_R b$, then $[a]_R = [b]_R$
• Or if $a \not\equiv_R b$, then $[a]_R \cap [b]_R = \emptyset$.

Equivalence Classes as Modulo

interesting but not really important