Proof:A/R partitions A

In our example of an equivalence relation, we noted that the equivalence classes partition the set into disjoint subsets.

In fact, this is a general phenomenon, which we prove here. We begin with a definition:

Definition: Partition
A collection of subsets of a set form a partition of if:
1. The cover , i.e. .
2. The are disjoint, i.e. unless .

The Venn diagram of a partition looks like this:

Now we can prove the following claim:

partitions . In other words,
1. Every element of is in some equivalence class, and
2. Two equivalence classes are either disjoint or identical
Proof:
For the first part, note that . This is because must be an equivalence relation, and is thus reflexive. This means so , and thus there exists some equivalence class containing .

For the second part, suppose that . We want to show that . We will show that ; the reverse direction is similar.

Choose an arbitrary ; we want to show that .

Since , we know that there exists some . By definition of ⟦a⟧ and ⟦b⟧, we have , , and as in the following picture:

We wish to show that . Since and is symmetric we have (arrow (i) in the picture below). We can then use transitivity to find that (since and ) (arrow (ii) in the picture below), and then again (since ) to conclude that (arrow (iii) in the picture below).

By definition, since , we have , as required.