Results 1 to 15 of 15

Math Help - Prove onto and one-to-one

  1. #1
    Newbie
    Joined
    Jan 2011
    Posts
    16

    Question Prove onto and one-to-one

    I've been struggling with the compositions and injection/surjection so I borrowed a book from my professor and I was using both books to teach myself. I've gotten considerably better at the application of the onto and one-to-one (i.e. actually composing two functions and determining whether it's onto, one-to-one, or both/neither) ... The next portion of the excercise has me a bit stumped, it's a more abstract concept which requires me to prove ....


    Suppose f, g, and h are all mappings of a set A into itself.

    (a) Prove that if g is onto and f \circ g = h \circ g, then f = h.

    (b) Prove that if f is one-to-one and f \circ g = f \circ h, then g = h.

    I've been memorizing the definitions for injection, surjection, and image as well as a few others but I'm having a really hard time visualizing these and I think that's why I'm not able to prove them. Thanks for any help you guys can provide!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Quote Originally Posted by imind View Post
    I've been struggling with the compositions and injection/surjection so I borrowed a book from my professor and I was using both books to teach myself. I've gotten considerably better at the application of the onto and one-to-one (i.e. actually composing two functions and determining whether it's onto, one-to-one, or both/neither) ... The next portion of the excercise has me a bit stumped, it's a more abstract concept which requires me to prove ....


    Suppose f, g, and h are all mappings of a set A into itself.

    (a) Prove that if g is onto and f \circ g = h \circ g, then f = h.

    (b) Prove that if f is one-to-one and f \circ g = f \circ h, then g = h.

    I've been memorizing the definitions for injection, surjection, and image as well as a few others but I'm having a really hard time visualizing these and I think that's why I'm not able to prove them. Thanks for any help you guys can provide!
    For a, try a proof by contradiction.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor FernandoRevilla's Avatar
    Joined
    Nov 2010
    From
    Madrid, Spain
    Posts
    2,162
    Thanks
    45
    (b)

    For all x\in A :

    f[g(x)]=f[h(x)]

    Now, apply that f is one to one.


    Fernando Revilla
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    I suggest part a) be done directly.
    If z\in A then \left( {\exists t \in A} \right)\left[ {g(t) = z} \right]. WHY?

    So that means that f(z)=h(z) for all z\in A. HOW?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Jan 2011
    Posts
    16
    Heh, Thanks for the help .. working on part a I've got the following and I'm kind of stuck as to where to go from here ... reminder, my issue is the overall lack of knowledge of "why" things are what they are ... I'm really having issues with understanding what exactly "onto-ness" means from an abstract concept ... here is what I've got so far:

    Suppose f, g, and h are all mappings of a set A into itself.

    a) Prove that if g is onto and f \circ g = h \circ g, then f = h

    By Contradiction:
    If g is onto and f \circ g=h \circ g; then f \neq h

    Proof:
    let f:A \rightarrow A and g:A \rightarrow A
    so the composition of f \circ g : A \rightarrow A
    Suppose \exists a \in A
    since g is onto,
    \exists b \in A \mid f(b)=a

    I'm not really sure where to go next ... I think I need to show that since fog and hog are equal there exists f(b)=a but that can't work cause f doesn't equal h ... does that look right? ... If it is I'm not really sure what it's saying and if anyone could show me an example I'd greatly appreciate it....
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Quote Originally Posted by imind View Post
    Heh, Thanks for the help .. working on part a I've got the following and I'm kind of stuck as to where to go from here ... reminder, my issue is the overall lack of knowledge of "why" things are what they are ... I'm really having issues with understanding what exactly "onto-ness" means from an abstract concept ... here is what I've got so far:

    Suppose f, g, and h are all mappings of a set A into itself.

    a) Prove that if g is onto and f \circ g = h \circ g, then f = h

    By Contradiction:
    If g is onto and f \circ g=h \circ g; then f \neq h

    Proof:
    let f:A \rightarrow A and g:A \rightarrow A
    so the composition of f \circ g : A \rightarrow A
    Suppose \exists a \in A
    since g is onto,
    \exists b \in A \mid f(b)=a

    I'm not really sure where to go next ... I think I need to show that since fog and hog are equal there exists f(b)=a but that can't work cause f doesn't equal h ... does that look right? ... If it is I'm not really sure what it's saying and if anyone could show me an example I'd greatly appreciate it....
    f(b) = h(b)

    For all b in B, there is an a in A such that g(a) = b. Since g is surjective, there is an a in A such that,

    f(g(a)) = h(g(a))

    .....
    Last edited by dwsmith; January 28th 2011 at 05:53 PM. Reason: wrong letters
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Jan 2011
    Posts
    16
    So final answer ...

    Suppose f, g, and h are all mappings of a set A into itself.

    a) Prove that if g is onto and f \circ g = h \circ g, then f = h

    By Contradiction:
    If g is onto and f \circ g=h \circ g; then f \neq h

    Proof:
    let f:A \rightarrow A and g:A \rightarrow A
    so the composition of f \circ g : A \rightarrow A
    Suppose \exists a \in A
    since g is onto,
    \exists b \in A \mid f(b)=a
    By definition f \circ g = h \circ g
    thus f(b) = h(b)
    therefore f = h which is a contradiction


    Does that look right dwsmith or should I alter it some? Now I'm trying to understand exactly what this is saying .. since the image under f and the image under h are equal the functions f and h must be equal? I'm going to move on and work on part b now, thanks so far for the help guys ... I had no idea there was a resource as good as this website out there, I may have to stick around
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Jan 2011
    Posts
    71
    I think you mean something more like "let a\in A" instead of "suppose \exists a\in A" (I guess if A is actually empty then the problem is vacuously true). Also, I think you mean that there exists a b\in A such that g(b)=a, not f(b)=a, since g is the only function assumed to be onto.

    I'd like to reiterate Plato's suggestion to just prove (a) directly. If you look at your proof it basically contains such a direct proof, although the last couple of lines could probably use some more justification. Maybe something like:

    Let a\in A. Since g is onto, there is some b\in A such that g(b)=a. Now, f(a)=f(g(b))=...

    As far as what "onto-ness" means, it just says that everything in the codomain/target space, or whatever you call it (the B in f:A\rightarrow B) gets hit by something from A when it gets run through the function.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Jan 2011
    Posts
    16
    Suppose f, g, and h are all mappings of a set A into itself.

    a) Prove that if g is onto and f \circ g = h \circ g, then f = h

    By Contradiction:
    If g is onto and f \circ g=h \circ g; then f \neq h

    Proof:
    let f:A \rightarrow A and g:A \rightarrow A
    so the composition of f \circ g : A \rightarrow A
    Suppose \exists a \in A
    since g is onto,
    \exists b \in A \mid g(b)=a
    By definition f \circ g = h \circ g
    thus f(a)=f(g(b))=h(g(b))
    therefore f = h and we arrive at a contradiction

    I corrected a few of the things you pointed out does that look better? The way our professor likes stuff is similar to the way I wrote it out here so for consistency I just try to learn it that way ... helps for regurgitation

    as for part b what do you think about the following

    for an arbitrary x in a .. by definition f(g(x)) = f(h(x)) and f is one-to-one then g(x) = h(x) so g must equal h

    how does that look logic wise?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Junior Member
    Joined
    Jan 2011
    Posts
    71
    Well, the only thing about saying just "suppose there exists an a in A" is that it isn't really supposing much. Unless A is empty then there is an a\in A. So what? I'm probably nitpicking, but "if a\in A", "for any a\in A", or just "suppose a\in A" all seem more natural.

    Your statement right before the proof is a little awkward too. The way it's worded makes it look like you're claiming to prove that f\neq h. Another minor thing: you need to show that f(a)=h(a) for all a\in A, so your last line should end with =h(a). Of course, g(b)=a so it does follow immediately, but you should still write it.

    Aside from that it looks good, but if you just start with the line "Suppose a\in A" and then chop off the last sentence, you have a direct proof.

    The proof of part b looks good.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Newbie
    Joined
    Jan 2011
    Posts
    16
    Thanks a ton... I'll add the b part a bit later today. If anyone has any other onto/one-to-one problems from some of there texts I'd greatly appreciate seeing them so I can really make sure I'm understanding this stuff. Were starting inverses next week which from reading ahead means we need to be able to understand onto and one-to-one which I'm guessing he'll cover also... Hoping to stay ahead haha
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771

    Problems about injections and surjections

    If anyone has any other onto/one-to-one problems from some of there texts I'd greatly appreciate seeing them so I can really make sure I'm understanding this stuff.
    First, there are these relatively simple facts.

    Proposition 1. If f o g is onto, then so is f.

    Proposition 2. If f o g is one-to-one, then so is g.

    Proposition 3. If f o g is onto and f is one-to-one, then g is onto.

    Proposition 4. Let h, s be functions from natural numbers to natural numbers, and suppose that s is not onto. Then h o s o h is not an identity.

    It is easy to deduce this claim from the first three. However, if we know, for example, that s(x)\ne 0 for all x, then it is possible to explicitly provide three numbers x_1,x_2,x_3 such that (h\circ s\circ h)(x_i)\ne x_i for some i=1,2,3. This requires some ingenuity.

    Next, the converse of the claims in the OP also holds.

    Proposition 5. Let f : A -> B. Then the following statements are equivalent.
    (1) f is onto.
    (2) For any set C and any g, h : B -> C, if g o f = h o f, then g = h.

    Proposition 6. Let f : A -> B where |B| > 1. Then the following statements are equivalent.
    (1) f is onto.
    (2) For any g : B -> B, if g o f = f, then g is an identity function.

    Proposition 7. Let f : A -> B. Then the following statements are equivalent.
    (1) f is one-to-one.
    (2) For any set C and any g, h : C -> A, if f o g = f o h, then g = h.

    Finally, if you you really want to improve your one-to-one kung fu, then here is another problem. Suppose that eq : E -> Y and g, h : Y -> Z.



    Definition. The function eq is called an equalizer of f and g if the following two conditions hold.
    (1) f\circ eq = g\circ eq.
    (2) For any y\in Y, if f(y) = g(y), then there exists a unique x\in E such that eq(x) = y.

    In other words, f(eq(x)) = g(eq(x)) for all x\in E, and if f(y) = g(y), that's only because y is the image of one and only one x\in E.

    Proposition 8. If eq is an equalizer, then it in one-to-one.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Newbie
    Joined
    Jan 2011
    Posts
    16
    thanks emakarov ... I'm pretty sure I can do the first 3 so I'm going to get started
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Newbie
    Joined
    Jan 2011
    Posts
    16
    Proposition 1:

    Let g: A -> B and f: B ->. Prove that f is onto if fog is onto

    outline Proof:

    The composition fog maps A -> C and fog is onto
    Thus for c in C there exists a in A such that fog (a) = f(g(a)) = c

    Do I need to move to since every element in B is an image under g there exists g(a) = b and then show that f(b) = c proving that f is onto? can I do it in that order?


    I'm kinda stuck on the proposition 2 ... I think I need to use 2 elements but I'm not sure where I need to go with it ... I think I got 5-7 though ... Thanks for the help guys ... Snow day tomorrow so I think I'm going to work on tackling Left/Right inverses and permutations! Let me know if you see any errors or better ways for me to get to my solution
    Follow Math Help Forum on Facebook and Google+

  15. #15
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771
    every element in B is an image under g
    This is false; it is not assumed that g is onto. However, you don't need to consider every element of B. For a given c, you have constructed a specific element b = g(a) and showed that c = f(b). Thus, you have proved that every c in C is the image of some b in B, i.e., that f is onto.

    Concerning problem 2, the intuitive idea is the following. Suppose you need to encode a message in two stages. In the first, you replace each letter by a number. If you replace two different letters with the same number, then regardless of the second stage, these letters will be indistinguishable in the resulting code. So my first idea was to use proof by contradiction. Suppose g is not injective; then there exist distinct a1, a2 such that g(a1) = g(a2). Therefore, f(g(a1)) = f(g(a2)), which contradicts the fact that f o g is one-to-one. However, there is an even easier direct proof. Suppose g(a1) = g(a2). Then f(g(a1)) = f(g(a2)) and, since f o g is one-to-one, a1 = a2.

    For other problems, it is probably better to start new threads.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prove that
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: May 21st 2010, 05:48 AM
  2. Prove n^2<= ......
    Posted in the Advanced Algebra Forum
    Replies: 12
    Last Post: November 17th 2009, 05:52 AM
  3. Replies: 2
    Last Post: August 28th 2009, 02:59 AM
  4. prove that
    Posted in the Algebra Forum
    Replies: 4
    Last Post: September 7th 2008, 05:14 PM
  5. prove
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 7th 2008, 01:45 PM

Search Tags


/mathhelpforum @mathhelpforum