Cantor's diagonalization on the rationals

[BWV]

Question that occurred to me, most applications of Cantors Diagonalization to Q would lead to the diagonal algorithm creating an irrational number so not part of Q and no problem.

However, it should be possible to order Q so that each number in the diagonal is a sequential integer- say 0 to 9, then starting over.

As a repeating decimal, this is a rational number but also not part of the list?

 

[fresh_42]

Question that occurred to me, most applications of Cantors Diagonalization to Q would lead to the diagonal algorithm creating an irrational number so not part of Q and no problem.

However, it should be possible to order Q so that each number in the diagonal is a sequential integer- say 0 to 9, then starting over.

As a repeating decimal, this is a rational number but also not part of the list?

I could well be on the list. The point of the diagonalization argument is to change the entries in the diagonal, and this changed diagonal cannot be on the list.

 

[BWV]

I could well be on the list. The point of the diagonalization argument is to change the entries in the diagonal, and this changed diagonal cannot be on the list.

Right, so you cycle 0.01234… to 0.12345…. and that number would not be in your list of rationals?

 

[fresh_42]

Whatever your list is, if you change the entire diagonal somehow, say by +1, and it would be on the list, say at the n-th position. What would the n-th digit be? The changed or unchanged version?

 

[FactChecker]

Question that occurred to me, most applications of Cantors Diagonalization to Q would lead to the diagonal algorithm creating an irrational number so not part of Q and no problem.

However, it should be possible to order Q so that each number in the diagonal is a sequential integer- say 0 to 9, then starting over.

As a repeating decimal, this is a rational number but also not part of the list?

In an indirect way, you have proven that the number you create can not become infinitely repeating. That should not be surprising, since infinity is a long time to keep repeating.

 

[SSequence]

Regarding the OP, it isn't quite clear what the question is. However, here is one issue related to this point.

I think that perhaps you might be thinking that since the set $Q$ (rational numbers) must have various enormously complicated re-arrangements, shouldn't it be possible to have an arrangement where the "actual" diagonal reads like [without changing any digits that is]:
0.999999999...
0.1234512345... (repeat forever)
0.000000000...
etc.
In other words, can it happen that the diagonal is a rational number? Actually, with a bit of work we can show that the diagonal must always be necessarily irrational (without changing any digits).

====================================

First write the set $S=\{0,1,2,3,4,5,6,7,8,9\}$. Now we can consider a digit change function $f:S \rightarrow S$ defined as:
$f(n)=n+2$ for $0\leq n<8$
$f(8)=0$
$f(9)=1$

Now given any complete listing of $Q$, suppose that the diagonal we obtain (without changing any digits) is equal to $r_1$. And suppose the number we obtain after changing all the digits of the diagonal [using function $f$ mentioned above] is $r_2$. The main thing to observe is the following:
$r_1 \in Q$ iff $r_2 \in Q$

However, the after effect of diagonalization that we carried out is that it is impossible for $r_2 \in Q$ to be true. And now, since $r_2 \notin Q$, we also get $r_1 \notin Q$. Therefore the original diagonal isn't in the actual list either.

Edit:
Similar considerations also apply to any "reasonably closed" set $S$ where $S \subseteq \mathbb{R} \cap [0,1]$. That is, when we list "all" the numbers in $S$, the diagonal (even without changing any digits) wouldn't belong to $S$.

 

[BWV]

Regarding the OP, it isn't quite clear what the question is. However, here is one issue related to this point.

I think that perhaps you might be thinking that since the set $Q$ (rational numbers) must have various enormously complicated re-arrangements, shouldn't it be possible to have an arrangement where the "actual" diagonal reads like [without changing any digits that is]:
0.999999999...
0.1234512345... (repeat forever)
0.000000000...
etc.
In other words, can it happen that the diagonal is a rational number? Actually, with a bit of work we can show that the diagonal must always be necessarily irrational (without changing any digits).

====================================

First write the set $S=\{0,1,2,3,4,5,6,7,8,9\}$. Now we can consider a digit change function $f:S \rightarrow S$ defined as:
$f(n)=n+2$ for $0\leq n<8$
$f(8)=0$
$f(9)=1$

Now given any complete listing of $Q$, suppose that the diagonal we obtain (without changing any digits) is equal to $r_1$. And suppose the number we obtain after changing all the digits of the diagonal [using function $f$ mentioned above] is $r_2$. The main thing to observe is the following:
$r_1 \in Q$ iff $r_2 \in Q$

However, the after effect of diagonalization that we carried out is that it is impossible for $r_2 \in Q$ to be true. And now, since $r_2 \notin Q$, we also get $r_1 \notin Q$. Therefore the original diagonal isn't in the actual list either.

I don’t understand if the diagonal is rational, then the simple manipulation of adding 1 to each digit will create another repeating decimal

Thinking about this some more

a) unlike irrationals, every number in Q has a finite number of decimal points (before it repeats)

