Results 1 to 15 of 15

Math Help - functions between sets

  1. #1
    Newbie
    Joined
    Jan 2009
    From
    Phoenix, Arizona
    Posts
    17

    functions between sets

    I need help with the following proof,

    Let f: maps S to T and g: maps T to U.
    1. If f and g are injective then gf (composition) is injective
    2. If f and g are surjective then gf is surjective
    3. If f and g are bijective then g*f is bijective.

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,407
    (1) Let a, b \in S such that: g (f(a)) = g(f(b))

    Since g is injective, this implies: f(a) = f(b)

    Since f is injective, ... you get the idea?

    ______________

    (2) Let u \in U. Since g is surjective, we know that \exists t \in T such that g(t) = u. Also, since f is surjective, we know that \exists s \in S such that f(s) = t

    Now consider g(f(s)).

    ______________

    (3) Try to remember what it means for a function to be bijective.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2009
    From
    Phoenix, Arizona
    Posts
    17
    So on #1, the next logical step would be a=b, which should prove #1.

    On #2, then g(f(s))=g(t)=u. So all I had to do was prove that g(f(s))=u?

    On #3, so if I've proved that it is injective and surjective then it is bijective by definition? If this is true, them I'm making this way more difficult than it needs to be. If not I guess I still do not get it.

    Thanks for your help, I have quite a few more questions. I'm just starting the class and I'm just not getting some of this.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,407
    #1: Yes, because we know f is injective.

    #2: Isn't that what it means for a function to be surjective by definition? We've shown that for an arbitrary element in U, there exists some element in S such that u = g(f(s)).

    #3: Just go by definition.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Dec 2008
    Posts
    130
    Quote Originally Posted by Eagle3 View Post
    I need help with the following proof,

    Let f: maps S to T and g: maps T to U.
    1. If f and g are injective then gf (composition) is injective
    2. If f and g are surjective then gf is surjective
    3. If f and g are bijective then g*f is bijective.

    Thanks
    rename sets A, B , C for simplicity:
    for 1, let a1, a2 in A. since f is 1-1 => f(a1)=/=f(a2) and g is 1-1 => g(f(a1))=/=g(f(a2)). therefore, gf(a1)=/= gf(a2). QED

    for 2, we show forall c in C there exists a in A s.t. gf(a)=c. let c in C. g is onto => there exists b in B s.t. g(b)=c. f is onto => there exists a in A s.t. f(a)=b => therefore gf(a)=g(b)=c. therefore gof is onto. QED
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Jan 2009
    From
    Phoenix, Arizona
    Posts
    17
    Here is what I was trying to do for #1.
    f:A to B and g:B to C
    x an element of A, y an element of B, and z an element of C
    if f is injective, then f(x)=f(y) which means x=y
    if g is injective, then g(y)=g(z) which means y=z
    based on the transitive property if x=y and y=z, then x=z
    therefore, g(f(x)) would also be an injection because f(x)=g(z) and x=z which has been shown to be true.

    This is why I was having so much trouble with surjective and bijective.

    Can you help me get started with this one?
    if p is prime and p|a and p|(a^2+b^2) prove or disprove p|b
    I have looked for a counterexample and can not find one, I'm going to assume it is true.

    Thanks again, trying to do this course on-line my be more than I bargained for.

    I really appreciate your help
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Jan 2009
    From
    Phoenix, Arizona
    Posts
    17
    Thanks for your help, it never ceases to amaze me how many different ways there are to do this and how much more difficult I can make it without really trying. What does =/= mean?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Dec 2008
    Posts
    130
    Quote Originally Posted by Eagle3 View Post
    Thanks for your help, it never ceases to amaze me how many different ways there are to do this and how much more difficult I can make it without really trying. What does =/= mean?

    not equal
    Follow Math Help Forum on Facebook and Google+

  9. #9
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,407
    Some facts:
    • If a \mid b, then a \mid kb for all k \in \mathbb{Z}. (In words, if  a \mid b, then a divides all of the multiples of b )
    • If a \mid b and a \mid c, then a \mid (b + c)
    • If p \mid ab where p is prime, then either p \mid a or p \mid b


    Since p \mid a and p \mid (a^2 + b^2), then p \mid (a^2 + b^2 - a^2) \Leftrightarrow p \mid b^2 (try to see how the first two facts apply here).

    Then finish it off with the third fact.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Jan 2009
    From
    Phoenix, Arizona
    Posts
    17
    Thanks, I've never seen it written that way.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Newbie
    Joined
    Jan 2009
    From
    Phoenix, Arizona
    Posts
    17

    o_O

    The part I do not understand now is are you using the second bullet to justify subtracting a^2. That is the step I would have never thought to do. Since, p|b^2 then p|bb and therefore p|b since p must divide one of the two.

    Thank you very much.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,407
    Using the first bullet, we have that: p \mid a^2 (imagine k = a).

    Using the second bullet, since we know p \mid (a^2 + b^2) and p \mid a^2, then p divides their difference.

    Then the conclusion follows as you have written.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Newbie
    Joined
    Jan 2009
    From
    Phoenix, Arizona
    Posts
    17
    Ok, I now understand how to prove that p|(a+b) and p|(a-b), what I'm still having trouble with is how I would know that p divides the difference. Is if merely because if it divides the sum it will divide the difference?
    Follow Math Help Forum on Facebook and Google+

  14. #14
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,407
    Does it help if I write it like this: (a^2 + b^2) - a^2 \ = \ (a^2 + b^2) {\color{red} \ + \ } (-a^2)

    We know p \mid (a^2 + b^2) and p \mid (-a^2) (imagine k = -a if that helps).
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Newbie
    Joined
    Jan 2009
    From
    Phoenix, Arizona
    Posts
    17
    Ok, now I really understand what you meant by a|b and a|c, then a|(b+c). I had to go back and read it a second time before it clicked.

    Thanks again you are a great teacher.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Sets and functions
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 2nd 2010, 09:51 PM
  2. a little bit of functions on sets
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: October 15th 2008, 06:06 PM
  3. Sets/Functions
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 6th 2007, 12:39 PM
  4. More sets and functions
    Posted in the Discrete Math Forum
    Replies: 14
    Last Post: August 24th 2007, 11:08 AM
  5. Sets and functions
    Posted in the Discrete Math Forum
    Replies: 12
    Last Post: August 21st 2007, 04:24 PM

Search Tags


/mathhelpforum @mathhelpforum