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

Homework Help: Cardinality of Infinite Sets

  1. Mar 14, 2010 #1
    1. The problem statement, all variables and given/known data
    Q1) Assuming that |R|=|[0,1]| is true, how can we rigorously prove that |R2|=|[0,1] x [0,1]|? How to define the bijection? [Q1 is solved, please see Q2]

    Q2) Prove that |[0,1] x [0,1]| ≤ |[0,1]|
    Proof: Represent points in [0,1] x [0,1] as infinite decimals
    Define f(x,y)=0.a1b1a2b2a3b3...
    To avoid ambiguity, for any number that has two decimal representations, choose the one with a string of 9's.
    f: [0,1] x [0,1] -> [0,1] is one-to-one, but not onto.
    This one-to-one map proves that |[0,1] x [0,1]| ≤ |[0,1]|.

    Now how can we formally prove that f is a one-to-one map (i.e. f(m)=f(n) => m=n)? All textbooks are avoiding this step, they just say it's obviously one-to-one, but this is exactly where I'm having trouble. How to prove formally?
    2. Relevant equations

    3. The attempt at a solution
    As shown above.

    Thanks a million! :)
    Last edited: Mar 15, 2010
  2. jcsd
  3. Mar 15, 2010 #2
    Q1 is solved, but I'm still having trouble with Q2.

    Can someone help me with Q2, please? It is an example I found on the internet, but I don't understand why the function f is one-to-one. How can we formally PROVE that f is a one-to-one map?

    Any help is appreciated!
  4. Mar 15, 2010 #3
    There is really nothing to it...you just have to say: suppose [tex]f(a,b)=f(c,d).[/tex] Then:

    [tex]0.a_1b_1a_2b_2...=0.c_1d_1c_2d_2...[/tex], so:

    [tex]a_i=c_i[/tex] and [tex]b_i=d_i[/tex] for all [tex]i[/tex],

    ie: [tex]a=c[/tex] and [tex]b=d[/tex], so [tex](a,b)=(c,d).[/tex]
  5. Mar 16, 2010 #4
    We can say [tex]a_i=c_i[/tex] and [tex]b_i=d_i[/tex] for all [tex]i[/tex] only because we have removed all ambiguities, so the decimal expansion of each number is unique, right??

    Also, why is f NOT onto??

  6. Mar 16, 2010 #5


    User Avatar
    Science Advisor

    Why do you think it's not? It is! Hence it is a bijection, which means [itex]|[0,1]^2|=|[0,1]|[/itex].

    The proof is trivial: let [itex]z\in [0,1][/itex], [itex]z=0,z_1z_2z_3z_4z_5...[/itex].
    Take [itex]x,y\in[0,1][/itex] with [itex]x=0.z_1z_3z_5...[/itex] and [itex]y=0.z_2z_4z_6...[/itex]. Then obviously [itex]f(x,y)=z[/itex].
  7. Mar 16, 2010 #6


    User Avatar
    Science Advisor

    First, this is exactly the same since f is bijective, hence you would just be computing the inverse which contributes nothing. Second, |A|<=|B| means by definition that there exists an injection A->B, not that there exists a surjection B->A. These are only equivalent if we invoke the axiom of choice. So it does not make more sence to construct a surjective map in the other direction.

    \\edit: it seems jbunniii deleted his reply.
  8. Mar 16, 2010 #7


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Yeah, I realized pretty quickly that it didn't make any sense, but not quickly enough!
  9. Mar 16, 2010 #8


    User Avatar
    Science Advisor

    I apologize ;)
  10. Mar 18, 2010 #9

    But now I seriously think that f is NOT onto.

    For example, 0.17070707... is not in the image of f.
    It must come from (0.10000..., 0.7777...), but by our definition of f, 0.10000... is always represented as 0.0999..., (we have to remove all the ambiguities, for any number that has two decimal representations, we choose the one with a string of 9's. When we define f, we have to remove the ambiguities, otherwise, f won't be one-to-one, actually I think f wouldn't even be a function.)
    So (0.10000..., 0.7777...) is always represented as (0.09999..., 0.7777...). There is no way we can get the element 0.17070707... in the image of f.

    Hence, f is definitely NOT onto, am I right???
  11. Mar 18, 2010 #10
    It looks to me like you are trying to prove that [tex]|[0,1] \times [0,1]| = |[0,1]|[/tex]. Now, I do not know what facts of life you are allowed to assume here, but it seems like the easiest way to go is to appeal to the Schroeder-Bernstein Theorem. If you are unfamiliar with it, the Schroeder-Bernstein Theorem says, briefly, that if [tex]A[/tex] and [tex]B[/tex] are sets, with both [tex]|A| \leq |B|[/tex] and [tex]|B| \leq |A|[/tex], then [tex]|A| = |B|[/tex]. This is more than a mere triviality, since it means that if we have an injection (one-one map, not necessarily onto, as pointed out above) [tex]A \rightarrow B[/tex] and an injection [tex]B \rightarrow A[/tex], then [tex]A[/tex] and [tex]B[/tex] have the same cardinal number.

    In this case, an injection [tex] [0,1] \rightarrow [0,1] \times [0,1][/tex] is easy. An injection [tex] [0,1] \times [0,1] \rightarrow [0,1][/tex] requires a bit more thought, but is readily exhibited, as you have seen.
  12. Mar 18, 2010 #11


    User Avatar
    Science Advisor

    If you are given that |R|= |[0,1]|, you already know that there exists a bijection f(x) from R to [0,1]. Then F(x,y)= (f(x), f(y)) is a bijection from RxR to [0, 1]x[0,1].
  13. Mar 18, 2010 #12

    Gib Z

    User Avatar
    Homework Helper

    Great proof Halls!
  14. Mar 18, 2010 #13

    For Q2, to prove |[0,1]|=|[0,1]x[0,1]|, I was going to use the Schroeder-Bernstein theorem, too.

    But someone said that f(x,y)=0.a1b1a2b2a3b3... is a BIJECTION. If it is a bijection, then we don't need that theorem. Can someone explain why f(x,y)=0.a1b1a2b2a3b3... is onto? I think my post #9 demonstrates that f is NOT onto. Am I missing something??
  15. Mar 18, 2010 #14


    User Avatar
    Science Advisor
    Homework Helper

    No, you're right. f(x,y) is not a bijection. Ignore statements it is and go ahead and prove the result anyway.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook