# need help with descrete math please

• Dec 6th 2008, 02:29 PM
tukilala
need help with descrete math please

Let f:A->B be a function. Prove that f^7 = f°f°f°f°f°f°f is a bijection if and only if f is a bijection.

help meeeeeeeeeeeeeee, thnx!!!
• Dec 6th 2008, 09:14 PM
Gamma
Just prove in generality
It is pretty easy to show a lemma that the composition of bijective functions is bijective.

Lemma: If $\displaystyle f: A \rightarrow B$ and $\displaystyle g: B \rightarrow C$ are bijective functions, then $\displaystyle g\circ f: A \rightarrow C$ is a bijective function.

Surjective: Let $\displaystyle c\in C$, then c has a unique preimage in B, this point has a unique preimage in A. $\displaystyle g\circ f(f^{-1}(g^{-1}(c))=c$

Injective: Suppose $\displaystyle g\circ f (x)=g\circ f (y) \Rightarrow f^{-1}(g^{-1}(g\circ f (x))=f^{-1}(g^{-1}(g\circ f (y)) \Rightarrow x=y$

So i mean the result is trivial for $\displaystyle n=1$, proceed by induction on $\displaystyle n$ to assume $\displaystyle f^n$ is bijective. Then you need only show that $\displaystyle f^{n+1}$ is bijective. Notice $\displaystyle f^{n+1}=f^n \circ f$ which is the composition of bijective functions, so by the lemma you have shown that if you compose the same function n times it is still bijective. 7 is a natural number, so you are done.

The other way you can do the same thing by induction and noticing that if you have $\displaystyle f \circ g$ and it is bijective, the second function g must be surjective (onto) and the first function f must be injective (1-1) since in this case these functions are the same, f is bijective.
• Dec 7th 2008, 06:36 AM
clic-clac
Quote:

Let f:A->B be a function.
Most of the time, $\displaystyle f^{2}$ isn't a function!

For the other way, when $\displaystyle f^{7}$ is a function, I agree with you Gamma but I don't see the induction.

Since $\displaystyle \circ$ is associative, $\displaystyle f\circ f^{6}=f^{6}\circ f$ is bijective means $\displaystyle f$ is bijective.
• Dec 7th 2008, 10:35 AM
Gamma
good point
yeah, that's a good point, I guess I just assumed we were talking about functions with a codomain the same as the domain, but in the statement of the problem it does say $\displaystyle f: A \rightarrow B$ so this is not guaranteed. So you are right, induction would fail if $\displaystyle B\not = A$, but hey, the idea is the same, good catch.