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

Equivalence Classes and Partitions

Define equivalence classes; prove that equivalence relations partition sets into disjoint classes.

Equivalence Classes and Partitions

You'll learn: How equivalence relations naturally organize sets into non-overlapping groups called equivalence classes.

What Is an Equivalence Class?

An equivalence class is the set of all elements related to a particular element by an equivalence relation. If you have an equivalence relation R on set A, and pick any element a in A, its equivalence class [a] contains every element that's related to a.

In notation: [a] = {x ∈ A | x R a}

Think of it like organizing people: if the relation is "born in the same month," then [Alice] would be all people born in Alice's birth month.

Equivalence Classes Partition Sets

Here's the powerful theorem: Every equivalence relation partitions a set into disjoint equivalence classes.

What does this mean?

  1. Every element belongs to exactly one equivalence class (no element left out)
  2. Equivalence classes never overlap (if two classes share any element, they're actually the same class)
  3. The union of all equivalence classes equals the original set

Simple Proof Sketch

  • Reflexivity ensures every element is in some class (at minimum, its own)
  • Symmetry means if a is in [b], then b is in [a] — they share the same class
  • Transitivity ensures classes are "complete" — if a relates to b and b relates to c, then a and c are in the same class

This creates perfectly separated groups, like sorting students by graduation year — every student has exactly one graduation year, and those groups don't overlap.

Key Takeaway: Equivalence relations divide sets into non-overlapping equivalence classes that completely cover the original set, creating a partition — a fundamental organizing principle in mathematics and computer science.