Understanding the use of the Cartesian Product in the proof of $|\mathbb R\times \mathbb R|=|\mathbb R|$

Question

Where the Cartesian Product of two sets $\mathbb A$ and $\mathbb B$ is such that $\mathbb A\times \mathbb B=\{{ (a,b)|a \in \mathbb{A}, b \in \mathbb{B}\}}$

In trying to understand the proof that $|\mathbb R\times \mathbb R|=|\mathbb R|$, the only part I can't understand is the use of the Cartesian Product. How can an element in the set $\mathbb R\times \mathbb R$ such as (0.7777777777......, 0.033333333333......) create the number (0.707373737373......) in $\mathbb R$?

The above step is necessary to invoke an injection but not a surjection from $\mathbb R\times \mathbb R$ to $\mathbb R$, since the proof I've been reading makes use of the Cantor-Bernstein-Shroeder theorem.

I can see that this number comes from adding the corresponding decimal digits from each of the numbers in (0.7777777777..........,0.033333333333............), but since when is combining decimal digits in this way an "allowable" operation?

Basically what's bothering me is how an elemental pair can become a single element/number? That is to say - all I'm asking here is why $\\(a,b)$ can become a single entity say $k$ by the Cartesian product?

If you would please be kind enough to explain this to me I would be most grateful.

Thank You.

Answer 1

First, a bit of pedantry (sorry, this isn't related to what you ask but somebody had to say it). You write later in the question that the set $\{\Bbb R\times \Bbb R\}$ is mapped to the set $\{\Bbb R\}$. But these are sets of one element, and those elements are the sets $\Bbb R \times\Bbb R$ and $\Bbb R $, respectively. Those two sets (the curly bracket ones) are in bijection (in fact there's only one possible function between them), but it's clearly not the bijection you want. You want a bijection between the sets $\Bbb R\times \Bbb R$ and $\Bbb R$.

Anyway, regarding the original question, there's no problem with mapping a pair of real numbers to another real number, just think of any real function of two variables (e.g. $\tan xy$). I will admit that it can be surprising that this can be done bijectively, but once the bijection is there and we've shown it's well defined, it's no different than any other mapping.

If it helps, to understand set theoretical arguments, we can forget absolutely every and any algebraic, analytic, geometric, or what-have-you properties of the set in question. In most cases, yes, any algebraic (and other) structures will be destroyed by such bijections. We needn't worry, all that matters here is the well-definedness and the bijective property.

What might help even further, is to consider sets with no additional structure defined whatsoever, such as $\{\text{yum},\ssi,@,\text{top_hat_73}\}$. If you understand maps between these sets, then you can picture the elements of $\Bbb R$ as meaningless labels just like in the previous set, but there's a certain infinite amount of labels. In fact, we could place the string of characters "$\text{yum}$" after the decimal point of each real number, and still have the bijection in question.

Regarding the recent comment, the pair $(a,b)$ is a single entity to begin with, namely an element of the set $\Bbb R \times \Bbb R$. So, it doesn't become a single entity under the unnamed bijection you refer to, it is one that is simply associated to another entity, one of $\Bbb R$. Elements of sets are just elements of sets, no matter how the set was constructed (and there are far more atrocious constructions than the cartesian product).

I may have localized a source of confusion. You correctly intuit that $\Bbb R \times \Bbb R$ and $\Bbb R$ are not "structurally equivalent" in any of the usual ways. For instance, they are not isomorphic as:

1. Ordered sets
2. Groups (additive, without $\mathsf{AC}$)
3. Rings
4. Groups (multiplicative, minus $0$)
5. Fields (giving $\Bbb R\times\Bbb R$ the complex product)
6. $\Bbb R$-Vector spaces
7. Metric (or normed, or inner product) spaces

And there's probably more. But they are in bijection, and the key is that the bijection can stomp all over the above properties if it wishes (and it does).

Maybe I can help you more if you describe the proof you've seen.

Answer 2

Cardinality, Bijections

To show that $\mathbb{R}^2$ has the same cardinality as $\mathbb{R}$ you have to show that a bijection $f$ between both sets exists. $$ f : \mathbb{R}^2 \to \mathbb{R} \\ $$ To what particular element from $\mathbb{R}$ a pair from $\mathbb{R}^2$ is assigned does not matter, only that $f$ is bijective.

