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?
  • 3
    $\begingroup$ 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$. $\endgroup$ Sep 24 '20 at 12:57
  • $\begingroup$ Minor detail but the interval might need to be $[0,1)$ instead (you cant make $1$ using the rules above) $\endgroup$
    – Sil
    Sep 24 '20 at 13:09
  • 2
    $\begingroup$ 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. $\endgroup$ 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.

  • $\begingroup$ 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? $\endgroup$
    – user828527
    Sep 24 '20 at 13:52
  • $\begingroup$ @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. $\endgroup$ Sep 24 '20 at 13:57
  • $\begingroup$ 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? $\endgroup$
    – user828527
    Sep 24 '20 at 14:23
  • $\begingroup$ @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. $\endgroup$ Sep 24 '20 at 14:27
  • $\begingroup$ Why the downvote? $\endgroup$ 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)\ .$$

  • $\begingroup$ 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? $\endgroup$
    – user828527
    Sep 25 '20 at 8:24
  • $\begingroup$ @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)$. $\endgroup$ Sep 25 '20 at 11:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy