Recall the relation on the set
One of the equivalence classes is which is equivalent to writing
We could do this because the equivalence class collects all the natural numbers that are related to zero under the relation
The following theorem generalises this idea for any relation on the set for the integer
Let be an equivalence relation on set If then
Essentially, equivalence classes are equal if the elements are related under the relation And simultaneously, knowing that elements are related under means their equivalence classes are equal.
An equivalence class divides set a into equivalence classes. We call this situation a partition of set
A partition of a set is defined as a set of non-empty subsets of such that both these conditions are simultaneously satisfied:
(i) the union of all these subsets equals
(ii) the intersection of any two different subsets is
Let’s return to our example: on the set We could represent this set as:
- NOTE: Each equivalence class above represents an infinite set and despite the drawing suggesting is larger than for instance, this is not true.
- The union of these equivalence classes gives the whole set:
In general, for the relation on a set
- The intersection of any of the equivalence classes results in an empty set:
for example is an empty set since there are no elements in that are also in
In general, we write
- The partition formed for this set
Let’s consider a new example.
Consider the partition
Let be the equivalence relation on the set of integers. The equivalence classes are the two elements of We want to identify the equivalence relation
- Clearly, the set has been split into odd and even integers. So we write
on the set of integers.
Note the following:
- We have exactly two equivalence sets, each are infinite. Since this is a partition, the sets do not intersect.
- Since is a partition, we also know the union of the two sets gives us
- So we can conclude that these are the equivalence classes of if the relation
- The equivalence classes do not intersect:
Consider the next example:
List all the partitions of the set
- We have the partition which corresponds to the equivalence relation We have
- We also have the partition corresponding to the equivalence relation
- Note in both partitions, the union of the elements give the set and the intersection of the elements is empty.