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 JeffJo » Sat Mar 18, 2017 7:04 am

Gofer wrote:Jeff, I suggest you read the following for the difference between 'proof of negation' (PoN) and 'proof by contradiction' (PbC): math.andrej.com/2010/03/29/proof-of-negation-and-proof-by-contradiction/.

Gofer, I suggest you read it yourself, and try express the point you think it makes that agrees with you but not with me.

You claimed "proof by negation." I said that wasn't a recognized term, that you mistook it for "proof of negation." And in fact, the site you cited is one of the ones I found that supported me, and not you.

I keep telling you that whichever contradiciton-based proof you think Cantor intended, it needs to start with "Suppose B..." and deduce FROM THAT SUPPOSITION a contradiction of some sort. Which is what Andrej Bauer says. Your usual reference, Wikipedia, outlined the two forms Andrej Bauer compared. It may have called them both proof-by-contradiction, but that is irrelevant since either one still needs to start with "Suppose B..." and deduce FROM THAT SUPPOSITION a contradiction of some sort.

Cantor's Diagonalization does not do this. It doesn't start with "Suppose B...". although you could quibble that it is just ordwered in a non-standard way. But is still does not deduce FROM THAT SUPPOSITION a contradiction of some sort. So it still can't be either form that both Wikipedia and Andrej Bauer compare.

Here they are for Cantor's theorem.

M = a set of Cantor strings.
A = M is countable.
B = M equals T.

Cantor's lemma: A -> not B
Cantor's theorem: B -> not A

Gee, that looks like a classic example of proof-by-contraposition to me.
JeffJo
Intellectual
 
Posts: 2607
Joined: Tue Mar 10, 2009 11:01 am

Re: Cantor Diagonal Argument disproof

Postby robert 46 » Sat Mar 18, 2017 10:01 am

JeffJo wrote:
robert 46 wrote:I used induction ...
Then you admit that infinite sets exist?

Not in the sense that infinite complete sets exist. Rather, open-ended sets are always incomplete, but always extendable. Whereas "infinite" means "endless", to think that there is an end to "endless" is nonsensical. So-called "infinite sets" cannot be constructed- they are a fantasy.
...to prove that if the expression 2^infinity has any meaning ...
It has no meaning unless you use transcendental numbers, which you deny exist.

This is what I said:
"2^n>2*n, n>2. So make of it what you will by induction as n approaches infinity."
Kindly address it.
Besides, if your version of mathematics (and it is most definitely not the accepted version) denies the existence of infinite sets, why do you care that other versions, which do allow the "construction" of infinite sets, prove there are different kinds of infinite sets?

robert 46 wrote: Because it introduces contradictions into mathematics.

Again: the only contradiction here is how you deny that infinite sets "exist," whatever you think that means, yet continue to treat them with some form of existence while evading the question "what is the largest natural number?"

There is no largest natural number. That doesn't mean that there exists a set with "all" the natural numbers. It means that any such "set" is incomplete but extendable.
mathematics with contradictions is illogical.
Then its good that there are no contradictions.

The Diagonal method applied to integers in the mirror case implies a missing element which is not an integer.
Yet now-a-days I see formal logic as being the basis for mathematics.
And that is what Euclid said. Yet you claimed that mathematics was a formal basis for logic, the reverse of what Euclid said. And evaded it when I pointed out your contradiction.

I consider formal logic to be a fundamental aspect of mathematics. Any branch of mathematics which is incompatible with the application of formal logic is basically flawed.
About what in particular? There are contradictions which arise consequent to hypothesizing infinite sets.
No, there aren't. There are contradictions arising from how you misrepresent how modern set theory deals with infinite sets.

What misrepresentation is there in assuming that integers have endless leading zeroes?
Oh, except that you can't name a natural number that is larger than all others.
I don't need to by defining the natural numbers to be an "open-ended" set, not a "complete" set.
Same thing. Is it a set, or not? Call it what you will, if it is a set then Cantor's proof works.