b) if you list every rational number that repeats up to n decimal places, the list will be n^10 x n (assuming base 10)

c) the diagonal world be rational and applying a modification will create a number not in that set of n, but will appear further down the list

d) as the number of columns in a complete list of Q is finite, then can’t you apply the above logic to your manipulated rational diagonal?

 

[SSequence]

I don’t understand if the diagonal is rational, then the simple manipulation of adding 1 to each digit will create another repeating decimal

This is a bit different from what I said. What I said was that suppose the diagonal is $r_1$. And suppose that the number obtained by applying the digit change operations of function $f$ (in post#6) on $r_1$ [actually, more precisely, the specific representation we obtain from the diagonal] is $r_2$. Then we must have $r_2 \notin Q$. However, we also have the following:
$r_1$ is rational iff $r_2$ is rational

Now since $r_2$ isn't a rational, $r_1$ isn't either.

============================

Now you are right in the sense that if it happens to be the case the original diagonal is rational, then actually, after any "fixed" digit change permutation (to the diagonal) the resulting number is guaranteed to be rational.

However, this is what I was trying to say. And that is that the original diagonal is guaranteed to be outside of $Q$.

============================

Now one thing is note that when we said $r_2 \notin Q$, this is much more general than that. That is, we can take any set $S$ which is a subset of reals in $[0,1]$. Once we list all the numbers in $S$ and then take the diagonal and change the digits appropriately, we will be guaranteed to get a number outside of $S$.

 

[BWV]

Looks like this same question came up here

https://www.physicsforums.com/threads/another-consequence-of-cantors-diagonal-argument.992377/

With the conclusion that it’s not possible to enumerate Q so the diagonal is rational, however to my simplistic thinking, as Q is infinite with no digit more plentiful than any other at any given place, we should be able to order them into a repeating decimal like in the OP, that contains every digit like 0.0123456789

 

[Jarvis323]

.

Looks like this same question came up here

https://www.physicsforums.com/threads/another-consequence-of-cantors-diagonal-argument.992377/

With the conclusion that it’s not possible to enumerate Q so the diagonal is rational, however to my simplistic thinking, as Q is infinite with no digit more plentiful than any other at any given place, we should be able to order them into a repeating decimal like in the OP, that contains every digit like 0.0123456789

As @SSequence pointed out, if the diagonal is rational, then its compliment is rational. But diagonalization ensures that the compliment isn't on the list. Therefore, either the diagonal isn't rational, or the list is missing at least one rational. As a concrete example, suppose you want $1/3$ on the diagonal, then the list cannot contain $1$, because $1$ has no digit in common with $1/3$.

 

[SSequence]

Now one thing is note that when we said $r_2 \notin Q$, this is much more general than that. That is, we can take any set $S$ which is a subset of reals in $[0,1]$. Once we list all the numbers in $S$ and then take the diagonal and change the digits appropriately, we will be guaranteed to get a number outside of $S$.

I think I forgot to add a certain point in this part. Assuming $S$ to be infinite (to exclude trivial cases), the above part should be right whenever $S$ is countable. If $S$ isn't countable then a bijection (or onto function) from $\mathbb{N}$ to $S$ shouldn't be possible anyway.

Not sure whether it is worth bumping the thread for (since, probably, it seems to be somewhat obvious anyway), but since it got bumped, might as well mention it briefly.

 

[Office_Shredder]

A bit of a side point, the diagonalization argument has nothing to do with the proof that the rational numbers are countable, that can be proven totally separately. Once you know that the rationals are countable, you can use that to prove that the diagonal is not rational, since if it was, that would give a contradiction.Therefore, the answer to your question of "well can't we just do xyz and make it rational" is just no, you can't. Trying to prove you can't by thinking hard about how the diagonalization works is hard, the easy way to prove it is to just know that the rationals are countable by some other method.

 

[BWV]

Sure, the rationals represented as fractions can be mapped to the natural numbers

another thought, if you list the natural numbers with an infinite number of leading zeros - just like you would on the other side of the decimal place for reals - then do the diagonalization algorithm from right to left, what then do you get - a natural number not on the list?

 

[FactChecker]

No. A natural number has a finite number of digits. Your generated string of digits never ends. It is not a number.

 

[BWV]

No. A natural number has a finite number of digits. Your generated string of digits never ends. It is not a number.

So that same argument should apply to the rationals - as every rational (in some base) likewise has a finite number of digits?

the arguments above that just fall back on Cantor’s diagonalization seem circular, ISTM that another reason my diagonalization of rationals in the OP fails is that

A) rationals have a finite number of decimals
B) therefore the list of rationals is not ‘square’ - the list of reals is inf x inf so a diagonal exists, but the list of rationals is inf x finite

 

[SSequence]

