2.10 Partitions of sets and equivalence relations
In this section \(S\) is a set.
A relation on \(S\) is a subset \(R\subseteq S\times S\). An equivalence relation on \(S\) is a relation on \(S\) with the following properties:
For all \(s\in S\), \((s,s)\in R\).
For all \(s,t\in S\), \((s,t)\in R\Rightarrow (t,s)\in R\).
For all \(s,t,u\in S\), \((s,t)\in R\) and \((t,u)\in R \Rightarrow (s,u)\in R\).
Properties (a), (b) and (c) are respectively called the reflexive, symmetric and transitive properties.
If \(R\) is a relation on \(S\), then we often write \(xRy\) for \((x,y)\in R\). One equivalence relation that exists on any set is equality. Explicitly, this is the relation \(R = \{ (x,x): x\in S\} \).
Suppose \(T\) is a set and \(f:S\to T\) is a map. Set \(K(f) = \{ (x,y)\in S: f(x) = f(y)\} \). Then \(K(f)\) is an equivalence relation on \(S\).
Exercise.
A partition of \(S\) is a set \(P\) of disjoint, nonemtpy subsets of \(S\) whose union is \(S\) itself.
Suppose \(T\) is a set and \(f:S\to T\) is a map which is onto. Then \(P(f) = \{ f^{-1}(t) : t\in S\} \) is a partition of \(S\).
Since \(f\) is onto, each of the sets \(f^{-1}(t)\) for \(t\in S\) is nonempty. If \(t_1 \neq t_2\), then \(f^{-1}(t_1) \cap f^{-1}(t_2)\) is obviously empty. So the sets in \(P\) are disjoint. And, for every \(s\in S\), we have \(s \in f^{-1}(f(s))\). So the union of the sets in \(P(f)\) is all of \(S\).
Suppose \(P\) is a partition of \(S\). Then, by definition, for every \(s\in S\), there exists a unique subset \(U\in P\) such that \(s\in U\). Write \(\pi _P(s) := U\). Then we have a surjective map \(\pi _P:S\to P\).
Suppose \(S = \{ 1,2,3\} \) and \(P = \{ \{ 1,2\} , \{ 3\} \} \). Then \(\pi _P(1) = \pi _P(2) = \{ 1,2\} \) and \(\pi _P(3) = \{ 3\} \).
Suppose \(R\) is an equivalence relation on \(S\) and \(s\in S\). The equivalence class of \(s\) is \([s]_R = \{ t\in S: tRs\} \). We write \(S/R = \{ [s]_R : s\in S\} \).
Suppose \(R\) is an equivalence relation on \(S\), and \(s\), \(t\in S\). Then \(s\in S\). So, in particular, \([s]\neq \emptyset \). Moreover, the following are equivalent:
\(sRt\).
\([s] = [t]\).
\([s]\cap [t]\neq \emptyset \).
Since \(sRs\) by reflexivity, \(s\in [s]\). We do the rest of the proof by going around the circle of implications.
1\(\Rightarrow \)2: Supose \(u\in [s]\). Then \(uRs\). So, since \(sRt\), transitivity implies that \(uRt\). So \(u\in [t]\). That shows that \([s] \subseteq [t]\). But then, by symmetry, we get that \(tRs\). So the same argument proves that \([t]\subseteq [s]\).
2\(\Rightarrow \)3: Obvious from the fact that \([s]\neq \emptyset \).
3\(\Rightarrow \)2: Suppose \(u\in [s]\cap [t]\). Then \(uRs\) and \(uRt\). So, by symmetry, \(sRu\). And, then, by transitivity, \(sRt\).
Suppose \(R\) is an equivalence relation on \(S\). Then \(S/R\) is a partition of \(S\).
Write \(\operatorname{\mathrm{Equiv}}\) for the set of equivalence relations on \(S\), and write \(\operatorname{\mathrm{Part}}\) for the set of partitions of \(S\).
If \(R\) is an equivalence relation on \(S\), then \(K(\pi _{S/R}) = R\).
If \(P\) is a partition of \(S\), then \(S/K(\pi _P) = P\).
Consequently, the map \(\operatorname{\mathrm{Equiv}}\to \operatorname{\mathrm{Part}}\) given by \(R\mapsto S/R\) sets up a one-one correspondence between equivalence relations on \(S\) and partitions of \(S\). The inverse of this map is the map \(P\mapsto K(\pi _P)\).
(a) Suppose \(R\) is an equivalence relation. Then \((s,t)\in K(\pi _{S/R})\Leftrightarrow [s] = [t]\). By Lemma 2.81, this happens if and only if \(sRs\). So, it follows that \(K(\pi _{S/R}) = R\).
(b) Exercise.