Cantor's method does not construct the hypothesized anti-diagonal element.
I interpret the strings as being in the domain of the integers with leading zeroes,
and you are wrong to do so. Every integer is represented by a finite string to digits. You can claim you make them infinite by padding them, but you still have a set of finite strings.

Why isn't that contradictory? For any leading 0, it can be negated to 1. The same is true of rational numbers with trailing zeroes. If there is a set of finite strings then the set must also be finite. But by implication endless leading or trailing zeroes do not constitute finite strings. The rational number (in binary) 0.11011 is distinguished from 0.11011000000000001 because both numbers have infinite trailing zeroes: 0.11011(0) is not equal to any other rational number, nor is 0.11011000000000001(0).
Can't you understand this simple difference (call it *)? The reals between 0 and 1 ***REQUIRE*** some strings that be represented as finite strings that get padded with zeroes. The integers ***ARE ONLY*** finite strings that you pad with zeroes. The argument is not a mirror for this reason.

It is not invalid to pad integers with leading zeroes. Whereas the cardinality of the integers is the same as the rational numbers, and the rational numbers are either padded with trailing zeroes or have repeating sequences, how can padding the integers with leading zeroes be invalid?
and find that the element hypothesized to be constructed cannot be an integer.
Nobody but you ever claimed it was. In fact, a crucial part of Cantor's proof is that the constructed string can be proven to belong to the set of all eligible strings. So this assertion not only doesn't disprove Cantor, it proves that you do not have a mirror of Cantor.

I don't see it that way: the mirror argument behaves identically to the Diagonal method, it is the interpretation of the result which brings out the contradiction.
It does not construct it.

It constructs it by induction.

The induction goes on endlessly, so there is nothing conclusive to show for it. The intermediate missing elements are all of finite length, and all the constructed missing elements are intermediate. Nothing else is constructed.
The integers are accepted as infinite.

So infinite sets exist?

If one recognizes "infinite" as "open-ended", and extendable.
And all we need to do to accept them is call them "open-ended" instead of "complete?" Then:

1.Let C0 be a string of characters where the nth character is "m" if n is odd, and "w" if m is even. Since the integers are accepted as (open-ended) infinite, this Cantor string is also accepted as (open-ended) infinite. So infinite Cantor strings exist.
2.Let C(n) the same as C0, except interchange "m" and "w" in the nth position. Now a set of (open-ended) infinite Cantor strings exists.
3.Perform (open-ended) diagonalization on this set. The result is an (open-ended) infinite Cantor string that is not in that set you diagonalized.
4.The same is true for any (open-ended) infinite set of Cantor Strings that can be put in 1:1 correspondence with the natural numbers. Which is all Cantor's proof requires.
There is no contradiction here.

The flaw in this is not recognizing that the length of the assumed complete list is actually 2^n as n approaches infinity. It is larger in length than n (which is the width), and this is the case for all finite lists assumed complete. The relationship does not change as n approaches infinity.

Thus the missing element in your example is from a portion of the assumed complete list; so it is not surprising that it is missing- not all elements have been examined because not all elements are examinable by the Diagonal method.
But this only means they are endless: i.e. open-ended. If the Diagonal method could be applied to the integers to give a conclusive result, that result would be a missing element which is not an integer.

Cantor diagonalization is not performed on integers. It is performed on sets that we hope will not be countable, and the integers are countable by definition. So again, I have the statement I called * that refutes your argument.

Let's say we "hoped" the integers would not be countable, so we apply the Diagonal method. We get a missing element, which would be interpreted as meaning the integers are not countable. However, we recognize that it is not an integer because it has infinite significant bits. The method has failed in this case. Why? It is merely the interpretation which shows that it fails. The "element" of infinite significant bits is by your interpretation actually constructed. So are we required to add this bizarre creature to the mathematical beastiary? Or instead do we recognize that the method is flawed???
Thus the method cannot be applied to give a conclusive result in all cases.

