# Show cardinality between two sets $x=(0,x_1x_2x_3...)_{10}=\sum _{k=1}^{\infty }x_k 10^{-k}$

For every real number $$x \in [0,1]$$ can be written in decimal form:

$$x=(0,x_1x_2x_3...)_{10}=\sum _{k=1}^{\infty }x_k 10^{-k}$$ where $$x_i \in \{0,1,2,3...,9\}$$ for every $$i$$. Because of uniqueness we disallow expansions that end with an infinite number of $$9$$s. Let $$A$$ be the set of all $$x \in [0,1]$$ whose decimal expansion only has even digits. Show that $$A$$ and $$R$$ has the same cardinality, i.e. $$|A| = |R|$$.

I am lost.

• What does $$(0,x_1x_2x_3...)_{10}$$ mean?
• What is $$x_i$$ which is suddenly defined? Or what is $$i$$?
• What is the implication of disallowing expansions that end in $$9$$s?
• What is $$x$$ in the sigma notation as I do not see it defined anywhere?
• How do I calculate the first number in this sequence? $$k$$ is one. What is $$x$$?
• More importantly, where do I learn enough to understand this question myself?
• So your question ist to understand the question? The $x_k$ are digits $\{0, \ldots, 9 \}$ and the whole thing is about digital numbers with base 10, like $\pi=3,1415\ldots$. Sep 24 '20 at 12:57
• Minor detail but the interval might need to be $[0,1)$ instead (you cant make $1$ using the rules above)
– Sil
Sep 24 '20 at 13:09
• The first step is to edit your query to answer two questions: (1) What does $R$ represent : are you (for example) intending that it refers to all real #'s? Please explicitly answer this question. (2) What is the background of the problem? That is, is this problem from a book or class, or from some other source (e.g. contest)? Further, if this problem is from a book/class, then it must have been intended that you use concepts from the book/class to attack the problem. What theorems or previously solved problems from the book/class do you think might be pertinent here? Pls be explicit. Sep 24 '20 at 13:28

To begin with, $$x=\sum_k^\infty x_k$$ is just the digital representation of a real number in $$[0,1]$$.

According to definition, the cardinality of two sets is $$|X|\leq|Y|$$ iff there is an injective mapping from $$X\to Y$$.

We have sets $$A$$ and $$R$$ as defined in the question. The elements of $$A$$ and $$R$$ are modeled by infinite sequences of digits $$x_k\in\{0,\ldots,9\}$$ with some additional restrictions.

As all elements of $$A$$ are obviously elements of $$R$$ we have $$|A|\leq |R|$$.

The startling thing and the point of the question is, that albeit $$R$$ has elements not fount in $$A$$ (such as $$\frac19=0,1111111\ldots$$), and all elements of $$A$$ are also in $$R$$, both have the same cardinality.

To show that wen need to show $$|R|\leq |A|$$ by finding an injection from $$R\to A$$.

As there is a countable infinity of indices, there is an easy trick:

Let $$x=\sum_k^\infty x_k\in R$$. Just map it to $$y=\sum_k^\infty y_k$$ with $$y_{2k+1}=2*x_k \mod 10$$ and $$y_{2k}=2*\lfloor{2*x_k/10}\rfloor$$.

In simpler word, take any digit $$x_k$$, double it resulting in two digits, the first one $$0,1$$, the last one even, Correct the the first one frm $$1$$ (which is not allowed in $$A$$ to $$2$$, if needed, and allign those digits at the end of the previously computed digits.

• Thank you for your answer! I am trying to make sense of what you wrote. I understand how the two sets can have the same cardinality. But what I don't understand is x_1 and x. x is every number between 0 and 1 per the definition. But x is also (0,x_1x_2x_3...)_10. What does that mean? Are they all the same x? Different? Is x_i different from x_k which is different from x_1x_2? Does x_1x_2 mean the numbers are multiplied or is that an actual number zero comma numberx1 numberx2 and so on?
– user828527
Sep 24 '20 at 13:52
• @mathggz choose $x_k$ to be any digit you like, for all $k$: then you have exactly one $x$. Make another choice for the $x_k$ and you have a different $x$. If you happen to choose $0.0999999\ldots$ that happens to be identical with $0.1$, that is why infinite series of 9s are excluded. Sep 24 '20 at 13:57
• How can k be 0.09999 when k starts at 1? If I pick k=1, then the first number is 1*10^-1. that is the first x. correct? but what is x_i and (0,x_1x_2x_3...)_10 in this context?
– user828527
Sep 24 '20 at 14:23
• @mathggz not $k$, but $x$ as a sequence of decimal digits: $x=0.x_1x_2x_3\ldots$. Just like you can write $\frac17=0.142857142857\ldots$, with $x_1=1, \,x_2=4$ etc. Sep 24 '20 at 14:27
• Why the downvote? Sep 24 '20 at 15:32

All your bulleted questions refer to the notations connected with the following fact: The set of real numbers $$x\in[0,1[\>$$ is in bijective correspondence with the set of all infinite decimal fractions $$0.x_1x_2x_3\ldots$$ with $$x_i\in\{0,1,2,\ldots,9\}$$, whereby $$0.x_1x_2x_3\ldots\quad \leftrightarrow \quad x=\sum_{k=1}^\infty x_k\,10^{-k}\ .$$ Some exception handling has to be done concerning the fact that, e.g., $$0.39999\ldots=0.40000\ldots\$$. Therefore decimal fractions ending with all nines have been excluded in your source. I shall not deal with this.

Now the actual problem is the following: You have the set $$R$$ of all sequences $$x:\quad{\mathbb N}\to\{0,1,2,\ldots,9\},\qquad k\mapsto x_k\ ,$$ (omit the sequences ending with all nines, if you like) and the subset $$A\subset R$$ of all sequences $$y:\quad{\mathbb N}\to\{0,2,4,\ldots,8\},\qquad k\mapsto y_k\ .$$ It is claimed that $$|R|=|A|$$, even though it seems that $$A$$ has much fewer elements than $$R$$. For the proof we need the Schroeder-Bernstein Theorem:

• Given two sets $$R$$ and $$A$$, and we can invent injective maps $$f:A\to R$$, $$\ g:R\to A$$, then $$|R|=|A|$$.

Of course the injection map $$f:A\to R$$ is injective. To construct the $$g:R\to A$$ we have to injectively encode each sequence $$x\in R$$ as a new sequence $$g(x)=:y\in A$$. Let $$x=(x_1,x_2,\ldots)\in R$$. Define $$y_{2i-1}:=2\left\lfloor{x_i\over2}\right\rfloor, \quad y_{2i}:=2(x_i-y_{2i-1})\in\{0,2\}\qquad(i\geq1)\ .\tag{1}$$ It is easy to see that $$y=(y_1,y_2,y_3,\ldots)\in A$$, and that the sequence $$x$$ can be reconstructed uniquely from the $$y$$. Therefore the $$g$$ constructed in this way is injective.

Example: $$x=(3,4,1,6,6,5,7,9,\ldots), \quad y=g(x)=(2,2,4,0,0,2,6,0,6,0,4,2,6,2,8,2,\ldots)\ .$$

• Thank you for the comment. I don't understand the last step. What is y_{2i-1} and y_{2i}? We use these to calculate each y1,y2 somehow? How did you conclude that?
– user828527
Sep 25 '20 at 8:24
• @mathggz: Each digit $x_i$ needs the two digits $y_{2i-1}$, $y_{2i}$ to be represented. The calculation of these $y_{2i-1}$, $y_{2i}$ is not "somehow", but clearly described in $(1)$. Sep 25 '20 at 11:21