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:
The Venn diagram of a partition looks like this:
Now we can prove the following claim:
For the first part, note that equivalence relation
, and is thus reflexive
. This means so , and thus there exists
some equivalence class containing
For the second part, suppose that want to show that . We will show that ; the reverse direction is similar.
Choose an arbitrary ; we want to show that .
Since there exists some . By definition of ⟦a⟧ and ⟦b⟧, we have , , and as in the following picture:
, we know that
We wish to show that 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).
. Since and is
By definition, since , we have , as required.
. This is because must be an