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

**kingwinner** · March 14th 2010, 03:36 PM

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]

**Drexel28** · March 14th 2010, 04:30 PM

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.

**kingwinner** · March 14th 2010, 07:04 PM

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] ) ?

**Drexel28** · March 14th 2010, 07:14 PM

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)$

**kingwinner** · March 15th 2010, 01:27 AM

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!

**Drexel28** · March 15th 2010, 09:00 AM

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')$

**kingwinner** · March 15th 2010, 09:10 PM

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??

**Drexel28** · March 15th 2010, 09:15 PM

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?

**kingwinner** · March 15th 2010, 09:54 PM

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]?

**Drexel28** · March 15th 2010, 09:56 PM

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)$ ?

**kingwinner** · March 15th 2010, 10:16 PM

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)??

**kingwinner** · March 18th 2010, 02:20 PM

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??

Thread: Cardinality of R, [0,1], R^2, [0,1] x [0,1]

LinkBack

Thread Tools

Display

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

Similar Math Help Forum Discussions

Cardinality

Cardinality

Cardinality

Cardinality

Cardinality of a Set

Search Tags