Give an example of sets $X, Y$ and functions $f: X \rightarrow Y$ and $g: Y \rightarrow X$ that satisfy the following...

  • $g \circ f$ is a bijection
  • $g \circ f$ is different from the identity function
  • $f$ is not a surjection
  • $g$ is not an injection
  • $X$ contains two elements

Nothing I try satisfies all conditions simultaneously. There must be a better way to solve this than guessing/checking. Any help you can give would be awesome! Thanks!


I'll start this off, and hopefully you'll see how to keep going.

  • We know $X$ contains 2 elements, so let's just say $X=\{1, 2\}$.

  • Now $g\circ f$ is a bijection - from $X$ to $X$ - which is not the identity. This leaves only one possibility: we must have $g\circ f(1)=2$ and $g\circ f(2)=1$, i.e., $g\circ f$ "flips" $1$ and $2$.

  • OK, now let's start thinking about what we know about $f$ and $g$ from what we've assumed so far. If $g\circ f$ is a bijection, then $f$ must be injective (why?). So our target set $Y$ has at least two distinct elements, $a$ and $b$, with $f(1)=a$ and $f(2)=b$.

  • But $f$ isn't supposed to be surjective. So $Y$ must have at least one more element, say $c$. For simplicity, let's try $Y=\{a, b, c\}$.

  • Now, we're almost done. Do you see how to define a $g$ from $Y$ to $X$ which satisfies all the requirements?

  • $\begingroup$ So $g(a) = 2$ and $g(b) = 1$ because $f(1) = a$ and $f(2) = b$ and we know, since $g \circ f$ is a bijection and not the identity that $g(f(1)) = 2$ and $g(f(2)) = 1$. Does that work? $\endgroup$
    – Stacy
    Dec 7 '15 at 5:37
  • $\begingroup$ @Stacy Yes, but you haven't yet completely defined $g$ - what should $g(c)$ be? $\endgroup$ Dec 7 '15 at 5:37
  • $\begingroup$ $g$ cannot be an injection, so $g(c)$ must be 1 or 2, but what other piece of evidence limits it to being one or the other? $\endgroup$
    – Stacy
    Dec 7 '15 at 5:41
  • $\begingroup$ @Stacy Nothing whatsoever, either choice is fine. But in answering the question, you do have to make a choice (or at least explicitly say that either choice is fine). $\endgroup$ Dec 7 '15 at 6:07

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.