Give an example of sets $X,Y$ and functions $f:X→Y$ and $g:Y →X$ such that $g \circ f = id_X$ Give an example of sets $X,Y$ and functions $f:X→Y$ and $g:Y →X$ such that $g \circ f = id_X$ but $f$ is not invertible, and $id_X$ is the identity function of $x$.
I am not sure how to even start this problem, because I do not know how to make up two function $f$ and $g$ such that $g \circ f = id_X$. Is there a key to creating functions such that this would be true?
 A: The conditions require $f$ to be one-to-one, an injection $X \to Y$. Let $X = Y = \mathbb{N}$, and $f(n) = n + 1$ for all $n \in \mathbb{N}$. Now define $g(m) = m - 1$ if $m > 0$, and $g(0) = 0$.
A: *

*$f$ has to be injective, because otherwise there would exist distinct $x,x' \in X$ such that $f(x)=f(x')$, and hence $g(f(x))=g(f(x'))$, implying $x=x'$, a contradiction.  

*Hence $f$ can't be surjective, because if it was then $f$ would be a bijection, and hence invertible.  


What's the simplest way this can happen? Make $X=\{a\}$ and $Y=\{b,c\}$. Define $f(a)=b$ and $g(b)=g(c)=a$. Then we claim $g \circ f = id_{X}$. Well, we just need to check $(g \circ f)(a)=a$. But that's easy: $g(f(a))=g(b)=a$. Done.  
Such a $g$ will always exist if $f$ is injective. Why? Well being injective means that if we know $f(x)$, we can find $x$. In other words there is a function $h$ from the set $\{f(x) | x \in X\}\subset Y$ (the image of $f$), to $X$, which sends $f(x)$ to $x$. The condition of injectivity is precisely that this function $h$ is well-defined.  
But that hasn't quite answered the question, because we wanted a function $g :Y \to X$. So we need to define $g$ on all the points of $Y$ that $f$ doesn't hit. But who cares! $g \circ f$ doesn't 'see' points in $Y$ which aren't in the image of $f$. So define $g$ to be whatever you like there. (Note that if $Y$ has at least one point not in the image of $f$, and $X$ has more than one point, then the choice of $g$ will not be unique).
