Equivalence Relation

Definition

An equivalence relation has the three properties: reflexivity, symmetry and transitivity

Example

Equality is an equivalence relation

Example

congruence is an equivalence relation

Proposition

For all integers , , and , we have

Proof

Let be an arbitrary integer
Since and , the definition of congruence gives
Let and be arbitrary integers, and assume that
We have , so for some integer , .
Now, , so we have , and the definition of congruence gives
Let , , and be arbitrary integers, and assume that and
We have and .
By DIC, we have , so , and the definition of congruence gives