MHB Marcus 's question at Yahoo Answers (Bijectivity on finite and infinite sets)

[Fernando Revilla]

Here is the question:

Supposed that A is a finite set, f: A --> A and g: A --> A. Supposed in addition that f o g: A --> A is a bijection. Prove that f and g are both bijections.
Give an explicit example to show that the conclusions of the previous problem is false if A is an infinite set. In other words, if A is an infinite set, f: A --> A and g: A --> A are functions and f o g: A --> A is a bijection it is not necessarily the case that f and g are both bijections.

Here is a link to the question:

Abstract math question: bijectivity on finite and infinite sets? - Yahoo! Answers

I have posted a link there to this topic so the OP can find my response.

 

[Fernando Revilla]

Hello Marcus,

For a finite set $A$, any map $h:A\to A$ is injective iff it is surjective iff it is bijective. Suppose $f\circ g$ is a bijecion. Let us see that $g$ is injective $$g(x)=g(y)\Rightarrow f[g(x)]=f[g(y)]=(f\circ g)(x)=(f\circ g)(y)\Rightarrow x=y$$ That is, $g$ is injective which implies ($A$ finite) that $g$ is a bijection. Now, $$f=f\circ (g\circ g^{-1})=(f\circ g)\circ g^{-1}$$ and the composition of bijections is a bijection.

For $A$ infinite, consider $A=\mathbb{Z}$, and let

$$f:A\to A\;,\quad f(x)=\left\lfloor\frac{x}{2}\right\rfloor\\g:A\to A,\;\quad g(x)=2x$$ Then, $$(f\circ g)(x)=f(2x)=\left\lfloor\frac{2x}{2}\right\rfloor=x$$ is the identity, so $f\circ g$ is a bijection, but $f$ is not injective, for example $f(0)=f(1)=0$.

If you have further questions, you can post them in the http://www.mathhelpboards.com/f15/ section.