Re: Request for Peer Review - Refutation of Cantor Theorem Conclusion

In article <1146790432.346585.73380@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
Scott <ToaTerra@xxxxxxxxx> wrote:

Arturo Magidin wrote:

...deleted text...

http://groups.google.com/support/bin/answer.py?answer=14213&topic=250

Thanks.

Next: the basic rules for ->this< discussion.


(1) You cannot define things into existence. You can make
definitions, but one must prove that such a thing exists if one
is to assert it does.

(2) The deduction theorem is valid. In other words, proving that
(p -> q) follows from T is equivalent to proving that q follows
from T and p.

(3) Reductio ad absurdo is valid. In other words, if from T and p it
is possible to deduce a contradiction, then it follows that from
T it is possible to deduce not(p).


Now. You want to discuss specifically and exclusively Cantor's
argument in the context of whether or not there exists a surjective
map from N to P(N).

Let me start:

(i) That N exists follows from the Axiom of Infinity and the Axiom of
specification.

(ii) That P(N) exists follows from the Axiom of the power sets.

(iii) That functions from N to P(N) exist follows variously from
axioms of union, power sets, specification, and the like.

Now: let f be ANY function from N to P(N). The set

D_f = { x in N : x not in f(x) }

exists by the Axiom of Specification, and by the axiom of the power
set and the axiom of extensionality, D_f is an element of P(N) for ANY
f.

Now, if you want to argue that there exists an f which is surjective,
then you must EITHER prove its existence from first principles, or
else you must label such an existence as an ASSUMPTION. And then you
must remember (3) above: if from this assumption we deduce a
contradiction, it will necessarily follow that it is the ASSUMPTION
that is false.

Agreed.


Feel free to proceed from there.


ASSUMPTION: f is surjective.

This does not work. What is "f"?

You'll note that above I explicitly quantified f. It said: FOR EVERY
f, such and such.

So this is not a sentence: it has free variables.

What you meant, perhaps, was:

ASSUMPTION: There exists a function f:N->P(N) such that f is
surjective.


ASSUMPTION: Cantor's proof works when f is surjective; ie, it generates
a contradiction.

Once again, you introduce confusion.

First: You should not speak of "Cantor's proof" without specifying
EXPLICITLY what you mean by that.

Second: You have not specified what it means for a proof to "work" or
"not work". Proofs are either valid or invalid. A valid proof is one
in which each step is either an axiom, a previously established
theorem, or follows from previous steps by valid rules of inference;
and such that the last line in the proof is the statement to be
established. What is "the proof works" supposed to mean?

Third: As I and others have noted and as you've been told repeatedly,
there is NOTHING in the proof of Cantor's Theorem that requires the
function ot be surjective. I have produced the standard statement and
proof that do NOT assume any such thing. So this sentence is once
again completely bogus.

Fourth: This should not be and is not an "assumption".

Cantor's Theorem says:

CANTOR'S THEOREM: For every set S, for every function f:S->P(S),
there exists D_f subset of S such that for all s in S, f(s)<>D_f.

That is a formula in which every variable is quantified.

The proof (the "argument") is:

Let S and f be given as in the statement. The set

D_f = {x in S : x not in f(x)}

exists by Separation, and by the Axiom of the Power set is an
element of P(S).

To prove that "for all s in S, f(s)<>D_f", let s in S. Then (s in
f(s)) or (s notin f(s)) by Excluded Middle.

First I apply the Deduction Theorem once:

Assume that s in f(s). Then s in f(s), so by definition of
D_f, s notin D_f. Since (s in f(s)) and (s notin D_f), it
follows that f(s)<>D_f.

Therefore, by the Deduction Theorem: If s in f(s), then f(s)<> D_f.

Second, I apply the Deduction Theorem again:

Assume that s notin f(s). Then s notin f(s), so by definition
of D_f, it follows that s in D_f. Since (s notin f(s)) and (s
in D_f), it follows that f(s)<>D_f.

