11
$\begingroup$

This is problem 0.6.9 from JOHN H.HUBBARD's Vector calculus, linear algebra, and differential forms

It seems quite difficult for me so I firstly think the situation in the binary.

I've found that the number given by the entries on the diagonal can be an irrational.

Suppose that we have a list including all of the rationals now, and write them in the binary form. If $a$ is a irrational number, we can start from checking the first digit. When checking its $n$th digit and we can rearrange the list by change the position of the first number in the rest of list that have the same $n$th digit.

If there exists a number that doesn't have a same digit as $a$, then it only can be $1-a$, so its a irrational number out of the list.

However, if $a$ is a rational number, then the $1-a$ is a rational number too, and it cannot be included in my new list.

Above sentence is about the binary situation, and what's the solution when written as decimals?

$\endgroup$
10
  • 2
    $\begingroup$ Some rationals can be written in more than one way as a sequence of digits. $\endgroup$
    – MJD
    Dec 25, 2023 at 15:59
  • 1
    $\begingroup$ @MJD I assume that in this case , the binary expansion eventually only having zeros is chosen. $\endgroup$
    – Peter
    Dec 25, 2023 at 16:03
  • 3
    $\begingroup$ Your title mentions decimals whereas your question mentions binary. Which one are you interested in? $\endgroup$ Dec 25, 2023 at 16:13
  • 1
    $\begingroup$ Every number with a finite decimal (resp. binary) representation can be written in two ways in decimal (resp. binary). Are you allowed to use that fact? $\endgroup$
    – David K
    Dec 25, 2023 at 16:24
  • 1
    $\begingroup$ @IzaakvanDongen Sorry, I misconstrued the phrase "Cantor construction" and was thinking about the uncountability of the reals rather than this question. You're right, of course, notwithstanding the answer below (which, IIRC, is a reminder that the Cantor construction doesn't translate easily to base two). $\endgroup$
    – David K
    Dec 26, 2023 at 0:07

3 Answers 3

11
$\begingroup$

Nice problem, I enjoyed thinking about it!


For your binary situation, we can indeed do this, but for my solution we require to write all rationale with only finitely many digits in their binary expansion (e.g. $\frac{3}{4} = 0.11_2$) to be written in an infinite form (e.g. $0.10111…_2$) (EDIT: see last paragraph to see why this isn’t necessary). Hence, we can now exploit the property that every non-zero rational number in this range has $1$s occur infinitely often in their binary expansion.

Start the list with $0$. Now, for the $n$th number listed, we take the rational with the smallest denominator in its simplified form (using smallest numerator to break ties) with $n$th binary digit being $1$ that’s not already in our list. This gives the following list: \begin{align*} 0&=0_2\\ 1&=0.1111111\dots_2\\ \frac{1}{2}&=0.0111111\dots_2\\ \frac{2}{3}&=0.1010101\dots_2\\ \frac{1}{3}&=0.0101010\dots_2\\ \frac{1}{4}&=0.0011111\dots_2\\ \frac{3}{4}&=0.1011111\dots_2\\ \frac{1}{5}&=0.0011001\dots_2\\ &\vdots \end{align*} Observe that every rational number will get on this list since we have induced an ordering on the rationals, and every number has infinitely many $1$s (this isn’t too hard to rigorise and I’ve left it as an exercise).

We also see the diagonal forms $0.1111\dots_2=1$, which indeed is rational so we’re done.


On the other hand, for the decimal case, if $q$ is the rational number along the diagonal, then $1-q$ must be on the list somewhere. But $q$ cannot be expressed with a finite decimal expansion (as there exist infinitely many numbers with all digits being neither $0$ nor $9$) and must contain digits $1-9$ in its decimal expansion, so $1-q$ must be a different number to $q$. In particular, the $n$th digit of $1-q$ is $9$ minus the $n$th digit of $q$, and so $1-q$ cannot fit on the list anywhere. Hence, this is impossible.

This reasoning doesn’t hold in the binary case due to the fact that no rationals in binary have all digits being neither $0$ nor $1$. In fact, we can further show that only in base $2$ will we ever be able to accomplish this using a very similar argument, which is very reminiscent of the fact that Cantor's diagonalisation argument doesn't really work in base $2$ and needs to be significantly modified.

