On page 3 / Proposition 2 of Dummit&Foote's Abstract Algebra (3rd ed.):
Let $A$ be a nonempty set.
(1) If $\sim$ defines an equivalence relation on $A$ then the set of equivalence classes of $\sim$ form a partition of $A$.
(2) If $\{A_i \mid i\in I\}$ is a partition of $A$ then there is an equivalence relation on $A$ whose equivalence classes are precisely the sets $A_i,i\in I$.
According to the book, those two statements show that the notions of an equivalence relation on $A$ and a partition on $A$ are the same. And the proofs are omitted by the book.
Below are my proofs and my questions related to this proposition:
- Proof for (1):
$A$ is nonempty in the first place. Since equivalence classes are defined upon elements in the set, if we let $E=\{E_\alpha \mid \alpha\in A\}$ where $E_\alpha$ is the equivalence class of $\alpha\in A$, then $E$ shall catch all the equivalence classes of $\sim$ on $A$. And since every element in $E$ is a nonempty set (each contains its $\alpha$), all the equivalence classes are nonempty.
For now, let $I$ denote the injective-indexing set for the equivalence classes of $\sim$ on $A$ so that each equivalence class is uniquely denoted as $E_i$ for some $i\in I$.
If $A\neq \bigcup_{i\in I}E_i$, then there exists $a\in A$ such that $a\notin \bigcup_{i\in I}E_i$ or the other way around.
For the former, let's construct a set, called $E_c$, such that for each $x\in A$, $x\in E_c$ iff $x\sim a$. $E_c$ is then an equivalence class of $\sim$ on $A$. Then, $E_c=E_i$ for some $i\in I$. Thus, $a\in \bigcup_{i\in I}E_i$.
For the latter, we have $a\in E_i$ for some $i\in I$. By definition we then have $a\in A$.
Hence, $A= \bigcup_{i\in I}E_i$ by contradiction.
If there exist $i,j\in I$ with $i\neq j$ such that $E_i\cap E_j\neq \emptyset$, let $E_i\cap E_j=B$, then there exists $b\in B$. Let a representative of $E_i$ be $x$ and a representative of $E_j$ be $y$, we then have $b\sim x$ and $b\sim y$. Then we have $x\sim b$ and thus $x\sim y$. By definition, it follows that all elements in $E_i$ are in $E_j$ and vice versa (i.e. $E_i=E_j$). By injection, $i=j$. Hence, for all $i,j\in I$ with $i\neq j$, we have $E_i\cap E_j=\emptyset$ by contradiction.
Thus, the equivalence classes of $\sim$ on $A$ form a partition of $A$.
- Proof for (2):
For personal preference, I won't use the index notation in this proof.
Given a partition of $A$, say $P$, let's define a binary relation $\sim$ by constructing a subset $R$ of $A\times A$ as follows:
$(a,b)\in R$ iff $a,b\in S$ for some $S\in P$.
Since for all $a\in A$, $a\in S$ for some $S\in P$, let $b=a$, we then have $(a,a)\in R$. Thus, $\sim$ is reflexive.
For all $a,b\in A$, if $(a,b)\in R$, then $a,b\in S$ for some $S\in P$. Then $b,a\in S$. Then $(b,a)\in R$. Thus, $\sim$ is symmetric.
For all $a,b,c\in A$, if $(a,b),(b,c)\in R$, then $a,b,c\in S$ for some $S\in P$. In particular, $a,c\in S$. Then $(a,c)\in R$. Thus, $\sim$ is transitive.
Hence, $\sim$ is an equivalence relation.
For each $a\in A$, let $E_a$ be the equivalence class of $a$. Then $E_a$ precisely contains all the $x\in A$ such that $(x,a)\in R$. Let $(x_1,a),(x_2,a)\in R$, we then have $x_1,a\in S_1$ and $x_2,a\in S_2$ where $S_1,S_2\in P$. If $S_1\neq S_2$, then $S_1$ and $S_2$ are disjoint. Since $a$ is in both, we must have $S_1=S_2$ by contradiction. Thus, all elements in $E_a$ must be in the same $S\in P$. That is, $E_a\subseteq S$ for some $S\in P$. Now, Assume this $S$ contains an element $b$ such that $b\notin E_a$. Since $S$ is a subset of $A$, we have $b\in A$. Since $b,a\in S$, we have $(b,a)\in R$. Together we have $b\in E_a$, which contradicts. Thus, $E_a=S$. Hence, the set of equivalence classes is a subset of the partition.
For each $S\in P$, since $S$ is nonempty, we can always fix an element $t\in S$. Clearly $t\in A$, thus there exists a set $E_t$ which is the equivalence class of $t$. For any $r\in S$, since $r,t\in S$, we have $(r,t)\in R$ and thus $r\sim t$. Since $r\in A$, we have $r\in E_t$. Thus, every element in $S$ is in $E_t$. If $E_t$ contains an element $\omega$ such that $\omega\notin S$, we have $\omega\sim t$ and thus $\omega,t\in S_3\in P$. In particular, $t\in S_3$. Then we must have $S_3=S$. Then $\omega\in S$. By contradiction, $S=E_t$. Hence, the partition is a subset of the set of equivalence classes.
This concludes that the set of equivalence classes is the partition.
Could someones please review my proofs to see if there are errors in any kind? Many thanks!
- My question:
I think by the two statements in proposition 2, it is not sufficient to show that the notions of an equivalence relation on $A$ and a partition on $A$ are the same.
First, let me define how I understand "two notions are the same": say I have two notions $A$ and $B$, as long as I get an instance of $A$, I can transform it to an instance of $B$. And if now I give you this instance of $B$ without showing you what my instance of $A$ is, then you should always know what's in my hand by transforming the instance of $B$ to an instance of $A$.
The thing is, I think proposition 2 does not guarantee that when you transform the instance of $B$ back to $A$, you would always get the exact same instance of $A$ as what in my hand. Say I have an equivalence relation, then I can transform it into a partition [(1)], and if I show you the partition you could find an equivalence relation [(2)] that transforms into the partition in the same manner. However, to me, this is like a mapping: (1) guarantees that each $\sim$ can be mapped to a partition, (2) guarantees that the mapping is surjective, but we still need to prove that such mapping is injective for the two notions to be the same.
That is, we still need to prove that no two different equivalence relations could give the same partition.
May I ask if my concern is necessary?
Best Answer
Your proof of (1) isn’t wrong, but you’re making things much harder than necessary. There is no reason to index $E$ injectively. For each $\alpha\in A$ we have $\alpha\in E_\alpha\in E$, so $\alpha\in\bigcup E$, and since $\alpha$ was an arbitrary element of $A$, it follows that $A\subseteq\bigcup E$. On the other hand, $E_\alpha\subseteq A$ for each $\alpha\in A$, so $\bigcup E\subseteq A$, and therefore $\bigcup E=A$.
Now suppose that $E_\alpha,E_\beta\in E$ are such that $E_\alpha\cap E_\beta\ne\varnothing$. Let $a\in E_\alpha\cap E_\beta$; then $a\sim\alpha$ and $a\sim\beta$. Let $x\in E_\alpha$; then $x\sim\alpha\sim a\sim\beta$, so $x\sim\beta$, and therefore $x\in E_\beta$. This shows that $E_\alpha\subseteq E_\beta$, and a similar argument shows that $E_\beta\subseteq E_\alpha$ and hence that $E_\alpha=E_\beta$. Thus, $E$ is a partition of $A$.
The proof of (2) is better in that respect, but one needn’t work quite that hard to show that the $\sim$-equivalence classes are the parts of the original partition. Fix $a\in A$; $P$ is a partition of $A$, so there is a unique $S_a\in P$ such that $a\in S_a$. Now let $x\in A$: clearly $x\in E_a$ iff $x\sim a$ iff there is an $S\in P$ such that $\{x,a\}\subseteq S$ iff $x\in S_a$, since $S_a$ is the only member of $P$ containing $a$. But $x\in E_a$ iff $x\in S_a$ simply means that $E_a=S_a$. That is, for each $a\in A$ the $\sim$-class of $a$ is identical to the unique member of $P$ containing $a$, so the partition of $A$ into $\sim$-classes (which we know from (1) is a partition) is identical to the partition $P$.
Your understanding of the sense in which the notions of equivalence relation on $A$ and partition of $A$ are ‘the same’ is correct. The demonstration of equivalence isn’t actually complete, because (1) doesn’t go quite far enough: now that we have (2), we should show that if we start with an equivalence relation $\sim$ on $A$, produce the associated partition as in (1), and then use (2) to produce an associated equivalence relation, we get back the original equivalence relation $\sim$. However, this is trivial, since two equivalence relations that have the same equivalence classes are easily seen to be the same relation.
This old answer of mine is another discussion of these matters.