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:
- I am not sure how to proceed with the second case.
- 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?
- Is there any other way besides using contradiction and separating into cases?
Helps are greatly appreciated. Many thanks!
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.