Skip to content
Tutorials Center
My learning

Topics

Lesson 21 of 37 ยท Sets, Relations and Functions

Equivalence Relations and Partitions

See how equivalence relations split a set into classes, why they match partitions exactly, and build modular arithmetic and union-find in runnable Python.

When you say two things are "the same in some respect", you are using an equivalence relation. Two fractions 1/2 and 2/4 are equal as numbers, two integers can have the same remainder mod 5, and two files can have identical contents. An equivalence relation on A is a relation that is reflexive, symmetric and transitive (see relations and their properties). The symbol ~ is common: a ~ b.

The big idea of this lesson: an equivalence relation and a partition of the set are two descriptions of the same thing.

Equivalence classes

For a โˆˆ A, the equivalence class of a is [a] = {x โˆˆ A : x ~ a}: everything equivalent to a. Three facts follow from the three properties:

  1. a โˆˆ [a] (reflexive), so no class is empty.
  2. a ~ b if and only if [a] = [b].
  3. Two classes are either equal or disjoint.

A partition of A is a family of nonempty, pairwise disjoint subsets whose union is A. Facts 1 to 3 say the classes form a partition. Conversely, given any partition, define a ~ b when a and b lie in the same block; this is an equivalence relation. The two constructions undo each other.

flowchart TB
    R["Equivalence relation ~"] -->|"group equivalent elements"| P["Partition into classes"]
    P -->|"a ~ b iff same block"| R

Relations and partitions are two views of one structure.

Python Equivalence classes of congruence mod 3

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Quotient sets and modular arithmetic

The set of all classes is the quotient set A/~. For congruence mod n on the integers, โ„ค/nโ„ค has exactly n classes [0], โ€ฆ, [nโˆ’1]. You can add classes by adding representatives: [a] + [b] = [a + b]. This is well defined because choosing a different representative of a class (say a + n instead of a) gives the same class again. Well-definedness checks are the standard proof obligation whenever you define something on classes.

Python Well-defined addition on residues

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Building the finest equivalence from pairs

Often you know only some equivalences ("these two accounts are the same person") and want the smallest equivalence relation containing them: reflexive, symmetric and transitive closure of the pairs. Union-find (disjoint-set union) maintains exactly this partition and is used in Kruskal's algorithm, image segmentation and type unification.

Python Union-find merges classes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Counting partitions

The number of partitions of an n-element set is the Bell number Bโ‚™: 1, 1, 2, 5, 15, 52, 203, โ€ฆ For {a, b, c} the five partitions are , {ab|c}, {ac|b}, {bc|a} and {a|b|c}, so there are five equivalence relations on a three-element set. The number of ways into exactly k blocks is a Stirling number of the second kind.

Python Bell numbers by recursion

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Not every relation that looks like "sameness" is an equivalence. "Is within 1 of" on integers is reflexive and symmetric but not transitive (12, 23, but not 1~3), so it does not partition the integers.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which three properties define an equivalence relation?

    Equivalence needs reflexive, symmetric and transitive. The antisymmetric variant defines partial orders.
  2. 2. How many equivalence classes does congruence mod 12 have on the integers?

    Remainders 0 through 11 give 12 distinct classes.
  3. 3. Two equivalence classes are always

    If two classes share an element x, transitivity and symmetry show every element of one is equivalent to every element of the other, so the classes coincide.
  4. 4. How many equivalence relations exist on a 3-element set?

    They correspond to partitions of the set, counted by the Bell number B3 = 5.

Summary

  • An equivalence relation is reflexive, symmetric and transitive; [a] is the class of everything equivalent to a.
  • Classes are nonempty, disjoint and cover the set, so equivalence relations and partitions correspond one to one.
  • The quotient set A/~ collects classes; operations on classes need a well-definedness check, as in โ„ค/nโ„ค.
  • Union-find computes the smallest equivalence containing given pairs; Bell numbers count partitions.

Next: Functions: Injective, Surjective, Bijective