B Another consequence of Cantor's diagonal argument

[Warp]

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

 

[Warp]

(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?

 

[PeterDonis]

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.

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.

 

[SSequence]

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, let's 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)

 

[FactChecker]

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.

 

[SSequence]

@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)

 

[Warp]

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.

 

[Jarvis323]

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

 

[PeterDonis]

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.

 

[Jarvis323]

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?

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.

 

[PeterDonis]

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.

 

[Jarvis323]

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?

 

[Office_Shredder]

I think it's a neat result that the diagonal is irrational.

 

[PeterDonis]

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.

 

[Office_Shredder]

I'm confused. Isn't the actual theorem if you write down an enumeration of the rational numbers, the diagonal is an irrational number?

 

[Jarvis323]

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.

 

[Warp]

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

 

[PeterDonis]

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.

 

[Warp]

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?

 

[Jarvis323]

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.

 

[PeterDonis]

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.

 

[PeterDonis]

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.

 

[Jarvis323]

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.

 

[PeterDonis]

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.

 

[Jarvis323]

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.

 

[PeterDonis]

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.

No. You are misstating the argument in the OP.

The argument given in the OP is:

We assume that there is an enumeration of the rationals that has an infinite repeating decimal on the main diagonal.

The diagonalization method of Cantor then ensures that we can explicitly construct another infinite repeating decimal (the one obtained by shifting each digit in the infinite repeating decimal on the main diagonal by one, wrapping 9 around to 0) which cannot be in the enumeration.

Since any infinite repeating decimal is rational, we thus have proven that any enumeration of the rationals that has an infinite repeating decimal on the main diagonal must be incomplete.

The argument does not prove that there cannot be an enumeration of the rationals that has an infinite repeating decimal on the main diagonal. It only proves that if such an enumeration exists, it must be incomplete.

The argument does not prove that no enumeration of the rationals can have a rational on the main diagonal. It is perfectly possible, consistent with the argument, that such an enumeration exists.

 

[Warp]

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:

I don't understand. That's exactly the conclusion I'm drawing. Namely: "If you take the list of all rational numbers, it's impossible to rearrange this list in a manner that the main diagonal of their decimal representation would form a rational number."

But then you say that's not a correct conclusion from the proof (or that the proof is not enough to prove that conclusion). I don't understand.

(Maybe you missed the part where I say "the list of all rational numbers"?)

 

[PeterDonis]

"If you take the list of all rational numbers, it's impossible to rearrange this list in a manner that the main diagonal of their decimal representation would form a rational number."

Here is your statement in the OP of what your OP argument shows:

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.