$$ \forall (x,y), (x', y') \in \mathbb{R}^2: f((x,y)) = f((x',y')) \Rightarrow (x,y) = (x', y') \\ \forall z \in \mathbb{R}: \exists (x, y) \in \mathbb{R}^2: f((x,y)) = z $$

A bijection provides a 1 to 1 correspondence between sets, here: between pairs from $\mathbb{R}^2$ and elements from $\mathbb{R}$. Every pair should get assigned to exactly one element. Each element should have exactly one pair assigned to it by $f$.

From your post it is not easy to see what mapping $f$ was used. You should try to extract that information from your proof.

Your Question

In trying to understand the proof that $|\mathbb R\times \mathbb R|=|\mathbb R|$, the only part I can't understand is the use of the Cartesian Product. How can an element in the set $\mathbb R\times \mathbb R$ such as (0.7777777777......, 0.033333333333......) create the number (0.707373737373......) in $\mathbb R$?

I can see that this number comes from adding the corresponding decimal digits from each of the numbers in (0.7777777777..........,0.033333333333............), but since when is combining decimal digits in this way an "allowable" operation?

What seems to be done here is to map from pairs of non-negative real numbers to a non-negative real number: $$ \mathbb{R}_+^2 \to^g D^2 \to^f D \to^h \mathbb{R}_+ \quad (*) $$ where $$ D \subset \{ 0,1,2,3,4,5,6,7,8,9, . \}^\omega \subset \Sigma^\omega $$ is the set string representations of non-negative decimal numbers, which is a subset of the set of infinite strings using digits and dot symbols, e.g. $0..0$ is maybe a drunken mouse, but no representation of a decimal, or $\cdots111.222\cdots$ is no representation of a finite number etc.

$g$ is a function that assigns a base 10 representation string to a real number.

$f$ zips two representation strings into one, $$ f( (d_m d_{m-1} \cdots d_0 . d_{-1} \cdots d_{-m} \cdots )_{10}, (D_m D_{m-1} \cdots D_0 . D_{-1} \cdots D_{-m} \cdots )_{10}) = (d_m D_m d_{m-1} D_{m-1} \cdots d_0 D_0 . d_{-1} D_{-1} \cdots d_{-m} D_{-m} \cdots)_{10} $$ Note: I omitted signs, because I do not know how it zips signed numbers in a bijective way, such that we could unzip and recover the signs correctly.

$h$ maps that string to a non-negative real number. $$ h((d_m d_{m-1} \cdots d_0 . d_{-1} \cdots d_{-m} \cdots )_{10}) = \sum_{k=-\infty}^m d_k 10^k $$ To have a bijection from left to right in equation $(*)$, each map in the chain must be bijective.

But we have $h((1.000\cdots)_{10}) = h((0.999\cdots)_{10}) = 1$, so $h$ is not injective.

So if this is really used in your proof, I would expect some normalization rules to restrict $D$ (and the involved mappings $g$ and $h$) to a normalized set, e.g. not including words with infinite 9 end words.

That might give a bijection between $\mathbb{R}_+^2$ and $\mathbb{R}_+$, but what about signed reals?

For this we need another bijection $s : \mathbb{R} \to \mathbb{R}_+$, e.g. $s = \exp$. This gives $$ \mathbb{R}^2 \to^s \mathbb{R}_+^2 \to^g D^2 \to^f D \to^h \mathbb{R}_+ \to^{s^{-1}} \mathbb{R} $$

Answer 3

Note that R × R is not equal to R. their cardinality is.
What you have is just a function between the two sets.
The point is that there is a bijection between the two sets.
For example, you can map even numbers to odd numbers: just send n to n+1.
This doesn't mean that even and odd numbers are the same thing, just that their sets have the same cardinality.
In the same way, a pair of reals is not a real in any way; the point ih the ways is which, starting from a pair of reals, I can arrive at a real.
Can i find a way in which i cover every real? Or a way in which I never arrive at the same real by different starting point?
If the answer to both questions is yes, pairs of reals and reals have the same cardinality.