Results 1 to 12 of 12

Math Help - Cardinality of R, [0,1], R^2, [0,1] x [0,1]

  1. #1
    Senior Member
    Joined
    Jan 2009
    Posts
    404

    Arrow Cardinality of R, [0,1], R^2, [0,1] x [0,1]

    Q1) Assuming that |R|=|[0,1]| is true, how can we rigorously prove that | R^2|=|[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
    x= 0.a_1a_2a_3...
    y= 0.b_1b_2b_3...
    Define f(x,y)= 0.a_1b_1a_2b_2a_3b_3...
    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?

    Thanks a million!


    [also under discussion in math links forum]
    Last edited by kingwinner; March 15th 2010 at 02:25 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by kingwinner View Post
    Q1) Assuming that |R|=|[0,1]| is true, how can we rigorously prove that | R^2|=|[0,1] x [0,1]|? How to define the bijection?


    Q2) Prove that |[0,1] x [0,1]| ≤ |[0,1]|
    Proof: Represent points in [0,1] x [0,1] as infinite decimals
    x= 0.a_1a_2a_3...
    y= 0.b_1b_2b_3...
    Define f(x,y)= 0.a_1b_1a_2b_2a_3b_3...
    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?

    Thanks a million!


    [also under discussion in math links forum]
    Since \mathbb{R}\simeq[0,1] there exists some \varphi:\mathbb{R}\to[0,1] which is bijective. Define \varphi\times\varphi:\mathbb{R}\times\mathbb{R}\to[0,1]\times[0,1] by (x,y)\mapsto (\varphi(x),\varphi(y)). This is readily verified to be a bijection.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Jan 2009
    Posts
    404
    Quote Originally Posted by Drexel28 View Post
    Since \mathbb{R}\simeq[0,1] there exists some \varphi:\mathbb{R}\to[0,1] which is bijective. Define \varphi\times\varphi:\mathbb{R}\times\mathbb{R}\to[0,1]\times[0,1] by (x,y)\mapsto (\varphi(x),\varphi(y)). This is readily verified to be a bijection.
    1) I checked that it is one-to-one, but how to prove that it is onto (i.e. image(φ x φ) = [0,1] x [0,1] ) ?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by kingwinner View Post
    1) I checked that it is one-to-one, but how to prove that it is onto (i.e. image(φ x φ) = [0,1] x [0,1] ) ?
    Let (x,y)\in [0,1]\times [0,1]. By, \varphi's surjecdtivity there exists some x',y'\in\mathbb{R} such that x'\overset{\varphi}{\mapsto}x and y'\overset{\varphi}{\mapsto}y. Clearly then, (x',y')\overset{\varphi\times\varphi}{\longmapsto}  (x,y)
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Jan 2009
    Posts
    404
    Thanks!

    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!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by kingwinner View Post
    Thanks!

    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!
    I think you're talking about the interleaving process. Think about two infinite length tuples. (a_1,b_1,a_2,b_2\cdots and (a'_1,b'_1,a'_2,b'_2,\cdots. This models exactly the idea behind the infinite decimal expansion. So, if these two tuples are equal then so are all of their coordinates. So, in fact a_1=a'_1,b_1=b'_1,a_2=a'_2,b_2=b'_2,\cdots and considering that the above is \varphi(x,y),\varphi(x',y') where x=.a_1a_2a_3\cdots,y=.b_1b_2b_3\cdots,x'=.a'_1a'_2  a'_3\cdots,y'=.b'_1b'_2b'_3\cdots. We see that \varphi(x,y)=\varphi(x',y')\implies x=x',y=y'\implies (x,y)=(x',y')
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Jan 2009
    Posts
    404
    Quote Originally Posted by Drexel28 View Post
    I think you're talking about the interleaving process. Think about two infinite length tuples. (a_1,b_1,a_2,b_2\cdots and (a'_1,b'_1,a'_2,b'_2,\cdots. This models exactly the idea behind the infinite decimal expansion. So, if these two tuples are equal then so are all of their coordinates. So, in fact a_1=a'_1,b_1=b'_1,a_2=a'_2,b_2=b'_2,\cdots and considering that the above is \varphi(x,y),\varphi(x',y') where x=.a_1a_2a_3\cdots,y=.b_1b_2b_3\cdots,x'=.a'_1a'_2  a'_3\cdots,y'=.b'_1b'_2b'_3\cdots. We see that \varphi(x,y)=\varphi(x',y')\implies x=x',y=y'\implies (x,y)=(x',y')
    Thanks!

    We can say this only because we have removed all ambiguities, so the decimal expansion of each number is unique, right??


    Why is f NOT onto??
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by kingwinner View Post
    Thanks!

    We can say this only because we have removed all ambiguities, so the decimal expansion of each number is unique, right??


    Why is f NOT onto??
    I assume you mean because you have eliminated infinite nines?

    Do you want the cool explanation or the lame one for why it's not onto?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member
    Joined
    Jan 2009
    Posts
    404
    Quote Originally Posted by Drexel28 View Post
    I assume you mean because you have eliminated infinite nines?

    Do you want the cool explanation or the lame one for why it's not onto?
    Yes, I mean in the case when there are two represenations of the same number (e.g. 0.999...=1.000...), we have made a choice of taking only one of them. To ensure that the function is one-to-one, we HAVE to make this choice, right?
    As I think 0.a1b1a2b2... = 0.a1'b1'a2'b2'... => a1=a1', b1=b1', a2=a2', b2=b2',... is true only becuase we've eliminated all ambiguities as above.


    As for the not onto part, I'm not sure what you meant, but I perfer the simpler explanation.
    Why is the map f: [0,1] x [0,1] -> [0,1] not onto? Is there any element in [0,1] which is not the image of any element in [0,1] x [0,1]?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by kingwinner View Post
    Yes, I mean in the case when there are two represenations of the same number (e.g. 0.999...=1.000...), we have made a choice of taking only one of them. To ensure that the function is one-to-one, we HAVE to make this choice, right?
    As I think 0.a1b1a2b2... = 0.a1'b1'a2'b2'... => a1=a1', b1=b1', a2=a2', b2=b2',... is true only becuase we've eliminated all ambiguities as above.


    As for the not onto part, I'm not sure what you meant, but I perfer the simpler explanation.
    Why is the map f: [0,1] x [0,1] -> [0,1] not onto? Is there any element in [0,1] which is not the image of any element in [0,1] x [0,1]?
    Well, let me firs ask you this. What is f(1)?
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Senior Member
    Joined
    Jan 2009
    Posts
    404
    Quote Originally Posted by Drexel28 View Post
    Well, let me firs ask you this. What is f(1)?
    f: [0,1] x [0,1] -> [0,1]
    f(. , .) should have two arguments, right? I don't think we can properly define f(1)??
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Senior Member
    Joined
    Jan 2009
    Posts
    404
    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.

    Is this why f is NOT onto??
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Cardinality
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 11th 2010, 08:08 AM
  2. Cardinality
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 31st 2009, 04:56 PM
  3. Cardinality
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: February 11th 2009, 06:36 PM
  4. Cardinality
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: February 8th 2009, 03:23 PM
  5. Cardinality of a Set
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 27th 2009, 04:33 PM

Search Tags


/mathhelpforum @mathhelpforum