Part 10 – Discrete mathematics for computer science – Equivalence relation and it’s use.

Part 10 – Discrete mathematics for computer science – Equivalence relation and it’s use.

Equivalence Relation in Discrete Mathematics

An equivalence relation is a relation that satisfies three key properties:

1. Reflexivity: $aRa$ for all $a$ in set $A$.
2. Symmetry: If $aRb$, then $bRa$.
3. Transitivity: If $aRb$ and $bRc$, then $aRc$.

Example of Equivalence Relation

Consider a relation $R$ on a set of integers where $aRb$ if $a\equiv b\mathrm{mod}3$. This means that two numbers are related if they have the same remainder when divided by 3.

 Reflexive: $a\equiv a\mathrm{mod}3$ (always true)
 Symmetric: If $a\equiv b\mathrm{mod}3$, then $b\equiv a\mathrm{mod}3$
 Transitive: If $a\equiv b\mathrm{mod}3$ and $b\equiv c\mathrm{mod}3$, then $a\equiv c\mathrm{mod}3$

Use of Equivalence Relations

1. Partitioning a Set – Equivalence relations divide a set into disjoint equivalence classes.
2. Modular Arithmetic – Used in cryptography and computer science.
3. Graph Theory – Helps in clustering similar nodes.
4. State Reduction in Automata – Used in minimizing finite automata.

Would you like some practice problems or examples on equivalence relations?

Part 10 – Discrete mathematics for computer science – Equivalence relation and it’s use.

Notes on Discrete Mathematics