Skip to content
Tutorials Center
My learning

Topics

Lesson 16 of 38 ยท Equivalence and Order

Partitions and Quotient Sets

Learn partitions of a set, the correspondence between partitions and equivalence relations, quotient sets A/~, and Bell numbers, with code.

The last lesson showed that an equivalence relation chops a set into disjoint classes. This lesson runs the idea in the other direction: any way of chopping a set into disjoint pieces comes from an equivalence relation. The two notions, partitions and equivalence relations, are different faces of one concept. Then we build the quotient set, whose elements are the pieces themselves.

Partitions

A partition of a set A is a collection ๐’ซ of subsets of A (called blocks or parts) such that

  1. every block is non-empty,
  2. different blocks are disjoint,
  3. the union of all the blocks is A.

In words: every element of A lies in exactly one block.

Examples for A = {1, 2, 3, 4}:

  • { {1, 2}, {3}, {4} } is a partition.
  • { {1, 2}, {2, 3, 4} } is not (2 lies in two blocks).
  • { {1}, {2, 3} } is not (4 is missing).
  • { {1, 2, 3, 4} } is a partition with one block, and { {1}, {2}, {3}, {4} } is the partition into singletons.

Some everyday partitions: students sorted into school years, files sorted by extension, the integers split into even and odd.

Equivalence relations and partitions are the same thing

From a relation to a partition. If ~ is an equivalence relation on A, the set of equivalence classes { [a] : a โˆˆ A } is a partition. Classes are non-empty (a โˆˆ [a]), two classes are equal or disjoint, and every a lies in some class [a].

From a partition to a relation. If ๐’ซ is a partition of A, define a ~ b when a and b lie in the same block. This is an equivalence relation: reflexive (a is in its own block), symmetric (the definition does not care about order) and transitive (if a, b share a block and b, c share a block, the block containing b is unique, so a, c share it).

The two constructions undo each other: the classes of the relation "same block" are exactly the blocks, and the relation "same class" is exactly the original relation. Therefore

Text
equivalence relations on A   โŸท   partitions of A    (a one-to-one correspondence)
Python Switch between partitions and relations

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.

The quotient set

If ~ is an equivalence relation on A, the quotient set A/~ is the set whose elements are the equivalence classes:

Text
A/~ = { [a] : a โˆˆ A }

It is an object built from the partition: a new set whose "points" are whole blocks. Two elements of A that are equivalent become one point of A/~.

For congruence mod 3 on โ„ค, the quotient is written โ„ค/3โ„ค (or โ„คโ‚™), and it has exactly three elements: [0], [1] and [2]. For congruence mod n, there are n classes. This is the set underlying clock arithmetic: on a 12-hour clock, 15:00 and 3:00 are the same point.

There is also a natural function q : A โ†’ A/~, q(a) = [a], called the quotient map (or canonical projection). It is always surjective, and q(a) = q(b) exactly when a ~ b.

Operations on classes

Often you can define operations on the quotient using representatives: [a] + [b] = [a + b]. For this to make sense (be well-defined) the result must not depend on which representatives you pick. For congruence mod 5: [2] + [4] = [6] = [1], and choosing other representatives gives the same class: [7] + [โˆ’1] = [6] = [1]. The reason is that if a โ‰ก a' and b โ‰ก b' then a + b โ‰ก a' + b'. This idea leads to modular arithmetic, quotient groups and quotient spaces in later math.

Python Arithmetic on remainder 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: Bell numbers

How many partitions does an n-element set have? These counts are the Bell numbers: 1, 1, 2, 5, 15, 52, 203, ... for n = 0, 1, 2, .... For n = 3 the five partitions are , {ab|c}, {ac|b}, {bc|a} and {a|b|c}. The numbers grow quickly, and they count the number of different equivalence relations on an n-element set (compare with the 2^(nยฒ) relations in total).

A simple recursion builds them. To partition {1, ..., n+1}, take the block containing element n+1, say it has k other elements chosen from the first n, then partition the remaining n โˆ’ k elements:

Text
B(n+1) = ฮฃ_{k=0..n} C(n, k) ยท B(n โˆ’ k)
Python Bell numbers two ways

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.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which is a partition of {1, 2, 3, 4, 5}?

    Every element lies in exactly one block. The first option repeats 2; the last misses 5.
  2. 2. How many elements does the quotient set โ„ค/ โ‰ก (mod 6) have?

    There is one class for each remainder 0, 1, 2, 3, 4, 5.
  3. 3. How many different equivalence relations exist on a 3-element set?

    They correspond to partitions: the Bell number B(3) = 5.
  4. 4. Why is [a] + [b] = [a + b] well-defined on remainder classes?

    If a โ‰ก a' and b โ‰ก b' (mod n), then a + b โ‰ก a' + b' (mod n).

Summary

  • A partition splits a set into non-empty, disjoint blocks that cover it.
  • Partitions and equivalence relations correspond exactly: classes give blocks, and "same block" gives a relation.
  • The quotient set A/~ has the classes as its elements; the quotient map a โ†ฆ [a] is surjective.
  • Operations on classes must be well-defined (independent of representatives).
  • The number of partitions of an n-element set is the Bell number: 1, 1, 2, 5, 15, 52, ...

Next: Partial Orders and Hasse Diagrams