Therefore, by the Deduction Theorem: If s notin f(s), then
f(s)<>D_f.

Since ( s in f(s) -> f(s)<>D_f) and (s notin f(s) -> f(s)<>D_f),
then

(s in f(s) OR s notin f(s)) -> (f(s)<>D_f).

Since (s in f(s) OR s notin f(s)) is a tautology by excluded
middle, Modus Ponens implies that f(s)<>D_f.

Thus, for all s in S, f(s)<>D_f. QED

That's "Cantor's argument".

If you have some objection to it, state it now. Otherwise, Cantor's
Theorem is a THEOREM, and the proof is valid; there is no "assumption"
that the proof valid, and there are no assumptions about the nature of
f.

PROOF: Given D_f = { x in N : x not in f(x) }. By the assumption,
(exists x)(f(x)=D_f) so let x=2.

This is invalid. You cannot decide what x will be. This is quite
simply not a valid argument. The rest of your "argument" is invalid
since this assertion is invalid.

(You do not need to assert any such nonsense anyway, so why oh why do
you insist on doing so? It does not simplify things: it only makes
your argument more and more nonsensical and complex).



Rather, what we have is:

THEOREM (not an assumption)
If f :N->P(N) is a function, then f is not surjective

Proof. By Cantor's theorem, there exists D_f in P(N) such that for
all n in N, f(n)<>D_f. Therefore, f is not surjective. QED


That's it.

Then D_f = { x in N : x not in
f(x) } -> { 2 in N : 2 not in f(2) } -> { 2 in N : 2 not in D_f
}. If (2 in D_f) then (2 notin D_f). If (2 notin D_f) then (2 in D_f).
Contradiction. Therefore, Cantor's proof works when f is surjective.

ASSUMPTION: Cantor's proof does not prove f is not surjective.

This is false.


PROOF: When f is not surjective, Cantor's proof works.

You have not told us what you think "Cantor's proof" is. You have also
not specified just what it means for a proof to "work" or "not work".

When f is
surjective, Cantor's proof works.

And here you are engaging in blatant equivocation. What does "the
proof works"? Since you have not specified anything, it can mean
anything.

Therefore, Cantor's proof is
independent of whether f is surjective or not. Therefore, Cantor's
proof does not prove f is not surjective.

No.

What you perhaps attempted to say is that since Cantor's argument
is valid whether or not f is surjective, then from the mere fact that
Cantor's argument is valid one cannot deduce that f is surjective or
that f is not surjective. In other words, you are trying to say that
if A->P and not(A)->P, then we cannot, in general, deduce either A or
not(A) from P. That much is correct.

However, what you have ignored here is that "Cantor's proof is valid"
is not a statement that is ->unconnected<- to the statements "f is
surjective" and "f is not surjective." The reason being that the last
line in Cantor's proof IS the statement "f is not surjective."

That means that we have a meta-implication that says that

If (Cantor's argument is valid for f) THEN (f is not surjective).

So rather, what you have are the following two meta-implications:

(f not surjective) --> (Cantor's argument is valid for f)
--> (f is not surjective)

And you also have

(f is surjective) --> (Cantor's argument is valid for f)
--> (f is not surjective).

Putting the two together we have

(f is surjective OR f is not surjective) --> (f is not surjective)

so we deduce that f is not surjective regardless.

Alternatively:

(p -> not(p)) -> not(p)

is a tautology. Therefore, from the second chain of implications we have

(f is surjective) --> not(f is surjective).

Applying the tautology and modus ponens, we deduce that
not(f is surjective) HOLDS. This is not an assumption anymore. We have
established that for all f:N->P(N), (f is not surjective).


--
======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
--- Calvin ("Calvin and Hobbes")
======================================================================

Arturo Magidin
magidin@xxxxxxxxxxxxxxxxx

.

Relevant Pages
Quantcast