Course contentsShow
← Mathematics
Lesson 2556 of 3,12151. Discrete Math — Sets, Relations, FunctionsFree lesson

Partitions Induce Equivalence Relations

Show that every partition of a set naturally defines an equivalence relation on that set.

Partitions Induce Equivalence Relations

What You'll Learn

You'll discover how every partition of a set automatically creates an equivalence relation on that set—the reverse direction of what we proved in the previous lesson.

The Core Idea

In the last lesson, we saw that every equivalence relation creates a partition. Now we prove the converse: given any partition of a set, we can define an equivalence relation that naturally arises from it.

Here's how it works: Suppose you have a partition P of a set S (remember, a partition divides S into non-empty, non-overlapping subsets that cover all of S). We define a relation R by saying:

"Two elements a and b are related if and only if they belong to the same block of the partition."

Formally: a R b ⟺ ∃ B ∈ P such that a ∈ B and b ∈ B.

Why This Is an Equivalence Relation

We must verify three properties:

  1. Reflexive: Every element a lives in exactly one block of the partition, so a is in the same block as itself. Thus a R a.

  2. Symmetric: If a R b, then a and b are in the same block B. Since being in the same block works both ways, b and a are also in the same block. Thus b R a.

  3. Transitive: If a R b and b R c, then a and b share a block, and b and c share a block. Since each element belongs to exactly one block and b connects them, all three must be in the same block. Thus a R c.

Analogy: Think of a partition as dividing students into classrooms. The relation "is in the same classroom as" is automatically reflexive (you're in your own classroom), symmetric (if you share a classroom with me, I share one with you), and transitive (if we're both in the same classroom as a third person, we're all together).

Key Takeaway: Every partition of a set naturally induces an equivalence relation where elements are related exactly when they belong to the same part of the partition.