Comparing sizes of infinite sets

Some people want to be able to compare the sizes of infinite sets while preserving the proper subset principle that holds for finite sets:

1. If A is a proper subset of B, then A < B.

We also want to make sure that our comparison agrees with how we compare finite sets:

2. If A and B are finite, then A ≤ B if and only if A has no more elements than B.

For simplicity, let’s just work with sets of natural numbers. Then there is a total preorder (total, reflexive and transitive relation) ≤ on the sets of natural numbers (or on subsets of any other set) that satisfies (1) and (2). Moreover, we can require the following plausible weak translation invariance principle in addition to (1) and (2):

3. A ≤ B if and only if 1 + A ≤ 1 + B,

where 1 + C is the set C translated one unit to the right: 1 + C = {1 + n : n ∈ C}. (See the Appendix for the existence proofs.) So far things are sounding pretty good.

But here is another plausible principle, which we can call discreteness:

4. If A and C differ by a single element, then there is no B such that A < B < C.

(I write A < B provided that A ≤ B but not B ≤ A.) When two sets differ by a single element, intuitively their sizes should differ by one, and sizes should be multiples of one.

Fun fact: There is no total preorder on the subsets of the natural numbers that satisfies the proper subset principle (1), the weak translation invariance principle (3) and the discreteness principle (4).

The proof will be given in a bit.

One way to try to compare sets that respects the subset principle (1) would be to use hypernatural numbers (which are the extension of the natural numbers to the context of hyperreals).

Corollary 1: There is no way to assign a hypernatural number s(A) to every set A of natural numbers such that (a) s(A) < s(B) whenever A ⊂ B, (b) s(A) − s(B) = s(1+A) − s(1+B), and (c) if A and B differ by one element, then |s(A)−s(B)| = 1.

For if we had such an assignment, we could define A ≤ B if and only if s(A) ≤ s(B), and we would have (1), (3) and (4).

Corollary 2: There is no way to assign a hyperreal probability P for a lottery with tickets labeled with the natural numbers such that (a) each individual ticket has equal non-zero probability of winning α, (b) P(A) − P(B) and P(1+A) − P(1+B) are always either both negative, both zero, or both positive, and (c) no two distinct probabilities of events differ by less than α.

Again, if we had such an assignment, we could define A ≤ B if and only if P(A) ≤ P(B), and we would have (1), (3) and (4).

I will now prove the fun fact. The proof won’t be the simplest possible one, but is designed to highlight how wacky a total preorder that satisfies (1) and (4) must be. Suppose we have such a total preorder ≤. Let A_n be the set {n, 100 + n, 200 + n, 300 + n, ...}. Observe that A₁₀₀ = {100, 200, 300, 400, ...} $ is a proper subset of A₀ = {0, 100, 200, 300, ...}, and differs from it by a single element. Now let’s consider how the elegant sequence of shifted sets A₀, A₁, ..., A₁₀₀ behaves with respect to the preorder ≤. Because A_n + 1 = 1 + A_n, if we had (3), the order relationship between successive sets in the series would always be the same. Thus we would have exactly one of these three options:

1. A₀ ≈ A₁ ≈ ... ≈ A₁₀₀

2. A₀ < A₁ < ... < A₁₀₀

3. A₀ > A₁ > ... > A₁₀₀,

where A ≈ B means that A ≤ B and B ≤ A. But (i) and (ii) each contradict (1), since A₁₀₀ is a proper subset of A₀, while (iii) contradicts (4) since A₀ and A₁₀₀ differ by one element.

This completes the proof. But we can now think a little about what the ordering would look like if we didn’t require (3). The argument in the previous paragraph would still show that (i), (ii) and (iii) are impossible. Similarly, A₀ ≥ A₁ ≥ ... ≥ A₁₀₀ is impossible, since A₁₀₀ < A₀ by (1). That means we have two possibilities.

First, we might have A₀ ≤ A₁ ≤ ... ≤ A₁₀₀. But because A₀ and A₁₀₀ differ by one element, by (4) it follows that exactly one of these ≤ is actually strict. Thus, in the sequence A₀, A₁, ..., A₁₀₀ suddenly there is exactly one point at which the size of the set goes up by one. This is really counterintuitive. We are generating our sequence of sets by starting with A₀ and then shifting the set over to the right by one (since $A_{n+1}=1+A_n), and suddenly the size jumps.

The second option is we don’t have monotonicity at all. This means that at some point in the sequence we go up and at some other point we go down: there are m and n between 0 and 99 such that A_m < A_m + 1 and A_n > A_n + 1. This again is really counterintuitive. All these sets look alike: they consist in an infinite sequence of points 100 units apart, just with a different starting point. But yet the sizes wobble up and and down. This is weird!

This suggests to me that the problem lies with the subset principle (1) or possibly with discreteness (4), not with the details of how to formulate the translation invariance principle (3). If we have (1) and (4) things are just too weird. I think discreteness is hard to give up on: counting should be discrete—two sets can’t differ in size by, say, 1/100 or 1/2. And so we are pressed to give up the subset principle (1).

Appendix: Existence proofs

Let U be any set. Let ∼ be the equivalence relation on subsets of U defined by A ∼ B if and only if either A = B or A and B are finite and of the same cardinality. The subset relation yields a partial order on the ∼-equivalence classes, and by the Szpilrajn extension theorem extends to a total order. We can use this total order on the equivalence classes of subsets to define a total preorder on the subsets, and this will satisfy (1) and (2).

If we want (3), let U be the integers, and instead of the Szpilrajn extension theorem, use Theorem 2 of this paper.

The proof of the “Fun Fact” is really easy. Suppose we have such a total preorder ≤. Let A = {2, 4, 6, ...}, B = {1, 2, 3, 4, ...} and C = {0, 2, 4, 6, 8, ...}. By (1), we have A < C. Suppose first that B ≤ A. Then C = 1 + B ≤ 1 + A = B by (3). Hence C ≤ A by transitivity, contradicting A < C. So A < B by totality. Thus B < C by (3). Since A and C differ by one element, this contradicts (4).