I am working on a homework problem and would like some guidance/verification that I am on the right track. The problem statement is as follows:
Prove that if $\sim$ is an equivalence relation of $X$, then the function $\pi : X \rightarrow X/\sim$ defined by $\pi(x) = [x]$ is a surjective map and the equivalence relation $\sim_{\pi}$ determined by $\pi$ is exactly $\sim$
My attempt at a solution (for the first part)
So to prove that some function $f: A \rightarrow B$ is surjective we need to show that $\forall b \in B, \exists a \in A \mid f(a) = b$. To that end, I began with the theorem that links equivalence classes on a set to the partition of the set:
Since $\sim$ is an equivalence relation on $X$, the set of all equivalence relations on $X, X/\sim$, is a partition of $X$. Thus every element $x \in X$ is in exactly one of the subsets of the partition $X/\sim$ (i.e., the equivalence classes) - in other words, the equivalence classes are nonempty, pairwise disjoint and their union is all of $X$. This means that every element, $x \in X$, is related to one of the representatives of each of the equivalence classes. Hence, for each $[x] \in X/\sim, \exists x \in X \mid \pi(x) = [x]$
Would this be acceptable as an answer?
For the second part
I'm having a little trouble figuring out where to go for this part. I figured I should probably start by understanding what exactly the relation $\sim_{\pi}$ is...
- So, if $\sim_{\pi}$ is defined by $\pi$ then would we say that for $x,y \in X, x \sim_{\pi} y$ if $\pi(x) = [x] = [y] = \pi(y)$?
- If so, would that just be saying that two elements of $X$ are related if they are in the same equivalence class? But then that would just be the general definition of equivalence class, and since $\sim$ is a general equivalence relation we can say that $\sim_{\pi} = \sim$?
I don't know how many features of equivalence relations you are allowed to assume, although I'm guessing you are allowed use the basics, like $x \sim y$ if and only if $[x] = [y]$ if and only if $x \in [y]$, and so on.
The first part is more or less a consequence of your observation that "the equivalence classes are nonempty". Specifically, if $A \in X/\sim$ then there exists some member $a \in A$, and for this $a$ we have $\pi(a) = [a] = A$, whence $A$ is in the image of $\pi$.
For the second part, yes $x \sim_\pi y$ if and only if $\pi(x) = \pi(y)$ if and only if $[x] = [y]$ if and only if $x \sim y$.