Results 1 to 4 of 4

Math Help - need help with descrete math please

  1. #1
    Junior Member
    Joined
    Nov 2008
    Posts
    50

    need help with descrete math please



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


    help meeeeeeeeeeeeeee, thnx!!!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Gamma's Avatar
    Joined
    Dec 2008
    From
    Iowa City, IA
    Posts
    517

    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.
    Last edited by Gamma; December 6th 2008 at 11:25 PM. Reason: Oops didn't realize you had to show the other direction too, and fixed vagueness of 1st and 2nd fcn.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member Gamma's Avatar
    Joined
    Dec 2008
    From
    Iowa City, IA
    Posts
    517

    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: May 29th 2011, 12:57 AM
  2. Replies: 2
    Last Post: February 14th 2011, 02:31 AM
  3. Replies: 1
    Last Post: June 19th 2010, 10:05 PM
  4. Replies: 1
    Last Post: June 2nd 2010, 09:49 AM
  5. descrete math
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: October 13th 2008, 08:41 PM

Search Tags


/mathhelpforum @mathhelpforum