Another consequence of Cantor's diagonal argument

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