[FOM] Cantor's Theorem

[Neil Tennant]

By "in no model of set theory is Cantor's Theorem false" I mean
"in no model of the set-theoretic axioms used to prove Cantor's Theorem is
Cantor's Theorem false."

Thus your worry about not being able to tell, when listing the axioms of
ZF, whether you have now specified all of set theory is irrelevant.
(Listing the axioms of ZF will take you an infinitely long time, by the
way, if you really do mean *axioms*, rather than "axioms or
axiom-schemes".)

The question arises: how weak a fragment of ZF proves Cantor's Theorem?
Answer: a separation axiom using a formula that contains parameters but no
quantifiers.

Cantor's Theorem really belongs to the crocodile-brain part of set theory.

The hereditarily finite pure sets form a model of (Z minus axiom of
infinity). Hence ((Z minus axiom of infinity) minus axiom of power sets)
is true in the hereditarily finite sets. And just one axiom (namely, an
instance of separation) of this already very reduced fragment of Z
suffices for Cantor's Theorem. 

Suppose you are a naif learning about sets. You are given a "logic of
sets" consisting of existentially non-committal rules of inference for
inferring to conclusions of the form

	t={x|F(x)}

and for inferring from major premises of the same form. (For a statement
of these rules, and a completeness proof for the resulting free logic of
sets, see chapter 7 of my book Natural Logic, Edinburgh University Press,
1978.)

Then:

Mother gives you the axiom of pair sets. 

(Alas, Mother does not give you Bob and Alice, so you cannot form the set
{Bob, Alice}. This is because Mother wants to keep things pure. She knows 
your tendency to break or maim concrete things, or to bite them or stick
them in your mouth.) 

Mother gives you the axiom of unions. 

Mother gives you the axiom of power sets.

Mother gives you the axiom of foundation.

Mother gives you the axiom scheme of separation.

You writhe and squirm in frustration, because, as you slowly twig, Mother
has really given you nothing yet. She has given you only conditional
existence claims: claims of the form that IF one is *given* such-and-such
things or sets, THEN such-and-such other sets exist. Everything Mother has
told you thus far is true in the empty universe.

Finally:

Mother gives you the axiom saying that the empty set (call it 0) exists.
It may itself be empty, but it sure is something.

KABOOM!: the hierarchy of hereditarily pure sets mushrooms up in the
Platonic portion of your infant mind. Like Conrad's idiot who drew circles
all day, however, you might get stuck in the giddy-making sequence 

	0, {0}, {{0}}, {{{0}}}, ...

courtesy of the axiom of pair sets. That's if Mother's affectionate name
for you is Ernstchen. But if her name for you is Johannchen, you might get
stuck in the delirium-inducing sequence

	0, {0}, {0,{0}} (thus far, courtesy of pair set), {0,{0},{0,{0}}}
	(courtesy of pair set and union), ...

But if Ernstchen and Johannchen take frequent rests, to take stock of what
they have generated thus far, and keep applying pair set and union to
everything they have generated, they will eventually generate each
hereditarily finite pure set.

Moreover, the universe of sets they will generate will make true all the
other axioms that Mother gave them! Given any h.f.p. set A, the h.f.p. set
consisting of exactly the subsets of A will eventually be formed by
applications of pair set and union alone. The power set axiom will not
actually be needed for the generation of h.f.p. sets. The power set axiom
will simply *be true of* all the h.f.p. sets that get generated by means
of pair set and union. Likewise with foundation, and all instances of the
axiom scheme of separation.

Mother was very prescient.

Mother has also been ultra-constructive. She has not permitted you to
"construct" any infinite set.

Mother then proves Cantor's Theorem for you, without using the power set
axiom, and without inducing any anxiety in your impressionable mind about
such monsters as omega. Omega is verboten, like Pegasus, Santa Claus and
gryphons. Mother is a truth-teller.

Mother's proof of Cantor's Theorem uses only the introduction and
elimination rules that Ernstchen and Johannchen were taught before they
were even allowed to play together, along with an innocuous,
quantifier-free instance of the axiom scheme of separation.

You know that anything provable from what Mother has given you so far (in
the way of axioms) remains provable no matter what other axioms she may
give you.

At around the time you get bored with generating ever more h.f.p. sets, it
dawns on you that the process is never-ending, and that you will be able
to "keep going on", even though every set X that you ever generate in this
way will be finite. That is, you will be able to put X into a 1-1
correspondence with one of the sets in Johannchen's obsessive sequence.

One day, around the time your voice deepens, Mother tells you about omega.
She ventures her timid suspicion that maybe, just maybe, omega (w) exists.

KABOOM!! again. You adolescent mind suffers another Hiroshima cloud in its
Platonic portion. Having been given the power set axiom, you
realize that the power set P(w) exists. Having been properly Cantored, you
realise that P(w) cannot be put into 1-1 correspondence with w. So there 
is an *uncountable* infinity! And P(P(w)) cannot be put into 1-1
correspondence with P(w). So there is a yet more uncountable infinity! ...
and the craziness will never stop.

Then, just when you are about to point all this out to Mother, as a kind
of metaphysical reductio ad absurdum of her daring to suggest that w
exists, you meet a fellow named Harvey who shows you that other lovely,
simple combinatorial statements that you thought had to be true of
the things that you and your friends had generated 'below omega' could be
proved in set theory only by assuming the existence of these transfinite
monstrosities.


___________________________________________________________________
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-3197