# What restrictions on decimal expansions lead to countably infinite subsets of the reals?

Consider real numbers $S : x \in [0,1]$ whose decimal expansions are $x = 0.d_1 d_2 d_3 \ldots$. Now institute various exclusions, listed below. I am interested to learn of general principles that will allow me to conclude that $S_X$ is either countable or uncountable.

1. $S_{!5}$: The decimal representation excludes all $5$'s.
2. $S_{5^{\textrm{th}}}$: In the decimal representation, every $5^{\textrm{th}}$ digit is $5$.
3. $S_{\textrm{odd}}$: The decimal representation excludes all even digits: $0,2,4,6,8$.
4. $S_{01}$: The decimal representation excludes all but the two digits: $0$ and $1$.
5. $S_{1}$: The decimal representation uses (after the $0.$) only the digit $1$: $0.1, 0.11, 0.111, \ldots$.
6. $S_{\ge}$: The decimal representation is non-decreasing: successive digits are the same or larger. E.g., $.1144456777777788999\ldots$.
7. $S_{k\pm}$: The decimal representation $k$-oscillates: The sequence consists of $k$ or more digits (non-strictly) increasing, followed by a sequence of $k$ or more digits that (non-strictly) decreases, and so on. E.g., for $k=5$, $0.11339 \; 966432 \; 567777 \; \ldots$.
8. $S_{\textrm{max/min}}$: The decimal representation is finitely oscillatory: there are only a finite number of digit minima and maxima in the sequence of digits.

Perhaps each case must be handled separately? I am particularly interested in difficult, borderline cases that are not so straightforward to settle, which could be used as good student exercises to distinguish countable from uncountable.

• Interesting examples. I agree that each case must be handled separately. First four are uncountable, the fifth and sixth ones are countable. I am not sure about the seventh and eighth ones yet. – Sungjin Kim Jan 28 '17 at 0:47
• @i707107 Seventh is uncountable, eighth is countable. – Reese Jan 28 '17 at 0:49
• I get the seventh now, but I don't really understand what eighth means. – Sungjin Kim Jan 28 '17 at 0:53
• Interestingly, in all three countable cases, the decimal expansions define subsets $\mathbb{Q} \cap [0,1]$. This may lead one to think of the hard cases (not just for students) discussed in this MO question. – Fabio Somenzi Jan 28 '17 at 5:43
• This does not really have anything to do with decimal expansions. You can simply think about sequences (there is a difference, but that is only on a countable set, which has no bearing on the question). All the listed examples where $S_X$ is countable have the property that the sequence is eventually constant, and it's straightforward to check that this implies countability (the converse is not true: for example, you could add some random noise, uniformly, to all elements of a countable $S_X$ and it would still give you a countable set). – tomasz Jan 28 '17 at 14:36

Don't know that I'd call it a general principle, but most of these follow from remapping the restricted set to the reals, perhaps in another basis.

1. $S_{!5}$: The decimal representation excludes all $5$'s.

Decrement all digits larger than $5$, then the set becomes the representation of the entire $[0,1]$ in base $9$, thus uncountable.

1. $S_{5^{\textrm{th}}}$: In the decimal representation, every $5^{\textrm{th}}$ digit is $5$.

Drop every $5^{th}$ digit, then the set becomes the decimal representation of the entire $[0,1]$, thus uncountable.

1. $S_{\textrm{odd}}$: The decimal representation excludes all even digits: $0,2,4,6,8$.

Remap the $5$ remaining digits $1,3,5,7,9$ to $0,1,2,3,4$, then the set becomes the representation of the entire $[0,1]$ in base $5$, thus uncountable.

1. $S_{01}$: The decimal representation excludes all but the two digits: $0$ and $1$.

That gives the representation of the entire $[0,1]$ in base $2$, thus uncountable.

1. $S_{1}$: The decimal representation uses (after the $0.$) only the digit $1$: $0.1, 0.11, 0.111, \ldots$.

This can be indexed by the number of decimal digits, thus countable.

1. $S_{\ge}$: The decimal representation is non-decreasing: successive digits are the same or larger. E.g., $.1144456777777788999\ldots$.

The sequence of digits will become constant eventually, thus countable.

1. $S_{k\pm}$: The decimal representation $k$-oscillates: The sequence consists of $k$ or more digits (non-strictly) increasing, followed by a sequence of $k$ or more digits that (non-strictly) decreases, and so on. E.g., for $k=5$, $0.11339 \; 966432 \; 567777 \; \ldots$.

Drop every other group of $k$ digits, and truncate the remaining ones to the first $k$ digits, which leaves groups of exactly $k$ increasing decimal digits. Consider each such group as one digit in some base made up of all increasing sequences of $k$ decimal digits. Then the set becomes the representation of the entire $[0,1]$ in that base, thus uncountable.

1. $S_{\textrm{max/min}}$: The decimal representation is finitely oscillatory: there are only a finite number of digit minima and maxima in the sequence of digits.

The sequence of digits will become constant eventually, thus countable.

[ EDIT ]   Numbered the points to stay in sync with the OP, and made a minor change to #7 which I had first (mis)read as exactly $k$ digits.

• Cogent analysis. – Joseph O'Rourke Jan 28 '17 at 1:26

As a general rule, if your set is such that given a number $x \in S$ you can change infinitely many digits at once and independently, it'll be uncountable - otherwise, it won't be. For example, $S_{\mathrm{odd}}$ is uncountable, because beginning with $x = 0.1111\ldots$ I can replace any combination of $1$s with $3$s and still obtain a number in $S_{\mathrm{odd}}$. On the other hand, $S_1$ is only countable; given any $x \in S_1$, the only way I can change infinitely many digits is by changing them all to $1$.

The key idea is basically reducing everything to $S_{01}$. $S_{01}$ is uncountable for a very simple reason: any number expressed using only zeroes and ones can be interpreted as a binary expansion of an unrestricted real. So every real between $0$ and $1$ "shows up" in $S_{01}$. As long as you can find a way of thinking of your set as $S_{01}$, you've got something uncountable.

To take an extreme example: say $S_{56}$ is the set of infinite decimals consisting entirely of $5$s, except for every $10000$th digit, which may be either a $5$ or a $6$. We can think of this as "basically" $S_{01}$ by (1) ignoring all the forced digits, and (2) where we get to choose between $5$ and $6$, treating a $5$ as a $0$ and a $6$ as a $1$. So, for example, we can see $0.555\ldots 555\mathbf{6}555\ldots 555\mathbf{5}555\ldots 555\mathbf{6}555\ldots$ as the binary string $0.101\ldots$. So $S_{56}$ is also uncountable.

• I very much like your $S_{56}$ uncountable example---Thanks! – Joseph O'Rourke Jan 28 '17 at 1:21