This does not say the same thing as the quote from you at the top of this post. Can you offer an additional argument that gets from the second statement of yours quoted above (the one from the OP of this thread) to the first (the one from your post #27)?

 

[Warp]

Yes: A number is rational if and only if its decimal representation has a recurring decimal (ie. an infinitely repeating pattern of digits).

In other words, if the decimal representation of a number has an infinitely repeating pattern of digits (even if this repeating pattern is just "0"), it is a rational number.

As a consequence, the decimal representation of an irrational never has a repeating pattern of digits.

Therefore, if it's not possible to list all the rational numbers in an order such that the diagonal of their decimal representation has an infinitely repeating sequence, that means that said diagonal always forms an irrational number, no matter how you rearrange the list of rational numbers.

 

[Office_Shredder]

Maybe the problem is this

The argument does not prove that there cannot be an enumeration of the rationals that has an infinite repeating decimal on the main diagonal. It only proves that if such an enumeration exists, it must be incomplete.

I think most people are using the word enumeration to mean a complete enumeration.

 

[PeterDonis]

A number is rational if and only if its decimal representation has a recurring decimal (ie. an infinitely repeating pattern of digits).

As you described it in the OP, a "recurring decimal" is a number like .0123456789..., i.e., it repeats starting with the first digit (talking only of digits after the decimal point, i.e., numbers between 0 and 1).

Not all rational numbers have that property. They all have the property that the decimal representation becomes repeating eventually, but they do not all have the property that the decimal representation starts repeating at the first digit.

 

[Office_Shredder]

If the diagonal is rational, then it starts repeating at some point down the list, and you can just flip the digits in the manner specified at that point. What you do for the first n digits of the number you're constructing doesn't matter.

 

[Warp]

Are you saying that my original argument does not prove that "no enumeration of all the rational numbers will form a rational number in its main diagonal" because rational numbers may have an arbitrarily large non-repeating string of digits before the recurring decimal part, and thus any "non-fitting" rationals could be placed at the beginning of the list, before the ones that participate in forming the recurring decimal of the diagonal?

I suppose there's a point there. Maybe the proof becomes complete when it's proven that there's an infinite amount of "non-fitting" rationals, and the beginning part of the decimal expansion of any rational number (ie. the part before the recurring decimal) is always finite? (It may be arbitrarily long, but always finite.)

 

[PeterDonis]

Are you saying that my original argument does not prove that "no enumeration of all the rational numbers will form a rational number in its main diagonal" because rational numbers may have an arbitrarily large non-repeating string of digits before the recurring decimal part, and thus any "non-fitting" rationals could be placed at the beginning of the list, before the ones that participate in forming the recurring decimal of the diagonal?

That was the sort of possibility I was thinking of, yes. However, I now realize that that objection is not valid.

The diagonalization process applied to any infinite sequence of infinite strings of digits will produce an infinite string of digits that cannot be in the sequence. That is always true. So if we have an infinite sequence of infinite strings of digits that we assume to include representations of all of the rational numbers (and such a sequence must exist because we know the rationals are countable), the diagonalization process applied to that sequence will have to give us an infinite string of digits that does not represent a rational number.

So now we can look at things in reverse, so to speak, and ask: given the infinite string of digits that we obtained from the diagonalization process as described above, which, as noted above, must represent an irrational number--call this string I--is it possible that the infinite string of digits on the main diagonal of the infinite sequence, the one we applied the "shift each digit by one, wrapping 9 to 0" algorithm to to obtain string I--call it string D--represented a rational number?

I think the answer to this question is no. Or, to put it another way, I think we can prove that applying any "digit shift" algorithm--i.e., an algorithm that shifts each digit the same way--to an infinite sequence of digits that represents a rational number, must result in an infinite sequence of digits that also represents a rational number. The proof seems simple, given that we know that any infinite string of digits that represents a rational number must eventually, after some finite number of digits, become an infinitely repeating string. And it seems obvious that applying any digit shift algorithm that shifts each digit the same way to an infinite string of digits that has this property, will produce another infinite string of digits that also has this property.

In other words, the set of infinite digit strings that represent rational numbers is closed under the "digit shift algorithm" operation. And that, I think, is sufficient to prove what you are saying, that any sequence of infinite digit strings that contains representations of all the rational numbers must have an infinite digit string that represents an irrational number on its main diagonal.

 

[Tendex]

Cantor's diagonalization schemes as is well known reveal the limitations of axiomatic set theory impredicativity involving infinite sets. Besides the inevitability of uncountable sets starting from countable infinite constructions(which is more frequently seen rather than as a limitation as an enrichment;"Cantor's transfinite paradise") it is used to prove Godel's incompleteness and the halting problem.

 

[JeffJo]

Since I missed out on the previous "debate," I'll point out some things that are appropriate to both that one and this one.

Here is an outline of Cantor's Diagonal Argument (CDA), as published by Cantor. I'll apply it to an undefined set that I will call T (consistent with the notation in Wikipedia). One important property of the elements t of T, is that each is a surjection from the natural numbers N to some set of characters C.

• Cantor used the set of two characters C={'m','w'}
• Wikipedia used the set of two characters C={'0','1'}
• When taught to teenagers, it is usually the decimal representation of real numbers, so it uses C={'0','1','2','3','4','5','6','7','8','9'}. With some additional steps.

Part A, "For any subset S of T, if S is countable, then S is a proper subset of T" (see note). Proof:

1. Let S be any subset of T, proper or improper, that is countable.
2. So a bijection b(n): N ->S exists.
3. Construct a new function s0:N->C such that that s0(n) is not equal to b(n)(n).
4. Prove that s0 is in T, but not in S.
5. QED.

Part B, basically as Cantor worded it:

From Part A, it follows immediately that T is uncountable. Otherwise we would have the contradiction, that an object s0 would be both an element of T, but also not an element of T.​

Part B, as I would word it:

The contrapositive of the proposition is Part A is "For any subset S of T, if S is not a proper subset of T, then S is not countable.​

​

This is applicable here, because the new proposition Warp is trying to prove doesn't fit step A4. The elements of his set T always degenerate to a repeating sequence (i.e., are rational numbers). To apply CDA, he has to prove that his s0 also degenerates like that, so it is in T, and also is not in the set S.

Note: What Cantor actually wrote is closer to "If s1, s2, …, sn, … is any simply infinite series of elements of T, then there always exists an element s0 of T, which cannot be connected with any element sn."
+++++

The problem Warp has with CDA, as it is usually taught, is that it is indeed logically invalid. I'm not saying the conclusion is wrong, just that the one-part CDA that is usually taught is invalid.

To apply proof by contradiction, one must use everything in the assumption to establish the contradiction. If I assume that the moon in made of individually wrapped packets of green and bleu cheeses, in a ratio that equals the square root of two, I can derive the contradiction that an even number must be equal to an odd number. But I only use the assumption about the ratio, not the kinds of cheeses that comprise the moon. So all I prove is that the square root of two is irrational.​

​

Similarly, as CDA is usually taught, only the assumption "there is a list" is used to derive the alleged contradiction. Never the assumption that this list is complete. What Part A proves, directly, is negation of the unused part. Which is why proof-by-contraposition is logically more valid than proof-by-contradiction. This is actually an age-old criticism of proof-by-contradition.​

 

[Jarvis323]

To apply CDA, he has to prove that his s0 also degenerates like that, so it is in T, and also is not in the set S.

I think what Warp has done is offer a sketch of a proof using the technique of diagonalization. It's not Cantor's original argument, nor is the goal or format the same.

It seems to me that diagonalization in this case is done on an enumeration of a particular set (which we already know is countable) and this is not a proof by contradiction as in Cantor's case. We already know the assumption is true. Then by construction s0 is defined. T is the reals and S is the rationals. We know already that S is a proper subset of T. And we don't need to show s0 is rational, we need to show it is in T (real) and not in S (not rational). Once that is done, the proof is complete.

A real/robust proof would need to be more careful in the details to fully convince. What about the arbitrary size of the whole portion? s0 doesn't have digits which don't affect the value, e.g. preceding 0s? But leeway is afforded to the sketch because it is a sketch of a known proof with a known result.

I may be wrong as I have been prone to be lately.

I think the confusion has been due to the OP saying Cantor's diagonalization argument, rather than just diagonalization, or maybe Cantor's diagonalization technique, which would be more specific. It is true that Cantor's specific argument doesn't work in this case.

 

[Warp]

The problem Warp has with CDA, as it is usually taught, is that it is indeed logically invalid.

Note that I don't "have a problem" with the diagonal argument. In this thread I simply explained that when thinking about it, I noticed that it appears to be impossible to rearrange the entire set of rational numbers in such an order that the main diagonal (or any diagonal in that direction for that matter) of their decimal expansion (or using any base) forms a rational number. I noticed this because the diagonalization method seems to produce a rational number that's different from any in the list, which contradicts the original setting (ie. that the list contains all rational numbers). And my question was if there's perhaps an intuitive way of understanding why it's impossible.

Essentially, the diagonalization process seems to prove that no matter what the rational number it is that you are trying to produce on the diagonal, you can always produce rational number that can't be put anywhere in the list (in such a manner that its corresponding digit on that diagonal is the correct one). And since it's relatively trivial to prove that there are infinitely many such "non-fitting" rational numbers, the only conclusion is that it's impossible to rearrange the list in such a manner.

Curiously, there's no limit to how long you can make the repeating pattern in the diagonal by rearranging the list of rationals, ie. you can make it arbitrarily long, but you cannot make the repeating pattern infinite. By necessity, if you make the repeating pattern in the diagonal infinite, the list will then be missing most rational numbers.

 

[Jarvis323]

Note that I don't "have a problem" with the diagonal argument. In this thread I simply explained that when thinking about it, I noticed that it appears to be impossible to rearrange the entire set of rational numbers in such an order that the main diagonal (or any diagonal in that direction for that matter) of their decimal expansion (or using any base) forms a rational number. I noticed this because the diagonalization method seems to produce a rational number that's different from any in the list, which contradicts the original setting (ie. that the list contains all rational numbers). And my question was if there's perhaps an intuitive way of understanding why it's impossible.

Essentially, the diagonalization process seems to prove that no matter what the rational number it is that you are trying to produce on the diagonal, you can always produce rational number that can't be put anywhere in the list (in such a manner that its corresponding digit on that diagonal is the correct one). And since it's relatively trivial to prove that there are infinitely many such "non-fitting" rational numbers, the only conclusion is that it's impossible to rearrange the list in such a manner.

Curiously, there's no limit to how long you can make the repeating pattern in the diagonal by rearranging the list of rationals, ie. you can make it arbitrarily long, but you cannot make the repeating pattern infinite. By necessity, if you make the repeating pattern in the diagonal infinite, the list will then be missing most rational numbers.

Maybe an intuitive reason is that there is no limit to how long the non repeating part can be for a rational number, just like there is no largest natural number. Imagine taking the number on the diagonal with the bits flipped, out to row i. For any i, there still exists a rational number with the same sequence up to i, which doesn't start repeating until after i. This goes on and on forever. You always have another rational number on the list which has the sequence you have produced so far as part of its non-repeating section.

Diagonalization is however some kind of complete infinite mapping over the whole list, and this means that always growing non-repeating part you are chasing gets extended to infinity.

It's sort of like how the sum of the natural numbers diverges, even though each of the numbers is finite. In the diagonalization of rationals, you are going through numbers with finite non-repeating parts but the diagonalization produces an infinite non-repeating part, because there are infinity many finite non-repeating parts.

 

[SSequence]

I think that this kind of result can probably be generalized a great deal. One reason to think so seems to be that this kind of result applies to many subsets of the interval $[0,1]$ of real numbers. But I haven't thought about in a proper detailed way to generalize this. Maybe it is relatively easy to do so, maybe it isn't.

Possibly one way to think is to consider the "controlling" of digits available in some subset of real interval $[0,1]$. Basically any subset of $[0,1]$ which has few basic "closure properties" will be guaranteed have this property hold.

For example, suppose we define a computable number in the interval $[0,1$] by a total computable function of the form $f:\mathbb{N} \rightarrow \{0,1,2,3,4,5,6,7,8,9\}$. Now we have subset of the interval $[0,1]$, whose elements are only those numbers whose decimal expansions are (total) computable. Call this set $C$. Then we have the following result:
"For any possible (complete) enumeration of the set $C$ (repetitions allowed), if we denote the number defined by taking the diagonal digits as $c$ then $c \notin C$."

We can similarly define a set $P \subset [0,1]$ where a number belongs to $P$ iff its decimal expansion is primitive recursive. By the decimal expansion being p.r. it is simply meant that there should exist a p.r. function $f: \mathbb{N} \rightarrow \{0,1,2,3,4,5,6,7,8,9\}$ which agrees with the decimal expansion. We have a similar result again:
"For any possible (complete) enumeration of the set $P$ (repetitions allowed), if we denote the number defined by taking the diagonal digits as $p$ then $p \notin P$."

Denoting $Q$ for set of rational numbers ... if we define $S=Q \cap [0,1]$ (the interval [0,1] is implicitly meant to be of real numbers), then we have a similar result to the above two again. [this is what the discussion in this thread has been about mainly]

 

[PeterDonis]

any subset of $[0,1]$ which has few basic "closure properties" will be guaranteed have this property hold.

The key closure property is the one I described in post #34: closure under the "digit shift" operation (shifting each digit of the number by a constant, wrapping around from the last digit in the set of digits to the first one). That is the key closure property because the digit shift operation is the one that is applied in the diagonal construction.

 

[SSequence]

Yes, your second last paragraph in post#34 looks correct to me. The way I see it is that diagonalization is a simple but general technique that can be applied in many contexts/settings.

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

I haven't about it in detail (so hopefully I am not making a silly mistake) but for the specific case w.r.t. real numbers, one point seems to be that if we have $S=\{0,1,2,3,4,5,6,7,8,9\}$ and the digit change function $f:S \rightarrow S$, as a specific example, is like:
$f(n)=n+2$ for $0 \leq n<8$
$f(8)=0$
$f(9)=1$
So if a subset of real interval [0,1] is closed under a digit change operation such as the above then one can see immediately that a result similar to one in OP is guaranteed to work (for the given subet of [0,1]).

But if the given subset of [0,1] is only closed under something like the following digit change operation:
$f(n)=n+1$ for $0 \leq n<9$
$f(9)=0$
then we probably would have to do a bit of additional working to make sure the result similar to one in OP applies. [I haven't thought about whether such a result will apply here in all possible cases or not]

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

At any rate, this sort of point is no longer relevant when we are diagonalizing over something like functions etc.

 

[PeterDonis]

$f(n)=n+2$ for $0 \leq n<9$
$f(9)=1$

This can't work as you state it, since there is no well-defined result for $f(8)$. To be a proper "cyclic" function, you should have $f(n)=n+2$ for $0 \leq n<8$, $f(8) = 0$, $f(9) = 1$.

if a subset of real interval [0,1] is closed under a digit change operation such as the above then one can see immediately that a result similar to one in OP is guaranteed to work (for the given subet of [0,1]).

But if the given subset of [0,1] is only closed under something like the following digit change operation:
$f(n)=n+1$ for $0 \leq n<9$
$f(9)=0$
then we probably would have to do a bit of additional working to make sure the result similar to one in OP applies.

I don't see why the second function would require additional work. Both of them are valid "cyclic" digit change operations, and should have the same closure properties as far as the diagonal construction is concerned.

 

[SSequence]

This can't work as you state it, since there is no well-defined result for $f(8)$. To be a proper "cyclic" function, you should have $f(n)=n+2$ for $0 \leq n<8$, $f(8) = 0$, $f(9) = 1$.

Right. I will edit the post.

I don't see why the second function would require additional work. Both of them are valid "cyclic" digit change operations, and should have the same closure properties as far as the diagonal construction is concerned.

I was just thinking about the point that such a function is not guaranteed to produce new real always. So I would have to think about it always working or not. Since I haven't thought about it, I didn't want to say that either of: "it always works" OR "sometimes it doesn't work".
[ note that context of my two posts just above was an arbitrary subset of real inteval [0,1]. The rational number in the interval [0,1] are one specific case of it. ]