Another consequence of Cantor's diagonal argument

  • B
  • Thread starter Warp
  • Start date
  • #1
109
11
Thinking about Cantor's diagonal argument, I realized that there's another thing that it proves besides the set of all infinite strings being uncountable.

Namely: That it's not possible to list all rational numbers in an order such that the diagonal of their decimal representation has an infinitely repeating sequence.

My logic goes like this: It's possible to list all rational numbers in order without repetitions, for example using the Calkin-Wilf sequence. However, let's assume that you could list all rational numbers in such an order that the diagonal of their decimal expansion formed an infinitely repeating sequence. Let's say, for example, the sequence 0123456789, like:

0.0xxxxxx...
0.x1xxxxx...
0.xx2xxxx...

and so on. However, if we now apply the diagonal argument and take those digits in the diagonal and eg. increment each of them (with 9 wrapping around to 0), we would get a number that has an infinitely repeating decimal sequence, which is rational, but which is different from all the numbers in the list. Which contradicts the premise that the list contained all the rational numbers.

Since we know that every number with an infinitely repeating decimal sequence is a rational number, the only possible conclusion is that it's not possible to list all the rational numbers in an order such that their diagonal forms a repeating sequence (even if that repeating sequence has all the digits).

However, it's not at all intuitive to me why that's not possible.