You can do this kind of thing (by adding an infinite number of 0's "to the left"). But the diagonalization would produce an infinite string of digits (right-to-left direction). Unless the string of digits becomes permanently 0 after a certain point (right-to-left direction), which they won't, then we have just produced something which is not a natural number.

A good analogy to this which would work is to list all terminating decimals (avoiding infinite number of 9's form) between 0 and 1. By terminating decimal I mean those numbers which have decimal representations with only a finite number of non-zero digits. When we diagonalize these [after digit alteration] we will get a number which won't be a terminating decimal.

 

[Jarvis323]

Sure, the rationals represented as fractions can be mapped to the natural numbers

another thought, if you list the natural numbers with an infinite number of leading zeros - just like you would on the other side of the decimal place for reals - then do the diagonalization algorithm from right to left, what then do you get - a natural number not on the list?

...0000
...0001
...0010
...0011
...0100

The diagonal would have ...000, which is on the list, but the compliment is ...111, which is not on the list but also it isn't a natural number.

 

[BWV]

A good analogy to this which would work is to list all terminating decimals (avoiding infinite number of 9's form) between 0 and 1. By terminating decimal I mean those numbers which have decimal representations with only a finite number of non-zero digits. When we diagonalize these [after digit alteration] we will get a number which won't be a terminating decimal.

But per above, can't you just extend that argument to all of ℚ, as a repeating decimal is an arbitrary representation that would terminate in some other base?

 

[Jarvis323]

But per above, can't you just extend that argument to all of ℚ, as a repeating decimal is an arbitrary representation that would terminate in some other base?

Then you have different encodings for different list elements? So what encoding is used to interpret the diagonal? If you can choose anyone you want, you can just say that whatever is on the diagonal encodes whatever you want it to?

 

[BWV]

Then you have different encodings for different list elements? So what encoding is used to interpret the diagonal? If you can choose anyone you want, you can just say that whatever is on the diagonal encodes whatever you want it to?

why not? start with base 2, list all terminating decimals, go to base 3 and so on. Interpret the diagonal in that base, so the first '.1' in binary is '.5' in the base-10 diagonal. Alternatively you could take the base-2 diagonal, convert to base 10 (or whatever) then convert the base 3 diagonal to the same base and so on. But as the list consists of finite numbers to the right of the decimal you can't construct the diagonal to begin with other than by adding arbitrary zeros on the right - and you won't get a repeating decimal on that - your diagonal will eventually end in zeros. If you then apply Cantor’s algorithm you create a repeating decimal, but that number will already have a representation in the list in a base where the decimal terminates. So could this could be used to prove the rationals are countable (of course there are easier and better ways to do that)?

 

[FactChecker]

So that same argument should apply to the rationals - as every rational (in some base) likewise has a finite number of digits?

And that is true. I don't know what that proves. An infinite number of digits to the right of the decimal point has meaning. It is a number. But an infinite number of digits to the left of the decimal point does not have a meaning as a number of any kind.

 

[BWV]

And that is true. I don't know what that proves. An infinite number of digits to the right of the decimal point has meaning. It is a number. But an infinite number of digits to the left of the decimal point does not have a meaning as a number of any kind.

the trailing zeros in 1/4 = 0.2500... are not equally meaningless? In the real world trailing zeros indicate precision - i.e. 0.2500... is really 1/4 not 0.2498, but to apply Cantor's diagonalization is not a practical problem and there is no need to put any zeros after 1/4 = 0.25, whether you are listing rationals or reals, and all terminating decimals would have an infinite number of meaningless zeros in his diagonalization

 

[FactChecker]

the trailing zeros in 1/4 = 0.2500... are not equally meaningless? In the real world trailing zeros indicate precision - i.e. 0.2500... is really 1/4 not 0.2498, but to apply Cantor's diagonalization is not a practical problem and there is no need to put any zeros after 1/4 = 0.25, whether you are listing rationals or reals, and all terminating decimals would have an infinite number of meaningless zeros in his diagonalization

No, 0.250000... is not equally meaningless. It is the number 0.25 exactly. On the other hand, what is the meaning of ...489231578.0 with infinite non-zero digits to the left? You invented it, now explain it.

 

[BWV]

No, 0.250000... is not equally meaningless. It is the number 0.25 exactly. On the other hand, what is the meaning of ...489231578.0 with infinite non-zero digits to the left? You invented it, now explain it.

It’s just an overly pedantic way to notate 489231578

 

[FactChecker]

It’s just an overly pedantic way to notate 489231578

No. To follow the Cantor Diagonalization method to the left, you will need to generate an infinite sequence of non-zero digits to the left. That is not a number of any kind.

 

[BWV]

No. To follow the Cantor Diagonalization method to the left, you will need to generate an infinite sequence of non-zero digits to the left. That is not a number of any kind.

I agree, which is the answer to my earlier question on why you can’t do it on natural numbers. An infinite amount of zeros on the left just means zero, but once you cycle the digits with the algorithm it fails