Gee, it can't be used to prove that a countable (by definition) set is uncountable.

What do we make of the bizarre creature in the mathematical contex?
Complaint: "Doctor, doctor, it hurts if I do this." Reply: "Don't do that."

It is fallacious to claim that the result should be accepted where we want the result to be accepted, and rejected where we want the result to be rejected.
By showing that the Diagonal method fails for integers,

The diagonal method is not supposed to work on integers.

Yet by your interpretation it returns a bizarre creature. So what are mathematicians to make of this? They can't just sweep it under the rug.
Of course the mirror argument is an extension- it does everything the Diagonal method does,...

... except operate on infinite strings.

It operates endlessly without actually returning the bizarre creature. This is the rational interpretation to resolve the dilemma.
Last edited by robert 46 on Sat Mar 18, 2017 3:22 pm, edited 1 time in total.
robert 46
Intellectual
 
Posts: 2838
Joined: Mon Jun 18, 2007 9:21 am

Re: Cantor Diagonal Argument disproof

Postby robert 46 » Sat Mar 18, 2017 1:48 pm

Gofer wrote:Robert, Cantor's diagonal method does NOT need to access previous elements in order to calculate an element, because they are independent,

The anti-diagonal element is consequential to examining an infinity of elements in the list. You can't assume an infinity of functional agents to accomplish this in parallel.
And even if the method was recursively defined, it would still produce a letter for every integer, making your objection to it once again wrong.

Function F(n, var r): F(n+1,r); prefix negated character at L(n,n) to r.
n=1; r=empty; F(n,r).

This recursive function never returns a result: it calls itself endlessly, and never executes the second statement.
Btw. the Sieve of Eratosthenes, only finds primes up to a specified integer, because it is inherently imperative, using a table to cross off numbers.

So it is invalid to assume it can work with an infinite table, and invalid to assume it works all-at-once. I consider it invalid that the Diagonal method can work with an infinite list, and invalid to assume it works all-a-once.
And again, the method is UNdefined for sets of all finite strings of a certain length, because it fails to access a letter for some integer N, making your argument wrong that it somehow fails for finite sets.

It fails not because it cannot access some letter for N, but because it cannot access some element in the list beyond N. And it fails in this way for both finite and infinite lists.
robert 46
Intellectual
 
Posts: 2838
Joined: Mon Jun 18, 2007 9:21 am

Re: Cantor Diagonal Argument disproof

Postby Gofer » Sat Mar 18, 2017 4:15 pm

> You claimed "proof by negation." I said that wasn't a recognized term, that you mistook it for "proof of negation." And in fact, the site you cited is one of the ones I found that supported me, and not you.

Now Jeff cries over semantics, which in this case, "by" and "of" pretty much means the same. And I just explained the difference between 'proof of negation' and 'proof by contradiction'.

>I keep telling you that whichever contradiciton-based proof you think Cantor intended, it needs to start with "Suppose B..."

Yes it does! But Cantor obviously left it out, hence his statements "it follows immediately" and "otherwise the thing would be a member of T and not a member of T", paraphrased, and which is exactly one gets using 'proof of/by negation'.

> Gee, that looks like a classic example of proof-by-contraposition to me.

No, those weren't proofs, but merely definitions and propositions.
Gofer
Intellectual
 
Posts: 283
Joined: Mon May 09, 2016 8:24 am

Re: Cantor Diagonal Argument disproof

Postby Gofer » Sat Mar 18, 2017 4:22 pm

> The anti-diagonal element is consequential to examining an infinity of elements in the list. You can't assume an infinity of functional agents to accomplish this in parallel.

So if I have the function (f x) := x^2, I can't create g := 2*f, because "an infinity of function agents" can't "accomplish this in parallel"?

>Function F(n, var r): F(n+1,r); prefix negated character at L(n,n) to r.
n=1; r=empty; F(n,r).
This recursive function never returns a result: it calls itself endlessly, and never executes the second statement.

