deGroot’s Problem

Recently, a lot of blogs (incited by the Everything Seminar) have been talking about the Axiom of Choice and it’s more horrifying implications. Well, I’m going to jump in on the bandwagon and present deGroot’s problem. This is essentially a continuous version of the Banach-Tarski paradox, and is therefore somewhat more horrifying than the standard version. The solution is due to Trevor Wilson, and my understanding is that it came out of an REU. This post is mostly taken from having to present his paper to one of my professors as part of an independent study on Banach-Tarski.

Standard Banach-Tarski is a discrete paradox. That is, the pieces move instantaneously from the unit ball you begin with to the two unit balls you finish with. De Groot asked if there were a continuous version, that is, a way to actually pull the ball apart with a continuous family of isometries. To this end, we define A, B \subseteq \mathbb{R}^n are continuously G-equidecomposable, written A\cong_G B if there are finite partitions \{A_i\}, \{B_i\} of A, B respectively and a family of G-paths \{\gamma^i\} so that for all i we have \gamma_0^i=e,\gamma_1^i A_i=B_i and \gamma_t^iA_i\cap \gamma_t^jA_j=\emptyset for all t\in [0,1] and all i\neq j. We omit G if it is the full isometry group. This is an equivalence relation on subsets of \mathbb{R}^n. We also define \mathscr{B} to be the bounded subsets of \mathbb{R}^n with n\geq 2 and we require that \mathbb{R}^2\subseteq G, that is, that the group of isometries contains all of the translations in the first two coordinates.

We define \left[A\right]=\{A'\in \mathscr{B}:A\cong A'\}, that is, continuous equidecomposability classes, and define \left[A\right]+\left[B\right]=\left[(A+u)\cup (B+v)\right] with u,v\in \mathbb{R}^2\subseteq G such that A+u lies to the left of B+v in the first coordinate. This summation is well-defined, associative and commutative, by fairly straightforward arguments. We’d like to be able to pick u=v=0, so we call a pair of disjoint sets A,B\in\mathscr{B} extricable if \left[A\right]+\left[B\right]=\left[A\cup B\right]. For a finite family of pairwise disjoint sets A_i\in \mathscr{B} we call it extricable if \sum_i [A_i]=[\cup_i A_i]. This means that, intuitively, two sets are extricable if we can separate them physically by breaking them into finitely many pieces. If \{A_i\} is extricable, then \{A_i^\prime\} is extricable when A_i^\prime\subset A_i for each i. We want to find a class of sets that are always extricable. So we let \mathscr{E}\subseteq\mathscr{B} consist of bounded sets A such that any two disjoint subsets of A are extricable. Equivalently, such that any finite pairwise disjoint family of subsets of A is extricable. We intend to show that \mathscr{E}=\mathscr{B}. To do so, we’ll need to know that \mathscr{E} is closed under taking subsets and under unions of extricable families, and that there is a partition of \mathbb{R} into sets S_1 and S_2 such that \Delta S=S_i-S_i are codense. We will assume both of these, and the second requires the use of the Axiom of Choice. We can now prove that \mathscr{E}=\mathscr{B}. First, we let A\in \mathscr{B}. Using the sets S_i\subseteq \mathbb{R}, i=1,2, we define S_{ij}=S_i\times S_j\times \mathbb{R}^{n-2}. Also, define A_{ij}=A\cap S_{ij}. Let r> the diameter of A, and now we know that \{A_{ij}\} is extricable, because we can translate A_{ij} by ir in the second dimension and then by (2i+j)r in the first. It is enough to show that A_{ij}\in \mathscr{E}. Actually, for any i and j there is a singe path \gamma in \mathbb{R}^2\subset G such that it can separate any disjoint pair B,C\subseteq A_{ij} defined as follows: Let \{a_k\}\to 0 and \{b_k\}\to 0 be sequences in \mathbb{R}\setminus\Delta S_i and \mathbb{R}\setminus\Delta S_j respectively, and define a sequence \{v_k\} in \mathbb{R}^2 by v_0=(r,b_0), v_{2k+1}=(a_k,b_k), v_{2k+2}=(a_k,b_{k+1}) Then, we let \gamma linearly interpolate between v_{k+1} and v_k during the time interval 2^{-k-1}\leq t\leq 2^{-k} and with \gamma(0)=0. For t>0 we have \gamma_t\notin \Delta S_i\times \Delta S_j, and so \gamma_t(A_{ij})\cap A_{ij}=\emptyset. And so, \gamma_t(C)\cap B=\emptyset for all t, and moreover \gamma_1(C)=C+(r,b_0,0,\ldots,0) lies strictly to the right of B, and so \gamma extricates \{B,C\}. And so we have established that \mathscr{E}=\mathscr{B}. This theorem has many consequences. For one thing, if n\geq 2, any finite partition of a bounded subset of \mathbb{R}^n is extricable by translations. However, here’s the coup de grace: If n\geq 2 and G is a path-connected group of isometries of \mathbb{R}^n containing all translations in two dimensions, then any two G-equidecomposable bounded subsets A and B of \mathbb{R}^n are continuously G-equidecomposable. If we suppose that A and B are discretely equidecomposable using the partitions \{A_i\} and \{B_i\} and isometries \{g_i\}. Choosing a path from e to g_i in G gives A_i\approx B_i, and so we have \left[A\right]=\sum_i \left[A_i\right]=\sum_i\left[B_i\right]=\left[B\right]. And now, we apply the traditional Banach-Tarski Paradox to obtain the following: If n\geq 3, then any two bounded subsets of \mathbb{R}^n with nonempty interior are continuously equidecomposable using proper isometries. This is the strong form of the Banach-Tarski paradox, in which the pieces are pulled apart continuously. I’ve been told that logicians who thought about this were trying to show that you couldn’t do this (or that it was consistent that you couldn’t). Well, ZFC is far richer than expected, it seems.

About these ads

About Charles Siegel

Charles Siegel is currently a postdoc at Kavli IPMU in Japan. He works on the geometry of the moduli space of curves.
This entry was posted in Group Theory, Logic. Bookmark the permalink.

3 Responses to deGroot’s Problem

  1. Slawekk says:

    While we are looking at the horrible consequences of AC it might be worthwhile to see what we loose if we don’t use it. For example, without AC the set of real numbers may be a countable union of countable sets and we can not reasonably define the Lebesgue measure on it, or any nontrivial (\sigma-additive) measure that assigns 0 to singletons.

  2. Charles says:

    Of course, I personally am a big fan of AC. Vector Spaces should have bases, nonzero rings should have maximal ideals, etc. I guess you could say that Zorn’s Lemma is the version that I truly believe in, and the others just come part and parcel with it. But in general, I believe we lose a lot more by not taking Choice than by accepting it. I mostly just thought that this was a fun result and that it should be shared.

  3. thomas1111 says:

    It’s indeed a very nice result I wasn’t aware of, thanks for sharing it. In return can I ask if you know whether the Banach-Tarski paradox can be obtained using only the countable axiom of choice? I had blogged about that a while ago but was confused and would welcome any hint…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s