Results 1 to 4 of 4

Thread: 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 $\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.
    Last edited by Gamma; Dec 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, $\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.
    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 $\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.
    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: Feb 14th 2011, 02:31 AM
  3. Replies: 1
    Last Post: Jun 19th 2010, 10:05 PM
  4. Replies: 1
    Last Post: Jun 2nd 2010, 09:49 AM
  5. descrete math
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: Oct 13th 2008, 08:41 PM

Search Tags


/mathhelpforum @mathhelpforum