FOM: Proper Names and the Diagonal Proof
Neil Tennant
neilt at mercutio.cohums.ohio-state.edu
Wed Jun 26 22:30:18 EDT 2002
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
More information about the FOM
mailing list