FOM: Proper Names and the Diagonal Proof

[Neil Tennant]

Here is a very simple form of Cantor's Theorem, provable by means 
of a Cantorian Counterexample that (as far as I can tell) Boolos didn't
construct (Logic, Logic & Logic, essay 21). I *THINK* I've got it right,
but will happily submit myself to "refereeing" by the list.

Definition: For any set X and any function f taking all and only
subsets of X as arguments, let D(X,f) =df 
  {x in X | for no subset W of X is x both in W and identical to f(W)}.

The statement to be proved is (*):

for all sets X, 
for all functions f taking all and only subsets of X as arguments, 
	if for every subset Z of X f(D(X,f))=f(Z) only if D(X,f)=Z,
	then f(D(X,f)) is not a member of X.

Note that in the hypotheses of this theorem we are not requiring f to be
1-1, nor are we requiring f to be onto X. But we have as immediate
corollaries Boolos's two forms of Cantor's Theorem (that there is no
function from X onto the power set of X; and that there is no 1-1 function
from the power set of X into X). As Boolos notes, each of these two forms
implies the standard form of Cantor's theorem, i.e. that there is no 1-1
function from X onto the power set of X.

The proof of (*) is intuitionistic relevant, and uses only Separation:

Since by Separation D(X,f) is a subset of X (call it now D for short),
f(D) exists. 
Assume f(D) is in X. 
Assume also that f(D) is in D. 
This contradicts the membership condition for D. 
So f(D) is not in D (so long as we continue to assume f(D) is in X). 
Now assume f maps only D to f(D). 
Then no subset of X both has f(D) as a member and gets mapped by f to
f(D).
That is, f(D) satisfies the conditions of membership in D. Contradiction.
Hence f(D) is not in X after all.

___________________________________________________________________
Neil W. Tennant
Professor of Philosophy and Adjunct Professor of Cognitive Science

http://www.cohums.ohio-state.edu/philo/people/tennant.html

Please send snail mail to:

		Department of Philosophy
		230 North Oval
		The Ohio State University
		Columbus, OH 43210

Work telephone 	(614)292-1591 
Private Fax 	(614)488-3198