Cantor diagonal argument-?

  • Thread starter phyti
  • Start date
  • #26
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
or that the theorem is false. you should check your definition before putting bold assertions.
I will give you the benefit of the doubt and assume you simply misread what I wrote. I will state it with more precision, and add an annotation in blue:


. Suppose you have a list of real numbers. (which may or may not contain all of the real numbers)
. Suppose you have an enumeration of said list.
. Applying Cantor's diagonal argument gives you a number not in the list.
. Therefore, said list cannot be a list of all real numbers.


You claim to have enumerated a list of real numbers. Therefore, your list does not contain all real numbers.
 
  • #27
16
0
I will give you the benefit of the doubt and assume you simply misread what I wrote. I will state it with more precision, and add an annotation in blue:


. Suppose you have a list of real numbers. (which may or may not contain all of the real numbers)
. Suppose you have an enumeration of said list.
. Applying Cantor's diagonal argument gives you a number not in the list.
. Therefore, said list cannot be a list of all real numbers.


You claim to have enumerated a list of real numbers. Therefore, your list does not contain all real numbers.
i will grant you the same benefit and point out that the construction i propose is based on the diagonal argument. every new sequence is the diagonal of the preceding sequences.
 
  • #28
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
Does your construction enumerate a list of reals? If so, then it's missing one.
 
  • #29
16
0
i am getting tired of authoritarian assertions, bold or blue. could somebody please come with a rational, logical argument?
By the way, i will grant you this: my construction does not enumerate the reals in an ordered sequence. but it still seems to me that any real would be eventually enumerated. as far as the syntax is concerned, binary sequences were used by Cantor himself as expression of real numbers.

"eventually" here is misleading. You can put reals in a one to one correpondence with the natural numbers, (in an unordered sequence) butyou cannot reach the end of an infinite sequence be it of reals or natural numbers. what counts is that in this construction you can not point at a real which will not be eventually output by the program.
 
Last edited:
  • #30
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
i am getting tired of authoritarian assertions, bold or blue. could somebody please come with a rational, logical argument?
Cantor already did. It's not my fault of you refuse to understand it.

By the way, i will grant you this: my construction does not enumerate the reals in an ordered sequence.
Just what do you think the word "enumerate" means? The simplest meaning to use is that an "enumeration of a set X" is a function that assigns to each natural number an element of X, such that each element of X is assigned to exactly one natural number. (i.e. a bijective function N->X)

In terms of computer science, an algorithm enumerates a set X if and only if every output the algorithm prints is an element of X, and every element of X is eventually printed.

Because an algorithm prints things one after another, they can be indexed by natural numbers. In particular, an algorithm cannot output an infinite collection of things, and then still do more stuff.

There are ways to generalize the notion of "algorithm" to allow it to proceed for a transfinite ordinal number of steps. However, the number of steps has to be uncountable if your "algorithm" is to print every real number. (and for the most natural generalizations I can imagine, it is known that the "algorithm" cannot be written explicitly)
 
Last edited:
  • #31
16
0
to enumerate means to every member of a set assign a natural number in such a way as not to miss any member of the set. it does not mean that the set should already be ordered, just that your procedure does not miss any member.
the simplest way of not missing any member of the set (let us say they are all in box A) is to take them in an arbitrary fashion and put them one by one in a box B, and while doing so, assigning a (consecutive) number to each.
The question is therefore: does my construction ensure that no real will be left over in box A? Once they are in box B they will be enumerated even if the numeral assigned to each real will be completely arbitrary.
 
  • #32
16
0
Cantor already did. It's not my fault of you refuse to understand it.


Just what do you think the word "enumerate" means? The simplest meaning to use is that an "enumeration of a set X" is a function that assigns to each natural number an element of X, such that each element of X is assigned to exactly one natural number. (i.e. a bijective function N->X)

In terms of computer science, an algorithm enumerates a set X if and only if every output the algorithm prints is an element of X, and every element of X is eventually printed.

Because an algorithm prints things one after another, they can be indexed by natural numbers. In particular, an algorithm cannot output an infinite collection of things, and then still do more stuff.

There are ways to generalize the notion of "algorithm" to allow it to proceed for a transfinite ordinal number of steps. However, the number of steps has to be uncountable if your "algorithm" is to print every real number. (and for the most natural generalizations I can imagine, it is known that the "algorithm" cannot be written explicitly)
you should really read Cantor. The diagonal argument is only valid for infinite sequences. a finite sequence is by definition incomplete.
 
  • #33
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
to enumerate means to every member of a set assign a natural number in such a way as not to miss any member of the set. it does not mean that the set should already be ordered
The meaning of the adjective "ordered" refers to the fact that if we swap two of the labels, we consider that a different sequence.

