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

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.


share|cite|improve this question
up vote 6 down vote accepted

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.

share|cite|improve this answer

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

share|cite|improve this answer

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.