2
$\begingroup$

Let $X,Y$ be nonempty sets and $f:X\to Y$ be a function.

Show that if there is a function $g:Y\to X$ such that $g\circ f$ is the identity function on $X$, then $f$ is one to one.

My approach is by using a contradiction and suppose that $f$ is not one-one. Then I divided into two cases where $f$ is not one-one but onto and $f$ is one-one but NOT onto.

Case 1: Suppose f is not one-one but onto. We can show that the number of elements in $X$ is strictly larger than the number of elements in $Y$. But there will be no such function $g:Y\to X$ such that $g\circ f$ is the identity function on $X$, a contradiction.

My question:

  1. I am not sure how to proceed with the second case.
  2. How to show more rigorously in the first case that "the number of elements in $X$ is strictly larger than the number of elements in $Y$" and "there will be no such function $g$". I assumed it is intuitive, I am not sure whether I am correct and if so can we show it more rigorously?
  3. Is there any other way besides using contradiction and separating into cases?

Helps are greatly appreciated. Many thanks!

$\endgroup$
2
$\begingroup$

I will answer your questions out of order.

2 . The number of elements in $X$ does not have to be strictly greater than the number of elements in $Y$ if $X$ and $Y$ are infinite.

3 . Suppose that $f(x)=f(y)$. Then $g\circ f(x)=g\circ f(y)$. But since $g\circ f$ is the identity, $x=g\circ f(x)=g\circ f(y)=y$. Thus $x=y$, so $f$ is injective.

1 . See my answer for 3.

$\endgroup$

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.