need help with descrete math please

**tukilala** · December 6th 2008, 02:29 PM

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

**Gamma** · December 6th 2008, 09:14 PM

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.

**clic-clac** · December 7th 2008, 06:36 AM

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.

**Gamma** · December 7th 2008, 10:35 AM

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.

Thread: need help with descrete math please

LinkBack

Thread Tools

Display

need help with descrete math please

Just prove in generality

good point

Similar Math Help Forum Discussions

Show that every Moore space of cardinality \leqslant [MATH]c[/MATH] has a countable s

Cayley Diagram for [math]A_{4}[/math] with 12 elements - Carter Ex 4.6(c) page 54

Finding the [MATH][/MATH] tags generator button in post menu??

Find the radius of convergence for the power series [MATH][/MATH] n=1, infinite (2x+1

descrete math

Search Tags