Cantor Diagonal Argument disproof

Got a great idea? Tell the world about it here.

Moderators: mvs_staff, forum_admin, Marilyn

Re: Cantor Diagonal Argument disproof

Postby robert 46 » Sun Mar 19, 2017 11:56 pm

Gofer wrote:
robert 46 wrote:g(n,m) returns 0 or 1 for every integer n and m. How? What are the parameters n and m? Are n and m indices into a 2-dimensional array?

One could interpret g as a two-dim. array. It does not matter how g returns a 0 or 1, just that it does; that is our description of it.

Insufficiently defined.
h(x)=flip(g(x,x)), so
h(x)=flip(g(N,x)) requires x=N, and h(x)=flip(g(x,M)) requires x=M. Thus the invocation of h(x) must be h(N) in the first case, and h(M) in the second case. [I don't know what you are trying to express with this silliness of not distributing the single parameter of h(x) to g(x,x).]

You failed to comprehend my point! Your task is to show if there exist ONE integer M and N such that h equals those functions FOR ALL x's.

Don't project your inanity on me. Whereas h(x)=flip(g(x,x)) you cannot introduce a different parameter into the invocation of the function. And you cannot redefine the function. Is this clear to you???
FYI: there is no recursive function which will work on an infinite list; there is no iterative function which will work on an infinite list;.

Of course there is such a function! In fact, in Haskell, the data type 'stream' is recursively defined WITHOUT an end, meaning it's infinite, and there are plenty of functions defined on it.

The data type "stream" refers to such things as a character input stream, and a character output stream. It works on one character at a time, but has a finite buffer to store characters for subsequent input or output. It is a FIFO list which is filled by one device and emptied by another. To think that it is "infinite" is ignorant nonsense.

Robert 46 wrote: So if the Sieve cannot work on an infinite array,

It is not defined for infinite arrays

And if it was defined for working on an infinite array, then what???

Meaningless statement!

Here is a definition of the Sieve of Eratosthenes which is defined to work on an infinite array:

To find all the prime numbers by Eratosthenes' method:
1.Create a list of consecutive integers from 2 through infinity: (2, 3, 4, ...).
2.Initially, let p equal 2, the smallest prime number.
3.Enumerate the multiples of p by counting to infinity from 2p in increments of p, and mark them in the list (these will be 2p, 3p, 4p, ...; the p itself should not be marked).
4.Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this new number (which is the next prime), and repeat from step 3.
5.When the algorithm terminates, the numbers remaining not marked in the list are all the primes.

If step 1 is impossible, then creating the list of Cantor strings from the set is also impossible.
robert 46 wrote: then why is it that the Diagonal method can work on an infinite list?

because it is defined to work on infinite lists of a certain type (having sufficient number of letters per row).

"Defining" it to work doesn't prove that it works: "The proof is in the pudding", as they say.


Try making some sense! It is clear that the Diag. method only fails if it fails to access a letter in a row, which only happens if the string on that row has too few letters; surely that is not hard to comprehend.

Maybe it is too hard for you to comprehend that the Diagonal method can only work on what it is given. If given a finite list of finite elements it can only work to the width, w, or length, l, whichever is shorter.
And if the list is finite and the method terminates, it ALWAYS constructs a string not equal to any previous string in the list.

And the reason why is because the method cannot examine the entire assumed complete list because it is longer than it is wide. However, it does terminate in the finite case, which is more than can be said for the infinite case.
robert 46
Intellectual
 
Posts: 2762
Joined: Mon Jun 18, 2007 9:21 am

Re: Cantor Diagonal Argument disproof

Postby Gofer » Mon Mar 20, 2017 6:08 am

One could interpret g as a two-dim. array. It does not matter how g returns a 0 or 1, just that it does; that is our description of it.

Insufficiently defined.


Irrelevant statement! One need not know g's implementation in order to construct h and analyze it, just like we do not need to know n's value in the Sieve method, just that it is an integer. We are essentially saying that if such a g with those properties exists, I can construct h having other properties.

Whereas h(x)=flip(g(x,x)) you cannot introduce a different parameter into the invocation of the function. And you cannot redefine the function.


You are still not getting it! I am NOT "redefining" h; I am saying there exist no integers M and N such that h equals any "row" or "column" in g. Is that clear to you?

The data type "stream" refers to such things as a character input stream, and a character output stream. It works on one character at a time, but has a finite buffer to store characters for subsequent input or output. It is a FIFO list which is filled by one device and emptied by another. To think that it is "infinite" is ignorant nonsense.


Again you misconstrue a definition for its implementation in the real world. It is DEFINED without end, but when simulated in a computer, it must have an end.

Your proposed "infinite" Sieve method cannot even find the prime number 5 because it fails to terminate when crossing off multiples of two. And it is not even close to the Diag. method which does not fail to find a single element for a list of infinite strings.

"Defining" it to work doesn't prove that it works: "The proof is in the pudding", as they say.


And the "pudding" in this case is infinite, so where/for which N exactly does the Diag. method terminate?

If given a finite list of finite elements it can only work to the width, w, or length, l, whichever is shorter.


Is it your point that when the Diag method has traversed N rows in the list, the constructed string so far could still be at the beginning of some later entry? Say that happens at row M, the constructed string just after row M would still differ at element M for that row, always!
Gofer
Intellectual
 
Posts: 237
Joined: Mon May 09, 2016 8:24 am

Re: Cantor Diagonal Argument disproof

Postby robert 46 » Mon Mar 20, 2017 8:52 am

Gofer wrote:
Whereas h(x)=flip(g(x,x)) you cannot introduce a different parameter into the invocation of the function. And you cannot redefine the function.

I am saying there exist no integers M and N such that h equals any "row" or "column" in g.

Recall that h(n)=flip(g(n,n)), and that g(n,n) returns a character 0 or 1. Therefore h(n) returns a character. The statement "h equals any row or column in g" is nonsensical because h does not return a string of characters, and g is purported to be a function, not necessarily an array.
...It is a FIFO list which is filled by one device and emptied by another

Again you misconstrue a definition for its implementation in the real world. It is DEFINED without end, but when simulated in a computer, it must have an end.

That is not the point. A stream is a FIFO list, and there is no implication that the list is filled faster than it is emptied such that the number of characters in it is ever infinite. In any case, if it was filled faster than emptied, it would take infinite time to become infinitely full because filling and emptying are iterative processes- they do not occur all-at-once.
Your proposed "infinite" Sieve method cannot even find the prime number 5 because it fails to terminate when crossing off multiples of two.

You mean "prime number 3". Whereas you believe the Diagonal method can examine infinite strings all-at-once, why can't Infinite-Eratosthenes cross off the multiples of 2 all-at-once?
And it is not even close to the Diag. method which does not fail to find a single element for a list of infinite strings.

They have the same problem: either they work sequentially and never terminate, or they work all-at-once. So, if Infinite-Eratosthenes doesn't work then neither does the Diagonal method.

"Defining" it to work doesn't prove that it works: "The proof is in the pudding", as they say.

And the "pudding" in this case is infinite, so where/for which N exactly does the Diag. method terminate?

"The proof is in the pudding" is a short version of "The proof of the pudding is in the eating". This means that to discover if the pudding is tasty it has to be eaten. So in the case of a proof, it must be tested to show that it works. Neither Infinite-Eratosthenes or Diagonal method working on infinite strings can be tested to show that they work.
If given a finite list of finite elements it can only work to the width, w, or length, l, whichever is shorter.

Is it your point that when the Diag method has traversed N rows in the list, the constructed string so far could still be at the beginning of some later entry?

I am saying that the constructed intermediate string is presumed padded with trailing zeroes, making it infinite, and that all the intermediate constructed strings could be at some later entries. I have proved that they are in the mirror case which works on integers. Read the entire topic to find it.

In the case of the Diagonal method working on reals, the intermediate strings are rational numbers with trailing 0s. Whereas the rational numbers are countable, a rational number cannot be the ultimate missing element because the rational numbers are a subset of the reals, and must be in the presumed complete list. Furthermore, the ultimate missing element cannot be a rational because it is impossible for it to contain a trailing repeating sequence. [1]


[1] The proof of this is that the probability is zero that the infinite diagonal element could be terminated with a repeating sequence.
robert 46
Intellectual
 
Posts: 2762
Joined: Mon Jun 18, 2007 9:21 am

Re: Cantor Diagonal Argument disproof

Postby Gofer » Mon Mar 20, 2017 9:44 am

Recall that h(n)=flip(g(n,n)), and that g(n,n) returns a character 0 or 1. Therefore h(n) returns a character. The statement "h equals any row or column in g" is nonsensical because h does not return a string of characters, and g is purported to be a function, not necessarily an array.


Try making some sense! Of course h returns a 0 or 1 for every integer. row M of g equals the function (g x M), and the opposite for the columns. The question is whether there exists functions (g x M) and (g N x) equaling h for some N and M? well?
I take it you know the definition of two functions being equal?

That is not the point. A stream is a FIFO list, and there is no implication that the list is filled faster than it is emptied such that the number of characters in it is ever infinite. In any case, if it was filled faster than emptied, it would take infinite time to become infinitely full because filling and emptying are iterative processes- they do not occur all-at-once.


Again you confuse an object's construction with its definition. The definition doesn't say anything about how it was constructed.

Your proposed "infinite" Sieve method cannot even find the prime number 5 because it fails to terminate when crossing off multiples of two.

You mean "prime number 3". Whereas you believe the Diagonal method can examine infinite strings all-at-once, why can't Infinite-Eratosthenes cross off the multiples of 2 all-at-once?


That's because the infinite Sieve has a sequential definition whereas the Diag. method hasn't.

No, I mean the prime number 5 because we know 3 is prime after running only a few steps of the infinite Sieve, but we have to wait and wait for the 5 to appear.

Neither Infinite-Eratosthenes or Diagonal method working on infinite strings can be tested to show that they work.


Strawman argument! since no infinite string could ever be created in the real world. As I've stated before, Cantor's theorem is NOT about the real-world EXISTENCE of infinite sets.

I am saying that the constructed intermediate string is presumed padded with trailing zeroes, making it infinite, and that all the intermediate constructed strings could be at some later entries.


That is incorrect! The "intermediate string" is simply a portion of the diagonal. Its "padding" is the 'yet to be evaluated later' portion of the string, if interpreted as a sequential algorithm.

And I have proved that they are in the mirror case which works on integers.
In the case of the Diagonal method working on reals, the intermediate strings are rational numbers with trailing 0s. Whereas the rational numbers are countable, a rational number cannot be the ultimate missing element because the rational numbers are a subset of the reals, and must be in the presumed complete list. Furthermore, the ultimate missing element cannot be a rational because it is impossible for it to contain a repeating sequence.


Strawman! Cantor's theorem has nothing to do with the reals or the integers except if used as indices.
Gofer
Intellectual
 
Posts: 237
Joined: Mon May 09, 2016 8:24 am

Re: Cantor Diagonal Argument disproof

Postby JeffJo » Mon Mar 20, 2017 9:50 am

Wikipedia lists two forms for Proof by Contradiction, but Gofer only uses that name for the first. Slightly edited, If A is the proposition to be proven:
  1. A is assumed to be false; that is, ~A is true.
  2. It is shown that ~A implies two mutually contradictory assertions, B and ~B.
  3. Since B and ~B cannot both be true, the assumption must be wrong and A must be true.
The second can be called “Proof of Negation”:
  1. A is assumed to be false.
  2. It is shown that ~A implies A.
  3. Since A and ~A cannot both be true, the assumption must be wrong and A must be true.
I say this can be called “Proof of Negation” because what you prove is the the negation of what you assumed. But Gofer seems to think it is:
  1. A is assumed to be false.
  2. It is shown that ~A implies A.
  3. Since A is true even if ~A is true, it must always be true.
See how this is saying that A is "proven by" the negation of what we assumed?

I believe it was on Tue Feb 21, 2017 12:34 pm that Gofer first claimed that Cantor’s Diagonal was “Proof by Negation,” an expression that is not recognized in any Mathematics that I know of. And in fact, the only hits for it on google, when I was trying to figure out what the **** Gofer was talking about, seemed to be ones where “Proof of Negation” was used and somebody confused it. Why Gofer continues to argue that one name is correct, and the other is not, is beyond me. As is why he continues to lie about the history here. He never pointed out that there was an author who said “Proof by/of Negation” was not “Proof by Contradiction” until after I found his error and the author. But my point was that I had to assume he used the wrong name, and referred to that author, to try to verify what he was talking about. I personally don’t care what the name is, as long as we can understand what he is talking about.

But there is a difference between the two names, and it leads to the error Gofer makes. Gofer correctly points out that in the first form of “Proof by Contradiction”, we infer A must be true because ~A can’t be true. That is, since we can’t accept a contradiction, by finding a contradiction that follows from ~A, we infer that we have proven A. But in fact, all we have proven is ~(~A). Some philosophers have postulated that there can be an “excluded middle” between A and ~A, call it X. So we can have both A and ~A be false, and X be true.

Whether or not you accept that (I don’t, unless the statement is a Godel sentence), “Proof by/of Negation” has the same fault. It does not prove A in all situations, which would be a “proof of” the negation of what it assumed. It only proves that there is the same kind of contradiction as before, and by finding it, it only proves ~(~A).

But that is all moot, because Cantor’s proof does not follow either form. According to Gofer (and hopefully he will recognize how I’m correcting what he said, using the set names Cantor did), the proposition is:
    Let M be the set of all Cantor Strings. Consider the two propositions:
  • A = “E is a set of Cantor Strings that can be counted.”
  • B = “E is equal to M.”
In Gofer’s words, what Cantor wants to prove is C=(B->~A). To use either form of Proof by Contradiction directly, we need to assume (~C) = (B and A). To use the second form, we need to prove that C follows from ~C, when in fact what Cantor proved is that A->~B. Yes, they are logically equivalent, but only after you apply contraposition, in which case the theorem is proven before you note that it is a contradiction.
JeffJo
Intellectual
 
Posts: 2551
Joined: Tue Mar 10, 2009 11:01 am

Re: Cantor Diagonal Argument disproof

Postby JeffJo » Mon Mar 20, 2017 10:04 am

robert 46 wrote:If these particular "Cantor strings" are used then only strings which "are all 0’s except the nth character, which is 1" are in the set.
You seem to be intentionally misrepresenting the proof. Is it because you have no valid counterargument, and must resort to your usual ploys? Or is it just that you refuse to even try to understand what you don't want to accept?

Cantor's proof is not predicated on assuming the diagonalized set, S, contains all Cantor strings. Besides, that was just an example of one set that is countable. You do understand what an example is, don't you?

This means that there is a square diagonal which is all 1's.
No, it doesn't. It means that there is an opened-ended list, of open-ended strings, with an open-ended diagonal that is all 1's. Because of the open-ended-ness, you can't call the "matrix" square, or taller-than-wide, or wider-than tall.

Negating this means that there is an element, D, which is all 0's. D does not belong to S, but D also does not belong to T because there is no single position which has a 1.
It means we constructed a string (not an "element") and called it D. In the example D is an open-ended string of 0's. That string is not in S, but it is in T. And the point of the proof is that D does belong to T, but does not belong to S. Therefore it is missing FROM S.

Cantor does not assume that his strings only "are all 0’s except the nth character, which is 1".
Never said he did. You do understand what an example is, don't you? And in fact., he never assumed anything about S except that it contained Cantor Strings, was infinite, and was countable. Which was clearly stated in 9C.

He assumes that the strings comprise all combinations of the two characters in all positions.
No, he assumes the strings in T comprise all such combinations. He only assumes that S has an infinite number of such strings, like in my example, and that it can be counted, like in my example.
JeffJo
Intellectual
 
Posts: 2551
Joined: Tue Mar 10, 2009 11:01 am

Re: Cantor Diagonal Argument disproof

Postby robert 46 » Mon Mar 20, 2017 11:02 am

Gofer wrote:
Recall that h(n)=flip(g(n,n)), and that g(n,n) returns a character 0 or 1. Therefore h(n) returns a character. The statement "h equals any row or column in g" is nonsensical because h does not return a string of characters, and g is purported to be a function, not necessarily an array.

Of course h returns a 0 or 1 for every integer. row M of g equals the function (g x M), and the opposite for the columns.

So now you are saying that g is a 2-dimensional array. In that case the expression is g[n,m] where g[x,M] is all of row M, g[N,x] is all of column N, and g[N,M] is a character. But you defined (g n m) as only returning a character, which is incompatible with the above development.
The question is whether there exists functions (g x M) and (g N x) equaling h for some N and M? well?

Still incomprehensibly worded. You appear to be asking whether the intersection of row M and column N equals the flipped character returned by h. But what is the parameter value for h?
That is not the point. A stream is a FIFO list, and there is no implication that the list is filled faster than it is emptied such that the number of characters in it is ever infinite. In any case, if it was filled faster than emptied, it would take infinite time to become infinitely full because filling and emptying are iterative processes- they do not occur all-at-once.

Again you confuse an object's construction with its definition. The definition doesn't say anything about how it was constructed.

The definition implies that a stream has infinite space to store input. It is better to say that it has open-ended space to store input: i.e it will accept all that it is given.

Your proposed "infinite" Sieve method cannot even find the prime number 5 because it fails to terminate when crossing off multiples of two.

You mean "prime number 3". Whereas you believe the Diagonal method can examine infinite strings all-at-once, why can't Infinite-Eratosthenes cross off the multiples of 2 all-at-once?

That's because the infinite Sieve has a sequential definition whereas the Diag. method hasn't

What don't you understand about my defining an Infinite-Eratosthenes procedure which returns all the primes???
No, I mean the prime number 5 because we know 3 is prime after running only a few steps of the infinite Sieve, but we have to wait and wait for the 5 to appear.

Well, we know 3 is prime by knowing that the first multiple of 2, 2*2, is greater than 3. However, the method states that all multiples are marked before determining the next prime, so we can't even get 3.
Neither Infinite-Eratosthenes or Diagonal method working on infinite strings can be tested to show that they work.

Strawman argument! since no infinite string could ever be created in the real world. As I've stated before, Cantor's theorem is NOT about the real-world EXISTENCE of infinite sets.

The point is that Finite-Eratosthenes works to provide all the primes up to a point, but Finite-Diagonal always identifies a missing element which is not actually missing from the assumed complete list. This is because Finite-Diagonal necessarily always fails as a consequence of an intrinsic flaw. There is no reason to believe that that intrinsic flaw does not make the Diagonal method fail in the infinite case.
I am saying that the constructed intermediate string is presumed padded with trailing zeroes, making it infinite, and that all the intermediate constructed strings could be at some later entries.

That is incorrect! The "intermediate string" is simply a portion of the diagonal.

Assume that the anti-diagonal string is initially filled with 0s, and if the flipped character is 1 then the character at n in the anti-diagonal string is changed to 1. Thus the anti-diagonal string is initially padded with trailing 0s, and all intermediate anti-diagonal strings are infinite. The intermediate anti-diagonal string is not in that portion of the list which has been examined.
Its "padding" is the 'yet to be evaluated later' portion of the string, if interpreted as a sequential algorithm.

You fail to understand that an intermediate anti-diagonal string is created for every character examined by the method. Thus if n elements are examined, n intermediate anti-diagonal strings are defined. They all share the leading characters of their predecessors, but are different strings from each other. [1]
And I have proved that they are in the mirror case which works on integers.
In the case of the Diagonal method working on reals, the intermediate strings are rational numbers with trailing 0s. Whereas the rational numbers are countable, a rational number cannot be the ultimate missing element because the rational numbers are a subset of the reals, and must be in the presumed complete list. Furthermore, the ultimate missing element cannot be a rational because it is impossible for it to contain a repeating sequence.

Strawman! Cantor's theorem has nothing to do with the reals or the integers except if used as indices.

Wikipedia disagrees by stating that the strings can be interpreted as reals in the range 0.(0)
to 0.(1) binary.


[1] Actually, this is incorrect. Some intermediate anti-diagonal strings are the same as others. Specifically, any intermediate anti-diagonal string which has a 0 as the flipped element is the same as a preceding intermediate anti-diagonal string which also has a 0 as the flipped element. However, the count of intermediate anti-diagonal strings which are different from each other is monotonically increasing.
Last edited by robert 46 on Mon Mar 20, 2017 8:59 pm, edited 1 time in total.
robert 46
Intellectual
 
Posts: 2762
Joined: Mon Jun 18, 2007 9:21 am

Re: Cantor Diagonal Argument disproof

Postby Gofer » Mon Mar 20, 2017 2:10 pm

So now you are saying that g is a 2-dimensional array. [No, I'm saying g could be seen as one] .But you defined (g n m) as only returning a character, [No, g return a 0 or 1 for every integer n and m] ,which is incompatible with the above development.
The question is whether there exists functions (g x M) and (g N x) equaling h for some N and M? well?

Still incomprehensibly worded. You appear to be asking whether the intersection of row M and column N equals the flipped character returned by h. [Again, you seem to not comprehend the definition of two functions being equal] But what is the parameter value for h?
What don't you understand about my defining an Infinite-Eratosthenes procedure which returns all the primes??? [So now you are saying your infinite Sieve works, implying the Diag. method works because of your analogy with it]

This is because Finite-Diagonal necessarily always fails as a consequence of an intrinsic flaw. [What flaw?]


I am saying that the constructed intermediate string is presumed padded with trailing zeroes, making it infinite, and that all the intermediate constructed strings could be at some later entries.

That is incorrect! The "intermediate string" is simply a portion of the diagonal.

Assume that the anti-diagonal string is initially filled with 0s, and if the flipped character is 1 then the character at n in the anti-diagonal string is changed to 1. Thus the anti-diagonal string is initially padded with trailing 0s, and all intermediate anti-diagonal strings are infinite. The intermediate anti-diagonal string is not in that portion of the list which has been examined.
Its "padding" is the 'yet to be evaluated later' portion of the string, if interpreted as a sequential algorithm.

You fail to understand that an intermediate anti-diagonal string is created for every character examined by the method. Thus if n elements are examined, n intermediate anti-diagonal strings are defined. They all share the leading characters of their predecessors, but are different strings from each other.

[Completely incomprehensible!]

Wikipedia disagrees by stating that the strings can be interpreted as reals in the range 0.(0)
to 0.(1) binary. [Irrelevant what W. says about it]
Gofer
Intellectual
 
Posts: 237
Joined: Mon May 09, 2016 8:24 am

Re: Cantor Diagonal Argument disproof

Postby Gofer » Mon Mar 20, 2017 3:09 pm

JeffJo wrote:Wikipedia lists two forms for Proof by Contradiction, but Gofer only uses that name for the first[Because that's what Andre Bauer uses!]. Slightly edited, If A is the proposition to be proven:
  1. A is assumed to be false; that is, ~A is true.
  2. It is shown that ~A implies two mutually contradictory assertions, B and ~B.
  3. Since B and ~B cannot both be true, the assumption must be wrong and A must be true.
The second can be called “Proof of Negation”:
  1. A is assumed to be false. [No, A is assumed true.]
  2. It is shown that ~A implies A. [No, it is shown that A implies a contradiction!]
  3. Since A and ~A cannot both be true, the assumption must be wrong and A must be true.[No, the conclusion is that ~A is true.]
I say this can be called “Proof of Negation” because what you prove is the the negation of what you assumed. But Gofer seems to think it is [no he does not!]
  1. A is assumed to be false.
  2. It is shown that ~A implies A.
  3. Since A is true even if ~A is true, it must always be true.
See how this is saying that A is "proven by" the negation of what we assumed?

I believe it was on Tue Feb 21, 2017 12:34 pm that Gofer first claimed that Cantor’s Diagonal was “Proof by Negation,” an expression that is not recognized in any Mathematics that I know of. And in fact, the only hits for it on google, when I was trying to figure out what the **** Gofer was talking about, seemed to be ones where “Proof of Negation” was used and somebody confused it. Why Gofer continues to argue that one name is correct, and the other is not, is beyond me. As is why he continues to lie about the history here. He never pointed out that there was an author who said “Proof by/of Negation” was not “Proof by Contradiction” until after I found his error and the author. But my point was that I had to assume he used the wrong name, and referred to that author, to try to verify what he was talking about. I personally don’t care what the name is, as long as we can understand what he is talking about. [All that the readers need to know is that I mentioned the phrase "proof OF negation" before Jeff decided to make an issue of it]

But there is a difference between the two names, and it leads to the error Gofer makes. Gofer correctly points out that in the first form of “Proof by Contradiction”, we infer A must be true because ~A can’t be true. That is, since we can’t accept a contradiction, by finding a contradiction that follows from ~A, we infer that we have proven A. But in fact, all we have proven is ~(~A). Some philosophers have postulated that there can be an “excluded middle” between A and ~A, call it X. [That may be true, but has nothing to do with constructive mathematics.] So we can have both A and ~A be false, and X be true. [No, constructivists only recognize TWO truth values and NO contradictions. See the "principle of bivalence"!]

Whether or not you accept that (I don’t, unless the statement is a Godel sentence), “Proof by/of Negation” has the same fault. It does not prove A in all situations [It never proves A, but ~A], which would be a “proof of” the negation of what it assumed. It only proves that there is the same kind of contradiction as before, and by finding it, it only proves ~(~A).

But that is all moot, because Cantor’s proof does not follow either form. According to Gofer (and hopefully he will recognize how I’m correcting what he said, using the set names Cantor did), the proposition is:
    Let M be the set of all Cantor Strings. Consider the two propositions:
  • A = “E is a set of Cantor Strings that can be counted.” [Incorrect proposition! E needs to be defined outside of it! Same for B.]
  • B = “E is equal to M.”
In Gofer’s words, what Cantor wants to prove is C=(B->~A). To use either form of Proof by Contradiction directly, we need to assume (~C) = (B and A). To use the second form, we need to prove that C follows from ~C, when in fact what Cantor proved is that A->~B. Yes, they are logically equivalent, but only after you apply contraposition, in which case the theorem is proven before you note that it is a contradiction.

No, proof of negation goes something like this: (B→(~C→⊥))→(B→~~C)→(B→~A).
Gofer
Intellectual
 
Posts: 237
Joined: Mon May 09, 2016 8:24 am

Re: Cantor Diagonal Argument disproof

Postby JeffJo » Mon Mar 20, 2017 3:24 pm

robert 46 wrote:
Gofer wrote:Cantor's theorem has nothing to do with the reals or the integers except if used as indices.

Wikipedia disagrees by stating that the strings can be interpreted as reals in the range 0.(0)
to 0.(1) binary.


Wikipedia wrote:The uncountability of the real numbers was already established by Cantor's first uncountability proof, but it also follows from the above result.[1] To see this, we will build a one-to-one correspondence between the set T of infinite binary strings[2] and a subset of R (the set of real numbers). Since T is uncountable, this subset of R must be uncountable. Hence R is uncountable.[4]


[1] "Above" refers to the proof, as I outlined it, that the set of all Cantor Strings is uncountable. Note that this doesn't say it is applied to the reals, but that it follows from the actual proof.

[2] This is not straight forward: the naive attempt at a correspondence is surjective, but not injective. For example, the distinct strings "010000..." and "001111..." both map to 1/4, but any two distinct real numbers in (0,1) map to distinct strings.

[3] It is compared to a subset, not the entire set of reals.

[4] Gofer is correct that Cantor did not apply the proof to reals - quite deliberately so. This does not mean that a similar proof can't be applied to them, but it is to a subset. And since the direct mapping is not injective, extra steps need to be taken for what I called step E.

That is not what Wikipedia does. They only show that the reals in [0,1] are bijective with a subset of T. Since T is uncountable, so is this range of the reals. I haven't examined this claim, since it is irrelevant.

Regardless, any attempt to discredit Cantor's proof has to apply to Cantor's proof, which is not about real numbers. Not in Cantor's proof, and not in Wikipedia. If your argument needs to use real numbers, than it is either not handling the injective issue properly, or it is based on a misinterpretation (or both).
JeffJo
Intellectual
 
Posts: 2551
Joined: Tue Mar 10, 2009 11:01 am

Re: Cantor Diagonal Argument disproof

Postby robert 46 » Mon Mar 20, 2017 8:37 pm

Gofer wrote:
robert 4 wrote:What don't you understand about my defining an Infinite-Eratosthenes procedure which returns all the primes??? [So now you are saying your infinite Sieve works, implying the Diag. method works because of your analogy with it]

Not in the least. I am saying that you can't "define" a method to work- it has to be "shown" to work.
This is because Finite-Diagonal necessarily always fails as a consequence of an intrinsic flaw. [What flaw?]

The flaw of not being able to examine all of an assumed complete list.
Wikipedia disagrees by stating that the strings can be interpreted as reals in the range 0.(0) to 0.(1) binary. [Irrelevant what W. says about it]

Seeing as how Cantor wanted to prove that the reals have a higher cardinality than the integers, it is nonsensical to say that the interpretation of the method as applying to reals is irrelevant.

*****

JeffJo brings up an interesting wrinkle in applying the diagonal method to reals. It is explained in the Wikipedia article Cantor Diagonal Argument.
JeffJo wrote:They only show that the reals in [0,1] are bijective with a subset of T. Since T is uncountable, so is this range of the reals.

Whereas a subset of a superset necessarily does not contain all the elements of the superset, the fact that an element is missing from the subset is of no value to determining whether a list produced from the superset is complete. The entire list of the superset must be examined to determine whether it actually is missing an element. The Diagonal method cannot do this under any circumstances where the list is presumed to contain all elements- including the case of Cantor strings.
I haven't examined this claim, since it is irrelevant.

Try examining it through an analysis of the implications, instead of voicing the unsupported opinion "since it is irrelevant".
Regardless, any attempt to discredit Cantor's proof has to apply to Cantor's proof, which is not about real numbers. Not in Cantor's proof, and not in Wikipedia. If your argument needs to use real numbers, then it is either not handling the injective issue properly, or it is based on a misinterpretation (or both).

All critical arguments, whether about strings, integers or reals, point to the conclusion that the Diagonal method doesn't actually do anything to show that an assumed complete list of the superset is missing an element- the Diagonal method is not up to the task in any case, finite or infinite.
robert 46
Intellectual
 
Posts: 2762
Joined: Mon Jun 18, 2007 9:21 am

Re: Cantor Diagonal Argument disproof

Postby JeffJo » Tue Mar 21, 2017 6:25 am

robert 46 wrote:JeffJo brings up an interesting wrinkle in applying the diagonal method to reals.
I've been showing it to you for months. You've ignored it, until now when you deliberately misinterpret it. (One way to tell when you do this, is you start with "Whereas" to make it sound like you are actually using logic.) And then you use it to evade the point, which was that Wikipoedia does not say thereal have anything to do with Diagonalization.

Whereas a subset of a superset necessarily does not contain all the elements of the superset, the fact that an element is missing from the subset
... Since, like I said, this particular subset is not used in the proof, this is irrelevant.

The entire list of the superset must be examined to determine whether it actually is missing an element.
"The entire list" that is "missing an element" is from the counting of S, not T. S does not appear in the comparison to reals.

The Diagonal method cannot do this under any circumstances where the list is presumed to contain all elements- including the case of Cantor strings.
The diagonal method does not claim to do that to T, or to R, or to a subset of R.

Try examining it through an analysis of the implications, instead of voicing the unsupported opinion "since it is irrelevant".
Try actually addressing what I said.

All critical arguments, whether about strings, integers or reals, point to the conclusion that the Diagonal method doesn't actually do anything to show that an assumed complete list of the superset is missing an element- the Diagonal method is not up to the task in any case, finite or infinite.
All critical arguments that actually address the diagonal method, and not you misrepresentation of it, show that it works.

Georg Cantor wrote:There is a proof of this proposition [that uncountable sets exist] that is much simpler, and which does not depend on considering the irrational numbers.
Deal with it.
JeffJo
Intellectual
 
Posts: 2551
Joined: Tue Mar 10, 2009 11:01 am

Re: Cantor Diagonal Argument disproof

Postby Gofer » Tue Mar 21, 2017 7:47 am

robert 46 wrote:Not in the least. I am saying that you can't "define" a method to work- it has to be "shown" to work.
The flaw of not being able to examine all of an assumed complete list.


Cantor's lemma + proof by contraposition show it "works" without assuming a "complete list". But it remains to be discussed whether that is what Cantor actually meant in his proof.

Fyi, Cantor's lemma doesn't "examine all of an assumed complete list", but merely a subset of T.

robert 46 wrote:Seeing as how Cantor wanted to prove that the reals have a higher cardinality than the integers, it is nonsensical to say that the interpretation of the method as applying to reals is irrelevant.


No doubt that was Cantor's ultimate goal, but the Diag. proof stands on its own regardless of the reals.
Gofer
Intellectual
 
Posts: 237
Joined: Mon May 09, 2016 8:24 am

Re: Cantor Diagonal Argument disproof

Postby JeffJo » Tue Mar 21, 2017 8:52 am

Gofer wrote:Cantor's lemma + proof by contraposition show it "works" without assuming a "complete list". But it remains to be discussed whether that is what Cantor actually meant in his proof.

The only thing that has been left out - well, ignored by you - is how it fits into any other form.

Fyi, Cantor's lemma doesn't "examine all of an assumed complete list", but merely a subset of T.
Since robert's idea of a list is, by definition, an ordering of a set by associating its element with N, Cantor's proof does indeed utilize the entire list of S to produce D. This is one thing robert refuses to let himself understand, and why he keeps going on about "examining" the list up to a finite point, and its aspect ratio. Another thing he refuses to let himself understand is that it finds a string that is not in S, not "missing from" anything, especially not "missing from" T.
JeffJo
Intellectual
 
Posts: 2551
Joined: Tue Mar 10, 2009 11:01 am

Re: Cantor Diagonal Argument disproof

Postby Gofer » Tue Mar 21, 2017 9:37 am

JeffJo wrote:
Gofer wrote:Cantor's lemma + proof by contraposition show it "works" without assuming a "complete list". But it remains to be discussed whether that is what Cantor actually meant in his proof.

The only thing that has been left out - well, ignored by you - is how it fits into any other form.


I haven't ignored it; I just think that Cantor's continuation mentioning "contradiction" and "the thing would be part of T and not part of T" better support proof of negation than proof by contraposition. So far you have refused to address the second quote, and how it fits into proof by contraposition.


Fyi, Cantor's lemma doesn't "examine all of an assumed complete list", but merely a subset of T.
Since robert's idea of a list is, by definition, an ordering of a set by associating its element with N, Cantor's proof does indeed utilize the entire list of S to produce D. This is one thing robert refuses to let himself understand, and why he keeps going on about "examining" the list up to a finite point, and its aspect ratio. Another thing he refuses to let himself understand is that it finds a string that is not in S, not "missing from" anything, especially not "missing from" T.


It would serve Robert well to answer the following questions:

1. Does the Diag. method ever fail to produce a 0 or 1 for every row in the list? By "fail", I mean "can't access" an element in that row.
2. Has the list a finite number of rows?
3. Is the constructed string thus far equal to the beginning of any string of the previous rows?

If "no" to all, it is clear that the constructed string will be/is infinite (without bound) and not equal to any other string of any row.
Gofer
Intellectual
 
Posts: 237
Joined: Mon May 09, 2016 8:24 am

PreviousNext

Return to Great Ideas

Who is online

Users browsing this forum: No registered users and 2 guests