I read lecture notes from mit ocw


I came across the lemma

Let $X$ be a set. Given an equivalence relation ~ on $X$ there is a 'unique partition ' on $X$

But in the proof there is nothing about uniqueness of partition.I want to know in which sense the partition is unique ( what does it meant by 'unique partition ' and why not 'just partition').


  • $\begingroup$ Page 2 on linked lecture notes $\endgroup$ – Cloud JR Sep 18 '18 at 17:53

The word "unique" is misleading here. What is meant is that there is a one to one correspondence between partitions of a set and equivalence relations on it. Each partition induces an equivalence relation, and each equivalence relation partitions a set. It looks like he leaves part of this as an exercise for the reader.

Sketch of Proof:

An equivalence relation partitions a set:

The equivalence classes form the disjoint "pieces" of the partition. Note that

a.) every element is in some equivalence class (namingly its own).

b.) The equivalence classes are disjoint.

A partition induces an equivalence relation:

Define two elements to be "equivalent" if they reside in the same "piece" of the partition. Show that this relation is reflexive, transitive, and symmetric.

  • $\begingroup$ Give an equivalence relation ,is it possible to partition a set in two different ways? How can we claim there is one to one correspondence between them $\endgroup$ – Cloud JR Sep 18 '18 at 18:07
  • 1
    $\begingroup$ @CloudJR I'm sorry I don't quite know how to explain it any differently than I have above. The Wikipedia section : en.wikipedia.org/wiki/… may make it clearer. $\endgroup$ – David Reed Sep 18 '18 at 18:16
  • $\begingroup$ This wikipedia article helps a lot thanks $\endgroup$ – Cloud JR Sep 18 '18 at 18:20
  • $\begingroup$ Thanks for your help $\endgroup$ – Cloud JR Sep 18 '18 at 18:21
  • 1
    $\begingroup$ @CloudJR Sure. I actually remember struggling with this concept when I initially came across it as well. It is important though for making combinatorial ("counting") arguments in certain fundamental theorems --like Lagrange's Theorem from Algebra:en.wikipedia.org/wiki/… $\endgroup$ – David Reed Sep 18 '18 at 18:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.