The fibres of a map form a partition of the domain.

Question

This is a question from the free Harvard online abstract algebra lectures. I'm posting my solutions here to get some feedback on them. For a fuller explanation, see this post.

This problem is from assignment 5.

Prove that the fibres of a map form a partition of the domain.

Let $G$ and $G^\prime$ be sets and $f$ be a map from $G$ to $G^\prime$. The nonempty fibres of $f$ correspond to the elements of the image of $f$ in $G^\prime$. Let $R$ be a relation on $G$ defined by $a \sim b$ if $a$ and $b$ are in the same fibre. For all $a\in G$, $f(a)=f(a)$, so $a\sim a$ and $R$ is reflexive. Assume, for some $a,b\in G$, that $a\sim b$. Then $f(a)=f(b)$. So $b\sim a$ and $R$ is symmetric. Assume, for some $a,b,c\in G$, that $a\sim b$ and $b\sim c$. Then $f(a)=f(b)$ and $f(b)=f(c)$. So $f(a)=f(c)$, $a\sim c$, and $R$ is transitive. Therefore, $R$ is an equivalence relation and the nonempty fibres of $f$ form a partition of $G$.

Again, I welcome any critique of my reasoning and/or my style as well as alternative solutions to the problem.

Thanks.

Answer 1

As ineff said, your solution is fine, and ineff has given you the other natural solution. Since you’re studying on your own, I just want to emphasize that if $G$ is a set, equivalence relations on $G$, partitions of $G$, and functions with domain $G$ are three ways of looking at essentially the same thing.

You’ve already seen that if $R$ is an equivalence relation on $G$, $\mathscr{P}(R)=\{[x]_R:x\in G\}$ is a partition of $G$ (where $[x]_R$ is the $R$-equivalence class of $x$), and if $\mathscr{Q}$ is a partition of $G$, then the relation $E(\mathscr{Q})$ defined by $$x\;E(\mathscr{Q})\;y \iff \exists Q\in\mathscr{Q} \big(x,y\in Q\big)$$ is an equivalence relation on $G$. Moreover, $E\big(\mathscr{P}(R)\big)=R$ for any equivalence relation $R$ on $G$, and $\mathscr{P}\big(E(\mathscr{Q})\big)=\mathscr{Q}$ for any partition $\mathscr{Q}$ of $G$. In other words, there’s a natural bijection between equivalence relations on $G$ and partitions of $G$ given by $R\mapsto\mathscr{P}(R),\mathscr{Q}\mapsto E(\mathscr{Q})$: every equivalence relation determines a partition, which in turn determines the original equivalence relation.

In this exercise you’ve shown that if $f$ is any function with domain $G$, the fibres of $f$ form a partition of $G$, say $\mathscr{P}(f)$. This correspondence also goes both ways. Suppose that $\mathscr{Q}$ is a partition of $G$. Define $g_\mathscr{Q}:G\to\mathscr{Q}$ by letting $g_\mathscr{Q}(x)$ be the unique member of $\mathscr{Q}$ containing $x$; clearly $g_\mathscr{Q}$ is a function with domain $G$, and it’s very easy to check that

$\qquad(1)\qquad\mathscr{P}(g_\mathscr{Q})=\mathscr{Q}$ for any partition $\mathscr{Q}$ of $G$, and
$\qquad(2)\qquad g_{\mathscr{P}(f)}=f$ for any function $f$ with domain $G$.

That is, we have a natural bijection between partitions of $G$ and functions with domain $G$ given by $\mathscr{Q}\mapsto g_\mathscr{Q},f\mapsto\mathscr{P}(f)$: every partition determines a function that in turn determines the original partition.

And of course these give rise to a natural bijection between equivalence relations on $G$ and functions with domain $G$.

You’ll be using all three points of view when you study quotient groups.

Answer 2

Your solution is correct. Since you asked for different solutions I'll give you one.

Let $f \colon G \to G'$ be a function. For each $x' \in G'$, we'll denote by $f^{-1}(\{x'\})$ the set $$\left\{x \in G : f(x)=x' \right\}$$ i.e. the fiber of $x'$ for the map $f$.

Now given $x',y' \in G'$ then $f^{-1}(\{x'\}) \cap f^{-1}(\{y'\}) \ne \emptyset$ if and only if there exists a $z \in G$ such that $x' = f(z) = y'$ and so thus $x'=y'$.

This implies that $f^{-1}(\{x'\}) \cap f^{-1}(\{y'\}) \ne \emptyset$ if and only if $f^{-1}(\{x'\})=f^{-1}(\{y'\})$, which means that the fibers (i.e the sets of form $f^{-1}(\{x'\})$ for some $x' \in G'$) form a partition of $G$.