That is a strawman because the Diagonal method obviously terminates for every position/integer.

> So it is invalid to assume it can work with an infinite table, and invalid to assume it works all-at-once. I consider it invalid that the Diagonal method can work with an infinite list, and invalid to assume it works all-a-once.

Another strawman because you're trying to equate the Diagonal method with the Sieve.

> It fails not because it cannot access some letter for N, but because it cannot access some element in the list beyond N. And it fails in this way for both finite and infinite lists.

No it does not fail for some N for infinite lists of infinite strings. But you are welcome to try and state what that N might be.
Gofer
Intellectual
 
Posts: 283
Joined: Mon May 09, 2016 8:24 am

Re: Cantor Diagonal Argument disproof

Postby robert 46 » Sat Mar 18, 2017 6:00 pm

Gofer wrote:robert 46 wrote> The anti-diagonal element is consequential to examining an infinity of elements in the list. You can't assume an infinity of functional agents to accomplish this in parallel.

So if I have the function (f x) := x^2, I can't create g := 2*f, because "an infinity of function agents" can't "accomplish this in parallel"?

No. The function works on generic variables, and a function working on another function works on the same generic variables. Thus:
f(x)=x^2; g(x)=2*f(x)=2*x^2.
So who is raising a strawman with your silly comment???

>Function F(n, var r): F(n+1,r); prefix negated character at L(n,n) to r.
n=1; r=empty; F(n,r).
This recursive function never returns a result: it calls itself endlessly, and never executes the second statement.

That is a strawman because the Diagonal method obviously terminates for every position/integer.

Then don't hypothesize a recursive method unless you can provide one that works. Another strawman.
> So it is invalid to assume it can work with an infinite table, and invalid to assume it works all-at-once. I consider it invalid that the Diagonal method can work with an infinite list, and invalid to assume it works all-a-once.

Another strawman because you're trying to equate the Diagonal method with the Sieve.

So if the Sieve cannot work on an infinite array, then why is it that the Diagonal method can work on an infinite list?
> It fails not because it cannot access some letter for N, but because it cannot access some element in the list beyond N. And it fails in this way for both finite and infinite lists.

No it does not fail for some N for infinite lists of infinite strings. But you are welcome to try and state what that N might be.

Is it true that 2^n>2*n, n>2???
robert 46
Intellectual
 
Posts: 2838
Joined: Mon Jun 18, 2007 9:21 am

Re: Cantor Diagonal Argument disproof

Postby Gofer » Sat Mar 18, 2017 7:11 pm

The function works on generic variables, and a function working on another function works on the same generic variables.


Excellent! So if I have the function (g n m) returning a 0 or a 1 for every integer n and m, I can construct the function (h x):=flip (g x x) such that there exist no integers N and M such that
(h x)=(g N x) and (h x)=(g x M)? True or false?

Then don't hypothesize a recursive method unless you can provide one that works.


Another strawman because it is not recursivity that is the issue, but whether the method returns a value for every integer, which it does!

So if the Sieve cannot work on an infinite array,


It is not defined for infinite arrays

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

Is it true that 2^n>2*n, n>2???


Another strawman because as I have been telling you numerous times by now, the Diag. method is UNDEFINED for finite lists containing all finite strings of a certain length.
Gofer
Intellectual
 
Posts: 283
Joined: Mon May 09, 2016 8:24 am

Re: Cantor Diagonal Argument disproof

Postby JeffJo » Sun Mar 19, 2017 6:14 am

On Fri Mar 17, 2017 at 4:30 pm, Gofer wrote:Cantor's lemma: A -> not B
Cantor's theorem: B -> not A

What Gofer called "Cantor's Lemma" is the contrapositive of what he called "Cantor's theorem." So at this point, if the proof of Cantor's lemma is complete, so is the proof of Cantor's theorem.

What is that so hard for Gofer to explicitly admit? Especially when he implicitly admits it here?

