of 7
The
Journ
al of Symbolic
Logic
Volume
70, Number
3, Sept.
2005
A CONTINUOUS
MOVEMENT
VERSION
OF THE
BANACH–T
ARSKI
PARADO
X: A SOLUTION
TO DE GROOT’S PROBLEM
TREV
OR M. WILSON
Abstr
act.
In 1924
Banach
and Tarski
demonstra
ted the existence
of a parado
xical
decomposition
of
the 3-ball
B
, i.e., a piece
wise
isometry
from
B
onto
two copies
of
B
. This
article
answers a question
of de Groot from 1958
by showing
that there is a parado
xical
decomposition
of
B
in which
the pieces
move contin
uousl
y while remaining
disjoint
to yield
two copies
of
B
. More generall
y, we show that if
n

2, any two bounded
sets in
R
n
that are equidecomposa
ble with
proper
isometries
are contin
uousl
y
equidecomposa
ble in this sense
.
x
1. Equidecomposability
and the Banach–T
arski
paradox.
Fix a group
G
of
isometries
of
R
n
and define
the following
relation—w
hich
is easily seen
to be an
equivalence
relation—on
subsets
of
R
n
.
Definition
1.1
.
A;B

R
n
are
G
-equidecomposab
le
(written
A

G
B
) if there
are finite
partitions
f
A
i
g
and
f
B
i
g
of
A
and
B
respecti
vely, and elements
g
i
2
G
, so
that for all
i
we have
g
i
A
i
=
B
i
. If the group
G
is the full isometry
group of
R
n
, or
if it is clear
from conte
xt which
group is intended,
we will simpl
y say that
A
and
B
are equidecomposa
ble and write
A

B
.
Occasionall
y
G
-equidecomposa
bility
is called
piecewise
G
-congruence
. It is a
much weaker condition
than
congruence
. In particular
, we have the following
classical
results
.
Theorem
1.2
(Banach–T
arski
paradox)
.
There is a partitionofthe 3-ball
B
into
twosets,eachofwhichisequidecomposab
lewith
B
.
Theorem
1.3
(Banach–T
arski
paradox, strong form)
.
If
n

3
, then any two
boundedsubsetsof
R
n
withnonempty
interiorareequidecomposab
le.
For modern
proofs of these
theor
ems,
and other
facts
about
equidecomposa
bility
,
see, e.g., [4], [6].
x
2. Continuous
equidecomposability
.
One
possib
le strengthening
of equidecom-
posability
is the following.
Definition
2.1
.
A;B

R
n
are
continuousl
y
G
-equidecomposab
le
(written
A

G
B
) if there are finite
partitions
f
A
i
g
and
f
B
i
g
of
A
and
B
respecti
vely,
Received January
20, 2005;
accepted
May 9, 2005.
Resear
ch supported
by NSF
Grant
DMS
9987437.
c
2005,
Associa
tion
for Symbolic
Logic
0022-4812/05/7003-0013/$1.70
946
A CONTINUOUS
MOVEMENT
VERSION
OF THE
BAN
ACH–T
ARSKI
PARADO
X
947
and a famil
y of
G
-paths
f
i
g
, so that for all
i
we have
i
0
=
e
,
i
1
A
i
=
B
i
, and
i
t
A
i
\
j
t
A
j
=
;
for all
t
2
[0
;
1] and all
j
6
=
i
. Again,
if
G
is the full isometry
group, or is clear
from conte
xt, we will omit
it from the notation.
In contr
ast, the standar
d notion
of equidecomposa
bility
in Definition
1.1—w
hich
we will call “discr
ete equidecomposa
bility”—is
equivalent
to only requiring
the
i
to be defined
at
t
= 1. Intuiti
vely, in a contin
uous
decomposition
the motion
can
be realized physicall
y by moving
the pieces
in time
rather than
transporting
them
instantaneousl
y to their
destina
tions
.
Before proceeding
we should
justify
our notation with
the following
observ
ation.
Proposition
2.2.

isanequivalencerelation.
Proof.
The trivial partition
and trivial path witness
A

A
. If
f
A
i
g
,
f
B
i
g
, and
f
i
g
witness
A

B
, then
the same
partitions
and the paths
f
i
1
t
(
i
1
)
1
g
witness
B

