Explain equivalence relation

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]:

[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.