- #1

- 1,018

- 1,066

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?

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- I
- Thread starter BWV
- Start date

- #1

- 1,018

- 1,066

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?

- #2

fresh_42

Mentor

- 15,565

- 13,677

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.

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?

- #3

- 1,018

- 1,066

Right, so you cycle 0.01234… to 0.12345…. and that number would not be in your list of rationals?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.

- #4

fresh_42

Mentor

- 15,565

- 13,677

- #5

FactChecker

Science Advisor

Gold Member

- 6,576

- 2,644

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.

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?

- #6

- 510

- 78

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##.

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

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

##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.

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##.

Last edited:

- #7

- 1,018

- 1,066

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?

- #8

- 510

- 78

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##I don’t understand if the diagonal is rational, then the simple manipulation of adding 1 to each digit will create another repeating decimal

##r_1## 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##.

Last edited:

- #9

- 1,018

- 1,066

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

- #10

- 765

- 643

.

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##.

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##.

Last edited:

- #11

- 510

- 78

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.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##.

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.

- #12

Office_Shredder

Staff Emeritus

Science Advisor

Gold Member

- 4,699

- 685

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.

- #13

- 1,018

- 1,066

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?

- #14

FactChecker

Science Advisor

Gold Member

- 6,576

- 2,644

- #15

- 1,018

- 1,066

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

- #16

- 510

- 78

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

- #17

- 765

- 643

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.

- #18

- 1,018

- 1,066

But per above, cant you just extend that argument to all of ℚ, as a repeating decimal is an arbitrary representation that would terminate in some other base?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.

- #19

- 765

- 643

Then you have different encodings for different list elements? So what encoding is used to interpret the diagonal? If you can choose any one you want, you can just say that whatever is on the diagonal encodes whatever you want it to?But per above, cant you just extend that argument to all of ℚ, as a repeating decimal is an arbitrary representation that would terminate in some other base?

- #20

- 1,018

- 1,066

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 cant construct the diagonal to begin with other than by adding arbitrary zeros on the right - and you wont 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)?Then you have different encodings for different list elements? So what encoding is used to interpret the diagonal? If you can choose any one you want, you can just say that whatever is on the diagonal encodes whatever you want it to?

Last edited:

- #21

FactChecker

Science Advisor

Gold Member

- 6,576

- 2,644

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.So that same argument should apply to the rationals - as every rational (in some base) likewise has a finite number of digits?

- #22

- 1,018

- 1,066

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 diagonalizationAnd 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.

- #23

FactChecker

Science Advisor

Gold Member

- 6,576

- 2,644

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.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

- #24

- 1,018

- 1,066

It’s just an overly pedantic way to notate 489231578No, 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.

- #25

FactChecker

Science Advisor

Gold Member

- 6,576

- 2,644

No. To follow the Cantor Diagonalization method to the left, you will need to generate an infinite sequence ofIt’s just an overly pedantic way to notate 489231578

Share:

- Replies
- 93

- Views
- 14K