A
. If additionall
y
f
B
0
j
g
,
f
C
j
g
and
f
j
g
witness
B

C
, then
the partitions
f
A
i
\
(
i
1
)
1
B
0
j
g
i;j
and
f
C
j
\
j
1
B
i
g
i;j
and the paths
f
i
:
(
j
i
1
)
g
i;j
witness
A

C
,
where “.” denotes
conca
tenation of paths.
a
Contin
uousl
y equidecomposa
ble sets are discretely equidecomposa
ble, and we
will shortl
y see that under
some
broad conditions
the converse is true.
x
3. A type
semigr
oup for bounded
sets.
To avoid the explicit
construction
of
complica
ted decompositions,
we will develop a notion
of addition
of sets that allows
us to combine
decompositions
of smaller
sets into a decomposition
of a larger set.
We want this addition
to be well-defined
on contin
uous
equidecomposa
bility
classes
(

-classes
.)
We will restrict
our attention
to the ideal
B
of bounded
subsets
of
R
n
, which
is
closed
under
equidecomposa
bility
, and additionall
y requir
e
n

2
;
R
2

G;
(1)
where by the latter condition
we mean
that
G
contains
all transla
tions
in the first
two dimensions—an
example
to keep in mind
is the group
of proper
isometries
of
R
n
. These
conditions
have a dual
purpose:
to allow us to define
addition
of

-classes,
and to show that

-classes
are the same
as

-classes,
i.e., that contin
uous
equidecomposa
bility
is no stronger
than
discrete equidecomposa
bility
for bounded
sets. We will also assume
the Axiom
of Choice
, which,
along
with
boundedness,
is
requir
ed for the Banach–T
arski
paradox anyway.
In the semigr
oup
of discrete equidecomposa
bility
types
(see, e.g., [4], [6],)
the
sum
of two bounded
sets may be defined
as the union
of disjoint
transla
tes. Since
it is not
apriori
apparent that this operation is well-defined
on contin
uous
equide-
composa
bility
classes,
we will further
restrict
the choice
of transla
tes. Writing
[
A
]
for
f
A
0
2
B
:
A
0

