Produced by Charles Wells.  Home.   Website Contents     Website Index   

Posted 27 May 2008

EQUIVALENCE RELATIONS

A partition  of a set S is a set of nonempty subsets of S which are pairwise disjoint and whose union is all of S.  An equivalence relation on a set S is a reflexive, symmetric, transitive relation on S. These two definitions provide exactly the same class of structures. The first one takes the set of equivalence classes as given data and the second one uses the relation as given data. Each aspect determines the other uniquely. Each definition is a different way of presenting the same type of structure.  This chapter spells this out in detail.

Contents

Partitions

Definitions

Simple examples

Counting Partitions

Notation

Equivalence relations

Equivalence relations and partitions

An equivalence relation determines a partition

A partition determines an equivalence relation

The fundamental theorem on equivalence relations

Consciousness-raising examples

Answers to exercises

Partitions

Definitions

Definition:  Partition

If S is a set, a family  of subsets of S (called the blocks or  equivalence classes of  )  is a partition of S if

PAR.1   Every block of  is nonempty.

PAR.2   Every element of S is an element of exactly one block of .

Alternative Definition:  Partition

If S is a set, a family  of subsets of S is a partition of S if

APAR.1   Every block of  is nonempty.

APAR.2   S is the union of all the blocks in .

APAR.3   If B and C are blocks in  and , then .

Remarks

¨   is the Greek letter capital pi.  

¨  The word “partition” has several other meanings in math.

¨  In everyday English, the word “partition” can refer to the division of something into pieces, but it can also refer to a wall that divides a room in two.  Don’t let this mess with your mind: the mathematical idea has nothing to do with walls.

¨  A partition is a set of blocks.  Don’t refer to one block as a partition.

¨  APAR.3 means by definition that  is pairwise disjoint.

Simple examples

Here are four partitions of the set {1, 2, 3, 4, 5}:

¨   

¨   

¨   

¨   

Remarks

Think about the remarks below until you see why they are correct:

¨   and  are the same partition (see here).

¨   and  are different partitions, because they have different blocks. 

¨  In , as in any partition with two blocks, each block is the complement of the other one.

¨   is the only partition of {1, 2, 3, 4, 5} with exactly one block.  Every nonempty set has a partition consisting of the whole set as the only block. 

¨   is the only partition with five blocks.  Every nonempty set has a partition whose blocks are all the singleton subsets of the set.

¨  The empty set has just one partition, whose set of blocks is empty. 

Non-examples

¨    is not a partition of the set {1, 2, 3, 4, 5} because the element 4 is not in any block.  It is, however, a partition of the set {1, 2, 3, 5}.

¨   is not a partition (of any set) because 4 is in two different blocks, violating PAR.1.   It violates APAR.3, too, because  but .

¨   is not a partition because one of its blocks is empty.

Representing partitions

Small finite partitions can be represented by diagrams like the following, which represents :