Equivalence Relation

 

What Is an Equivalence Relation?

Let $A$ be a set.
A relation $\sim$ on $A$ is called an equivalence relation if it satisfies three properties:

1. Reflexive

For every $a \in A$,

$$a \sim a$$

2. Symmetric

For all $a, b \in A$,

$$a \sim b \Rightarrow b \sim a$$

3. Transitive

For all $a, b, c \in A$,

$$a \sim b \text{ and } b \sim c \Rightarrow a \sim c$$

---

Why Equivalence Relations Are Important

Equivalence relations allow us to:

• Group elements into equivalence classes

• Treat different objects as “essentially the same”

• Build structures like modular arithmetic, finite fields, and quotient sets

---

Congruence Modulo $n$

Let $n \in \mathbb{Z}, n > 0$.
For integers $a$ and $b$, we say:

$$a \equiv b \pmod{n}$$

if and only if:

$$n \mid (a - b)$$

That is, $a - b$ is divisible by $n$.

---

Claim

Congruence modulo $n$ is an equivalence relation on $\mathbb{Z}$.

We prove this by verifying the three properties.

---

1. Reflexive Property

We must show:

$$a \equiv a \pmod{n}$$

Proof

$$a - a = 0$$

Since $n \mid 0$ for all $n$,

$$a \equiv a \pmod{n}$$

✅ Reflexive

---

2. Symmetric Property

Assume:

$$a \equiv b \pmod{n}$$

Then:

$$n \mid (a - b)$$

This implies:

$$n \mid -(a - b) = (b - a)$$

Hence:

$$b \equiv a \pmod{n}$$

✅ Symmetric

---

3. Transitive Property

Assume:

$$a \equiv b \pmod{n} \quad \text{and} \quad b \equiv c \pmod{n}$$

Then:

$$n \mid (a - b) \quad \text{and} \quad n \mid (b - c)$$

Adding:

$$(a - b) + (b - c) = a - c$$

So:

$$n \mid (a - c)$$

Hence:

$$a \equiv c \pmod{n}$$

✅ Transitive

---

Conclusion

Since congruence modulo $n$ is reflexive, symmetric, and transitive, it is an equivalence relation on $\mathbb{Z}$.

---

Example: Congruence Modulo 5

Consider integers:

$$7, 12, 17, 22$$

Each satisfies:

$$7 \equiv 12 \equiv 17 \equiv 22 \pmod{5}$$

because all differ by multiples of 5.

---

Equivalence Classes Modulo 5

The equivalence class of an integer $a$ is:

$$[a] = \{ x \in \mathbb{Z} \mid x \equiv a \pmod{5} \}$$

Example

$$[2] = \{ \dots, -8, -3, 2, 7, 12, 17, \dots \}$$

There are exactly 5 equivalence classes modulo 5:

$$[0], [1], [2], [3], [4]$$

---

Why This Matters in Number Theory

Congruence equivalence classes form:

• The ring $\mathbb{Z}_n$

• The foundation of modular arithmetic

• The basis for finite fields (when $n$ is prime)