Some people want to be able to compare the sizes of infinite sets
while preserving the proper subset principle that holds for finite
sets:
- 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:
- 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):
- 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:
- 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:
A0 ≈ A1 ≈ ... ≈ A100
A0 < A1 < ... < A100
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).