e.g. the ordered sequences (1,2,2,3) and (2,1,3,2) are different. But the unordered sequences {1, 2, 2, 3} and {2, 1, 3, 2} are the same. (I'm using {..} to denote a multiset here, not an ordinary set)


The question is therefore: does my construction ensure that no real will be left over in box A? Once they are in box B they will be enumerated even if the numeral assigned to each real will be completely arbitrary.
You have labelled countably many real numbers. Therefore, there are uncountably many real numbers without label. Cantor's diagonal argument explicitly constructs a real number that fails to be labelled.

For any natural number n, let f(n) denote the real number that you labelled with n.

For any real number s, let s<n> denote the n-th digit to the right of the decimal expansion of s. (If a number has two decimal expansions, use the one that ends in all 0's instead of the one that ends in all 9's)

Define a real number r whose n-th digit is given by

[tex]
r\langle n \rangle = \begin{cases}
4 & f(n)\langle n \rangle \neq 4 \\
6 & f(n)\langle n \rangle = 4
\end{cases}
[/tex]

Observe that, for every n, we have the following fact:

[tex] r\langle n \rangle \neq f(n) \langle n \rangle[/tex]

and therefore

[tex]r \neq f(n)[/tex].

In other words, r is unlabelled.
 
  • #34
16
0
we are turning in circles. I am questioning the validity, or at least the universality, of Cantor's argument. you reply by explaining to me what cantor's argument means. i wish you were less didactic and more to the point.
i am using the diagonal argument to show that cantor's conclusion is not universally valid. you can chose to restrict the definition of the concepts involved in such a way as tp preserve the conclusion, but that is surely not satisfactory.
So please, show me if and where i am wrong, not in general because everybody thinks cantor is right, but because somewhere in my argumentation there is something that does not add up. i am still waiting.
in short, my argumenation is itself a diagonal argument> i use the form used by cantor to prove him wrong.
 
  • #35
D H
Staff Emeritus
Science Advisor
Insights Author
15,393
683
There are ways to generalize the notion of "algorithm" to allow it to proceed for a transfinite ordinal number of steps.
This is what hachem has done with his algorithm. The diagonalization step is itself an infinite loop. What his algorithm does in essence is to generate the power set of aleph-null. In other words, it does not generate an enumerable list.
 
  • #36
16
0
everybody seems keen to restrict the meaning of enumerate to a specific form of enumerating. for me it means notning more than a way to assign a numeral in consecutive order of processing (the first you take out of box A gets the number 1, the second the number 2, etc). What you must do to get the items out of box A into box B is irrelevant, as long as you process them all. Now the point is that the procedure itself must ensure that we do not miss any item in box A. does my procedure ensure that, if not, what is wrong with it?
furthermore, speaking of aleph-null presupposes the validity of the diagonal argument, which, once again, is put here to the question.
more precisely, whether the diagonal argument, which is in itself a valid form of argumentation, is sufficient to sustain cantor's conclusion of the un-enumerability of reals (and therefore of the existence of different infinites).
 
Last edited:
  • #37
D H
Staff Emeritus
Science Advisor
Insights Author
15,393
683
An non-finite enumerable set can be placed in one-to-one with the integers. You are assuming your algorithm generates an enumerable set. It does not. Your diagonalization step ensures that this is the case.
 
  • #38
16
0
quote D H :"An non-finite enumerable set can be placed in one-to-one with the integers. You are assuming your algorithm generates an enumerable set. It does not. Your diagonalization step ensures that this is the case."
if you mean by that that being a form of diagonal argument is sufficient to sustain the conclusion that the algorithm is not producing an enumerable set, then i am afrais that you are only rehearsing the ad hominem or authority argument. you are also assuming what is exactly in question. that would make it a circular argumentation.
furthermore, i am not assuming my algorith generates an enumerable set, i am trying to prove it. that is what you must prove wrong.
 
  • #39
D H
Staff Emeritus
Science Advisor
Insights Author
15,393
683
The burden of proof is on you, the proponent, not on me. That said, Cantor's diagonalization argument disproves your conjecture. Now lets look at your algorithm.

In pseudocode (and only the main lines):
1- ouput an arbitrary infinite binary sequence
2- output a second, different from the first, infinite binary sequence
Both of these steps require an infinite amount of time. You can't use either recursively.
 
  • #40
16
0
quote D H: Both of these steps require an infinite amount of time. You can't use either recursively.

Cantor's diagonal argument is based on infinite sequences. you either grant me the same right or disprove cantor. you cannot have it both ways.
 
  • #41
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
So please, show me if and where i am wrong, not in general because everybody thinks cantor is right, but because somewhere in my argumentation there is something that does not add up. i am still waiting.
You don't have an argument. You simply (imprecisely) state an algorithm, ask us if it provides an enumeration of the reals, and then complain when we prove that it does not. I have seen no attempt by you to actually prove your algorithm enumerates the reals.
 
Last edited:
  • #42
D H
Staff Emeritus
Science Advisor
Insights Author
15,393
683
You are doing something entirely different than Cantor's diagonalization theorem. You are using nested recursion, i.e., transfinite recursion. End of story.
 
  • #43
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
DH: I have assumed (possibly incorrectly) that when hachem says "output an arbitrary infinite binary sequence", he means to output a real number. And by Cantor's other diagonal argument, (or equivalently, by introducing multitasking) an ordinary Turing machine is capable of outputting a (coutably) infinite sequence of (countably) infinite binary sequences.

(of course, it's still not capable of outputting all countably infinite binary sequences)

(and, of course, there exist infinite binary sequences that cannot be printed by a Turing machine)
 
Last edited:
  • #44
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
Cantor's diagonal argument is based on infinite sequences. you either grant me the same right or disprove cantor. you cannot have it both ways.
(1) The diagonal argument doesn't purport to be an algorithm that can be executed on a Turing machine. You, on the other hand, have presented an algorithm, and therefore suffer from that constraint.

(2) On the other hand, it is very easy to convert the diagonal argument into a computable function, since it doesn't need access to the entire infinite sequence of infinite sequences; in order to compute the n-th digit of its output, it simply needs to read the (n, n)-th digit of the input data.
 
  • #45
16
0
well, that's it then. end of story. does not fit in what you have learned, therefore it must be wrong.
what the algorithm does is legitimate by cantorian standards. you are defending the same position his opponents were during his lifetime. In other words, you are setting back the history of mathematics by just a little more than a century.
The use of pseudo-code is a legitimate means of proof. i am not a programmer but even i can say that it would be very easy to write it in a computer language.
The problem of the infinite statements would remain though, for that i would advise you to (re) read cantor and/or follow a course in the philosophy of mathematics. i thank you for this discussion which has served to convince me that my algorithm is at least worth studying carefully. not being a mathematician either i am of course highly interested in the opinon of experts.
 
  • #46
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
well, that's it then. end of story. does not fit in what you have learned, therefore it must be wrong.
The claim that (given the traditional definitions) the reals are enumerable is in the same category as claims such as "1 = 0".

Unless you are just presenting yourself extremely poorly, you are not doing something that "doesn't fit in" with what I have learned; you are doing something that actually does fit in with what I have learned, but for some inexplicable reason insist on assuming a contradiction.


The use of pseudo-code is a legitimate means of proof.
Pseudocode can be used in a proof. However, by itself, it is not a proof, because it is a presentation of an algorithm, not a deductive argument that derives conclusions from hypotheses.


not being a mathematician either i am of course highly interested in the opinon of experts.
Funny; I am both a mathematician and a computer scientist, and you seem to be entirely disinterested in both my opinion and my expertise.
 
Last edited:
  • #47
16
0
quote Hurkyl:
(1) The diagonal argument doesn't purport to be an algorithm that can be executed on a Turing machine. You, on the other hand, have presented an algorithm, and therefore suffer from that constraint.

(2) On the other hand, it is very easy to convert the diagonal argument into a computable function, since it doesn't need access to the entire infinite sequence of infinite sequences; in order to compute the n-th digit of its output, it simply needs to read the (n, n)-th digit of the input data.
__________________
i think it is wrong to turn it into a realizability issue. cantor's argument is based on the infinite, his whole philosophy is based on (the different forms of ) the infinite. once again, it makes no sense to apply his arguments to finite sequences, his position was so controversial exactly because he assumed the actual infinite in his argumentation.
 
  • #48
16
0
as far as 1=0; i am sorry to say that all you offered me was the claim of authority. i am not even claiming that reals are enumerable, only saying that the diagonal argument as used by cantor is not conclusive, and that my algorithm is here to sustain this last claim. if you still want to stick to the non-enumerability of reals, as i expect you will, i say you should look for other, better arguments.
 
  • #49
gel
533
5
In other words, you are setting back the history of mathematics by just a little more than a century.
The use of pseudo-code is a legitimate means of proof.
None of the other posters are setting anything back. Your pseudocode does not prove anything.

1- ouput an arbitrary infinite binary sequence
2- output a second, different from the first, infinite binary sequence
3- infinite loop: construe and output the diagonal of the preceding
sequences.
If you did this, you can still construct a new number that isn't in your list by the diagonal argument. I'm not sure what step 3 is supposed to prove - on the n'th step all it does is give you a number not equal to the previous n-1 numbers.
 
  • #50
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
i am not even claiming that reals are enumerable, only saying that the diagonal argument as used by cantor is not conclusive
Cantor's argument is a fully rigorous, deductive proof that there is no bijection between the naturals and a reals. If you do not find that "conclusive", then I must conclude that you have no interest in doing or learning mathematics, and so there is no point in allowing this discussion to continue here.
 

Related Threads on Cantor diagonal argument-?

  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
2
Views
2K
  • Last Post
2
Replies
38
Views
9K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
2
Views
2K
  • Last Post
3
Replies
62
Views
5K
  • Last Post
Replies
17
Views
779
  • Last Post
4
Replies
86
Views
4K
Top