Is a digit-reversal function well-defined for all real numbers in [0,1)?

Question

Motivation

Conway's base 13 function has the intriguing property of mapping any non-empty interval to every real number — yet almost every input is mapped to zero.

I’m interested in finding a function with similarly behavior, but which also acts meaningfully on irrational numbers.

For simplicity, I'm considering a function $f: [0, 1) \rightarrow [0, 1)$. My idea is to reverse the fractional digits. E.g. 0ドル.123$ could become 0ドル.321$.

Given any point $p = (x, y) \in [0, 1)^2$ one can find $p' = (x', f(x')) \in [0, 1)^2$ such that $|p - p'|_2 < \epsilon$ for an arbitrarily small $\epsilon > 0$.

Question

While the digit-reversal idea seems promising, it runs into problems with irrational numbers. It is unclear which digit the irrational number ends on.

Can the last fractional digits of an irrational number be known? More specially, can a digit-reversal function exist?

My thoughts

This section is a naive attempt on finding the "last" digit of a number with infinite fractional digits. My question is about the existence of such a function even if my attempt fails.

Context-free grammars as a concept for last fractional digits

I suggest the following representation for real numbers in $[0, 1)$. Consider the following grammar:

$S \rightarrow (0.X)_{\text{base 2}}\\X \rightarrow \epsilon~|0~|~1~|~0X0~|~0X1~|~1X0~|~1X1$

($\epsilon$ is the empty symbol which simply removes the $X$. For simplicity 0. shall be zero.)

This grammar builds binary fractional parts from the center outward. It can produce binary numbers like 0ドル.0$, 0ドル.1$, 0ドル.11$, 0ドル.001$ but also numbers with infinitely many digits by never terminating the recursive expansion. E.g. the grammar can produce 0ドル.01...01$ for the rational binary number 0ドル.\overline{01}$. It is hard to write down $\pi$ but easy to find infinitely many approximations — eventually including the exact value.

Given that grammar, it is easy to define the reversal of a number with infinitely many fractional digits.

Naive algorithm for reversing digits iteratively

The function below never terminates for almost all numbers. The algorithm only illustrates how bits could be inverted without knowing the "last" digit. I think of the algorithm as something like an infinite sum.

def f(x):
 r = 0
 
 while x > 0:
 x *= 2 # shift input up
 bit = int(x) # pick leading bit
 x -= bit # pop leading bit
 r += bit # push leading bit
 r /= 2 # shift result down
 return r

Editing remarks

I restructured my question such that my thoughts are separate from my general question. The existing responses should not be effected by the change.

• Martin R: The function is undefined for all irrational numbers because the while loop never terminates. Actually the same is true for many rational numbers.
• Marian D.: @MartinR how does Conway’s base 13 function determine the point at which a number’s base-13 expansion switches to only decimal digits? Doesn’t the algorithm also run indefinitely for some numbers?

Answer 1

As noted in the comments, the function that you have attempted to create does not lead to a well-defined function because the while loop never terminates.

But the underlying question is whether it is possible to meaningfully have a digit reversal function. Not whether said function is computable. Not whether we can find it. But whether, mathematically, it can exist and be well-defined.

The answer is that, if you accept ZFC, then such functions do exist. To construct them, we need the concept of the Ultrafilter. The explanation there can make your eyes water. So here is a simple one.

An ultrafilter $\mathscr{U}$ on the natural numbers is a collection of infinite subsequences of the natural numbers such that the following is true:

If we partition the natural numbers into a finite collection of sets, then for one and only one of those sets will there be a subsequence in $\mathscr{U}$ that is entirely in that partition.

What requires a fancy construction in ZFC is that this is true of any way to partition the natural numbers into a finite collection of sets. This allows us to, for any partitioning of the natural numbers, pick one partition. And we do so in a consistent way.

First, take any real number $r$ in canonical form. This is the usual decimal representation, where we end with repeating 0s instead of repeating 9s for numbers where we have a choice.

Look at the finite terminating decimal approximations to $r$ of different lengths. We can partition the natural numbers into those where the last digit is 0,ドル 1, 2, \ldots, 9$. $\mathscr{U}$ has a subsequence in only one of those partitions. And so we can pick the last digit.

Next, let's partition the natural numbers into those where the last two digits are 00,ドル 01, \ldots, 99$. $\mathscr{U}$ has a subsequence in only one of those partitions. And so we can pick the last two digits. Note that whatever subsequence $\mathscr{U}$ has in one of those partitions, it is also in one of the partitions we had before, and so our last two digits end with the last digit we already found.

We can repeat to pick the last 3 digits, and again it will agree with the last 2 digits we already picked.

As we continue this process indefinitely, we will wind up picking out exactly terminating sequence for $r$. This sequence can be reversed, and will give a function that works exactly like you hope for. What function this will be depends on the ultrafilter $\mathscr{U}$ that we started on. Since many ultrafilters exist, many such functions exist. (But, unfortunately, none are computable since we have no computable way to construct an ultrafilter.)

• Marian D.: Wouldn't the ultrafilter imply that real numbers are countable? I am not 100% sure, but it seems to me that you can apply the diagonization argument and show that for every ultrafilter there exists one real number that cannot be reversed.
• btilly: @MarianD. Very unlikely. If you can prove that, then you've found a contradiction within ZFC. Which would be big news. That said, I have no idea what diagonalization argument would make you think that it could be proven.