Proof:A/R partitions A

In our example of an equivalence relation, we noted that the equivalence classes partition the set [math]A [/math] 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:

The cover [math]A [/math], i.e. .
The [math]A_i [/math] are disjoint, i.e. unless [math]i = j [/math].

The Venn diagram of a partition looks like this:

Now we can prove the following claim:

Claim (see proof):

partitions . In other words,

Every element of [math]A [/math] is in some equivalence class, and
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 [math]R [/math] is symmetric we have (arrow (i) in the picture below). We can then use transitivity to find that (since [math]bRc [/math] and [math]cRa [/math]) (arrow (ii) in the picture below), and then again (since [math]aRd [/math]) to conclude that [math]bRd [/math] (arrow (iii) in the picture below).

By definition, since , we have , as required.