[FOM] FOM Cantor's argument

[steve newberry]

To: F.O.M.
Subject: FOM Cantor's argument.

This is a question to which I have devoted a [for myself] disastrously
excessive amount of time and thought. The best short summary is to
be found in Wittgenstein's "Remarks of the Foundations of Mathematics"
I won't try to quote it, go look it up for yourself. [You won't have wasted
your time!]

There are two caveats w.r.t. Cantor's argument.

(1) It may or may not be constructive, but it surely is NOT predicative.

(2) As ordinarily presented, it is a "proof by contradication". That is, we 
seek to
prove B. We assume ~B. We show that  ~B  leads to a contradiction. We
interpret the contradiction as a FALSE proposition, hence to be rejected, 
and then
by Modus Tollens, [.:B => C. & ~C. => ~B.] obtain ~~B, or classically, B. 
Q.E.D.

So where's the problem? Certainly the negation of a contradiction is a 
tautological
truth, a u-valid proposition. That is the premiss. But what of the 
conclusion? If the
conclusion is also a tautology, then no problem. But in this case, the 
conclusion is
most emphatically NOT a tautology. It is quintessentially **contingent**. 
It is a
matter of FACTUAL truth or falsehood. We know already from the 
Loewenheim-Skolem
Theorem that models exist in which the Cantor Theorem is false. Hence it is 
necessarily
contingent.

Now it is a simple fact of elementary propositional logic that a tautology 
cannot validly
imply [material implication] a contingent proposition. Where  'Dom(B)' 
denotes the
domain of realization of  B, and  Dom(C) and denotes the domain of 
realization of  C,

         B  validly implies C iff Dom(B) is a subset of  Dom(C). - - - - - 
- - - - - - - - - (*)

If  B  is a tautology, then Dom(B) is the Universe, everything. If  C is 
contingent, then
Dom(C) is a  **proper** subset of  Dom(B), and the implication: .B => C. in 
invalid.

And it really is that simple. And that applies, not merely to Cantor's 
Theorem, but to
ALL theorems which assert matters of fact, whether of existence, or of 
cardinality, or of
any other non-tautological conclusion.

For whatever it's worth, the following theorem constitutes a mild 
generalization of the
Cantor Powerset Theorem. I use the classic Reductio proof because I don't 
know how
else to prove it.

                   The Generalized Diagonal Theorem

                         by R. Stephen Newberry

Generalized Diagonal Theorem: Where F is any function from any
domain to any range, the set D(F) , defined as the set of all k in
domain(F) s.t. k is not an element of F(k), is not an element of range(F)
i.e., F necessarily does not assume the value D(F).

Proof: Assume the contrary: If we had F(j) = D(F) for some j in
N, then either:

         j is in D(F), so j is not in F(j); but by assumption
         F(j) = D(F), so j is not in D(F) by definition of D(F).
or
         j is not in D(F), so j is in F(j); but by assumption
         F(j) = D(F), so j is in D(F) by definition of D(F);

The supposition F(j) = D(F) has led to a contradiction.
Consequently, D(F) is not an element of range(F), thus
proving the theorem. QED

Note that we now obtain the Powerset Theorem as a corollary:

Corollary: For any set S , no function F from S to P(S)
can be a surjection, since by definition, P(S) must contain
D(F), hence by the Generalized Diagonal Theorem , D(F)
cannot appear in range(F) and hence, F cannot be a
surjection. Q.E.D.

However, this does raise an interesting consideration:
Clearly, by the Loewenheim-Skolem Theorem, there
exists a counter-model in which Powerset(N) is countable;
that entails that the Powerset Theorem is only *contingently*
true [see Note 1]; and hence is only n-valid [valid on all and
only finite domains]; furthermore, the fact that the Powerset
Theorem is a corollary of the Generalized Diagonal Theorem
entails that the G.D.T. is itself contingent, n-valid, and has
an infinite counter-model . This places in doubt the validity
of  the proof, on the grounds that the negation of a contradiction
can not  VALIDLY imply a contingent statement because
the domain of realization of the premiss is a superset of
the domain of realization of the conclusion, hence it is
possible for the premiss to be true when the conclusion
is false.

A constructive presentation of either of these two counter-
models would be of interest, "and is left as an exercise for the
reader."

Note 1: The set of all cwffs of classical logic of first-order can
be partitioned into three blocks: U + N + K where B , ~B
belong to  U  iff ~B  is a contradiction, which entails that  B  is
"u-valid".  [U is called the ABSOLUTE block, "U" for universal];
B , ~B  belong to  N + K  iff they are not absolute, in which case
they are said to be CONTINGENT.

B , ~B  belong to  N  iff ~B  is an "axiom of infinity", i.e., is consistent
but has no finite realizations. Then  B  is "n-valid";
B , ~B  belong to K iff both have finite realizations. B  is then "k-valid".