Thursday, December 5, 2013

Ordering subsets of the line and the Banach-Tarski paradox

Suppose we want to rank the subsets of the interval [0,1] by size. Consider this:

  1. There is a total, transitive and reflexive ordering (i.e., a total preorder) ≤ of subsets of the interval [0,1] such that (a) if AB, then AB and (b) if A and B are disjoint non-empty sets with AB, then A<AB,
where X<Y means that XY but not conversely.

Condition (a) is intuitively correct for any notion of size comparison. Condition (b), then, is like a regularity condition in probability theory. Any regular probability is going to yield a comparison like in (1).

One can get such an ordering by applying Szpilrajn's Theorem to get a total ordering of the subsets of [0,1] that extends subset inclusion. Note, however, that Szpilrajn's Theorem uses a version of the Axiom of Choice. It's an interesting question whether one can have (1) without any Axiom of Choice.

Now, the Banach-Tarski Paradox—that a solid ball can be disassembled into a finite number of subsets that can be reassembled into two solid balls each of the same size as the original—also uses a version of the Axiom of Choice. It would be nice to have (1) while avoiding the Banach-Tarski Paradox. One might even think Bayesian epistemology requires that one be able to hold on to (1) while avoiding the Banach-Tarski Paradox, since the latter spells doom for rigid-motion invariant probabilities in a three-dimensional region. But without using any version of the Axiom of Choice one can prove:

Theorem. If (1) is true, then the Banach-Tarski Paradox holds.

This essentially follows from Note 1 in Pawlikowski's paper, together with the fact that the solid ball has the same cardinality as [0,1] (so an order on the subsets of [0,1] as in (1) transfers to an order on the subsets of the ball that satisfies (1)), and the following pleasant observation:

  1. If ≤ is as in (1) and A1,A2,A3,A4 are non-empty sets, then if B=A1A2A3A4, then at most one of the Ai satisfies the condition BAi<Ai and at least one of the Ai satisfies the condition Ai<BAi.
Say that X~Y iff XY and YX. To prove (2), suppose first that Ai>BAi and ji. Then AjBAi. Moreover, AiBAj. Thus, BAjAi>BAiAj, and so we do not have Aj>BAj. Next, suppose Ai does not satisfy AiBAi. Thus, by totality of ≤, we have Ai>BAi. But this can happen for at most one i. So there will be three distinct i such that AiBAi. To obtain a contradiction, suppose all three inequalities are non-strict and suppose i and j are two of the three indices. Then Ai~BAi and Aj~BAj. Observe that Aj is a subset of BAi, and hence AjAi. By the same argument, AiAj, and so Aj~Ai. The same will go for the third index, so there are three indices i, j and k such that Ai~BAi~Aj~BAj~Ak~BAk. But BAk contains the union of Ai and Aj and so by (1) we have Ai<BAk, which is a contradiction.

Corollary 1. The claim that every partial order extends to a total order implies the Banach-Tarski Paradox.

And since it's well known that the Banach-Tarski Paradox cannot be proved in Zermelo-Fraenkel (ZF) set theory unless ZF is inconsistent:

Corollary 2. Claim (1) cannot be proved in ZF, unless ZF is inconsistent.

I have some thoughts on how one might perhaps be able to improve Corollary 1 to show the result under the weaker assumption that every set has a total order. (The existence of Lebesgue nonmeasurable sets can be proved from that.)

Philosophical implications: I think standard Bayesianism requires both (1) and the falsity of Banach-Tarski. So standard Bayesianism fails. Moreover, we get an argument for the possibility of incommensurability in decision theory. For if (1) is false, then there can be incommensurability (denying (1) requires affirming that there are some partially preordered sets that have no total preorder whose strict order relation extends the strict order relation of the original preorder), and if Banach-Tarski is true, there can be incommensurability (incommensurability in probabilities implies incommensurability in choices).

No comments: