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).

Example

For the set \(A = \{1, 2, 3\}\), the relation \(R = \{(1, 1), (2, 2), (3, 3), (2,3), (3, 2)\}\) is an equivalence relation.

The relation \(R\) is reflexive because \((1, 1), (2, 2), (3, 3) \in R\).
The relation \(R\) is symmetric because \((2, 3), (3, 2) \in R\). \((1,2)\) and \((2,1)\) do not have to be in \(R\).
The relation \(R\) is transitive because \((2, 3), (3, 2) \in R\) and \((2, 2), (3, 3) \in R\).

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:

\[[a]_R = \{b \in A | a \equiv_R b\} \]

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\).

Example

For the set \(A = \{1, 2, 3\}\) and the equivalence relation \(R = \{(1, 1), (2, 2), (3, 3), (2,3), (3, 2)\}\), the equivalence classes are:

\([1]_R = \{1\}\)
\([2]_R = \{2, 3\}\)
\([3]_R = \{2, 3\}\)

As we can see, \([2]_R = [3]_R\) and \([1]_R \cap [2]_R = \emptyset\) and therefore the equivalence classes partition the set \(A\).

Equivalence Classes as Modulo

interesting but not really important