$f \circ g$ is invertible then f,g both invertible 
*

*Given A a finite set, and f and g functions from A to A, and $f \circ g$ invertible - prove f,g invertible as well.

*Show that if A is infinite, and $f \circ g$ is invertible, f,g aren't necessarily invertible.


Ok, so for 1 I did as following:


*

*$f \circ g$ is invertible, then f is surjective and g is injective.

*to show that f is also injective, I need to show $f(x_1)=f(x_2) \to x_1 = x_2$

*because of defenition - there exist a,b such that $g(a)=x_1$, $g(b)=x_2$

*so, $a=f(g(a))=f(x_1)=f(x_2)=f(g(b))=b$, then g(a)=g(b), then $x_1 = x_2$

*now we know that f is invertible and we have to show that g is invertible.

*$f \circ g$ is invertible, then exists h such that $f \circ g \circ h = Id_A$ is invertible

*$ f^{-1} \circ f \circ g \circ h \circ h^{-1} = f^{-1} \circ Id_A \circ h^{-1}$

*$g = h^{-1} \circ f^{-1}$

*then g is invertible as composition of invertible functions.

*Q.E.D


I'm not sure about this proof, would appreciate your attention and critique.
Second of all I have no idea where to start and in what direction to prove 2 - would appreciate your guiding.
 A: There are some errors: point 3 is false, and it's not necessarily true that in point 4 $a=f(g(a))$. I don't even see where you use the hypotesis that A is finite. You were right saying that $f$ is surjective and $g$ is injective. Since they have domain and codomain A, that is finite, they are necessarily bijective. For example if f weren't injective you would have that $|A| > |f(A)|$ and then f not surjective, leading to an absurd. This is where you use the fact that A is finite, because you can find non injective functions that have the same cardinality between infinte sets, like the function in $\mathbb{N}$ $$0 \mapsto 0$$ $$n \mapsto n-1 \ for \ n\ge 1$$ A similar argument goes for g.
For a counterexample of 2 take $A=\mathbb{N}$ and $g(n)=n+1$ and f the function as above. They are not bijective but their composition is.
A: Here is a counterexample for $2$:
$$f(x)=x^{2}, D_f=\mathbb{R} \ \ \ \ \ \ g(x)=\sqrt{x}, D_g=[0,+\infty)$$
Then $$(f\circ g)(x)=x, D_{f\circ g}=[0,+\infty)$$
$f\circ g$ is invertible while $f$ clearly is not.
A: Another counterexample for $A$ infinite:
Let $A=\mathbb R^{\mathbb N}$ be the vector space of real-valued sequences. Define the two functions
$$g:A\to A, \space (x_1,x_2,x_3,\dots) \mapsto (0,x_1,x_2,x_3,\dots)$$
$$f:A\to A, \space (x_1,x_2,x_3,\dots) \mapsto (x_2,x_3,x_4,\dots)$$
Then we obtain $f \circ g=id_A$ and is hence invertible, but $f$ is not.
A: Basic infinite counterexample: $f:\mathbb N\to\mathbb N$ defined $g(n)=n+1$ as $$f(n)=\begin{cases}0&n=0\\n-1&\text{otherwise}\end{cases}$$
Then $f(g(n))=f(n+1)=n$ is invertible, but $g$ is not surjective and $f$ is not one-to-one.
You can skip a lot of noise in your answer by noticing that if $A$ is finite and $f:A\to A$ is surjective, then it is one-to-one, and like-wise if $g:A\to A$ is one-to-one, then $g$ is surjective. This is only true for finite sets.
