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

Here’s a detailed and easy-to-understand explanation of Equivalence Relation from Discrete Mathematics – Part 10, especially useful for Computer Science, Engineering, or GATE aspirants:

Part 10 – Discrete Mathematics for Computer Science

Equivalence Relation and Its Use

Definition:

A relation R on a set A is called an Equivalence Relation if it satisfies all three properties:

1. Reflexive – Every element is related to itself.

   (a, a) ∈ R for all a ∈ A

2. Symmetric – If a is related to b, then b is related to a.

   (a, b) ∈ R ⇒ (b, a) ∈ R

3. Transitive – If a is related to b and b to c, then a is related to c.

   (a, b) ∈ R and (b, c) ∈ R ⇒ (a, c) ∈ R

Example:

Let A = {1, 2, 3, 4}
Define R on A as: R = { (1,1), (2,2), (3,3), (4,4), (1,2), (2,1) }

• Reflexive? All (a, a) are present

• Symmetric? (1,2) & (2,1) both present

• Transitive? No (1,2), (2,1) ⇒ (1,1) is there, but no (1,1), (1,2) ⇒ (2,2)? Not always

So, R is NOT an equivalence relation.

Correct Example (Equivalence):

Let A = {1, 2, 3}
Define R = { (1,1), (2,2), (3,3), (1,2), (2,1) }

Add (1,2), (2,3), (1,3), (3,1), (2,1), (3,2), etc.
If for all combinations:

• Reflexive holds

• Symmetric holds

• Transitive holds
  Then R is an equivalence relation.

Real-life Analogy:

• “Is equal to” ( = ) is an equivalence relation

• “Has same birthday as” – Reflexive (you share your own birthday), Symmetric (if A has B’s birthday, B has A’s), Transitive (if A and B, B and C → A and C)

Use of Equivalence Relations in Computer Science:

Equivalence Classes:

If R is an equivalence relation on A and a ∈ A, then:

[a] = { x ∈ A | (a, x) ∈ R } is the equivalence class of a.

Example:
In mod 3:
A = {0, 1, 2, 3, 4, 5}
Then
[0] = {0, 3}
[1] = {1, 4}
[2] = {2, 5}

Important Tips for Exams:

• Always check all three properties.

• Know how to form equivalence classes.

• Understand how equivalence partitions a set into disjoint subsets.

Would you like:

• Practice problems with solutions?

• Visual diagrams (like Venn or Hasse for equivalence classes)?

• A PDF summary or worksheet?

Let me know! I’m here to help you master this topic

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

Discrete Mathematics – (Relations)