5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Sungjin Kim Jan 28 '17 at 0:47
  • 1
    $\begingroup$ @i707107 Seventh is uncountable, eighth is countable. $\endgroup$ – Reese Jan 28 '17 at 0:49
  • $\begingroup$ I get the seventh now, but I don't really understand what eighth means. $\endgroup$ – Sungjin Kim Jan 28 '17 at 0:53
  • 2
    $\begingroup$ 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. $\endgroup$ – Fabio Somenzi Jan 28 '17 at 5:43
  • 1
    $\begingroup$ 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). $\endgroup$ – tomasz Jan 28 '17 at 14:36
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Cogent analysis. $\endgroup$ – Joseph O'Rourke Jan 28 '17 at 1:26
5
$\begingroup$

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.

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

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.