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
Solution:
- 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
Hence:
- So
- The equivalence classes do not intersect:
Consider the next example:
List all the partitions of the set
Solution:
- 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.
Leave a Reply