---
title: "Explain equivalence relation"
subject: "Theory of Computation"
chapter: 1
key: "semester_3/theory_of_computation:equivalence-relation-explain"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/equivalence-relation-explain
site: BCT Engineering
---

# Explain equivalence relation

Theory of Computation · Chapter 1: Introduction

- Asked in: 2072 Kartik
- Video: [Equivalence Relation in Discrete Mathematics with examples](https://www.youtube.com/watch?v=VkWGSqRGozw) — Gate Smashers
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/equivalence-relation-explain
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-1

## Question

Explain what an equivalence relation is.

## Short answer

An equivalence relation on a set is a binary relation that is reflexive, symmetric, and transitive. For example, congruence modulo 3 on integers. It partitions the set into disjoint equivalence classes, used in minimizing DFAs.

## Answer

A relation R on a set A (R ⊆ A × A) is an **equivalence relation** if it has all three properties:

1. **Reflexive:** (a, a) ∈ R for every a ∈ A.
2. **Symmetric:** if (a, b) ∈ R then (b, a) ∈ R.
3. **Transitive:** if (a, b) ∈ R and (b, c) ∈ R then (a, c) ∈ R.

**Example.** On the integers, a ≡ b (mod 3), meaning 3 divides a − b.
- Reflexive: a − a = 0 is divisible by 3.
- Symmetric: if 3 | (a − b) then 3 | (b − a).
- Transitive: if 3 | (a − b) and 3 | (b − c), then 3 | (a − c) because a − c = (a − b) + (b − c).

**Non-example.** "a ≤ b" on integers is reflexive and transitive but not symmetric. "a is a friend of b" is usually not transitive.

**Equivalence classes.** For a ∈ A, [a] = { b : (a, b) ∈ R }. An equivalence relation splits A into disjoint classes whose union is A (a **partition**). For mod 3 the classes are [0], [1], [2]:

```text
[0] = {..., −3, 0, 3, 6, ...}
[1] = {..., −2, 1, 4, 7, ...}
[2] = {..., −1, 2, 5, 8, ...}
```

**Use in this subject.** Equivalence of DFA states (indistinguishability) is an equivalence relation. Its classes become the states of the minimal DFA.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. Which set of properties defines an equivalence relation?
   A. Reflexive, antisymmetric and transitive
   B. Reflexive, symmetric and antisymmetric
   C. Reflexive, symmetric and transitive
   D. Symmetric, transitive and total
   Answer: C. All three of reflexive, symmetric and transitive must hold. (Key point: Three properties)

2. How is transitivity of a ≡ b (mod 3) shown?
   A. a − a = 0 is divisible by 3
   B. a − c = (a − b)(b − c)
   C. b − a = −(a − b)
   D. a − c = (a − b) + (b − c), a sum of multiples of 3
   Answer: D. The sum of two multiples of 3 is a multiple of 3. (Key point: Mod 3 transitivity)

3. Why is 'a ≤ b' on integers not an equivalence relation?
   A. It is not reflexive
   B. It is not defined on integers
   C. It is not transitive
   D. It is not symmetric
   Answer: D. a ≤ b does not imply b ≤ a. (Key point: Non-example)

4. What do equivalence classes do to the set A?
   A. Merge A into one element
   B. Leave some elements uncovered
   C. Partition it into disjoint classes whose union is A
   D. Overlap and cover A twice
   Answer: C. Classes are disjoint and cover A; mod 3 gives [0], [1], [2]. (Key point: Equivalence classes)