B Another consequence of Cantor's diagonal argument

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