A
g
, define
addition
by
[
A
] + [
B
] = [(
A
+
u
)
[
(
B
+
v
)]
;
(2)
where
u;v
2
R
2

G
are chosen
so that
A
+
u
lies strictl
y to the left of
B
+
v
in the
first coordinate, i.e.,
p
1
(
v
u
)
>p
1
(
a
b
) for all
a
2
A
and
b
2
B;
(3)
where
p
1
is the first coordinate projection.
948
TREV
OR M. WILSON
Proposition
3.1.
Theoperation
(2)
iswell-defined,
associative,andcommutative.
Proof.
The sum
[
A
] + [
B
] is independent
of the choice
of
u
and
v
: if
u
0
and
v
0
also satisfy
(3) then
(
A
+
u
)
[
(
B
+
v
)

(
A
+
u
0
)
[
(
A
+
b
0
) by transla
ting
A
+
u
and
B
+
v
along
line segments
. Now we will show that [
A
] + [
B
] is independent
of
the choices
of representa
tives of [
A
] and [
B
]. Suppose
A

A
0
is witnessed
by the
pieces
f
A
i
g
and
f
A
0
i
g
and paths
f
i
g
, and
B

B
0
is witnessed
by the pieces
f
B
i
g
and
f
B
0
i
g
and paths
f
i
g
. Since
A
and
B
are bounded
and the time
interv
al [0
;
1] is
compact
we may choose
u
and
v
so that
p
1
(
v
u
)
>p
1
(
a
b
) for all
i;j;t;a
2
i
t
(
A
i
)
;b
2
j
t
(
B
j
)
:
Then
the decomposition
[
A
]+[
B
] = [
A
0
]+[
B
0
] is witnessed
by the pieces
f
A
i
+
u
g
[
f
B
j
+
v
g
and
f
A
0
i
+
u
g
[
f
B
0
j
+
v
g
and the paths
f
Ù
u
i
Ù
u
g
[
f
Ù
v
j
Ù
v
g
, where
Ù
denotes
transla
tion in the first coordinate. Ther
efore the operation is well-defined.
Associa
tivity is trivial.
For comm
utativity, choose
r>
diam(
A
[
B
); then
[
A
] + [
B
] = [
A
[
(
B
+
r
)] = [
A
[
(
B
r
)] = [
B
] + [
A
]
is witnessed
by
1
= 0 and
2
t
=
re
it
r
, where
R
2

G
is consider
ed as
C
.
a
x
4. Extricability.
Next we consider
a property
of pairs
of sets
A;B
2
B
that
makes the condition
(3) unnecessary
, so that in defining
[
A
] + [
B
] we can safely
choose
u;v
= 0 in (2).
Definition
4.1
.
A pair
of disjoint
sets
A;B
2
B
is
extricable
if [
A
] + [
B
] =
[
A
[
B
]. More gener
ally, a finite
famil
y of pairwise
disjoint
sets
A
i
2
B
is extrica
ble
if
P
i
[
A
i
] = [
S
i
A
i
].
Intuiti
vely, sets are extrica
ble if they
can be physicall
y separ
ated from each
other
with
a finite
number
of cuts. Note
that if
f
A
i
g
is extrica
ble and
A
0
i

A
i
for all
i
,
then
the same
G
-paths extrica
te
f
A
0
i
g
. We are interested
in sets that are small
enough
that their
subsets
are always extrica
ble:
Definition
4.2
.
Let the class
E

B
consist
of bounded
sets
A
such
that any
two disjoint
subsets
of
A
are extrica
ble, or equivalentl
y (by induction,)
such
that
any finite
, pairwise
disjoint
famil
y of subsets
of
A
is extrica
ble.
In fact, we will show that
E
=
B
, but first we need
some
lemmas
.
Lemma
4.3.
E
isclosedundersubsetsandunderunionsofextricablefamilies.
Proof.
Closur
e under
subsets
is obvious
. If the sets
A
i
2
E
form an extrica
ble
famil
y, then
given finitel
y many pairwise
disjoint
B
j

S
i
A
i
, we have

[
j
B
j

=
X
i

[
j
(
A
i
\
B
j
)

=
X
i;j
[
A
i
\
B
j
] =
X
j

[
i
(
A
i
\
B
j
)

=
X
j
[
B
j
]
and
f
B
j
g
is extrica
ble.
a
Lemma
4.4.
There is a partition
f
S
1
;S
2
g
of
R
such thatthe algebraic diªerences
±
S
i
=
S
i
S
i
arecodensein
R
.
Proof.
Define
K
=
S
n
2
N
1
3
n
Z
and
H
=
K
+
1
2
Z
. Use the Axiom
of Choice
to select
coset
representa
tives
f
r
g
for
R
=H
, and define
S
1
=
S
(
r
+
K
) and
S
2
=
S
1
+
1
2
. For all
a;b
2
S
i
, if
a
b
2
H
then
a
b
2
K
, so ±
S
i
is disjoint
from
the dense
set
H
n
K
=
K
+
1
2
.
a
A CONTINUOUS
MOVEMENT
VERSION
OF THE
BAN
ACH–T
ARSKI
PARADO
X
949
Theorem
4.5.
E
=
B
.
Proof.
Let
A
2
B
. Using
the sets
S
i

R
,
i
= 1
;
2 from above, define
S
ij
=
S
i

S
j

R
n
2
and let
A
ij
=
A
\
S
ij
. Choose
r>
diam
A
; then
f
A
ij
g
is extrica
ble
by linear
ly transla
ting
A
ij
by
ir
in the second
dimension
and then
by (2
i
+
j
)
r
in
the first, as shown schema
ticall
y in Figur
e 1 below. Now by Lemma
4
:
3 it suºces
to show
A
ij
2
E
. In fact, for any
i
and
j
there is a single
path
in
R
2

G
that
can separ
ate any disjoint
pair
B;C

A
ij
, defined
as follows. Let
f
a
k
g
!
0 and
f
b
k
g
!
0 be sequences
in
R
n
±
S
i
and
R
n
±
S
j
respecti
vely, and define
a sequence
f
v
k
g
in
R
2

G
by
v
0
= (
r;b
0
)
; v
2
k
+1
= (
a
k
;b
k
)
; v
2
k
+2
= (
a
k
;b
k
+1
)
:
Then
let
linear
ly interpola
te betw
een
v
k
+1
and
v
k
during
the time
interv
al 2
k
1

t

2
k
, and define
(0) = 0 (Fig.
2.) For all
t >
0 we have
t
=
2
±
S
i

±
S
j
, so
t
(
A
ij
)
\
A
ij
=
;
. Ther
efore
t
(
C
)
\
B
=
;
for all
t
, and moreover
1
(
C
) =
C
+ (
r;b
0
;
0
;:::;
0) lies strictl
y to the right
of
B
, so
extrica
tes
f
B;C
g
.
a
A
A
11
[
A
12
6
A
21
[
A
22
6
-
A
11
-
A
12
-
A
21
-
A
22
Figure
1.
f
A
ij
g
is extrica
ble.
-
6
-
v
0
v
1
v
2
v
3
Figure
2.
The path
.
Immedia
tely we have the following:
Corollary 4.6.
If
n

2
,anyfinitepartitionofaboundedsubsetof
R
n
isextricable
bytranslations
.
x
5. Acontinuous
paradox.
Wehaveshownthatunder
theconditions
(1), bounded
sets may be contin
uousl
y separ
ated into pieces
. If the group
G
is path-connected,
950
TREV
OR M. WILSON
as is the group of proper
isometries,
congruences
of these
pieces
may be realized
contin
uousl
y. Thus
we have the following
result.
Theorem
5.1.
If
n

2
and
G
isapath-connected
groupofisometries
of
R
n
con-
tainingalltranslations
intwodimensions
,thenanytwo
G
-equidecomposab
lebounded
subsets
A
and
B
of
R
n
arecontinuousl
y
G
-equidecomposab
le.
Proof.
Suppose
that
A
and
B
are discretely equidecomposa
ble using
the parti-
tions
f
A
i
g
and
f
B
i
g
and isometries
f
g
i
g
. Choosing
a path from
e
to
g
i
in
G
gives
A
i

B
i
, so we have [
A
] =
P
i
[
A
i
] =
P
i
[
B
i
] = [
B
].
a
Consequentl
y, we obtain
a contin
uous
version
of the strong form of the Banach–
Tarski
paradox:
Corollary 5.2.
If
n

3
then any two bounded subsets of
R
n
with nonempty
interiorarecontinuousl
yequidecomposab
leusingproperisometries
.
Proof.
Simpl
y note
that the proof of the Banach-T
arski
paradox (see, e.g., [4],
[6],)
uses
only the group of proper
isometries,
which
satisfies
the conditions
of the
theor
em.
a
In particular
, the 3-ball
has a contin
uous
paradoxical
decomposition,
solving
a
question
of de Groot posed
in [1, p. 25] and again
by Wagon [6, pp. 32, 232].
In the
latter, the question
appears
in a slightl
y diªer
ent form:
Question
5.3 (De Groot’s question)
.
Let
B
,
B
1
, and
B
2
be pairwise
disjoint
unit
balls
in
R
3
. Can
B
be partitioned
into sets
A
1
;:::;A
m
;A
m
+1
;:::;A
m
+
n
such
that
for each
i
= 1
;:::;m
+
n
and
t
2
[0
;
1] there is an isometry
Û
i
t
satisfying:
1.
Û
i
0
is the identity;
Û
i
1
(
A
i
),
i
= 1
;:::;n
partitions
B
1
;
Û
i
1
(
A
i
),
i
=
n
+ 1
;:::;
n
+
m
partitions
B
2
.
2. For each
i
, the isometries
Û
i
t
depend
contin
uousl
y on
t
.
3. For each
t
2
[0
;
1], the sets
Û
i
t
(
A
i
),
i
= 1
;:::;m
+
n
are pairwise
disjoint.
Corollary 5.4.
DeGroot’squestionhasanaºrmativeanswer.
Proof.
By Corollary
5.2, there is a contin
uous
decomposition
B

B
1
[
B
2
witnessed
by pieces
C
i
and
paths
i
for
i

n
. Set
m
=
n
and
define
A
i
=
C
i
\
(
i
1
)
1
B
1
,
A
n
+
i
=
C
i
\
(
i
1
)
1
B
2
, and
Û
i
=
Û
n
+
i
=
i
for all
i

n
.
a
In a slightl
y diªer
ent vein, we may apply the theor
em to Laczk
ovich’s solution
[5]
of Tarski’
s circle-squaring
problem:
that a circle (including
interior)
is equidecom-
posable in
R
2
with
a squar
e of equal
area. In fact, Laczk
ovich’s result
uses
only
transla
tions,
so Theor
em 5.1 immedia
tely yields
the following.
Corollary 5.5.
A circle is continuousl
yequidecomposab
leby translations
with a
squareofequalarea.
x
6. Necessity
of conditions
for theor
em 5.1.
In the real line, contin
uous
equide-
composa
bility
is much stronger
than
discrete equidecomposa
bilty
because
it pre-
serves order type.
Theorem
6.1.
If
A;B

R
and
A

B
by isometries
, then
A
and
B
are order-
isomorphic
.
Proof.
If the decomposition
is witnessed
by
f
A
i
g
,
f
B
i
g
, and
f
i
g
, then
each
i
t
is in the path-component
of the identity
and is therefore a transla
tion.
For all
t
2
[0
;
1] define
the piece
wise
transla
tion
g
t
=
S
i
i
t
j
A
i
. We have
g
1
(
A
) =
B
, and
A CONTINUOUS
MOVEMENT
VERSION
OF THE
BAN
ACH–T
ARSKI
PARADO
X
951
g
1
is strictl
y order-preserving:
Fix
x;y
2
A
with
x < y
and suppose
x
2
A
i
and
y
2
A
j
. If
i
=
j
, then
g
1
(
x
) =
i
1
x<„
i
1
y
=
g
1
(
y
). Otherwise
, since
i
t
A
i
and
j
t
A
j
are disjoint
for all
t
, the contin
uous
function
g
t
(
x
)
g
t
(
y
) =
i
t
x
j
t
y
is nonz
ero,
and since
it is positi
ve for
t
= 0 it is positi
ve for
t
= 1 and
g
1
(
x
)
<g
1
(
y
).
a
For example
,
f
2
n
g
n
2
N
[
f
0
g
6
f
2
n
g
n
2
N
[
f
2
g
even though
the two sets are
discretely equidecomposa
ble, since
only the former has a least
element.
The next
two examples
show the necessity
of assuming
that
G
is path-connected,
and of
allowing
more pieces
in the decomposition.
Example
6.2
.
Let
n
= 2 and let
G
be the full isometry
group of
R
2
. Choose
an infinite
set
A

R
2
so that all distances
in
A
are distinct
and no three points
are collinear
; e.g., consider
R
2
as
C
and let
A
=
f
e
i
2
n
:
n
2
N
g
. We claim
that
A
6
gA
if
g
is an improper
isometry
. Otherwise
, some
piece
in the decomposition
must contain
three points
f
a
i
g
, which
map to
ha
i
respecti
vely for some
isometry
h
in the path-component
of the identity
. Then
by uniqueness
of distances
we have
ha
i
=
ga
i
for all
i

3. However, the images of three non-collinear
points
uniquel
y
deter
mine
an isometry
, so
h
=
g
is improper, a contr
adiction.
Example
6.3
.
Let
S
be the unit spher
e in
R
n
and choose
x
2
R
n
with
j
x
j
>
3.
Then
S
[
f
x
g
and
S
[
f
0
g
are discretly equidecomposa
ble by transla
tion using
the
two pieces
S
and
f
x
g
. Conversely, since
d
(
S;x
)
>
diam(
S
[
f
0
g
), no piece
of a
decomposition
can intersect
both
S
and
f
x
g
, so if there are only two pieces,
they
must be
S
and
f
x
g
themselv
es. However, if there is a contin
uous
decomposition,
then
without
loss of gener
ality
it fixes
S
and connects
0 and
x
with
a path in
R
n
n
S
,
which
is impossib
le.
x
7. Remarks.
Remark
7.1
.
A re-examina
tion
of Section
4 shows that Corollary
4.6 may be
strengthened
to place
a bound
on the number
of pieces
. In extrica
ting
an
n
-
partition
of a bounded
set
A
, the only subdi
vision
occurs
when we take a common
refinement
with
the partition
f
A
ij
=
A
\
S
ij
g
i;j
=1
;
2
in Theor
em 4.5, so each
of the
original
pieces
is divided
in four, and the partition
may be extrica
ted in 4
n
pieces
.
Likewise, Theor
em 5.1 can be strengthened
to say that if the bounded
sets
A
and
B
are equidecomposa
ble in
n
pieces,
then
they
are contin
uousl
y equidecomposa
ble
in 16
n
pieces
: each
piece
is divided
in four to be extrica
ted from
A
, and its image
under
the decomposition
is divided
in four to be extrica
ted from
B
. In fact, we
can do slightl
y better
: without
loss of gener
ality
one piece
of the decomposition
remains
fixed, so these
two subdi
visions
coincide
and it is divided
in four only once.
Ther
efore
A
and
B
are contin
uousl
y equidecomposa
ble in 4
2
(
n
1) + 4 = 16
n
12
pieces
.
In the special
case of paradoxical
decompositions
of a ball we can do better
still.
Ther
e is a discrete decomposition
of a ball
B
with
two copies
B
1
[
B
2
using
five
pieces,
described
in [6, p. 41]. By transla
ting and rotating
B
1
and
B
2
, we may assume
that each
of them
contains
a piece
whose
total
movement
is a transla
tion by some
element
of the subgr
oup
K
0
=
K

K

R
n
2
of
R
n
, with
K
from Lemma
4.4;
then
since
the sets
S
ij
are invariant
under
K
0
, these
two pieces
are only subject
to
one subdi
vision
each.
Moreover, another
one of the pieces
is a single
point
, which
952
TREV
OR M. WILSON
cannot
be subdi
vided
at all. Thus
a contin
uous
decomposition
may be accomplished
in 4
2

2 + 4

2 + 1 = 41 pieces
.
Remark
7.2
.
Dougherty
and Foreman
[2] give a version
of the Banach–T
arski
paradox using
sets with
the Baire property
. However, the sets
S
i
in Lemma
4.4
cannot
have the Baire property
, since
otherwise
one of them
would
be nonmea
ger
and by Pettis’s Theor
em (see, e.g., [3]) its algebraic diªer
ence
±
S
i
would
contain
a neighborhood
of zero. Ther
efore our procedur
e for gener
ating
a contin
uous
decomposition
from a discrete one does
not preserv
e the Baire property
in the
pieces,
and the question
of the existence
of a contin
uous
paradox using
pieces
with
the Baire property
is left open.
x
8. Ackno
wledgments.
This
paper is the result
of an under
gradua
te resear
ch
project
supported
by an NSF
grant.
The author
would
like to thank
Prof. A. S.
Kechris
of Caltech
for his time
and guidance
.
REFERENCES
[1]
Theod
orus Jozef
Dekker
,
Paradoxicaldecompositions
ofsetsandspaces
, Ph.D
. thesis,
Drukk
erij
Wed. G. van Soest
, Amster
dam,
1958.
[2]
Rand
all Dougher
ty
and
Matthew Foreman
,
Banach-Tarski paradox using pieces with the
property of Baire
,
Proceedings
of the National
Academy
of Sciences of the United States of America
,
vol. 89 (1992),
no. 22, pp. 10726–10728.
[3]
Alex
ander
S. Kechris
,
Classicaldescriptivesettheory
, Gradua
te Texts in Mathema
tics, vol. 156,
Springer
-Verlag, New York, 1995.
[4]
Mikl
́
os Laczkovich
,
Equidecomposability
anddiscrepancy;asolutionofTarski’scircle-squaring
problem
,
Journalf
̈
urdieReineundAngewandteMathematik
, vol. 404 (1990),
pp. 77–117.
[5]
,
Equidecomposability
ofsets,invariantmeasures,andparadoxes
,
Rendicontidell’Istituto
di
Matematica
dell’Universit
`
a di Trieste
, vol. 23 (1991),
no. 1, pp. 145–176,
(1993),
School
on Measur
e
Theory
and Real Anal
ysis (Grado
, 1991).
[6]
Stan Wagon
,
The Banach-Tar
ski paradox
, Ency
clopedia
of Mathema
tics and its Applica
tions,
vol. 24, Cambridge
University
Press, Cambridge
, 1985.
DEPARTMENT
OF MATHEMA
TICS
CALIFORNIA
INSTITUTE
OF TECHNOL
OGY
PASADEN
A, CA 91125,
USA
E-mail
: trev@its
.caltech.edu