FOM: 1-1 correspondence (failure of induction)

Dean Buckner Dean.Buckner at
Wed Aug 28 13:38:24 EDT 2002

Allen Hazen's last posting unfortunately crossed with mine.  He objected
that in my original posting I was arguing by induction, and objected that I
should not assume this (or at least, that to assume this was a petitio

In the posting that crossed, I proposed a slightly different argument.
Nonetheless my argument (as I now see) still used a form of induction, so I
'd like to discuss it in more detail.

1.  Hazen objects that there can be a linearly ordered series with a "first"
and "last" member which (contrary to my supposition) is infinite.  For
example, every ordinal number from 1 onwards, plus the first transfinite
ordinal omega.

2.  He objects to the argument that since the set containing the first
member is finite, and the set of the first and second members is finite, the
set of all members must be finite.

3.  But this is not my argument.  The idea is to start off without any
concept of "finite" or "infinite", and see what properties we can deduce of
any collection of objects that has a "first" and a "last" member, wrt a
simple ordering.

4.  We start with a set of objects S.  We make no assumptions about what
these objects are, though we'll visualise them as guests at a dance.  And we
don't even understand what "finite" is.  This set S can be just any bunch of
things whatever.

5.  Then we suppose a 1-1 function f and a set of objects T, such that f: S
onto T.  Visualise these as the partners that people in S have brought to
the dance.

6.  Suppose that there is another 1-1 function g, from S to T.  This can be
any function you like.  Imagine each guest "chooses" a partner from T, the
only constraint being s/he cannot be chosen by any other (i.e. f is 1-1).
Then we want to establish that g is "onto" T, that no partner in T is left

7.  We take the "first" person a, and three other people:

    (i) f(a), a's existing partner in T
    (ii) g(a) the partner that a "chooses" from T
    (iii) a', the partner in S of g(a) (i.e such that f(a') = g(a))

We simply remove a from S, and g(a) from T.  This leaves the set S', and the
set T'.  And guess what.  There is a 1-1 function *f from S' onto T', if we
stipulate that for any x in S', if x=a', *f(x) = f(a), otherwise *f(x) =

8. Now the crucial inductive step.  We started with two sets (S and T), with
a certain relation between them (the function f).  We removed a pair of
objects (a and
g(a) ), leaving another pair of sets S' and T', and the function *f.

We could repeat this process, but there's no point.  S and T, S' and T', and
the relations between them, are indistinguishable.  There is nothing to
differentiate any of the objects that we pull out of S, unless it is the
"last" object, and then the game is over (advantage us).

That is the basic principle behind induction: that if *one* case of removal
or addition of the same kind of object leaves with essentially the same
state of affairs as before, then all else being equal, we can assume so for
*every* such case.

Thus we conclude that, for every x removed from S, there exists  a subset of
S, a subset of T, and a 1-1 function from one *onto* the other.  So long as
the x is not "special", or different from any other x removed.  But then,
the game is over.

9.  This shows that a set of any objects has the following property: given f
1-1 from S onto T, you can show that every 1-1 function from S to T must be
onto.  This property (which I had no conception of before) I call

10.  Hazen's objection seems to be that the set may be infinite, and that,
therefore, I merely assume finitude.  On the contrary.  I simply assume that
the set is of any objects, and from this deduce it has a certain property I
go on to label finitude.  It's up to Hazen, or anyone else, to show that
there may be certain sets of objects, or certain kinds of objects within
them, for which the argument above does not follow.  For example, it could
be objected that the "last" member of S was "the first transfinite ordinal".
But he would have convincingly (or rather intelligibly) to explain what this
creature was!  (And also why, bizarrely, the partner swap argument fails).

[ Afterthought: Or is it this: that transfinite logic allows us to postulate
kinds of object, whose essential nature is, that they are immune to the
ordinary laws of logic?  Imagine that instead of choosing an "ordinary"
dancing partner, a chooses a "transfinite object" in S.  This would have to
be such that, when it and a are removed from T, we are unable to match its
partner with f(a).  For if we could, and if there were no other such weird
objects in the collection, the set would be finite after all.  But I confess
I don't see how this would be.  Everyone who knows, says that transfinite
logic confounds our ordinary intuitions.  & I agree.


Dean Buckner

Work 020 7676 1750
Home 020 8788 4273

Dean Buckner

Work 020 7676 1750
Home 020 8788 4273

More information about the FOM mailing list