Help With Proof of Theorem 1.A. in "Topics in Algebra"

Question

Here is a statement of the theorem. I am attempting to prove the part starting from "Conversely...".

The distinct equivalence classes of an equivalence relation on A provide us with a decomposition of A as a union of mutually disjoint subsets. Conversely, given a decomposition of A as a union of mutually disjoint, nonempty subsets, we can define an equivalence relation on A for which these subsets are the distinct equivalence classes.

I found a similar thread discussing the problem, but it did not exactly answer the question I had: Proof of theorem about equivalence classes

So far, I have proved that the binary relation, $\sim$ defined by $x \sim y$ if and only if $x, y \in A_{\alpha}$, is an equivalence relation where $A_{\alpha}$ is an element of my paritions. Whenever I tried to prove that the set of equivalence classes are the $A_{\alpha}$'s, I got a bit stuck.

My thoughts so far are to fix an element, $i$, in my indexing set and choose an $x \in A_i$. Then $x \sim x$, so $x \in [x]$. Conversely, if $x \in [x]$, then I must prove that $x \in A_i$. All I know so far is that $x \in A_j$ for some $j$ in my indexing set. I don't really know how to prove that $A_j = A_i$.

Answer 1

I am not sure if fixing a set $A_i$ before defining the equivalence relation leads to success. I would suggest defining it right away for $A$ as a whole.

Let $A = \bigcup_{i=1}^n A_i$ be a disjoint union with $A_i \neq \emptyset$ for all $i$. Define $f: A \rightarrow \{1, \dots n\}$ with $f(a) = i \Leftrightarrow a \in A_i$*. Now define the equivalence relation $\sim$ as:

$$ x \sim y \Leftrightarrow f(x) = f(y) $$

This is indeed an equivalence relation which can be easily shown.

Now show that $A/\sim = \{A_1, \dots A_n\}$

• $\subseteq$: Let $B \in A/\sim$. Then $B \neq \emptyset$, therefore a $b\in B \subseteq A$ exists. Prove that $B = A_{f(b)}$.
• $\supseteq$: Show that $A_i \in A/\sim$. Because $A_i \neq \emptyset$, we have an $x\in A_i$ with $[x]_\sim \in A/\sim$. Prove that $[x]_\sim = A_i$.

*) This might look suspicious at first because it does not guarantee well-definedness of $f$, but given the disjoint union $f$ indeed maps one element from $A$ to exactly one element from $\{1, \dots, n\}$.

Actually, the theorem is stronger since it also works with an infinite number of partitions. You could think about whether or how this proof can be fixed.

Answer 2

First of all, if you have a relation $\sim$ on $A = \bigcup_{i = 1}^n A_i$, where $A_i$'s are mutually disjoint, then for set of all related pairs $\mathscr{R}$ you have $\mathscr{R} \subseteq A\times A$. This might seem to be a simple property but notice that the statement says "we can define an equivalence relation on A". So if we can construct one such equivalance relation, we are done. Now you have mutually disjoint, nonempty subsets of $A$ so you can construct an equivalance relation $\sim$ = $(A, \mathscr{R})$ where $$\mathscr{R} = \bigcup_{i = 1}^n (A_i \times A_i)$$ Now, let us prove that $\sim$ is an equivalance relation. Here, by definition of $A$, reflexivity holds for the relation $\sim$ because for all $x \in A$, the pair $(x,x) \in \mathscr{R}$ (this is because none of the subsets are empty and they are mutually disjoint). Symmetry also holds because if you have $x,y \in A_j$ where $A_j \subseteq A$ with $1 \le j \le n$, then for all such $x$,$y$ , $(x,y),(y,x) \in A_j \times A_j$. You can show that transitivity also holds with a similar argument. Again say $u,v,t \in A_k$ where $A_k \subseteq A$ with $1 \le k \le n$. Then notice that for all such $u$,$v$,$t$, $(u,v),(v,t),(u,t) \in A_k \times A_k$. Therefore $\sim$ is an equivalance relation.

Actually if you write all the elements of $A_j \times A_j$ and $A_k \times A_k$ for $A_j = \{x,y\}$ and $A_k = \{u,v,t\}$, you can see why $\sim$ = $(A, \mathscr{R})$ is an equivalance relation (For example $A_j \times A_j = \{(x,x),(x,y),(y,x),(y,y)\}$).