Course contentsShow
← Computer Science
Lesson 72 of 2,8722. Discrete Mathematics for CSFree lesson

Equivalence Relations

Define equivalence relations as reflexive, symmetric, and transitive; explore examples like equality and modular arithmetic.

Equivalence Relations

What you'll learn: You'll discover how certain special relations — called equivalence relations — organize sets into neat groups where elements behave "the same" in some way.

The Core Idea

An equivalence relation is a relation that satisfies three properties all at once:

  1. Reflexive: Every element relates to itself
  2. Symmetric: If a relates to b, then b relates to a
  3. Transitive: If a relates to b and b relates to c, then a relates to c

When a relation has all three properties, it creates natural "clusters" or groups of equivalent elements.

Classic Examples

Equality (=)

The simplest equivalence relation!

  • Reflexive: x = x ✓
  • Symmetric: If x = y, then y = x ✓
  • Transitive: If x = y and y = z, then x = z ✓

Modular Arithmetic

"Two integers are related if they have the same remainder when divided by 3."

For example, {1, 4, 7, 10, ...} all leave remainder 1 when divided by 3, so they're equivalent under "mod 3."

  • Reflexive: 7 mod 3 = 7 mod 3 ✓
  • Symmetric: If 4 ≡ 7 (mod 3), then 7 ≡ 4 (mod 3) ✓
  • Transitive: If 1 ≡ 4 (mod 3) and 4 ≡ 7 (mod 3), then 1 ≡ 7 (mod 3) ✓

Why It Matters

Equivalence relations partition a set into disjoint groups called equivalence classes. Elements in the same class are interchangeable for whatever property you care about — this underpins concepts like data classification, hashing, and program equivalence.

Key Takeaway: An equivalence relation is reflexive, symmetric, AND transitive — it groups elements that are "the same" in a well-defined way, like equality or sharing a remainder.