This post is a rewritten (and slightly extended) form of a survey paper that I wrote in 2014 for a seminar as a graduate student. Proofs for many of the results have been omitted as they are available in their respective papers, listed in the references at the end of this post. I will, however, list proofs that make important points (such as the proof of the Sierpiński-Mazurkiewicz Paradox which doesn’t use the Axiom of Choice) or were not given in the original source (as is the case for a lemma in the first paper of Sherman).
1. The Paradox of Sierpiński and Mazurkiewicz
1.1 Definition We say that $t\in\mathbb{C}$ is algebraic if it is the solution of a non-zero polynomial with integer coefficients. If $t\in\mathbb{C}$ is not algebraic, then it is transcendental.
1.2 Lemma Let $p_{1},p_{2}$ be distinct polynomials with integer coefficients and $t\in\mathbb{C}$ transcendental. Then, $p_{1}\left(t\right)\neq p_{2}\left(t\right)$.
Proof. By definition, $p_{1}\left(t\right)-p_{2}\left(t\right)=\left(p_{1}-p_{2}\right)\left(t\right)\neq0$. QED
1.3 Definition. A function $f:U\to V$, where $U,V\subseteq\mathbb{R}^{n}$, is distance-preserving if $|f\left(x\right)-f\left(y\right)|=|x-y|$ for all $x,y\in U$. We say that $f$ is an isometry if it is a bijective distance-preserving map. If an isometry exists between $U$ and $V$, then we say that $U$ and $V$ are congruent, denoted $U\cong V$.
1.4 Theorem. (Sierpiński-Mazurkiewicz Paradox, 1914). There exists a nonempty $E\subseteq\mathbb{C}$ with subsets $A,B\subseteq E$ which satisfy $E=A\cup B$ and $A\cap B=\varnothing$ such that $A\cong E\cong B$.
Proof. Let $P=\mathbb{Z}_{\geq0}\left[x\right]$, $t=e^{i}$, and $E=\left\{ p\left(t\right):p\in P\right\} $. Then, by Lemma 1.2, $A=\left\{ p\left(t\right)\in E:p\left(0\right)=0\right\} $ and $B=\left\{ p\left(t\right)\in E:p\left(0\right)\neq0\right\}$ are disjoint, and obviously $E=A\cup B$. Now, let $f:A\to E$ and $g:B\to E$ be the isometries defined by $f\left(a\right)=e^{-i}a$ and $g\left(b\right)=b-1$. QED
This theorem comes before the more famous paradox, the Banach-Tarski Paradox, which says that any ball in $\mathbb{R}^{3}$ can be split into a finite number (5) of pieces and rearranged via isometries to form two copies of the same ball. However, unlike the Banach-Tarski Paradox, there is no need for the Axiom of Choice, as the sets are obviously constructed with no arbitrary choices! For a complete treatment, see Stan Wagon’s book titled The Banach-Tarski Paradox [1].
Now, we look at the general definition of a paradoxical decomposition.
1.5 Definition. Let $G$ be a group acting on a set $X$. we say that $A,B\subseteq X$ are $G$-congruent if there exists $g\in G$ such that $gA=B$. We say that $A,B$ are $G$-equidecomposible (in $n$ pieces), denoted $A\overset{G}{\sim}B$ ($A\overset{G}{\sim}_{n}B$) if $A$ and $B$ can be partitioned into the same countable number of respectively $G$-congruent pieces. We say that a nonempty $E\subseteq X$ is $G$–$\left(m,n\right)$-paradoxical if, for positive integers $m,n$ there is a partition $\left\{A,B\right\}$ of $E$ with $A\overset{G}{\sim}_{m}E$ and $B\overset{G}{\sim}_{n}E$.
N.B.: Some authors use the inverse of this definition. That is, they define partitions $\left\{ A_{i}\right\} _{i=1}^{m},\left\{ B_{j}\right\} _{j=1}^{n}$ of $E$ with $g_{i},h_{j}\in G$ such that $\left\{ g_{i}\left(A_{i}\right)\right\} \cup\left\{ h_{j}\left(B_{j}\right)\right\}$ is a single partition of $G$, whereas the above definition (as well as the proof of the Sierpiński-Mazurkiewicz Paradox) uses a single partition to make two. To translate between the two definitions, just note that we can get from the single partition $\left\{ g_{i}\left(A_{i}\right)\right\} \cup\left\{ h_{j}\left(B_{j}\right)\right\}$ to the original partitions via $g_{i}^{-1}$ and $h_{j}^{-1}$.
1.6 Theorem (Tarski). [1, Cor. 9.2] Suppose $G$ acts on $X$ and $E\subseteq X$. Then, there is a finitely additive, $G$-invariant measure $\mu:\mathscr{P}\left(X\right)\to\left[0,\infty\right]$ with $\mu\left(E\right)=1$ if and only if $E$ is not $G$-paradoxical.
1.7 Remark. Tarski’s Theorem is one of the main theorems of the study of paradoxical decompositions. This tells us that the existence of a finitely additive measure which normalizes the set is essentially the same as saying there are no paradoxes in this set.
1.8 Remarks. We omit $G$ when it is obvious what it is. From now on, we take $X=\mathbb{C}$ and $G$ the group of planar isometries acting on $\mathbb{C}$ in the obvious way. Therefore, Theorem 1.4 says that there exists a $\left(1,1\right)$-paradoxical subset of the plane.
2. Other Paradoxical Subsets
Note that the set constructed in the Sierpiński-Mazurkiewicz paradox is unbounded and countable. So, a natural question would be: “Are there any bounded paradoxical subsets? Are there any which are not countable?”
The answer to the first question is yes, but it was shown in 1926 by Lindenbaum that it cannot be $\left(1,1\right)$-paradoxical.
2.1 Theorem (Lindenbaum, 1926). There is no bounded subset of the plane which is $\left(1,1\right)$-paradoxical.[3]
A proof is given in [4] for Proposition 43.
In fact, Glen Aldridge Sherman, in 1990, showed that we cannot even find one that is $\left(1,2\right)$-paradoxical. [5]
First, though, we will introduce the following definition and prove the lemma given in his paper which was not given a proof.
2.2 Definition. Let $G$ be a group acting on $X$, and let $E\subseteq X$ be a $G-\left(m,n\right)$-paradoxical subset with witnessing partitions $A_{1},\ldots,A_{m}$, $B_{1},\ldots,B_{n}$ and group elements $g_{1},\ldots,g_{m},h_{1},\ldots,h_{n}\in G$. If we write $\mathscr{A}=\left\{ A_{i}\right\}$, $\mathscr{B}=\left\{ B_{j}\right\}$, $\mathscr{G}=\left\{ g_{i}\right\}$, and $\mathscr{H}=\left\{ h_{j}\right\}$, then the associated digraph $\Gamma=\Gamma\left(\mathscr{A},\mathscr{B},\mathscr{G},\mathscr{H}\right)$ of the decomposition is an infinite digraph with vertex set $V\left(\Gamma\right)=E$ and the set of directed edges consists of pairs $\left(x,g_{i}\left(x\right)\right)$ and $\left(x,h_{j}\left(x\right)\right)$ where $x\in A_{i}\cap B_{j}$.
2.3 Lemma. Let $\Gamma$ be a connected directed graph with invalency 1 at each vertex. Then, $\Gamma$ contains at most one cycle.
Proof. Let $\Gamma$ be any directed graph with invalency 1 at each vertex. If $\Gamma$ has two cycles, then there is no way to connect them, as this would break the invalency condition. Hence, $\Gamma$ is not connected. Therefore, if $\Gamma$ is a connected directed graph with invalency 1 at each vertex, then $\Gamma$ has at most one cycle. QED
2.4 Theorem (G.A. Sherman, 1990). There is no bounded subset of the plane which is $\left(1,2\right)$-paradoxical.[5]
In the same paper, however, Sherman constructs a bounded $\left(2,2\right)$-paradoxical subset, while just two years earlier, W. Just had constructed a bounded $\left(1,3\right)$-paradoxical subset.
2.5 Theorem (W. Just, 1988). There is a bounded $\left(1,3\right)$-paradoxical subset of the plane.[6]
2.6 Theorem (G.A. Sherman, 1990). There is a bounded $\left(2,2\right)$-paradoxical subset of the plane.[5]
So, this answers the first question! However, these sets are still countable. Can we get anything bigger? Well, the easy way to see this is by using the Axiom of Choice.
2.7 Theorem (Burke, 2000) (Requires AC). For any countable $\left(m,n\right)$-paradoxical subset of the plane with witnessing sets $\left\{ A_{0,j}:0\leq j\lt m\right\}$, $\left\{ A_{0,j}:m\leq j\lt m+n\right\}$ and corresponding isometries $f_{j}$ having the form $f_{j}\left(z\right)=a_{j}z+b_{j}$ where $|a_{j}|=1$, there is an uncountable $\left(m,n\right)$-paradoxical subset.
What if we don’t want to use the axiom of choice? In this case, it is time for some stuff that wasn’t included in my original write up. First, one needs to be familiar with a paper by von Neumann titled Ein System algebraisch unabhängiger Zahlen, or A System of Algebraically Independent Numbers.[11] Click that link for the English translation of his paper which I had translated myself (for my second seminar of 2014). My main motivation for this paper was simply for the next result.
2.8 Theorem. [1, Thm 6.2] There is an uncountable $\left(1,1\right)$-paradoxical subset of the plane.
Now that we have a bunch of examples of paradoxical subsets of the plane, let’s talk about their measures!
3. Measures of Paradoxical Subsets
3.1 Definition. Let $I=\left[a_{1},b_{1}\right]\times\cdots\times\left[a_{n},b_{n}\right]$. Then, define $\nu\left(I\right)=\prod_{i=1}^{n}\left(b_{i}-a_{i}\right)$. The Lebesgue outer measure of a subset $A\subseteq\mathbb{R}^{n}$ is $m^{*}\left(A\right)=\inf\left\{ \sum_{k\geq0}\nu\left(J_{k}\right):A\subseteq\bigcup_{k\geq0}J_{k}\right\}$, where each $J_{k}$ is of the same form as $I$. The Lebesgue inner measure is $m_{*}\left(A\right)=\sup\left\{ m^{*}\left(K\right):K\subseteq A,K\text{ }{\rm compact}\right\}$. We say that $A$ is measurable if $m^{*}\left(A\right)=m_{*}\left(A\right)$, and we call this common value the Lebesgure measure of $A$, denoted $m\left(A\right)$. An inner regular measure is a measure on a topological space where the inner measure may be approximated by compact measurable subsets. An outer regular measure is a measure on a topological space where the outer measure may be approximated by open measurable subsets. A measure is regular if it is both inner and outer regular.
3.2 Theorem. The following statements are true for the Lebesgue measure $m$ on $\mathbb{R}^{n}$.
- 1. Any open or closed ball is measurable, and the measure is exactly what you would expect. In particular, in $\mathbb{R}^{2}$, $m\left(N_{r}\left(x\right)\right)=\pi r^{2}$.
- 2. Lebesgue measure is countably additive.
- 3. Countable subsets have measure $0$. (Converse is not true: Cantor set). Proof sketch: Enumerate the set and cover each point $a_{i}$ by open intervals of lengths $\varepsilon2^{-i}$.
- 4. If a subset has measure $0$, then it has empty interior. (Converse is not true: Fat Cantor set). Proof sketch: If there are interior points, then there are neighborhoods contained in the subset, which have non-zero measure.
- 5. There exist non-measurable subsets (Requires Axiom of Choice).
- 6. Lebesgue measure is regular.
- 7. (Banach, 1923) There exists a finitely-additive isometry invariant extension $\tilde{m}$ on all subsets of the plane. That is, for measurable $X\subseteq\mathbb{R}^{2}$, $\tilde{m}\left(X\right)=m\left(X\right)$. Such a measure is called a Banach measure.[7]
Most of the results referenced in Theorem 3.2 can be found in any standard Measure Theory text.
3.3 Lemma (Sherman, 1991). If $X$ is a paradoxical subset of $\mathbb{C}$, then $\tilde{m}\left(X_{0}\right)=0$ for every bounded $X_{0}\subseteq X$. (May be strengthened to allow for every $X_{0}$ with finite outer measure).[8]
3.4 Theorem (Sherman, 1991). Every paradoxical subset of $\mathbb{C}$ has empty interior.
3.5 Theorem (Sherman, 1991). Every measurable paradoxical subset of $\mathbb{C}$ has measure zero.
3.6 Corollary. Let $X\subseteq\mathbb{C}$ with either nonempty interior or nonzero measure. Then, there is a total, finitely additive, isometry invariant measure $\mu$ on $\mathbb{C}$ with $\mu\left(X\right)=1$. Proof sketch: Tarski’s theorem.
3.7 Question. Since Lemma 3.3 may be be made more general by allowing for the subsets to be of finite outer measure, Sherman posed a question in his 1991 paper regarding the outer measure of a paradoxical subset. Can one obtain a paradoxical subset of the plane which has nonzero outer measure? The answer is “Yes!” (If you accept the Axiom of Choice).
3.8 Theorem (Laczkovich & Burke, 2000). There exist unbounded (Laczkovich) [10] and bounded (Burke) [9] paradoxical subsets which have positive outer measure.
This theorem is inseparable from the Axiom of Choice, however, because (as stated in Theorem 3.2), the Axiom of Choice is needed to prove the existence of non-measurable subsets. Since the inner measure of any paradoxical subset will always be 0, this means that the outer measure being positive necessarily means we’re working with a non-measurable subset. Note that not even the Axiom of Dependent Choice, which is typically enough for most of Real Analysis, is enough for this.
References
[1] Wagon, Stan. The Banach-Tarski Paradox. New York: Cambridge University Press, 1994.
[2] S. Mazurkiewicz et W. Sierpiński, “Sur un ensemble superposable avec chacune de ses deux parties.” C. R. Acad. Sci. Paris 158 (1914), 618-619.
[3] A. Lindenbaum, Contributions a l’ètude de l’espace mètrique I, Fund. Math 8 (1926), 209-222.
[4] H. Hadwiger, H. Debrunner, and V. Klee, Combinatorial Geometry in the Plane, Holt, Rinehart, and Winston, New York 1964.
[5] Sherman, Glen Aldridge. “On bounded paradoxical subsets of the plane.” Fundamenta Mathematicae 136.3 (1990): 193-196.
[6] Just, W. “A bounded paradoxical subset of the plane.” Bull. Pol. Acad. Sci. 36 (1988): 1-3.
[7] S. Banach, “Sur le problème de la mesure.” Fund. Math. 4 (1923), 7-33.
[8] Sherman, Glen Aldridge. “Properties of Paradoxical Subsets in the Plane.” Journal of Geometry. 40.1-2 (1991): 170-174.
[9] Burke, Maxim R. “Paradoxical decompositions of planar sets of positive outer measure.” Journal of Geometry. 79.1-2 (2004): 56-58.
[10] Laczkovich, Miklós. “Paradoxical Decompositions: A Survey of Recent Results.” First European Congress of Mathematics Paris, July 6-10, 1992 Vol. II: Invited Lectures (Part 2), 1994.
[11] von Neumann, John, “Ein System algebraisch unabhängiger Zahlen.” Math. Ann. 99 (1928).