Thread: need help with descrete math please

1. 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!!!

2. Just prove in generality

It is pretty easy to show a lemma that the composition of bijective functions is bijective.

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

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

Injective: Suppose $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 $n=1$, proceed by induction on $n$ to assume $f^n$ is bijective. Then you need only show that $f^{n+1}$ is bijective. Notice $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 $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.

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

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

Since $\circ$ is associative, $f\circ f^{6}=f^{6}\circ f$ is bijective means $f$ is bijective.

4. 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 $f: A \rightarrow B$ so this is not guaranteed. So you are right, induction would fail if $B\not = A$, but hey, the idea is the same, good catch.