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

Printable View

- December 6th 2008, 03:29 PMtukilalaneed 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!!! - December 6th 2008, 10:14 PMGammaJust prove in generality
It is pretty easy to show a lemma that the composition of bijective functions is bijective.

Lemma: If and are bijective functions, then is a bijective function.

Surjective: Let , then c has a unique preimage in B, this point has a unique preimage in A.

Injective: Suppose

So i mean the result is trivial for , proceed by induction on to assume is bijective. Then you need only show that is bijective. Notice 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 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. - December 7th 2008, 07:36 AMclic-clacQuote:

Let f:A->B be a function.

For the other way, when is a function, I agree with you Gamma but I don't see the induction.

Since is associative, is bijective means is bijective. - December 7th 2008, 11:35 AMGammagood 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 so this is not guaranteed. So you are right, induction would fail if , but hey, the idea is the same, good catch.