Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

$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.

share|cite|improve this question
Should we tag it as elementary-set-theory? – Nuno Nov 19 '10 at 15:51
@Nuno: I agree, and I made the change. – Carl Mummert Nov 19 '10 at 17:15
@Carl Mummert: Oops; sorry I missed that. I've been trying to keep an eye out for those... – Arturo Magidin Nov 19 '10 at 17:39
up vote 3 down vote accepted

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})$?

share|cite|improve this answer
thank you very much for your quick reply and your helpful suggestions! – Greg S Nov 19 '10 at 15:54

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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