[Math] Concerning the Countability of the Set of Reals with Decimal Representations Consisting of All $1s$

elementary-set-theoryfunctions

The Problem:

Exhibit a one-to-one correspondence between the set of of positive integers and the set, $S$, of real numbers with decimal representations consisting of all $1$s.

Where I Am:

I realize that $S$ is countable (or else the problem wouldn't be solvable), but I'm not sure how to actually construct an explicit bijection of the type requested, which I assume is the point of the problem. I can create a nice, upper diagonal matrix in which each element of the set is represented as a rational number like so:

$$
\begin{matrix}
\frac{1}{1} & \frac{11}{1} & \frac{111}{1} & \cdots \\
\frac{1}{10} & \frac{11}{10} & \frac{111}{10} & \cdots \\
& \frac{11}{100} & \frac{111}{100} & \cdots \\
& & \vdots & \ddots \\
\end{matrix}
$$

This looks promising but I can't seem to write a function that iterates over it properly. Also, I'm not sure if I need to consider negative numbers, as the problem doesn't make that clear (or does it?).

Best Answer

Each positive integer $n$ can be represented uniquely in the form $n=2^k(2m+1)$, where $k$ and $m$ are non-negative integers. You could match $n$ with the real number having $k$ ones to the left of the decimal point and $m$ ones to the right of the decimal point. This gives you an explicit bijection if we consider only positive reals with terminating decimal expansions. To handle the ones with fractional part $\frac19=0.111\ldots$, make a minor change: let $m-1$ be the number of ones to the right of the decimal point of $m>0$, and let $m=0$ indicate an infinite string of ones to the right of the decimal point.

Added: As the OP points out in a comment below, there is a small problem with this: $1=2^0(2\cdot0+1)$, so this scheme has the positive integer $1$ corresponding to a naked decimal point. It’s actually the integers greater than $1$ that match up under this scheme with the positive real numbers whose decimal representations contain only ones. To fix this, associate with each positive integer $n$ the non-negative integers $k$ and $m$ such that $n+1=2^k(2m+1)$ and then proceed as before. (I’m leaving this as an adjustment instead of rewriting the answer from scratch, because textbooks too often present just the polished finished product, and I think that it’s instructive occasionally to see the steps by which that final product was reached.)

If the negative reals represented only by ones are to be included as well, you could use a slight refinement of the same basic idea. Write $n$ as $2^k\cdot4^\ell(2m+1)$, where $k\in\{0,1\}$, and $\ell$ and $m$ are non-negative integers. That associates each positive integer $n$ with an ordered triple $\langle k,\ell,m\rangle$, which you can assign to the real number $(-1)^kr$, where $r$ is the real number corresponding to $2^\ell(2m+1)$ in the first scheme.

Added: The same problem arises here if $\ell=m=0$, which happens for $n=1$ and $n=2$, so we associate with each $n\in\Bbb Z^+$ the triple $\langle k,\ell,m\rangle$ corresponding to $n+2$ and proceed as before.

Related Question