Let $\mathcal{R}$ be an equivalence relation on $S$ and define for each $p \in S, T_{p}=[p]={x: x \in S, x \mathcal{R} p}$.
Since $p \in[p]$, it is clear that $S$ is the union of all the distinct subsets $T_{a}, T_{b}, T_{c}$, induced by $\mathcal{R}$. Now for any pair of these subsets, as $T_{b}$, and $T_{c}$ we have $T_{b} \cap T_{c}=\emptyset$ since, otherwise, $T_{b}=T_{c}$ by Problem 5. Thus, $\left{T_{a}, T_{b}, T_{c}, \ldots\right}$ is the partition of $S$ effected by $\mathcal{R}$.

Conversely, let $\left{T_{a}, T_{b}, T_{c}, \ldots\right}$ be any partition of $S$. On $S$ define the binary relation $\mathcal{R}$ by $p \mathcal{R} q$ if and only if there is a $T_{i}$ in the partition such that $p, q \in T_{i}$. It is clear that $\mathcal{R}$ is both reflexive and symmetric. Suppose $p \mathcal{R} q$ and $q \mathcal{R} r$; then by the definition of $\mathcal{R}$ there exist subsets $T_{j}$ and $T_{k}$ (not necessarily distinct) for which $p, q \in T_{j}$ and $q, r \in T_{k}$. Now $T_{j} \cap T_{k} \neq \emptyset$ and so $T_{j}=T_{k}$. Since $p, r \in T_{j}$, then $p \mathcal{R} r$ and $\mathcal{R}$ is transitive. This completes the proof that $\mathcal{R}$ is an equivalence relation.

These figures need no elaboration once it is understood a minimum number of line segments is to be used. for example, $\emptyset$ is not joined directly to ${a, b, c}$ since $\emptyset \subseteq{a, b, c}$ is indicated by the path $\emptyset \subseteq{a} \subseteq{a, b} \subseteq{a, b, c} .$

Using the distinct symbols $x_{1}, x_{2}, x_{3}, \ldots, x_{n}$, we form the product
$$
\begin{array}{r}
A=\left(x_{1}-x_{2}\right)\left(x_{1}-x_{3}\right)\left(x_{1}-x_{4}\right) \cdots\left(x_{1}-x_{n}\right) \
\left(x_{2}-x_{3}\right)\left(x_{2}-x_{4}\right) \cdots\left(x_{2}-x_{n}\right) \
\cdots \cdots \cdots \cdots \cdots \cdot \cdots \cdot \
\left(x_{n-1}-x_{n}\right)
\end{array}
$$
A transposition $(u, v)$, where $u<v$, on $A$ has the following effect: (1) any factor which involves neither $x_{u}$ nor $x_{v}$ is unchanged, (2) the single factor $x_{u}-x_{v}$ changes sign, (3) the remaining factors, each of which contains either $x_{u}$ or $x_{v}$ but not both, can be grouped into pairs, $\left(x_{u}-x_{w}\right)\left(x_{v}-x_{w}\right)$ where $u<v<w$, $\left(x_{u}-x_{w}\right)\left(x_{w}-x_{v}\right)$ where $u<w<v$, and $\left(x_{w}-x_{u}\right)\left(x_{w}-x_{v}\right)$ where $w<u<v$, which are all unchanged. Thus, the effect of the transposition on $A$ is to change its sign.

Now the effect of $\alpha$ on $A$ is to produce $(-1)^{r} A$ or $(-1)^{s} A$ according as $\alpha$ is written as the product of $r$ or $s$ transpositions. Since $(-1)^{r} A=(-1)^{s} A$, we have $A=(-1)^{s-r} A$ so that $s-r$ is even. Thus, $r$ and $s$ are either both even or both odd.