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

• Mar 14th 2010, 03:36 PM
kingwinner
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]
• Mar 14th 2010, 04:30 PM
Drexel28
Quote:

Originally Posted by kingwinner
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.
• Mar 14th 2010, 07:04 PM
kingwinner
Quote:

Originally Posted by Drexel28
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] ) ?
• Mar 14th 2010, 07:14 PM
Drexel28
Quote:

Originally Posted by kingwinner
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)$
• Mar 15th 2010, 01:27 AM
kingwinner
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!
• Mar 15th 2010, 09:00 AM
Drexel28
Quote:

Originally Posted by kingwinner
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')$
• Mar 15th 2010, 09:10 PM
kingwinner
Quote:

Originally Posted by Drexel28
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??
• Mar 15th 2010, 09:15 PM
Drexel28
Quote:

Originally Posted by kingwinner
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?
• Mar 15th 2010, 09:54 PM
kingwinner
Quote:

Originally Posted by Drexel28
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]?
• Mar 15th 2010, 09:56 PM
Drexel28
Quote:

Originally Posted by kingwinner
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)$?
• Mar 15th 2010, 10:16 PM
kingwinner
Quote:

Originally Posted by Drexel28
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)??
• Mar 18th 2010, 02:20 PM
kingwinner
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??