1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

[Discrete Math] f: A->B; surjective? find necessary & sufficient condition.

  1. Feb 21, 2006 #1
    [Discrete Math] f: A-->B; surjective? find necessary & sufficient condition.

    Ok in practice for my discrete exam, I have the following problem.

    Let f : A->B be a function.
    a) Show that if f is surjective, then whenever g o f = h o f holds for the functions g,h : B -> C, then g =h.

    b) Find a necessary and sufficient condition for f such that for any set C and any functions g,h:B->C, if g o f = h o f, then g = h


    I need help at starting this problem. How do I start on a)? Here's what I know,

    g o f : A -> C , so (g o f)(a) = g(f(a)),

    such that (a,c) are elements in g o f <=> [tex]\exists b \in B:(a,b)\in f[/tex], [tex](b,c)\in g[/tex]

    I hope that latex stuff comes out right. Anyways I've got 3 hours to figure this out. I just need a push forward, maybe some hints, or suggestions.
     
    Last edited: Feb 21, 2006
  2. jcsd
  3. Feb 21, 2006 #2

    0rthodontist

    User Avatar
    Science Advisor

    For the first one, prove it by contradiction. If g, h are unequal then there must be some element (b, c) of g that is not an element of h (without loss of generality; it could be the other way around but in that case simply rename h g and rename g h). But since f is onto, what can you say about g o f that you can't say about h o f with regards to (b, c)?
     
  4. Feb 21, 2006 #3
    Here's what I don't understand... When you have g(f)=h(f), obviously g = h...

    As far as proving it by contradiction... If g,h are unequal, then there must be some element (b,c) of g that is not an element of h. But since f is onto, you can say that (b, c) [tex] \in [/tex] g(f), and you can't say (b, c) [tex] \in [/tex] h(f) (I think).
     
  5. Feb 21, 2006 #4

    0rthodontist

    User Avatar
    Science Advisor

    No, you're wrong. Here's the problem:
    Let A = {1, 2}, let B = {3, 4}, and let C = {5, 6}
    Let f = {(1, 3), (2, 3)}
    g = {(3, 5), (4, 5)}
    h = {(3, 5), (4, 6)}
    Now is it true that g o f = h o f here? And is it true that g = h? Do you understand why not?
     
  6. Feb 21, 2006 #5
    What's g(f) and h(f), I don't understand how to show g(f) and h(f) using sets.

    g != h
     
  7. Feb 21, 2006 #6

    0rthodontist

    User Avatar
    Science Advisor

    Do you know about the definition of functions as sets of ordered pairs?
     
  8. Feb 21, 2006 #7
    (a,b) in f, is f(a)=b? like that?
     
  9. Feb 21, 2006 #8

    0rthodontist

    User Avatar
    Science Advisor

    Yes, so can you figure out what functional composition looks like for ordered pairs?
     
  10. Feb 21, 2006 #9
    Something like
    g(f(a))=g(b)=c (a,c)
    But somebody is going to have to give me an example of using the sets A, B, C, because I'm drawing a blank as to how the hell to get g(f(a))=g(b)=c by replacing the a's, b's, c's with the numbers in the sets...
     
  11. Feb 21, 2006 #10

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    No need to look at it as ordered pairs. Work by contradiction though. Suppose g and h are unequal, even though f is surjective and (g o f) = (h o f). Then by definition of equality of functions, there is some b in B such that:

    g(b) != h(b)

    But for all b in B, there is an a in A such that f(a) = b, since f is surjective, so there is some a in A such that:

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

    By definition of composition, this means that there is some a such that:

    (g o f)(a) != (h o f)(a)

    By definition of equality of functions, this means that

    (g o f) != (h o f)

    contradiction.

    For part ii), look at why a surjective f makes [(g o f) = (h o f)] imply [g = h]. It's because if f weren't surjective, then there could be some element of B, call it b, which f doesn't reach, but which g and h differ on. If g and h differ on b, then g != h, but if f never reaches b, then as long as g and h agree on Im(f), (g o f) = (h o f). So what is the necessary and sufficient condition on f such that (g o f) = (h o f) implies g = h? It's that g and h don't differ on B - Im(f). So either Im(f) = B (that is, f is surjective), or |C| < 2, making it impossible to differ no matter how big B is and no matter how small Im(f) is.
     
  12. Feb 22, 2006 #11

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    I would go further than AKG: please don't think about functions as ordered pairs, I implore you.

    As for the second part of the question, think about it as word association.

    Right cancellation is to surjective as left cancellation is to...

    can only be one thing, really. Now prove it.

    Can I give another example?

    Suppose that f maps into the set {0,1}, and suppose that it isn't surjective, well, that just means that f(x)=0 for all x (or f(x)=1 for all x, doesn't matter which).

    Now, I can make g and h whatever the hell I feel like and gf(x)=g(0) and hf(x)=h(0) for all x.

    So I am free to make g(0)=h(0) and we get gf=hf, and I'm free to make g(1) and h(1) completely different. (This is AKG's 'parts that f doesn't reach').

    This shows that right cancellation implies f is surjective, it is up to you to prove the opposite thing.
     
  13. Feb 22, 2006 #12

    0rthodontist

    User Avatar
    Science Advisor

    Well, you're saying the same thing. Equality of functions is just equality of sets.

    There is sometimes an advantage to looking at functions as ordered pairs. I am taking formal language theory and we see that an automaton Q, sigma, delta, q0, F can be represented as a graph where the edges correspond to ordered pairs in the function delta. function = ordered pairs = edges of a graph. That would not have been as clear without the ordered pair concept.
     
  14. Feb 22, 2006 #13

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    Of course it is technically saying the same thing, but the whole point is that looking at them as ordered pairs is a poor way to look at them. Looking at them as edges of a graph is an even worse way to look at them. The goal here was to prove some property of surjective functions, not to think up all possible ways to regard functions.
     
  15. Feb 22, 2006 #14

    0rthodontist

    User Avatar
    Science Advisor

    In finite automata it seems that visualization as graphs is really the best way to think about the automata, from an intuitive perspective. I'm not saying you need to explicitly think about ordered pairs in this problem but it is not entirely useless. It seems to me that the best way to think about easy function problems like this is in terms of domain-codomain diagrams, where the idea of images and preimages gets close to ordered pairs.

    Anyway, it's simple to give counterexamples in the notation of ordered pairs. You could organize it as a table, but why bother. The notation is there, it only takes a minute to learn if he doesn't already know it, and he may run into it later.
     
    Last edited: Feb 22, 2006
  16. Feb 22, 2006 #15

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    I agree that thinking in terms of domain-codomain diagrams with pictures of images and preimages is a good, if not natural way to think about these problems. If you believe that ordered pairs, graphs, or automata (whatever those may be) are somehow easier, more intuitive, more effective, or at all necessary, then go ahead and believe it, but I don't think you'll convince me. It's simple to give a counterexample in any notation, I would bet, but in which "notation" is it easiest to think of a counterexample?
     
  17. Feb 23, 2006 #16

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    If you think only in terms of ordered pairs to describe functions then the number of functions you can actually work with reasonably is vanishingly small.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?