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

Cardinality, Hilbert Hotel

  1. Dec 6, 2005 #1
    Just come across this question on a problem sheet and it's got me rather confused!
    You have to prove that |[0,1]|=|[0,1)|=|(0,1)| without using Schroeder-Bernstein and using the Hilbert Hotel approach. After looking at the Hilbert Hotel idea I can't really understand how this helps! This questions quite bugging me now!

    Thanks for any help!
     
  2. jcsd
  3. Dec 6, 2005 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    You're probably trying to write down nice functions, don't.


    You can biject the rationals {1/n : n in N} with a proper subset of itself a la hilbert hotel, this gives you a bijection between [0,1] and [0,1) by extension, and shows you how to explicitly write bijections between any infinite set S and S\F for any finite subset F.
     
  4. Dec 7, 2005 #3

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper
    2015 Award

    clever. i kind of like the bernstein approach.

    i just discovered for myself (while teaching an elementary course in proofs) the well known idea of defining an injection from positive rationals to positive integers sending n/m to 2^n 3^m.

    to me this is nicer since it can be written down, than cantors diagonal construction of a surjection fro Z+ to Q+.

    by the way bernstein's theorem was proved first by cantor, but with the hypotheses that all infinite sets are comparable. i did not know this either until today.

    my extreme ignorance is offered as a lesson of inspriation to all budding mathematicians, i.e. even if you do not know squat, you can still create a lot of new mathematics, in some specialized field.
     
    Last edited: Dec 7, 2005
  5. Dec 8, 2005 #4

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    The prime power proof certailny far nicer than the diagonal counting argument for at least two reasons.

    1. it embodies a general constructive proof that the finite union of any countable sets is countable since there are infinitely many primes.

    2. it doesn't use the word diagonal: diagonal proofs show that Q is countable and that R is not; this is a a pedagagoically stupid situation.
     
  6. Dec 8, 2005 #5
    And indeed, any countable union of countable sets, [itex]\bigcup_{k\in\mathbb{N}}A_k[/itex], is countable. If [itex]f_k[/itex] is a bijection from [itex]A_k[/itex] to [itex]\mathbb{N}[/itex] then we have the injection [itex]x \mapsto 2^m3^n[/itex] where [itex]m[/itex] is the smallest natural number such that [itex]x\in A_m[/itex] and [itex]f_m(x)=n[/itex].
     
    Last edited: Dec 8, 2005
  7. Dec 8, 2005 #6

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Does that work? It doesn't appear to, in fact it appears to fail spectacularly to even be a function. Of course i might be wrong, but it just doesn't appear to make sense as a definition. I mean, what if all the A_k are equal (say N) and each f_k is the identity. Then how does that map even work? I can see how it could be altered to be an injection, since any element in the union is uniquely specified by a 2-tuple (p,q), but just not by the definition given.

    In any case I meant to state that the method given generalizes to show that any finite *product* of countable sets is countable, not finite *union* (or coproduct). finite coproducts and countable coproducts of countable sets are easily shown to be countable.
     
    Last edited: Dec 8, 2005
  8. Dec 9, 2005 #7
    In this case, the union is just [itex]\mathbb{N}[/itex], and for any [itex]x\in\mathbb{N}[/itex], the smallest [itex]m[/itex] such that [itex]x\in A_m[/itex] is 0. Since [itex]f_0[/itex] is the identity function, [itex]x[/itex] is mapped to [itex]2^03^x=3^x[/itex].

    I don't really like the way my definition reads. One small modification: Let [itex]g:\bigcup_{k\in\mathbb{N}}A_k\rightarrow\mathbb{N}[/itex] be the function [itex]x \mapsto 2^m3^{f_m(x)}[/itex] where [itex]m[/itex] is the smallest natural number such that [itex]x\in A_m[/itex].

    Ah, right.
     
  9. Dec 9, 2005 #8

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Ah, I see what's wrong (in my viiew). Your unions are not taken to be disjoint unions. Usually, in set theory questions like this, we assume the unions are disjoint. So in my example where each A_k is a copy of N we view them as distinct copies of N so that the '3' in the first copy is not the same '3' as the one in the second copy. THis is probably just me being sloppy.
     
    Last edited: Dec 9, 2005
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Cardinality, Hilbert Hotel
  1. Cardinality help (Replies: 5)

  2. Cardinal Numbers (Replies: 1)

  3. Cardinality Question (Replies: 1)

Loading...