Proof:A/R partitions A

From CS2800 wiki

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 [math]A_1, A_2, \dots, A_n [/math] of a set [math]A [/math] form a partition of [math]A [/math] if:
  1. The [math]\href{/cs2800/wiki/index.php/Sequence_notation}{A_i} [/math] cover [math]A [/math], i.e. [math]A \href{/cs2800/wiki/index.php/Equality_(sets)}{=} A_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} A_2 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} A_n [/math].
  2. The [math]A_i [/math] are disjoint, i.e. [math]A_i \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} A_j = \href{/cs2800/wiki/index.php/%E2%88%85}{∅} [/math] unless [math]i = j [/math].

The Venn diagram of a partition looks like this:

Partition.svg

Now we can prove the following claim:

[math]\href{/cs2800/wiki/index.php/A/R}{A/R} [/math] partitions [math]A [/math]. In other words,
  1. Every element of [math]A [/math] is in some equivalence class, and
  2. Two equivalence classes are either disjoint or identical
Proof:
For the first part, note that [math]a \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦a⟧} [/math]. This is because [math]R [/math] must be an equivalence relation, and is thus reflexive. This means [math]\href{/cs2800/wiki/index.php/XRy}{aRa} [/math] so [math]a \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦a⟧} [/math], and thus there exists some equivalence class containing [math]a [/math].

For the second part, suppose that [math]\href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦a⟧} \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} \href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦b⟧} \href{/cs2800/wiki/index.php/Equality_(sets)}{≠} \href{/cs2800/wiki/index.php/%E2%88%85}{∅} [/math]. We want to show that [math]\href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦a⟧} \href{/cs2800/wiki/index.php/Equality_(sets)}{=} \href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦b⟧} [/math]. We will show that [math]\href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦a⟧} \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} \href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦b⟧} [/math]; the reverse direction is similar.

Choose an arbitrary [math]d \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦a⟧} [/math]; we want to show that [math]d \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦b⟧} [/math].

Since [math]\href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦a⟧} \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} \href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦b⟧} \href{/cs2800/wiki/index.php/Equality_(sets)}{≠} \href{/cs2800/wiki/index.php/%E2%88%85}{∅} [/math], we know that there exists some [math]c \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦a⟧} \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} \href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦b⟧} [/math]. By definition of ⟦a⟧ and ⟦b⟧, we have [math]\href{/cs2800/wiki/index.php/XRy}{aRc} [/math], [math]\href{/cs2800/wiki/index.php/XRy}{bRc} [/math], and [math]\href{/cs2800/wiki/index.php/XRy}{aRd} [/math] as in the following picture:

Eqv-class-partition-1.svg

We wish to show that [math]\href{/cs2800/wiki/index.php/XRy}{bRd} [/math]. Since [math]\href{/cs2800/wiki/index.php/XRy}{aRc} [/math] and [math]R [/math] is symmetric we have [math]\href{/cs2800/wiki/index.php/XRy}{cRa} [/math] (arrow (i) in the picture below). We can then use transitivity to find that [math]\href{/cs2800/wiki/index.php/XRy}{bRa} [/math] (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).

Eqv-class-partition-2.svg

By definition, since [math]bRd [/math], we have [math]d \href{/cs2800/wiki/index.php/%5Cin}{\in} \href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦b⟧} [/math], as required.