Interestingly, the only rational number that can be formed along the diagonal in the binary case must be one with a finite binary expansion using the same reasoning above. (I only realized this after I had already gotten a solution, but you can indeed aim to get $0$ and avoid rewriting fractions with finite binary expansions, since every rational number has infinitely many zeroes in it).

$\endgroup$
4
  • $\begingroup$ I'm having trouble following the reasoning. "But q cannot be expressed with a finite decimal expansion" Why? Many rationals have a finite decimal expansion; "and must contain digits 1-9 it is expansion" Why? Many rationals use only a subset of 0-9 in their digits; "so 1-q must be a different number to q" That's true iff q is not 1/2, and doesn't seem logically related to any of the previous sentences?; $\endgroup$
    – Stef
    Dec 26, 2023 at 8:50
  • $\begingroup$ "In particular the nth digit of 1-q is 9 minus the nth digit of q" If q and 1-q have finite decimal expansion (and thus two possible expansions each), then if you can choose the expansions of q and 1-q, then you can choose them such that the nth digit of one is 9 minus the nth digit of the other, for instance 1-0.25 = 0.749999... but if you cannot choose then it doesn't have to be that way, for instance 1-0.25 = 0.75 or 1-0.249999... = 0.749999... $\endgroup$
    – Stef
    Dec 26, 2023 at 8:52
  • $\begingroup$ @Stef The comments about $q$ are not about whether it is a rational number; they are about whether it will be possible to include all other rational numbers in the list after deciding that the diagonal is $q$. If $q$ has a finite decimal expansion then after $N$ digits it will be either all $0$ or all $9$, so we can only have $N$ rational numbers in the list that have no $0$s or $9$s. But there are infinitely many such numbers. $\endgroup$
    – David K
    Dec 26, 2023 at 9:06
  • $\begingroup$ @DavidK Awesome! Thanks $\endgroup$
    – Stef
    Dec 26, 2023 at 9:11
0
$\begingroup$

Let me outline the solution for binary representation. Here we assume that any binary ending with an infinite tail of $1$'s has been replaced by the corresponding finite binary expansion (ending with an infinite tail of $0$'s). Start with the following obvious fact:

Given a finite list of length $k$ of rational numbers, there is a number not on the list with $(k+1)$-th digit $0$.

Now we start with the usual "snaking" enumeration of all the rationals (in binary), and modify it so as to obtain the rational $0$ (i.e., $0.000\ldots$) along the diagonal inductively. If the $k$-th digit of the $k$-th number on the list is $0$, we leave it in place. Otherwise, we replace it by the earliest number on the list with digit $0$ in $k$-the place, shift the entire list by one rank, and proceed inductively to create a new list $L$.

To show that every binary number eventually appears on $L$, we argue by contradiction. Suppose some numbers don't appear on $L$. Take the earliest number $n$ on the old list which does not appear on $L$. Consider the set $S$ of numbers preceding $n$ on the old list. Since they all appear on $L$ by hypothesis, we can find the largest rank $k$ on the new list $L$ among numbers in the finite set $S$. But $n$ has digits $0$ at position $r>k$ (infinite tails of $1$'s are not allowed). Therefore it will be included on $L$ no more than $r-k$ steps after the last number before it has been included. The contradiction proves that all numbers eventually appear on $L$.

$\endgroup$
8
  • $\begingroup$ Where does the number $0.010101\dots_2=\frac{1}{3}$ appear on this list? $\endgroup$ Dec 25, 2023 at 17:26
  • $\begingroup$ Hmm I may be misreading your solution… What rational number do you construct from the diagonal? $\endgroup$ Dec 25, 2023 at 17:29
  • $\begingroup$ Yes, so how can the number $0.010101\dots_2$ show up on this list? It doesn’t match the first digit, second digit, etc. $\endgroup$ Dec 25, 2023 at 17:31
  • $\begingroup$ @SharkyKes, I hope this is better. $\endgroup$ Dec 26, 2023 at 11:08
  • $\begingroup$ Yeah this is better, although this argument doesn't work for decimal since there exist rational numbers with no $0$ in their decimal expansion (e.g. $\frac{1}{3}$). $\endgroup$ Dec 26, 2023 at 11:16
0
$\begingroup$

I give you some reference and ask Santa for 2024 with https://en.m.wikipedia.org/wiki/Linear-feedback_shift_register#Fibonacci_LFSRs

You should be surprise with the connection between polynomial and binary representation see Polynomial representation of binary

Hope this helps

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .