Q1) Assuming that |R|=|[0,1]| is true, how can we rigorously prove that | |=|[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=
y=
Define f(x,y)=
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]
I think you're talking about the interleaving process. Think about two infinite length tuples. and . 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 and considering that the above is where . We see that
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]?
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??