FOM: Re: 1-1 corespondence

A.P. Hazen a.hazen at
Sat Aug 17 01:41:31 EDT 2002

   I think Dean Buckner's informal presentation has led him to underspecify
his proposal.  (I'm all in favor of informal presentations-- one of the
things I like about David Lewis's "Parts of Classes" is its demonstration
that it is possible to argue rigorously abot set theory IN ENGLISH-- but
sometimes it's possible to overloook something essential in an "intuitive'
   Dean's idea is this:  Suppose you have a set of objects, and a 1-1
correspondence between them and certain subsets of them, with the following
properties.  (i) The objects are strictly linearly ordered (Dean talks
about "putting" the objects into a container, one after another, with the
order being that in which they are tossed in).  (ii) There is a last object
in the order [this condition is not emphasized, but is presupposed in his
claim that there is an object correlated with the set of all the objects].
(iii) Each object is correlated with the set containing itself and all
earlier objects in the order.  He asks if the existence of such an ordering
and such a correspondence is sufficient for the set of objects to be finite.
   First answer: NO.  Standard practice among set theorists (as in the
excellent introductory text by Suppes that Hamilton refers to) is to
identify an ORDINAL NUMBER with the set of all "earlier" ordinals.
Ordinals are strictly linearly ordered; every ordinal has a SUCCESSOR, its
immediate follower in the linear order, identified with the SET obtained
from the given ordinal by adding itself (as a new member) to itself (as set
of earlier ordinals).  Now consider the set of ordinals OTHER THAN ZERO up
to and including some infinite (transfinite) ordinal.  This is an infinite,
strictly linearly ordered set with last member.  Correlate each of its
members with the set obtained from its successor by deleting ZERO.  This
correlation satisfies (iii).
   What went wrong?  My set (previous paragraph) is, contrary to what Dean
thinks provable, equinumerous with some of its proper subsets: after all,
it contains all the positive integers (=finite ordinals other than ZERO),
and they are equinumerous with the odds.  My GUESS is that Dean reasoned by
induction: the set correlated with the first object in the ordering is not
equinumerous with any of its proper subsets (it is a unit set, and its only
proper subset is the null set); if the set of objects up to a given one in
the ordering is not equinumerous with any of its proper subsets, neither is
the set of objects up to the NEXT one (longwinded argument below).  But to
infer from this that the WHOLE set is not equinumerous with any of its
proper subsets we need to assume that the ordering is an "inductive"
series: in effect, that the set is finite.
   What REALLY went wrong?  Perhaps thinking of the ordering as given by
successive (physical) operations on the objects was misleading.  Suppose
our "pebbles" (Dean's way of imagining the objects) are labeled with the
ordinals from 1 to OMEGA+2, inclusive, and we want to put them in a (big!)
pail, one at a  time, in order.  Putting the pebbles labeled with finite
positive integers into a pail is a "supertask" (plausibly impossible if
there is a finite lower limit to the time it takes to move each pebble)
which must be completed before the last three pebbles are put in.
Longwinded argument postponed from "What went wrong" paragraph above:
Suppose there is no 1-1 correspondence between {...,a} (the set of objects
up to and including a in the ordering) and any of its proper subsets.  Then
there is no such 1-1 correspondence for {...,a,b}.  For suppose there were
an F:{...,a,b} --1-1--> X, where X is a proper subset of {...,a,b}.  Case
(i): b is one of the values of F. Let c be the object such that F(c)=b, let
d=F(b).  Define G by setting G(c)=d and otherwise letting G(x)=F(x) for x
in {...,a}.  G is 1-1 from {...,a} into one of its proper subsets.  Case
(ii): there is no c such that F(c)=b. Then F-, the restriction of F to
{...,a}, is 1-1 from {...,a} to its proper subset {...,a}-{F(b)}.
Contradiction in both cases.
Allen Hazen
Philosophy Department
University of Melbourne

More information about the FOM mailing list