Counting Without Numbers

A shepherd with no numbers can still tell whether any sheep are missing. Drop a pebble in a bag for each animal that leaves in the morning; take one out for each that returns at night. If the bag empties exactly, the flock is complete. No counting occurs anywhere in the procedure.

This is the older idea, and it is the one that survives contact with infinity. Two collections are the same size when their members can be paired off with nothing left over on either side. For finite collections this agrees with counting exactly. For infinite ones it is the only definition available, because counting requires finishing.

Apply it and the answers are immediate and unwelcome.

How many even numbers are there, compared with whole numbers? Pair 1 with 2, 2 with 4, 3 with 6, and generally n with 2n. Every whole number is used once. Every even number is reached once. Nothing is left over. The sets are the same size.

This is not a sleight of hand, though it feels like one, and the feeling is worth taking seriously because it is pointing at something real. Among the first million numbers, half are even. That is a fact about density, and density is a perfectly good notion that happens not to be the same notion as size. For finite sets the two agree. For infinite ones they part company, and only one of them is a statement about how many.

The response before the nineteenth century was to treat this as a reason to distrust the whole business. Galileo, in 1638, noticed that every number has exactly one square and concluded that the terms 'equal', 'greater' and 'less' simply do not apply to infinite quantities. Aristotle had drawn a similar line: the infinite is potential, a process that can always be continued, never a completed totality you can hold and compare.

Dedekind's move was to stop treating it as a paradox and make it the definition. A set is infinite precisely when it can be matched one-to-one with a proper part of itself. The thing that had looked like a contradiction became the criterion, which is a manoeuvre the subject performs repeatedly.

Hilbert dramatised it with a hotel. Infinitely many rooms, numbered 1, 2, 3 and so on, all occupied. A guest arrives.

The manager asks each guest to move from room n to room n+1. Everyone still has a room; nobody is doubled up; room 1 is now empty. The hotel was full and had space.

A coach arrives with infinitely many new guests. The manager asks each existing guest to move from room n to room 2n. All the odd rooms are now free, and there are infinitely many of them.

Infinitely many coaches, each with infinitely many guests, and it can still be done, though at that point you need to be a little more careful about the scheme.

The most surprising result in this direction concerns fractions. Between any two fractions there are infinitely many more; they are dense in a way the integers conspicuously are not; there is no next fraction after 1/2. Surely there must be more of them.

There are not. Lay them in a grid, numerator across, denominator down, so every positive fraction appears somewhere. Now walk the grid in diagonals: 1/1, then 1/2 and 2/1, then 1/3 and 2/2 and 3/1, and so on, skipping anything you have already listed in a different form. Every fraction sits at a definite position in that walk and is reached after finitely many steps. The fractions can be listed, so they are countable, so there are exactly as many of them as there are counting numbers.

Countable is the technical word for this, and it does not mean small or finite. It means the members can be arranged in one endless list, such that each appears at some finite position: that the set can be exhausted by a process that never ends.

At this point a reasonable person concludes that all infinite sets are countable, that infinity is one thing wearing different clothes, and that the pairing definition has flattened every distinction worth making.

That was Cantor's expectation too, and it is wrong.