FOM: Cantor'sTheorem & Paradoxes & Continuum Hypothesis

[Neil Tennant]

On Mon, 12 Feb 2001, Kanovei wrote:

> 
> >From: Neil Tennant <neilt at mercutio.cohums.ohio-state.edu>
> >Cantor's theorem does not depend on the assumption that
> the power set of the continuum exists.
> 
> Once again, the proof has two important issues, 
> [...stuff omitted...-NT]
> 2) foundationally - the postulate that all elements of P(N) 
> (or P(X),for "arbitrary" X - which was not much meaningful 
> for a XIX century mathematician) 
> are "already given" and no new ones can appear in the course 
> of the proof. 

The alleged postulate that all the subsets of X (for arbitrary X) are
"already given" does not appear anywhere in the actual proof of Cantor's
theorem.  As my earlier note tried to make clear, that proof has the form
of a reductio---a derivation of absurdity---from two premisses:

(1) X is a set
(2) R is a 1-1 function that maps members of X to subsets of X, and is 
such that every subset of X is the R-image of some member of X.

The mere occurrence of the quantifying phrase "every subset of X" in (2)
does not amount to the sort of "postulate" that Kanovei claims is at work
in the proof.

For all its austere simplicity, thep poof of Cantor's Theorem nevertheless
seems to provoke the strangest flights of metaphysical fancy. For all
that, it remains a theorem of intuitionistic Z (Zermelo set theory,
without Replacement!).

One of the reasons (perhaps) why some people (Robert Tragesser?) have
sometimes mistakenly thought that Cantor's Theorem is classical and not
intuitionistic is that the last part of the proof is often (carelessly)
presented as proceeding from the law of exluded middle. In such
presentations, the writer will say something like this:

	Assume d is in D. Then by the definition of D, d is not 
	in D. Contradiction.
	Now assume that d is not in D. Then again by the definition
	of D, d is in D. Contradiction.

The formalization of such reasoning would be a natural deduction of the
following form:

                       		    _________(1)    _______________(1)
				    d is in D       not-(d is in D)
			    		:		      :
   d is in D or not-(d is in D)		#		      #
   ______________________________________________________________(1)
					#

in which the premiss for the final or-elimination appears to be an
instance of the law of excluded middle.  But any such appearance is really
illusory, since the use of any premiss of the form (A or not-A) to obtain
a contradiction can be disposed of by the following intuitionistic
re-write:
   	        __(1)
		A
		:
		#
		______(1) [negation introduction]
	 	not-A
		  :
		  #

The same unnecessarily classical-seeming presentations of proofs of
contradiction are frequently to be encountered in philosophers' accounts
of the Russell Paradox and of the Liar Paradox.  But the reasoning in
these paradoxes, too, is thoroughly intuitionistic. (If it weren't, then
one of the obvious ways to avoid these paradoxes would be to insist that
all reasoning be intuitionistic!---but of course intuitionists know very
well that that would not do.)

Neil Tennant