$M$, $N$ are sets, $f: M \rightarrow N$ is a function, $R \subseteq M\times M$ is an equivalence relation on $M$, $\pi: M \rightarrow M/R$ is the canonical projection (i.e. $\pi(x)=[x]_R$), and $\ker f \subseteq M\times M$ is defined as $\{(x,y) \in M \times M: f(x)=f(y)\}$.

Show that $R \subseteq \ker f \Leftrightarrow (\exists F: M/R \rightarrow N)(f=F\circ \pi)$ and that there is exactly one $F$, if both statements in the logical equivalence are true.

Now, let's see what I've come up with so far:

"$\Rightarrow$": assume $R \subseteq \ker f$ and construct a function $F: M/R \rightarrow N$ which works like this: given a $c \in M/R$, choose an $x \in M$ with $c=[x]_R$ and let $F(c)=f(x)$. This works exactly because we know that $(\forall a,a' \in [x]_R)(f(a) = f(a'))$. Now let $x \in M$ and $y=\pi(x)=[x]_R$, then $F(y)=f(x)$ and $F(\pi(x))=(F\circ \pi)(x)=f(x)$ for all $x \in M$.

"$\Leftarrow$": assume $\exists F: M/R \rightarrow N$ with $f=F\circ \pi$: then $(\forall c \in \{[x]_R: x\in M\})(F(c)=f(x))$. Let $a \in M/R$ and $x,x' \in a$, then $\pi(x)=\pi(x')$. We can then apply $F$ to both sides and see that $f(x)=F(\pi(x))=F(\pi(x'))=f(x')$, i.e. $R\subseteq M\times M$ can be defined as $\{(x,y)\in M\times M: f(x)=f(y)\}$ and therefore $R\subseteq \ker f$.

Have I missed something important or is this correct? If so, how would I go about proving that there is exactly one F satisfying the given attributes?

As a side-note: I'm very new to mathematics (and I'm no native speaker either), so any hints regarding style/language are very welcome.

  • $\begingroup$ Should we tag it as elementary-set-theory? $\endgroup$ – Nuno Nov 19 '10 at 15:51
  • $\begingroup$ @Nuno: I agree, and I made the change. $\endgroup$ – Carl Mummert Nov 19 '10 at 17:15
  • $\begingroup$ @Carl Mummert: Oops; sorry I missed that. I've been trying to keep an eye out for those... $\endgroup$ – Arturo Magidin Nov 19 '10 at 17:39

Your "$\Leftarrow$" proof is a muddled. First, $R$ is not necessarily equal to $\mathrm{ker} f$, but that is what you are asserting is happening when you say "$R$ can be defined as...". Second, I don't see you showing that every element of $R$ is in $\mathrm{ker} f$, which is what you need to do.

In that direction, you want to show that if $f=F\circ \pi$ for some function $F\colon M/R \to N$, then $R\subseteq \mathrm{ker} f$. Since you are trying to prove an inclusion, what you want to do is start by taking an element $(a,b)\in R$, and show that $(a,b)\in \mathrm{ker}f$. So you want to show that $f(a)=f(b)$. We know that $f(a) = F\circ\pi(a) = F(\pi(a)) = F([a]_R)$. And then...

To show that the function $F$ is unique, assume you have a function $G\colon M/R\to N$ with $f=G\circ\pi$. You want to show that $F=G$ (this will prove uniqueness). They have the same domain and they have the same codomain, so you only need to show that for every $[x]_R\in M/R$, you have $G([x]_{R})=F([x]_{R})$. Now, $G([x]_R) = G(\pi(x)) = f(x)$. What about $F([x]_{R})$?

  • $\begingroup$ thank you very much for your quick reply and your helpful suggestions! $\endgroup$ – Greg S Nov 19 '10 at 15:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.