Gofer then says why it is a proof (he even said it was constructive, which some think is important):

Proof by contraposition: (A->not B)->(B->not A). Note that this is constructive


Cantor said essentially the same thing:
    From this proposition [that is, the lemma "A-> not B"] it follows immediately ["->"] that the totality of all elements of M ["B"] cannot ["not"] be put into the sequence [Reihenform]: E1, E2, …, Ev, … ["A"]

Maybe Gofer is confused by the semantic issue, where I use the general form "(not B -> not A) -> (A->B)"? And he somehow thinks there is a difference? If that is his problem, I will strive to match my semantics to Cantor's, which is in the form Gofer used, admitted Cantor used, admitted was a proof by contraposition, and admitted was constructive.

Yet Gofer still continues to argue all four of those points.

Later, he makes himself even more of (not "by") a hypocrite by accusing me of what it is clear he is doing:
Now Jeff cries over semantics, ...
... which is all that he himself is doing, since he admits that there is a proof-by-contraposition, yet insists that it isn't so. And quibbles that I used "not B" where Cantor actually used "B."

But BTW, I never said that you can't force a proof that looks like a proof-by-contradiction (or proof-of-negation), just that Cantor didn't. His statement of a contradiction, that Gofer used to demand I address but has refused to admit how I did, merely distinguishes B from not B.

...which in this case, "by" and "of" pretty much means the same.
<sigh>. They have different connotations [see above usage comparison], and only one is semantically correct here. But Gofer ignores how he used the wrong name for his (this time) chosen source, which was my only point. It seems Gofer can never admit his mistakes, even simple ones like this.

