Friday, March 1, 2024

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:

  1. 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):

  1. 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:

  1. 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 An be the set {n, 100 + n, 200 + n, 300 + n, ...}. Observe that A100 = {100, 200, 300, 400, ...} $ is a proper subset of A0 = {0, 100, 200, 300, ...}, and differs from it by a single element. Now let’s consider how the elegant sequence of shifted sets A0, A1, ..., A100 behaves with respect to the preorder ≤. Because An + 1 = 1 + An, 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. A0 ≈ A1 ≈ ... ≈ A100

  2. A0 < A1 < ... < A100

  3. A0 > A1 > ... > A100,

where A ≈ B means that A ≤ B and B ≤ A. But (i) and (ii) each contradict (1), since A100 is a proper subset of A0, while (iii) contradicts (4) since A0 and A100 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, A0 ≥ A1 ≥ ... ≥ A100 is impossible, since A100 < A0 by (1). That means we have two possibilities.

First, we might have A0 ≤ A1 ≤ ... ≤ A100. But because A0 and A100 differ by one element, by (4) it follows that exactly one of these is actually strict. Thus, in the sequence A0, A1, ..., A100 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 A0 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 Am < Am + 1 and An > An + 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).


IanS said...

Typos: I think some of the inqualities are the wrong way around. Reverse the inequalities in (ii) and (iii), and in the next sentence change “since A0 is a proper subset of A100” to “since A100 is proper subset of A0”. Similar problems in the next two paragraphs.

Why are violations of (4) a problem? Intuitively, translation (as defined here on the natural numbers), makes infinite sets ‘smaller’ by emptying the initial segment. How much smaller? It depends on how dense the set is. :-) Put differently, if you think that A1, …, A99 are in some sense ‘between’ A0 and A100, then shouldn’t this apply to their rankings too? The ranking A0 > A1 etc. seems intuitively plausible.

Alexander R Pruss said...

Thanks for catching the typos.

If we're looking at densities of sets, I can see how the translation makes a difference. But I'm looking at size as in counting, and counting is always by whole numbers.