Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Denumerable set and surjective function

  1. Oct 19, 2011 #1
    This is the problem:

    "Prove that if A is denumerable and there exists a g: A -> B that is surjective, then there exists an h: B -> A so that h is injective."

    So I've started it as:

    Suppose a set A is denumerable and a function f: A-> B is surjective. Since there exists a surjective function f: A-> B and A is denumerable, B is countable..."

    I'm a little stuck here. Any ideas?
     
  2. jcsd
  3. Oct 20, 2011 #2
    Any ideas?
     
  4. Oct 20, 2011 #3
    I'm really stuck guys :frown:
     
  5. Oct 20, 2011 #4

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Try to explicitely define h. You won't need anywhere that A and B are denumerable.

    Try to define h as some kind of "inverse" of g.
     
  6. Oct 20, 2011 #5

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    Try a simpler problem first, replacing the assumption "A is denumerable" with "A = N, the set of natural numbers." If you have surjection g : N --> B, you can explicitly define an injection h : B --> N in terms of g. See if you can figure that out first.
     
  7. Oct 20, 2011 #6
    Good idea.

    How about something like this:

    Suppose there exists a function f: N -> B for some set B. Then, for all b in B, there exists an n in N such that f(n) = b. Define h: B-> A as the function that maps all b in B to a single n in N such that h(b) = n. Since f is surjective, there exists such a function. Since h(b') = h(b) = n iff b' =/= b, h is injective.

    Am I on the right track?
     
  8. Oct 20, 2011 #7

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    Great. For each b, there might be a number of different n's you could choose. How might you explicitly choose one of those n's from amongst all the possible choices, if you had to?
    This isn't quite right, perhaps a typo?
    Yes.
     
  9. Oct 20, 2011 #8
    Perhaps an n such that if f(n) = f(n') = b, n=n'?

    Not a typo, just brainstorming. :redface:
     
  10. Oct 20, 2011 #9

    disregardthat

    User Avatar
    Science Advisor

    How may you explicitly choose an element from a subset of the natural numbers?

    You can use the axiom of choice, or a much easier method which you probably are familiar with.
     
  11. Oct 20, 2011 #10
    The well-ordering principle?
     
  12. Oct 21, 2011 #11
    Quick question, can I assume A = N without loss of generality?
     
  13. Oct 21, 2011 #12

    disregardthat

    User Avatar
    Science Advisor

    Why wonder when you can just pick the smallest one?

    You can assume A = N if you are comfortable with the proof of how it applies generally (hint: A is in bijection with N).
     
  14. Oct 21, 2011 #13
    I'm not sure if we have gone over the theorem that states that every subset of N has a smallest element, is it related to the well-ordering principle?

    So perhaps something like this:

    Suppose there exists a function f: N -> B for some set B. Then, for all b[itex]\in[/itex]B, there exists an n[itex]\in[/itex]N such that f(n) = b. Define h: B-> N as the function f(b) = n' where for all b[itex]\in[/itex]B, n'[itex]\in[/itex]N' is the smallest element of some N'[itex]\subseteq[/itex]N. Thus, h is injective.
     
  15. Oct 21, 2011 #14

    disregardthat

    User Avatar
    Science Advisor

    Well, it's obvious isn't it? If n is a number in a subset A of N, then one of 1,2,3,...,n is the smallest element of the set. Prove: Every subset of the natural numbers containing the number n has a smallest element, by induction on n.

    There is something weird about defining h(b) = n', where n' is the smallest element of some subset N' of N. You must specify this subset, or else h is not well-defined (it can't be any arbitrary set). I suggest you define N' = f^(-1)(b) (= the set {n in N : f(n) = b}). Then you can show injectiveness.
     
  16. Oct 21, 2011 #15
    Ah, I think I have seen that before. In light of this, does the proof I provided above work?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook