FOM: If cars were numbers

[Dean Buckner]

It's coming up to the holidays and all the cars in the street are surrounded
by families packing camping gear, suitcases, beach balls, Barbie dolls and
the usual holiday paraphernalia.  There's a lot of coming and going to and
from the houses, and everyone wants a space right in fromt of the house. But
this is inner-city London and parking is at a premium.  You can probably get
some place in the street, but not the one you want.  So you see embarrassed
people walking the whole length of the street carrying a fishing rod or a
baby's potty.

Each car has a place it currently occupies in the street, but many cars are
not in the place that they want to be.  So the residents decide to move
every car to the right place by the following means.  Take each car x in
turn, decide the place where it needs to go, then swap places with the car y
that occupies this space.  Do the same for y.  Since every car that needs to
move, can be swapped with the car that occupies its place, it should be
possible for every car to move where it wants.  Thus the serious packing can
begin.  Bien a vous, bonne vacance.

Could there be any empty spaces left over after the move has taken place?
Surely not.  Intuitively, every move involves two cars swapping places.  If
every space was filled before the move, every space must be filled
afterwards.  Suppose there was an empty space e following the move.  Since
every space was filled by a car beforehand, some car x.1 originally occupied
e.  This must have swapped with some car x.2, which, if it was not in the
correct space, would have swapped with x.3 and so on.  Let S be the set (if
such a set exists) of cars {x.1, x.2, x.3, . } that were successively parked
at e.  For any x.n in S, there exists a set P(x.n) of all cars that were
parked at e before x.n, and which have now moved to the place they belong.
Car x.n either belongs at e, in which case it is still there, or it belongs
somewhere else.  If so, there is a car x.n+1 that is not in the place it
belongs, and is therefore not in P(x.n), and which moves to e after x.n.
This in turn defines a set P(x.n+1) which wholly contains P(x.n).

Intuitively, S is the union of all such subsets of S.  Every such set either
contains the car parked at e, in which case this set is S itself, or it does
not, in which case it is a proper subset of some "larger" set of S, and
therefore not identical with S.  If there is a set consisting of every cars
that was or is parked at e, then it contains the car currently parked at e.
Therefore e cannot be empty.

Could this be true of an infinite number of cars?  This would lead to the
following difficulty.  The function taking us from any car to the place it
belongs, could be any function whatsoever.  There is already a function f,
taking us from cars to the spaces they used to occupy, that is "onto": every
space was occupied by some car.  Any function g, that is 1-1, and takes us
from these cars to any other space in the set of spaces must also be "onto":
every space continues to be occupied after we have applied the function
(moved the cars).  If S were infinite, every function f:S -> S would have to
map S onto S, rather than a proper subset of S.  Yet, infinite sets are not
supposed to behave like this.

As an example of the difficulty, imagine an infinite numbers of cars
{x1,x2,x3, .}, and imagine they are currently "parked" at an infinite number
of spaces {s1,s2,s3, .}.  Suppose we want to re-park every car such that
every car whose number is n, moves to the space whose number is n+1.  We do
this by the swapping method as above.  We start by moving car 1 to space 2,
swapping with the car at 2, which moves to space 1.   Then car 2 moves from
1 to space 3, with car 3 moving to space 1.  It goes on.  Every move, the
set of cars parked at space 1 increases by 1.  But always there is a car
parked at 1.  Every member of S contains all but one of its members
correctly parked, namely the car oarked at space 1.  This car must always
move the next time round, but there is always one there.

If S, the infinite set consisting of the union of all sets cars that were
once parked at 1, it is not clear . Every set P consists of a car that is
incorrectly parked at 1, and which therefore cannot be the set of all such
cars, since to every such set there must correspond another, "larger" one.

This puzzle underlies the general puzzle I have had all along about infinite
sets.


Dean Buckner
4 Spencer Walk
London, SW15 1PL
ENGLAND

Work 020 7676 1750
Home 020 8788 4273