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

Proof of a Countability Theorem

  1. Nov 28, 2007 #1
    Hey all,

    Can anyone prove this theorem?

    Let N (natural numbers) ---> X be an onto function. Then X is countable.

    I've been staring at it for 3 hours and really can't come up with anything. Any help?
     
  2. jcsd
  3. Nov 28, 2007 #2
    Wikipedia gives this definition for countable:
    You have given us the opposite: a surjective function N --> S.

    So, let "f" be your N --> X.

    Now consider the inverse of f. It is an injective function X --> N. Because you have an injective function X --> N, you have proven X is countable.

    If you want to get super fancy, you could even use f to define a countable ordering for the members of X, but this much shouldn't be necessary...
     
  4. Nov 28, 2007 #3

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    What do you mean by the "inverse" of f? If you are only given that f is surjective, it may not be injective and so may not have an inverse.
     
  5. Nov 28, 2007 #4

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Let f be the function that maps N onto X

    If f-1({x}) is the set of natural numbers s.t f(n)=x. Clearly these partition N, and all of them are non-empty. hence, for each x, there exists some n s.t. f(n)=x. Then, defining g(x) by g(x)=n for some n satisfying the f(n)=x, we can map X bijectively to some subset of N (if you want a more rigorous definition of g, let g(x) be the minimum element of f-1(x), which exists by well ordering). Hence X is countable
     
    Last edited: Nov 28, 2007
  6. Nov 28, 2007 #5
    Thanks for the replies. Shredder,

    Why does "f f-1({x}) is the set of natural numbers s.t f(n)=x" clearly partition N? Also, why is the map from X to some subset of N bijective?
     
  7. Nov 28, 2007 #6

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    [tex]f^{-1}( \{ x \} )[/tex] partitions N as for each n, f(n) maps to exactly one x. To be a bit more technical, it should be clear that [tex]f^{-1}(X)=N[/tex] i.e. the set of natural numbers that map to somewhere in the set X is all of N, but [tex]\bigcup_{x \epsilon X} f^{-1}( \{ x \} ) = f^{-1}( \bigcup_{x \epsilon X} \{ x \} ) = f^{-1}(X)=N[/tex] and for [tex]x_1, x_2 \epsilon X[/tex] if [tex]n \epsilon f^{-1}( \{ x_1 \} ), f^{-1}( \{ x_2 \} )[/tex] then by definition [tex]f(n)=x_1, x_2[/tex] that is [tex]x_1=x_2[/tex] Obviously this can't happen, so they have empty intersections.

    Not all maps from X to a subset of N are bijective, just the one I described where you pick for each [tex]x \epsilon X[/tex] precisely ONE [tex]n_x[/tex] s.t. [tex]f(n_x)=x[/tex] then if this map is called g(x), g(x) is 1-1, and [tex] \{ n_x \epsilon N | x \epsilon X \} [/tex] is obviously a subset of N. So g is a bijection between X and this set

    EDIT: I'm missing a lot of curly braces (which kind of makes sense, as they're supposed to indicate a block should be treated as an individual thing, and hence are invisible), but is there a way to make them show up? Alternatively, you'll have to imagine that where it looks like I'm describing a set, I am indeed
     
    Last edited: Nov 28, 2007
  8. Nov 28, 2007 #7

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    TeX for a brace is \{ or \}.
     
  9. Nov 28, 2007 #8

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Thanks. I added them in
     
  10. Nov 28, 2007 #9
    There should be a partial inverse.

    See here:

    We're not really interested in reversing the surjection, what we're interested in is the existence of an injection from Y into X, which "g" from the quote provides.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?