"Proof of Negation" is a bit of a misnomer; it really means "Proof by the contradiction (that what you assumed is subsequently proven to be negated)." And if Gofer will stop ignoring how his favorite source (isn't it interesting how he picks among possible sources, so that he can find the one with a favorable interpretation?) - that is to say, https://en.wikipedia.org/wiki/Proof_by_contradiction - calls his PoN a "proof by contradiction."
JeffJo
Intellectual
 
Posts: 2607
Joined: Tue Mar 10, 2009 11:01 am

Re: Cantor Diagonal Argument disproof

Postby Gofer » Sun Mar 19, 2017 8:04 am

Jeff still refuses to see that:

1. I have never denied that Cantor's theorem can be proven from the lemma and contraposition.
2. (not B->not A)->(A->B) is NOT a theorem in constructive logic whereas (A->not B)->(B->not A), (A->B)->(not B->not A) and (not B->A)->(A->not not B) ARE!
3. Cantor saying "it follows immediately" could mean anything, INCLUDING 'proof by/of negation'. But the fact that a contraposition is a theorem means that it does not follow "immediately" without invoking that theorem.
4. I already pointed out that "some author uses 'proof of negation'" BEFORE Jeff said so, making his arguing about it a red herring.
5. semantically both forms are correct, those being 'proof of/by negation'.

Note that 'proof by contradiction' always has the form (not not A)->A, which is the 'excluded middle' not recognized in constructive logic whereas 'proof by negation' is, meaning they are distinct.
Gofer
Intellectual
 
Posts: 283
Joined: Mon May 09, 2016 8:24 am

Re: Cantor Diagonal Argument disproof

Postby JeffJo » Sun Mar 19, 2017 12:20 pm

Here are several points that need to be reiterated, because someone here ignores them.
  1. “Construction” in mathematics means to show that an abstract object with some set of properties follows logically from one’s axioms. Some misguided individuals think this means you demonstrate physical existence – which is absurd. For example, no true circle “physically exists” because any physical process is flawed. But the abstract concept of a circle “logically exists.”
    2
  2. Modern set theory constructs the set of all natural numbers, N, by showing that a set can contain the number 1 and, if it contains the number n, it also contains the number n+1. This can be called construction by induction. The (logical) existence of every natural number follows from these to constructive steps. The application of them may be “opened-ended,” but denying it as a constructive process means that there is some number n+1 that is not in the set, when is.
    3
  3. A set that is constructed by induction this an example of “completed infinity.” Not “complete infinity.” This does not mean that the set can be physically made complete, it means that the logical definition is completed.
    4
  4. ”Potential infinity,” or “as n approaches infinity,” is a different concept altogether. It describes a tendency of a finite function as bigger values from N are used as its argument. It is a misrepresentation to suggest that any find of infinity – potential or completed – be used for n.
    5
  5. A string is merely a function that associates a character with a sequence of natural numbers starting with 1.
    6
  6. A Cantor String is a string that associates one of two characters (Cantor used “m” and “w”; I’ll use “0” and “1”) with every natural number.
    7
  7. Since N can be constructed, a Cantor String that is all 0’s can also be constructed. Call it C0.
    8
  8. The set of all Cantor Strings, C, can be constructed-by-induction by saying it contains C0 and, if contains a string with a 0 in position n, it contains a string that changes that position to a 1.
    9
  9. Cantor’s diagonal proof, and anything that claims to mirror it, must follow these steps:
    1. Identify a class of objects. Cantor used Cantor Strings.
    2. Call the set of all of these objects that belong to that class T.
    3. Assume there is an ordered set S of these objects; that is, one that can be counted. With Cantor Strings, such a set is the set of strings that are all 0’s except the nth character, which is 1.
    4. Find the anti-diagonal D that follows logically from that ordering, using construction-by-induction. By definition, D cannot belong to S.
    5. Show that D must belong to T.

Robert 46 ignores all of these points:
[Infinites sets do ]not [exist] in the sense that infinite complete sets exist.
See points #1 and #2.
So-called "infinite sets" cannot be constructed- they are a fantasy.
See point #1.
This is what I said:
"2^n>2*n, n>2. So make of it what you will by induction as n approaches infinity."
Kindly address it.
I have, many times. I did again, in point #4. Kindly address this.
There is no largest natural number. That doesn't mean that there exists a set with "all" the natural numbers.
See point #1.
The Diagonal method applied to integers in the mirror case implies a missing element which is not an integer.
Your supposed “mirror case” fails step E of the outline, so it is not a mirror case. You are confusing being in S, with being in T. Specifically, you can’t call the “anti-diagonal” a missing element of T if it isn’t supposed to be an element of T. Kindly address this.
I consider formal logic to be a fundamental aspect of mathematics.
So do I. What you said was that mathematics was a formal basis for logic, which is the opposite, and not true. Kindly address this.
What misrepresentation is there in assuming that integers have endless leading zeroes?
None. But they don’t need to be. And because you do use endless leading zeros for every integer in your set S, the antidiagonal you arrive at has infinite leading 1’s. So it is not an integer, and you fail step E of the outline I gave for a mirror. This is the misrepresentation. Kindly address it, and not something else that I didn’t claim was a misrepresentation.
Cantor's method does not construct the hypothesized anti-diagonal element.
Yes, it does. See points #1 and #9D.
For any leading 0, it can be negated to 1.
And again, that means that any antidiagonal you produce has infinite leading 1’s, so it is not an integer. You fail step E, so you do not have a mirror. Please address this point.
I don't see it that way: the mirror argument behaves identically to the Diagonal method
IT FAILS STEP E.
The induction goes on endlessly, so there is nothing conclusive to show for it.
”goes on endlessly” is what “induction” means. It shows, endlessly, that anything you want to call an integer can be generated. This is construction. See point #1.
So infinite sets exist?
If one recognizes "infinite" as "open-ended", and extendable.
Call it what you want. They are logically constructed. See point #1.
The flaw in this is not recognizing that the length of the assumed complete list is actually 2^n …
The flaw in your alleged flaw, is that there is no assumed “physically-complete” list, there is a “logically-completed” one. See point #3.
Let's say we "hoped" the integers would not be countable, so we apply the Diagonal method.
Since the integers are the very definition of a countable set, it is absurd to hope that. But if you would try to understand what the proof does, you would see THAT YOU FAIL STEP E. This does not show that there is something wrong with the method, it shows that there is something wrong with you saying you applied it to integers.
It is fallacious to claim that the result should be accepted where we want the result to be accepted, and rejected where we want the result to be rejected.
No, it is fallacious to claim that you have a valid result when you did something wrong in order to claim it.
The diagonal method is not supposed to work on integers
Yet by your interpretation it returns a bizarre creature.
My only interpretation is that it returns a non-integer, but it needs to be an integer for you to have a mirror proof. I think you have forgotten what your point was with the alleged mirror.
JeffJo
Intellectual
 
Posts: 2607
Joined: Tue Mar 10, 2009 11:01 am

Re: Cantor Diagonal Argument disproof

Postby JeffJo » Sun Mar 19, 2017 12:38 pm

Gofer still refuses to see that he never actually takes a position, so it is hard to argue with him.
Gofer wrote:Jeff still refuses to see that:

1. I have never denied that Cantor's theorem can be proven from the lemma and contraposition.
You mean just like I never said it can't be done by contradiciton? Just that it wasn't what Cantor did?

2. (not B->not A)->(A->B) is NOT a theorem in constructive logic whereas (A->not B)->(B->not A), (A->B)->(not B->not A) and (not B->A)->(A->not not B) ARE!

Since "A" and "B" are arbitrary, and so may be negative statements, this makes no sense.

3. Cantor saying "it follows immediately" could mean anything, INCLUDING 'proof by/of negation'.
No, it means that what follows needs no more steps, which proof by contradiction (of which proof of negation is a form) does.

4. I already pointed out that "some author uses 'proof of negation'" BEFORE Jeff said so, making his arguing about it a red herring.
I have no idea what you are calling a red herring, but if you didn't identify who and where "some author" said something, and what that was, this is clearly an attempt to evade your mistakes.

5. semantically both forms are correct, those being 'proof of/by negation'.
And semantically, either form is a proof by contradiction.

+++++
But what are you arguing about, anyway? And why?

Note that 'proof by contradiction' always has the form (not not A)->A, which is the 'excluded middle' not recognized in constructive logic whereas 'proof by negation' is, meaning they are distinct.[/quote]
JeffJo
Intellectual
 
Posts: 2607
Joined: Tue Mar 10, 2009 11:01 am

Re: Cantor Diagonal Argument disproof

Postby robert 46 » Sun Mar 19, 2017 12:48 pm

Gofer wrote:
The function works on generic variables, and a function working on another function works on the same generic variables.


Excellent! So if I have the function (g n m)

Please use standard terminology: g(n,m)
returning a 0 or a 1 for every integer n and m, I can construct the function
(h x):=flip (g x x) [h(x)=flip(g(x,x))] such that there exist no integers N and M such that
(h x)=(g N x) [h(x)=g(N,x)] )and (h x)=(g x M) [h(x)=g(x,M)]? True or false?

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? If so, g(n,m) is an access function.

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


