# Equivalence relation

<https://en.wikipedia.org/wiki/Equivalence_relation>

> An **equivalence relation** is a binary relation that is at the same time reflexive, symmetric and transitive.

A given binary relation $$\sim$$ on a set $$X$$ is said to be an equivalence relation iff it is reflexive, symmetric and transitive.

That is, $$\forall a, b, c \in X$$:

* reflexivity: $$\forall a : a \sim a$$
* symmetry: $$\forall a,b : (a \sim b) \to (b \sim a)$$
* transitivity, $$\forall a,b,c :(a \sim b \land b \sim c) \to (a \sim c)$$

A set $$X$$ together with the relation $$\sim$$ is called a *setoid*.

As a consequence of these 3 properties an equivalence relation provides a *partition* of a set into *equivalence classes*. Two elements of the given set are equivalent to each other iff they belong to the same equivalence class.

The *equivalence class* of $$a$$ under $$\sim$$, denoted $$\[a]$$, is defined as: $$\[a] = {b \in X | a \sim b }$$. For example, if $$X$$ is the set of all cars, and $$\sim$$ is the equivalence relation *has-the-same-color-as*, then one particular *equivalence class* consists of all green cars.

## The relation is-equal-to

The relation *is-equal-to* (=), is the canonical example of an equivalence relation, where $$\forall a, b, c$$:

* reflexivity: $$a = a$$
* symmetry: if $$a = b$$ then $$b = a$$
* transitivity: if $$a = b$$ and $$b = c$$ then $$a = c$$

## Example #1

The relation $$R$$ is defined by the set of the ordered pairs,\
$$R={(1,1),(2,2),(3,3),(1,2),(2,1),(2,3),(3,2),(1,3),(3,1)}$$,\
on the set $$A={1,2,3}$$.\
Is $$R$$ an equivalence relation?

Reflexivity:

* $$a \sim a$$
* it needs to have 3 ordered pairs $$(x,x)$$ to be reflexive, which it does:
* $${(1,1),(2,2),(3,3)}$$

Symmetry:

* if $$a \sim b$$ then $$b \sim a$$
* if it has a pair $$(x,y)$$ then it must also have a pair $$(x,y)$$
* $${(1,2),(2,1)}$$
* $${(2,3),(3,2)}$$
* $${(1,3),(3,1)}$$

Transitivity:

* if $$a \sim b$$ and $$b \sim c$$ then $$a \sim c$$
* if there's a pair $$(x,y)$$ and $$(y,z)$$ then there must be $$(x,z)$$
* if $${(1,2),(2,3)}$$ then $${(1,3)}$$: it does have it

All 3 properties hold so $$R$$ an equivalence relation.