FOM: 1-1 correspondence (dancing partners)

[Dean Buckner]

Thanks for the replies to my question.  As there was no clear consensus, let
me go a little further.

All the guests S are lined up on one side of the banqueting table, facing
their partners T on the other side.  Thus there is a mapping f: S -> T from
guests to partners that is both 1-1 and onto.

Suppose every guest chooses a partner from the other side of the table and
goes off to dance.  Thus there is a function g: S -> T that is certainly
1-1, but is it onto?  Could every x take a partner from T, and there still
be people in T "left over"?

Possibly, if the sets are infinite in the Cantorean sense.  But suppose
there exists a "counting function"

    c(a) = {a}
    c(b) = {a,b}
    c(c) = {a,b,c}

that maps each guest in S, onto a set of guests, i.e.

    For all x [ c(x) <> S implies for some y (y notin c(x) & c(y) = c(x) U
{y} ]

and assume one members maps onto the whole set.

    for some x c(x) = S

We start with guest a, at the one end of the table, who chooses partner
g(x), and goes off to dance.  Then a's partner f(a) goes off to sit oppose
the partner of g(x), and the waiters clear the space at the end of the
table, then we turn to the next guest b, who chooses a partner g(b) and so
on and on.  As the guests go off to dance, we are "gradually" clear the
table.  Unless of course it's an infinitely long table.

However, notice we always move the dinner partner of the guest who has gone
to dance, into the space vacated by the dancing partner, so for any x there
is always a 1-1 and onto function from S - c(x), the remaining guests on the
S side, to T - g(c(x)), the remaining partners, some of whom have been moved
into new places.

If we assume, as above, that for some x, S = c(x), this is tantamount to
assuming that there is a "last" guest at the end of the table.  S - c(x) is
empty, and since there can be no mapping onto a non-empty set (is that
correct?), it follows T - g(c(x)) must be empty also.  Thus g is also
"onto".

Thus, if there exists a counting function c, the set S has to be finite.

Thinking about this further (and as Andrej Bauer i think also noticed) the
assumption that for some x, c(x) = S is effectively denying a form of the
axiom of infinity.





Dean Buckner
London
ENGLAND

Work 020 7676 1750
Home 020 8788 4273