Then don't hypothesize a recursive method unless you can provide one that works.

Another strawman because it is not recursivity that is the issue, but whether the method returns a value for every integer, which it does!

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; there are no infinity of function invocations which will work in parallel on an infinite list. To think otherwise is to live in a bizarre fantasy world. Both you and JeffJo act like religious converts who revel in living in a bizarre fantasy world.
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???
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.
Is it true that 2^n>2*n, n>2???

Another strawman because as I have been telling you numerous times by now, the Diag. method is UNDEFINED for finite lists containing all finite strings of a certain length.

As I see it, the generic function accepts what it is given and does what it can. It is invalid to "define" it to only work with infinite strings. It has the same problem with both finite strings and infinite strings: it cannot examine all of an assumed complete list.

So, whereas 2^n>2*n, n>2, what is inferred as n approaches infinity? Is it not the case that 2^n>2*n always? Is there anything to imply a discontinuity??? If not, then in the infinite case the array is necessarily longer than it is wide, or else the infinite case is contradictory and delusional to believe in.
robert 46
Intellectual
 
Posts: 2838
Joined: Mon Jun 18, 2007 9:21 am

Re: Cantor Diagonal Argument disproof

Postby robert 46 » Sun Mar 19, 2017 1:45 pm

JeffJo wrote:9 Cantor’s diagonal proof, and anything that claims to mirror it, must follow these steps:
  1. Identify a class of objects. Cantor used Cantor Strings.
  2. Call the set of all of these objects that belong to that class T.
  3. Assume there is an ordered set S of these objects; that is, one that can be counted. With Cantor Strings, such a set is the set of strings that are all 0’s except the nth character, which is 1.
  4. Find the anti-diagonal D that follows logically from that ordering, using construction-by-induction. By definition, D cannot belong to S.
  5. Show that D must belong to T.

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. This means that there is a square diagonal which is all 1's. 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.

