Sets and Their Sizes by Fred M. Katz

The possibility that whole and part may have the same number of terms is, it must be confessed, shocking to common sense ... Common sense, therefore, is here in a very sorry plight; it must choose between the paradox of Zeno and the paradox of Cantor. I do not propose to help it, since I consider that, in the face of the proofs, it ought to commit suicide in despair.

Bertrand Russell, Principles of Mathematics

Is common sense confused about set size, as Russell says? Or can we elaborate on common sense to get a plausible and reasonably adequate theory of cardinality?

The Standard Theory

Cantor's theory of cardinality is as old as sets themselves and so widely held as to be worthy of the name the standard theory . Cantor's theory is based on the important notion of one-to-one correspondence:

A one-one correspondence between two sets is a relation which pairs each member of either set with exactly one member of the other.

and consists of just two principles

One-One. Two sets are the same size just in case there is a one-one correspondence between them.

Cantor . A set, x, is smaller than a set, y, just in case x is the same size as some subset of y, but not the same size as y itself.

For example, the upper-case letters of the alphabet can be paired with the lower-case letters:

ABCDEFGHIJKLMNOPQRSTUVWXYZ
abcdefghijklmnopqrstuvwxyz

So, the standard theory says, the set of upper-case letters is the same size as the set of lower-case letters. Fine and good.

The Conflict

The standard theory also says that the set of even numbers is the same size as the set of integers since these two sets can also be paired off one-to-one:

...,  -n, ..., -3, -2, -1, 0, 1, 2, 3, ... n ...
...,  -2n, ..., -6, -4, -2, 0, 2, 4, 6, ... 2n ...

Similarly, the standard theory says that there as many prime numbers as there are positive even numbrers, since we can pair the n-th prime with the n-th positive even number.

In such cases involving infinite sets, common sense chokes on the standard theory.

In the first case, common sense holds that the set of integers is larger than the set of even integers. The integers contain all of the even integers and then some. So it's just good common sense to believe there are more of the former than the latter. This is just to say that common sense seems to follow:

SUBSET. If one set properly includes another, then the first is larger than the second

even into the infinite, where it comes up against the standard theory.

Common sense can make decisions without help from SUBSET. Though the set of primes is not contained in the set of even integers, it is still clear to common sense that the former is smaller than the latter. One out of every two integers is even, while the prime numbers are few and far between. No doubt, to use this reasoning, you need a little number theory in addition to common sense; but, given the number theory, it's the only conclusion common sense allows.

An Alternative

Sets and Their Sizes reviews Cantor's main argument for the standard theory and offers an alternative account of set size.

The alternative accommodates the bits of common sense reasoning illustrated above. It maintains SUBSET and a few and far between principle and much else besides.

The alternative is based on a general theory, ClassSize. ClassSize consists of all sentences in the first order language with a subset predicate and a less-than predicate which are true in all interpretations of that language whose domain is a finite power set. Thus, ClassSize says that smaller than is a linear ordering with highest and lowest members and that every set is larger than any of its proper subsets. Because the language of ClassSize is so restricted, ClassSize will have infinite interpretations. In particular, the notion of one-one correspondence cannot be expressed in this language, so Cantor's definition of similarity will not be in ClassSize, even though it is true for all finite sets.

The main formal results are:.

• ClassSize is decidable but not finitely axiomatizable.
• ClassSize has finite completions, which are true only in finite models and infinite completions, which are true only in infinite models.
• Each infinite completion is determined by a set of remainder principles, which say, for each natural number, n, how many singletons remain when the universe is partitioned into n disjoint subsets of the same size.
• Every infinite completion of ClassSize has a model over the power set of the natural numbers which satisfies an additional axiom:

OUTPACING. If initial segments of A eventually become smaller than the corresponding initial segments of B, then A is smaller than B.

Models which satisfy OUTPACING seem to accord with common intuitions about set size. Such models agree with the ordering suggested by the notion of asymptotic density, but they go much further in making distinctions among sizes of sets of natural numbers. In fact, the ordering of sets by size is very much like the ordering of non-standard natural numbers.