(It's very obvious that you cannot list them so that the repeating sequence lacks one of the digits, because then the rational numbers whose decimal expansion does not have said digit wouldn't fit anywhere. It's much less obvious if the sequence has all the digits, eg. 0123456789.)
 

Answers and Replies

  • #2
109
11
(Sorry for the additional post, but I can't find an edit button for my original post. I would add this as an edit, but it doesn't seem to be possible at this point.)

I notice that' there doesn't seem be an actual question in my post. I suppose my question would be: Why is it not possible to list all the rational numbers in such an order? Is there an intuitive way of understanding the reason?
 
  • #3
PeterDonis
Mentor
Insights Author
2019 Award
31,124
10,040
Why is it not possible to list all the rational numbers in such an order? Is there an intuitive way of understanding the reason?
If you don't find a proof you came up with yourself intuitive, I'm not sure how anyone else can be much help. :wink:

However, I can offer the following thought:

Since we're only talking about rational numbers, we have two possibilities:

(1) There are some bit strings in the list that are all zeroes after some finite index ##i##. The only possible infinite repeating sequence on the diagonal that such bit strings can support is an infinite string of zeroes. The diagonalization then gives us an infinite string of some nonzero digit, and obviously such a number can't be in the list, since the list contains bit strings that are zero after some finite index ##i##. So obviously such a list cannot contain all rational numbers.

(2) We carefully select a list of rational numbers that contains no numbers whose bit strings are all zeroes after some finite index ##i##--in other words, we limit ourselves to those rational numbers that, after some finite index ##i##, are repeating sequences of one or more digits, where zero can only be in the repeating sequence if it has more than one digit. So, for example, the rational number 1/2 would not be in this list, but 1/3 would, and so would 1/11, since its bit string is 090909...

We could try to analyze in detail how diagonalization of such a list would work--but we don't have to, because of course it's obvious from the start that such a list cannot contain all rational numbers, since we explicitly excluded the ones which are all zeroes after some finite index ##i##. So either way we know that our list cannot contain all rational numbers.
 
  • #4
449
51
I notice that' there doesn't seem be an actual question in my post. I suppose my question would be: Why is it not possible to list all the rational numbers in such an order? Is there an intuitive way of understanding the reason?
Interpreting your question for a specific repetition sequence, I assume what you are trying to say is that an enumeration of rational numbers whose diagonal contains the pattern 0123456789 (repeated forever) can't contain all rational numbers. Your conclusion seems correct to me. But didn't you describe the reason yourself (take digits on diagonal and increment by 1 to form a new rational number)?

EDIT: It seems to me that other digit alterations would be more efficient/easier to work with (e.g. for this see post#34 in your thread that got locked). But, in this post, lets work with the digit alteration you suggested. END

For example:
##Q_0:## 0.0xxxxxxxxxxxxxxxxxxxxxxxx
##Q_1:## 0.x1xxxxxxxxxxxxxxxxxxxxxxx
##Q_2:## 0.xx2xxxxxxxxxxxxxxxxxxxxxx
##Q_3:## 0.xxx3xxxxxxxxxxxxxxxxxxxxx
##Q_4:## 0.xxxx4xxxxxxxxxxxxxxxxxxxx
##Q_5:## 0.xxxxx5xxxxxxxxxxxxxxxxxxx
##Q_6:## 0.xxxxxx6xxxxxxxxxxxxxxxxxx
##Q_7:## 0.xxxxxxx7xxxxxxxxxxxxxxxxx
##Q_8:## 0.xxxxxxxx8xxxxxxxxxxxxxxxx
##Q_9:## 0.xxxxxxxxx9xxxxxxxxxxxxxxx
##Q_{10}:## 0.xxxxxxxxxx0xxxxxxxxxxxxxxx
##Q_{11}:## 0.xxxxxxxxxxx1xxxxxxxxxxxxxx
##Q_{12}:## 0.xxxxxxxxxxxx2xxxxxxxxxxxxx
##Q_{13}:## 0.xxxxxxxxxxxxx3xxxxxxxxxxxx
##Q_{14}:## 0.xxxxxxxxxxxxxx4xxxxxxxxxxx
...........

As you mentioned yourself the rational number ##Q=0.\overline{1234567890}## [the bar denotes repetition of same pattern forever] won't be on the list. For example, let's take the first rational number ##Q_0##. There is only one way we could have ##Q_0## getting its first digit (after decimal point) equal to ##1##. And that possibility is:
##Q_0=0.0\overline{9999}##
But now, as you can observe, we have ##Q \neq Q_0##.
##Q_0=0.1 \neq Q##

Let's move to second number ##Q_1##. The only way ##Q_1## could equate its first two digits with ##Q## would be to have:
##Q_1=0.11\overline{9999}##
But now, as you can observe, we have ##Q \neq Q_1##.
##Q_1=0.12 \neq Q##

Let's move to third number ##Q_2##. The only way ##Q_2## could equate its first three digits with ##Q## would be to have:
##Q_2=0.122\overline{9999}##
But now, as you can observe, we have ##Q \neq Q_2##.
##Q_2=0.123 \neq Q##

Let's move to fourth number ##Q_3##. The only way ##Q_3## could equate its first four digits with ##Q## would be to have:
##Q_3=0.1233\overline{9999}##
But now, as you can observe, we have ##Q \neq Q_3##.
##Q_3=0.1234 \neq Q##

Jumping to ##Q_8## now. Writing it side by side with ##Q## we get:
##Q=0.12345678901234567890\overline{1234567890}##
##Q_8: 0.xxxxxxxx8xxxxxxxxxxxxxxxx......##
So we at least know ##Q_8## would have to be:
##Q_8=0.123456788xxxxxxxxxxxxxxxx......##

To avoid inequality with ##Q##, at this point, we are forced to have ##Q_8## of the form:
##Q_8=0.123456788\overline{9999}xxxxxxxxxxxxxxxx......##
But this leads to:
##Q_8=0.123456789 \neq Q## (note that: ##Q_8=0.123456789 < 0.12345678901<Q## etc.)

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

Finally, let's move to ##Q_9## now. Writing it side by side with ##Q## we get:
##Q=0.12345678901234567890\overline{1234567890}##
##Q_9=0.xxxxxxxxx9xxxxxxxxxxxxxxx......##
So we at least know ##Q_9## would have to be:
##Q_9=0.1234567899xxxxxxxxxxxxxxx......##

To avoid inequality with ##Q##, at this point, we are forced to have ##Q_9## of the form:
##Q_9=0.1234567899\overline{9999}##
But this leads to:
##Q_9=0.12345679 \neq Q##

Moving to ##Q_{10}## now. Writing it side by side with ##Q## we get:
##Q=0.12345678901234567890\overline{1234567890}##
##Q_{10}=0.xxxxxxxxxx0xxxxxxxxxxxxxx......##
So we at least know ##Q_{10}## would have to be:
##Q_{10}=0.12345678900xxxxxxxxxxxxxx......##
To avoid inequality with ##Q##, at this point, we are forced to have ##Q_{10}## of the form:
##Q_{10}=0.12345678900\overline{9999}......##
But this leads to:
##Q_{10}=0.1234567901 \neq Q##

Moving to ##Q_{11}## now. Writing it side by side with ##Q## we get:
##Q=0.12345678901234567890\overline{1234567890}##
##Q_{11}=0.xxxxxxxxxxx1xxxxxxxxxxxxx......##
So we at least know ##Q_{11}## would have to be:
##Q_{11}=0.123456789011xxxxxxxxxxxxx......##
To avoid inequality with ##Q##, at this point, we are forced to have ##Q_{11}## of the form:
##Q_{11}=0.123456789011\overline{9999}##
But this leads to:
##Q_{11}=0.12345679012 \neq Q##


And so on. (note: need to check typos and clerical mistakes in the post)
 
Last edited:
  • #5
FactChecker
Science Advisor
Gold Member
5,784
2,151
It seems to me that you are considering a hard thing (that the list has the property of an infinitely repeating diagonal sequence) and then are surprised that it can not be done. Your proof that it is impossible seems valid to me, and I consider it to be short and simple enough to become intuitive.
 
  • #6
449
51
@FactChecker
I think that it becomes easier to see directly if:
(i) we consider a digit change that is always guaranteed to diagonalize [otherwise, it seems, we would have to (additionally) consider something similar (or at least something that serves as a substitute) to post#4].

(ii) the realisation that, with the digit change, a pattern like 1234567890 (that repeats forever in cycles of finite length) will lead to a new pattern (that will still again repeat forever in cycles of finite length)
 
  • #7
109
11
I didn't mean to say that the proof is unintuitive. I meant to say that it's unintuitive why you can't list all the rational numbers in an order that makes the diagonal contain a rational number.

In retrospect, it's after all relatively obvious why in my example 0.12345678901234... is not in the list: Because it cannot be added to the list anywhere, due to the constraint put on the diagonal. No matter where you try to put that number, it never fulfills that constraint. There's no place where the correspondent digit is correct for the diagonal, under the given constraints.

Of course by the same argument no other repeating pattern in the diagonal would work either.

This leads to the semi-interesting conclusion that it's impossible to rearrange the list of rational numbers in such a manner that the diagonal of their decimal expansion forms a rational number. In other words, no matter how you rearrange the list of rationals, the diagonal will always contain an irrational number.
 
  • Like
Likes SSequence
  • #8
370
219
(1) There are some bit strings in the list that are all zeroes after some finite index ##i##. The only possible infinite repeating sequence on the diagonal that such bit strings can support is an infinite string of zeroes. The diagonalization then gives us an infinite string of some nonzero digit, and obviously such a number can't be in the list, since the list contains bit strings that are zero after some finite index ##i##.
I don't quite follow.

Are you talking about diagonalization on an enumeration of the rationals with all zeros after N digits or the set of rationals with finite non-zero digits. i.e. $$Q_n = \{ q \in Q \textit{ s. t. } \forall_{i>n}(q_i= 0)\}$$ or $$\{ q \in Q \textit{ s. t. } \exists_n\forall_{i>n}(q_i= 0)\}$$

If it's the first one, it's a finite set, so diagonalization on it can't produce an infinite sequence.

If it's the second one, then what you said doesn't seem obvious. Why diagonalization must give a trailing infinite string of some nonzero digit? The set is infinite, and there is no largest natural number.
 
Last edited:
  • #9
PeterDonis
Mentor
Insights Author
2019 Award
31,124
10,040
Are you talking about diagonalization on an enumeration of the rationals with all zeros after N digits or the set of rationals with finite non-zero digits.
Neither. Given any set of rationals, or more precisely of infinite strings of binary digits that represent rationals, either the set includes some rationals whose infinite strings of binary digits are all zero after some finite index, or it doesn't. Those are the two mutually exclusive, logically exhaustive possibilities. I am not making any further assumptions, in the first possibility, about the properties of the infinite strings of binary digits that are all zero after some finite index, beyond that bare statement.
 
  • #10
370
219
Neither. Given any set of rationals, or more precisely of infinite strings of binary digits that represent rationals, either the set includes some rationals whose infinite strings of binary digits are all zero after some finite index, or it doesn't. Those are the two mutually exclusive, logically exhaustive possibilities. I am not making any further assumptions, in the first possibility, about the properties of the infinite strings of binary digits that are all zero after some finite index, beyond that bare statement.
Can you clarify this sentence?
PeterDonis said:
The only possible infinite repeating sequence on the diagonal that such bit strings can support is an infinite string of zeroes.
I interpret "such bit strings" to be a set, but don't follow how any definition of that set supports the conclusion.
 
  • #11
PeterDonis
Mentor
Insights Author
2019 Award
31,124
10,040
I interpret "such bit strings" to be a set
No. In that sentence, I'm talking about the first of the two possibilities: we have an enumeration of infinite bit strings, in which some of the bit strings are all zeroes after some finite index (and the finite index may be different for different bit strings). "Such bit strings" refers to the bit strings in the enumeration that are all zeroes after some finite index.

We are considering the question of whether such an enumeration of bit strings, with some infinite repeating sequence along the main diagonal, can enumerate all rationals--i.e., every rational number is represented by at least one bit string in the enumeration. My point is that, if we are considering an enumeration that meets the above requirement (some of the bit strings have all zeroes after some finite index), the only possible infinite repeating sequence that can be along the main diagonal is all zeroes.
 
  • #12
370
219
This leads to the semi-interesting conclusion that it's impossible to rearrange the list of rational numbers in such a manner that the diagonal of their decimal expansion forms a rational number. In other words, no matter how you rearrange the list of rationals, the diagonal will always contain an irrational number.
Does it matter at all how we think about rearranging? I mean, you have an infinite list, which by definition (as an enumeration) is computable. So now you want to rearrange it. To do so, you need another computable number. But consider that some infinite bit sequences are not computable. The point is that an enumeration cannot be ordered arbitrarily right?

Suppose you have an oracle that gives you the nth digit of an uncomputable number. Does anything change?
 
  • #13
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
3,898
171
I think it's a neat result that the diagonal is irrational.
 
  • #14
PeterDonis
Mentor
Insights Author
2019 Award
31,124
10,040
I think it's a neat result that the diagonal is irrational.
That's not the result. The diagonal, by hypothesis, is a repeating decimal, which represents a rational number. But it is a rational number that is not in the list.
 
  • #15
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
3,898
171
I'm confused. Isn't the actual theorem if you write down an enumeration of the rational numbers, the diagonal is an irrational number?
 
  • #16
370
219
I'm confused. Isn't the actual theorem if you write down an enumeration of the rational numbers, the diagonal is an irrational number?
Yes.
 
  • #17
109
11
Does it matter at all how we think about rearranging? I mean, you have an infinite list, which by definition (as an enumeration) is computable. So now you want to rearrange it. To do so, you need another computable number. But consider that some infinite bit sequences are not computable. The point is that an enumeration cannot be ordered arbitrarily right?
In this case I'm talking about the list of all rational numbers. All rational numbers are computable (because all rational numbers have a finite recurring decimal pattern), and being countable, the list of all rational numbers is enumerable, and listable in any order you want (and it's even possible to list them without repetitions).

The thing I noticed during this is that no matter how you order the list of all rational numbers, the diagonal will always form an irrational number. (Might be a somewhat trivial result, but I found it interesting.)
 
  • #18
PeterDonis
Mentor
Insights Author
2019 Award
31,124
10,040
The thing I noticed during this is that no matter how you order the list of all rational numbers, the diagonal will always form an irrational number.
No, that is not what your argument in the OP of this thread proves. See my post #14.
 
  • #19
109
11
No, that is not what your argument in the OP of this thread proves. See my post #14.
Do you mean that the proof I wrote in my original post is not enough to prove the hypothesis that the diagonal of the list of all rational numbers (no matter how it's ordered) always forms an irrational number?

If the proof is not complete, what would make it complete?
 
  • #20
370
219
Peter, I think you may be confused. The standard cantor argument is on the reals, and proves the reals are not enumerable because if you had such an enumeration you could construct a real number not in the list.

The op is asking about the rationals, and in this case the interesting thing is that the diagonal of an enumeration of the rationals must be irrational, because we know that the rationals are enumerable.

This means that you cannot enumerate the rationals in a way that gives an irrational number on the diagonal. It's not obvious why that should be at face value.
 
Last edited:
  • #21
PeterDonis
Mentor
Insights Author
2019 Award
31,124
10,040
Do you mean that the proof I wrote in my original post is not enough to prove the hypothesis that the diagonal of the list of all rational numbers (no matter how it's ordered) always forms an irrational number?
Yes.

If the proof is not complete, what would make it complete?
It can't be made "complete" in the sense you mean. Your scenario specifies that the diagonal sequence being constructed is a repeating decimal. All repeating decimals represent rational numbers.

What your proof actually shows is that no complete enumeration of the rational numbers can have the property you specified, of having the digits on its main diagonal form a repeating decimal. In other words, any enumeration of the rational numbers that does have the digits on its main diagonal form a repeating decimal must leave out at least one rational number.

I am surprised that you don't get this, since you stated it explicitly in your OP in this thread:

if we now apply the diagonal argument and take those digits in the diagonal and eg. increment each of them (with 9 wrapping around to 0), we would get a number that has an infinitely repeating decimal sequence, which is rational, but which is different from all the numbers in the list. Which contradicts the premise that the list contained all the rational numbers.

Since we know that every number with an infinitely repeating decimal sequence is a rational number, the only possible conclusion is that it's not possible to list all the rational numbers in an order such that their diagonal forms a repeating sequence (even if that repeating sequence has all the digits).
See the bolded items in the above quote.
 
  • #22
PeterDonis
Mentor
Insights Author
2019 Award
31,124
10,040
The op is asking about the rationals, and in this case the interesting thing is that the diagonal of an enumeration of the rationals must be irrational
No, that is not what the OP argument proves. See my posts #14, and now #21.

Everyone, please read what the OP actually says. I bolded the key statements in post #21.
 
  • #23
370
219
In this case I'm talking about the list of all rational numbers. All rational numbers are computable (because all rational numbers have a finite recurring decimal pattern), and being countable, the list of all rational numbers is enumerable, and listable in any order you want (and it's even possible to list them without repetitions).

The thing I noticed during this is that no matter how you order the list of all rational numbers, the diagonal will always form an irrational number. (Might be a somewhat trivial result, but I found it interesting.)
Yes, I know that. But the thing is, it is not listable in any order you want. It's only listable in an order that is computable. It means you have to be able to have a program with finite source code that can do the listing or rearranging.
 
  • #24
PeterDonis
Mentor
Insights Author
2019 Award
31,124
10,040
Yes, I know that.
No, you don't. As I've already pointed out several times now, the OP does not prove that the diagonal will form an irrational number. It explicitly states the opposite: that the diagonal number, by construction, is rational.

It's only listable in an order that is computable.
This is not a requirement for an enumeration.
 
  • #25
370
219
No, you don't. As I've already pointed out several times now, the OP does not prove that the diagonal will form an irrational number. It explicitly states the opposite: that the diagonal number, by construction, is rational
Which is a contradiction that there existed an enumeration of Q which forms a rational on the diagonal, thus no enumeration of Q can have a rational on the diagonal.
 

Related Threads on Another consequence of Cantor's diagonal argument

  • Last Post
Replies
2
Views
2K
  • Last Post
2
Replies
49
Views
9K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
1
Views
1K
  • Last Post
2
Replies
38
Views
9K
  • Last Post
Replies
2
Views
2K
Replies
55
Views
1K
  • Last Post
3
Replies
62
Views
5K
  • Last Post
Replies
17
Views
858
Top