Cantor does not assume that his strings only "are all 0’s except the nth character, which is 1". He assumes that the strings comprise all combinations of the two characters in all positions.
robert 46
Intellectual
 
Posts: 2838
Joined: Mon Jun 18, 2007 9:21 am

Re: Cantor Diagonal Argument disproof

Postby Gofer » Sun Mar 19, 2017 2:42 pm

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.

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.


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.

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.

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!


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. And if the list is finite and the method terminates, it ALWAYS constructs a string not equal to any previous string in the list.

----

We can interpret an infinite list as a tuple having a value and a list, (value, list), such that every function defined on it has a recursive execution, (f list) = (f value, f list). It is clear that the two can be executed in parallell.
Last edited by Gofer on Sun Mar 19, 2017 2:48 pm, edited 1 time in total.
Gofer
Intellectual
 
Posts: 283
Joined: Mon May 09, 2016 8:24 am

Re: Cantor Diagonal Argument disproof

Postby Gofer » Sun Mar 19, 2017 2:42 pm

2. (not B->not A)->(A->B) is NOT a theorem in constructive logic whereas (A->not B)->(B->not A), (A->B)->(not B->not A) and (not B->A)->(A->not not B) ARE!


Since "A" and "B" are arbitrary, and so may be negative statements, this makes no sense.


No! Under constructive mathematics, a proof means constructing the actual "proof object" whereas 'not a proof' means assuming A leads to a contradiction. So (not not B) actually means assuming (not B) leads to a contradiction, meaning B OUGHT to be true but can't be shown, hence (not not B) does NOT imply B.


3. Cantor saying "it follows immediately" could mean anything, INCLUDING 'proof by/of negation'.
No, it means that what follows needs no more steps, which proof by contradiction (of which proof of negation is a form) does.


But so does proof by contraposition because its theorem needs to be mentioned; only then "it follows immediately".

4. I already pointed out that "some author uses 'proof of negation'" BEFORE Jeff said so, making his arguing about it a red herring.
I have no idea what you are calling a red herring, but if you didn't identify who and where "some author" said something, and what that was, this is clearly an attempt to evade your mistakes.


I cannot be bothered to provide the exact posting, but if you search through the pages for "proof of negation", you can see where it first occurred.

5. semantically both forms are correct, those being 'proof of/by negation'.
And semantically, either form is a proof by contradiction.


Not according to Andrej Bauer and his article on the subject.

+++++
But what are you arguing about, anyway? And why?


Bad memory? My claim is that Cantor's statements after "it follows immediately" better support the idea of proof by negation than contraposition; but either obviously proves the theorem.
Gofer
Intellectual
 
Posts: 283
Joined: Mon May 09, 2016 8:24 am

PreviousNext

Return to Great Ideas

Who is online

Users browsing this forum: No registered users and 1 guest