R ~ n-dimensional space

• Oct 3rd 2007, 11:21 AM
fifthrapiers
R ~ n-dimensional space
This problem will show that the reals ~ n-dimensional space (that is, they have the same cardinality).

Use this theorem in your arguments:

Theorem: If there exists a 1:1 function f : x -> Y and another 1:1 function g : Y -> X, then X ~ Y (has the same cardinality)

Let I = (0, 1) be the openn unit intervall and S = {(x,y) | 0 < x < 1, 0 < y < 1} be the openn unnit square.

a.) Find a 1:1 function f : I -> S

b.) Produce a 1:1 function by using the fact that every real # has a decimal expansion.

HINT: Any terminating expansion like .432 represents the same # as 0.431999999.... You can avoid this by always picking the terminating expansion (that is for the pairs of reals in S).

c.) Conclude I ~ S

d.) Show $\mathbb{R}$ ~ $\mathbb{R}^n$ for any $n \in \mathbb{N}$
• Oct 4th 2007, 01:04 AM
Opalg
Given a point $(0.a_1a_2a_3\ldots,\;0.b_1b_2b_3,\ldots)$ in the unit square, form the number $0.a_1b_1a_2b_2a_3b_3\ldots$. That will give you a map from the square to the interval, and you need to prove that it is 1–1.
• Oct 4th 2007, 04:57 AM
Rebesques
Opalq has also just given a method to map the unit n-square $\{\overline{x}\in R^n: \ |\overline{x}|< 1\}$ to (0,1). Let $\overline{x}=(x_1,x_2,\ldots,x_n)=(0.x_{11}x_{12}x _{13}\ldots,0.x_{21}x_{22}x_{23}\ldots,0.x_{n1}x_{ n2}x_{n3}\dots)$ and map this to $(0,1)\ni y=0.x_{11}x_{21}\ldots x_{n1}x_{12}x_{22}\ldots x_{n2}\ldots$ . (Tmi)
• Oct 4th 2007, 09:11 PM
fifthrapiers
Quote:

Originally Posted by Rebesques
Opalq has also just given a method to map the unit n-square $\{\overline{x}\in R^n: \ |\overline{x}|< 1\}$ to (0,1). Let $\overline{x}=(x_1,x_2,\ldots,x_n)=(0.x_{11}x_{12}x _{13}\ldots,0.x_{21}x_{22}x_{23}\ldots,0.x_{n1}x_{ n2}x_{n3}\dots)$ and map this to $(0,1)\ni y=0.x_{11}x_{21}\ldots x_{n1}x_{12}x_{22}\ldots x_{n2}\ldots$ . (Tmi)

I guess I'm confused on finding a one-to-one "function".. as I don't see how to do so using a decimal expansion. And then the bigger question is how does this prove the same cardinality.

Well, we do know that the reals has the same cardinality in (0,1) as on the whole line..but still I don't think that helps me.
• Oct 5th 2007, 08:24 AM
Rebesques
Well, functions are defined by assigning a (unique) value to every argument. Since decimal expansions are unique, we have a function here.

If we can also estabish that it is 1-1 and onto, then the domain and the image have the same cardinality. That's up to you!
• Oct 5th 2007, 10:13 AM
Opalg
Quote:

Originally Posted by fifthrapiers
I guess I'm confused on finding a one-to-one "function".. as I don't see how to do so using a decimal expansion. And then the bigger question is how does this prove the same cardinality.

Well, we do know that the reals has the same cardinality in (0,1) as on the whole line..but still I don't think that helps me.

I'll try to describe it more precisely. We want to find a function f from the open unit square S to the open unit interval I. Start with a point (x,y) in S. To define f(x,y) we first write the decimal expansions of x and y, namely $x=0.x_1x_2x_3\ldots,\;y=0.y_1y_2y_3\ldots$. These expansions are unique (provided that we do not allow expansions ending in an infinite string of 9s). Now we define z=f(x,y) to be the number obtained by interleaving the decimal expansions of x and y. In other words, $z=0.x_1y_1x_2y_2x_3y_3\ldots$. This defines a function f from S to I, and you need to prove that it is 1-1.

Quote:

Originally Posted by Rebesques
If we can also estabish that it is 1-1 and onto, then the domain and the image have the same cardinality. That's up to you!

Here's where things get really tricky. The function f that I just defined is 1-1 but it is not onto. For example, the number z=1/11 is not in the range of f. In fact, 1/11 = 0.090909... . If this number is in the range of f the we would need to have z=f(x,y), where the decimal expansion of x is given by the digits in the odd-numbered places in the decimal expansion of z, and the decimal expansion of y is given by the digits in the even-numbered places in the decimal expansion of z. In other words, x=0.00000... and y=0.99999... . But neither of these is allowed: x and y are supposed to be in the open unit interval, so they cannot be equal to the endpoints 0 or 1 of the interval. Also, we don't allow expansions ending in an infinite string of 9s. That shows that the function f is not onto.

There is no easy way round this difficulty. In fact, I don't know of any constructive way of describing a function from S to I that is both 1-1 and onto. The way to show that S and I have the same cardinality is to produce two functions, f (from S to I) and g (from I to S), both of which are 1-1. (We already have f, as above. It's easy to construct a suitable function g from I to S, for example g(x)=(x,1/2).) You can then quote the theorem that is given in the statement of the problem:
Theorem: If there exists a 1:1 function f : x -> Y and another 1:1 function g : Y -> X, then X ~ Y (has the same cardinality).
• Oct 5th 2007, 10:47 AM
Rebesques
Quote:

Here's where things get really tricky. The function f that I just defined is 1-1 but it is not onto. For example, the number z=1/11 is not in the range of f. In fact, 1/11 = 0.090909... . If this number is in the range of f the we would need to have z=f(x,y), where the decimal expansion of x is given by the digits in the odd-numbered places in the decimal expansion of z, and the decimal expansion of y is given by the digits in the even-numbered places in the decimal expansion of z. In other words, x=0.00000... and y=0.99999... . But neither of these is allowed: x and y are supposed to be in the open unit interval, so they cannot be equal to the endpoints 0 or 1 of the interval. Also, we don't allow expansions ending in an infinite string of 9s. That shows that the function f is not onto.

There's no trouble with that Op, all we lose is the 2^n edgepoints, while the sets involved are both infinite. It's the same "composition of sequences" trick that makes things work in dimension one. :)
• Oct 5th 2007, 02:56 PM
Opalg
Quote:

Originally Posted by Rebesques
There's no trouble with that Op, all we lose is the 2^n edgepoints, while the sets involved are both infinite. It's the same "composition of sequences" trick that makes things work in dimension one. :)

No, there are uncountably many such points, even in the one-dimensional case: any point for which either the odd-numbered or the even-numbered places in the decimal expansion ends with an infinite sequence of 9s fails to be in the range of the map f, and there are uncountably many such points in the unit interval. Believe me, it may sound like a tiresome detail, but there's no getting around it. That is why the question contained the instruction to use the Cantor-Bernstein Theorem.
• Dec 7th 2007, 03:05 AM
Rebesques
Quote:

and there are uncountably many such points in the unit interval

Oh u r right, hadn't even thought of that :o Let's see what can be done now...