2
$\begingroup$

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

  • 0
    Should we tag it as elementary-set-theory?2010-11-19
  • 0
    @Nuno: I agree, and I made the change.2010-11-19
  • 0
    @Carl Mummert: Oops; sorry I missed that. I've been trying to keep an eye out for those...2010-11-19

1 Answers 1

3

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

  • 0
    thank you very much for your quick reply and your helpful suggestions!2010-11-19