Part VIII · Foundations Chapter 54 of 60
Measure and the Lebesgue integral
How much do all the fractions in a segment weigh? The answer ‘nothing’ forced length to be defined afresh, and led to an integral that can handle the Dirichlet function, to sets that can’t be measured, to a ball from which two are assembled, and to a circle cut into a square.
Builds on: 53 · Rigorous analysis
You will learn
- find the Lebesgue measure of simple sets and understand why some sets have measure zero while others can’t be measured
- compute the Lebesgue integral by layers and know when a limit can be taken under the integral sign
- explain what the Banach–Tarski paradox and Laczkovich’s theorem on squaring the circle actually say
2Can you cut a disc into pieces and reassemble them into a square?
The last chapter ended with the Dirichlet function, which has no Riemann integral: every piece of every partition contains both fractions, where it equals one, and irrational numbers, where it equals zero. And yet intuition suggests an answer. The area under the graph is the height $1$ times the “length” of the set of fractions in the segment $[0, 1]$. There are infinitely many fractions, they’re present in every segment, but they can be counted (chapter 52), while the points of the segment can’t. If the set of fractions weighs nothing, the integral is zero.
To turn “weighs nothing” into a theorem, we have to say what the length of an arbitrary set of points is. For a segment the answer is clear, and for a union of several segments too, but not for the set of fractions, Cantor dust, or the set of numbers whose decimal expansion has no sevens. Length was redefined from scratch at the start of the twentieth century, and each step of that work began with a paradox. This chapter is five paradoxes and their resolutions.
The fractions weigh nothing
There are fractions in every segment, however tiny. And yet together they take up less room than any segment.
Write all the fractions of the segment $[0, 1]$ as a sequence: $r_1 = 0$, $r_2 = 1$, $r_3 = \frac12$, $r_4 = \frac13$, $r_5 = \frac23$, $r_6 = \frac14$, $r_7 = \frac34$, …, first those with denominator $1$, then $2$, $3$ and so on, skipping reducible ones. Each fraction gets its own number. Now cover the first fraction with an interval of length $\frac{\varepsilon}{4}$, the second with an interval of length $\frac{\varepsilon}{8}$, the $k$th with length $\frac{\varepsilon}{2^{k+1}}$. All the fractions are covered, and the total length is at most $\frac\varepsilon4 + \frac\varepsilon8 + \ldots = \frac\varepsilon2$. The number $\varepsilon$ can be as small as you like: the fractions fit into a cover of any length, however tiny.
A set $A \subset \mathbb R$ has measure zero if for every $\varepsilon > 0$ it can be covered by a finite or countable collection of intervals with total length less than $\varepsilon$.
Every finite or countable set of points on the line has measure zero.
The trick is to split the budget $\varepsilon$ the way Zeno split a journey: leave half the budget untouched, and of the other half give a half to the first point, a quarter to the second, and so on.
The picture is deceptive. It seems that intervals covering all the fractions must cover the whole segment, since the fractions are everywhere. That’s not so, and the widget lets you see it for yourself.
Not every set has measure zero. If the segment $[0, 1]$ could be covered by intervals of total length $\frac12$, the notion of length would lose its meaning. Intuition says this can’t happen, but intuition has let us down before: the fractions also “fill” the segment. We need a theorem, and it rests on the completeness of the real numbers.
If a segment $[a, b]$ is covered by a finite or countable collection of intervals, their total length is greater than $b - a$.
First choose a finite collection from the infinite one (that’s where completeness is needed), then lay the chosen intervals out in a chain.
Émile Borel proved this in his thesis, defended in 1894; later it became clear that the same argument works for any collections of intervals, not only countable ones. The lemma implies that a segment doesn’t have measure zero, and then it isn’t countable either: otherwise it could be covered by intervals of total length $\frac12$. That’s a new proof of Cantor’s theorem from chapter 52: no diagonal, just length.
Dust with weight and without
The Cantor set has as many points as the whole segment, but its length is zero. And there’s dust that contains no segment at all, yet has length one half.
The Cantor set from chapter 52 is what you get by throwing the middle third out of the segment $[0, 1]$, then the middle third out of each of the two remaining segments, and so on without end. We proved there that it has as many points as the segment, and that the removed intervals together have length $1$.
The Cantor set has measure zero.
After $n$ steps of the construction the Cantor set lies in $2^n$ segments of length $\frac1{3^n}$. Replace each segment by an interval twice as long with the same centre: that’s a cover of total length $2 \cdot \left(\frac23\right)^n$. The Sceptic names $\varepsilon$; the powers of $\frac23$ tend to zero, and for large $n$ this sum is less than $\varepsilon$. For example, for $\varepsilon = 0.01$ the value $n = 14$ will do: $2 \cdot \left(\frac23\right)^{14} \approx 0.0068$.
The Cantor set contains no segment, not even a tiny one: after $n$ steps its pieces are shorter than $\frac1{3^n}$. It might seem that without segments inside, a length can’t be positive. But you can throw out less. Henry Smith in 1875, and later Vito Volterra and Cantor himself, built sets that are made the same way but weigh more.
The fat Cantor set (the Smith–Volterra–Cantor set) is what remains of the segment $[0, 1]$ if at the first step an interval of length $\frac14$ is removed from the middle, and at step $n$ an interval of length $\frac1{4^n}$ is removed from the middle of each of the $2^{n-1}$ remaining segments.
The fat Cantor set contains no segment, and the total length of the intervals removed from $[0, 1]$ is $\frac12$.
First let’s make sure the construction is legitimate: that there’s something to remove from. At step $n$, $2^{n-1}$ intervals of length $\frac1{4^n}$ are removed, $\frac{2^{n-1}}{4^n} = \frac12 \cdot \frac1{2^n}$ in all, and over all steps $\frac12\left(\frac12 + \frac14 + \ldots\right) = \frac12$. So after any number of steps more than half the length remains, divided equally among $2^n$ segments: each is longer than $\frac1{2^{n+1}}$ and all the more longer than the next interval to be removed, $\frac1{4^{n+1}}$. The total removed is $\frac12$: that’s already computed. And after $n$ steps $2^n$ segments of equal length remain, with total length at most $1$, so each is shorter than $\frac1{2^n}$. Any segment of positive length sooner or later is longer than $\frac1{2^n}$ and doesn’t fit into any of the pieces, so the fat Cantor set contains none.
Exactly half the segment has been thrown out, and you want to say the length of what’s left is the other half. But so far it’s only a wish: what’s left isn’t a segment or a union of segments, and we have no rules for subtracting infinitely many intervals. We’ll have to set them up.
Rules for length
If every set of points has a length that doesn’t change under a shift and adds up over countably many pieces, then the length of the segment $[0, 1]$ is both zero and infinity.
In chapter 20 we defined area by rules. Let’s try the same with length. We’d like to assign to each set $A \subset \mathbb R$ a number $\mu(A) \ge 0$ (the Greek letter “mu”, for “measure”) so that: for a segment $[a, b]$ it equals $b - a$; a shifted set has the same length; and the length of a union of non-overlapping pieces is the sum of the lengths of the pieces, not just for two or three pieces but for countably many.
Why only countably many pieces? A segment is the union of its points, each of length zero, yet the segment itself has length one. There are no sums of uncountably many terms, and countable additivity is the strongest requirement that can be made. But even it turns out to be too strong if every set is required to have a length.
There’s no way to assign to every set $A \subset \mathbb R$ a number $\mu(A) \in [0, +\infty]$ such that $\mu([0, 1]) = 1$, the measure doesn’t change under shifts, and it’s countably additive.
The idea: build a set $V$ with countably many shifts that don’t overlap and fit between the segments $[0, 1]$ and $[-1, 2]$. Then $\mu(V)$ can be neither zero nor a positive number.
Call numbers $x$ and $y$ from $[0, 1]$ relatives if $x - y$ is a rational number. This is an equivalence relation (chapter 51), and the segment splits into classes of relatives. By the axiom of choice take exactly one number from each class; call the set of chosen numbers $V$. For each fraction $q \in [-1, 1]$ consider the shift $V + q$.
Shifts by different fractions $q \ne q'$ don’t overlap: if $v + q = v' + q'$ for $v, v' \in V$, then $v - v' = q' - q$ is a fraction, $v$ and $v'$ are relatives, and only one number was taken from each class into $V$; so $v = v'$ and $q = q'$. All the shifts lie in $[-1, 2]$. And together they cover $[0, 1]$: any $x$ in the segment is a relative of some $v \in V$, the difference $x - v$ is a fraction in $[-1, 1]$, and $x$ lies in the corresponding shift.
There are countably many fractions in $[-1, 1]$. By countable additivity and invariance under shifts, the measure of the union of all the shifts is $\mu(V) + \mu(V) + \mu(V) + \ldots$ Additivity also implies monotonicity: if $A \subset B$, then $\mu(B) = \mu(A) + \mu(B \setminus A) \ge \mu(A)$. So $1 = \mu([0, 1]) \le \mu(V) + \mu(V) + \ldots \le \mu([-1, 2]) = 3$. But the sum of infinitely many equal terms is zero if $\mu(V) = 0$ and infinity if $\mu(V) > 0$. Neither lies between $1$ and $3$. A contradiction.
Giuseppe Vitali published this in 1905. The set $V$ can’t be drawn or given by a formula: it picks one representative from each of uncountably many classes, and there’s no rule for the choice; there’s only the axiom of choice, which asserts that such a set exists. In 1970 Robert Solovay showed that without the full axiom of choice a non-measurable set may not exist: there’s a model of set theory in which every set of the line is measurable (provided a theory with a so-called inaccessible cardinal is consistent). So one of the requirements has to be sacrificed, and the one sacrificed is the requirement to measure everything.
The outer measure of a set $A \subset \mathbb R$ is the greatest lower bound of the total lengths over all finite or countable collections of intervals that cover $A$: $\mu^*(A) = \inf \sum_k |I_k|$.
Outer measure is defined for every set, is monotone ($A \subset B \Rightarrow \mu^*(A) \le \mu^*(B)$), doesn’t change under shifts, is countably subadditive, $\mu^*\bigl(\bigcup A_n\bigr) \le \sum \mu^*(A_n)$, and for a segment equals its length.
Monotonicity: every cover of $B$ also covers $A$, so the greatest lower bound for $A$ is taken over a larger collection of covers and is no bigger. Shifts: shifting a cover gives a cover of the shifted set with the same total length. Subadditivity: if $\sum \mu^*(A_n)$ is infinite, there’s nothing to prove. Otherwise, for a tolerance $\varepsilon$, cover each $A_n$ by intervals with total length less than $\mu^*(A_n) + \frac{\varepsilon}{2^n}$; this can be done by the definition of the greatest lower bound. All these intervals together are a countable collection covering the union, and their total length is less than $\sum \mu^*(A_n) + \varepsilon$. Since $\varepsilon$ is arbitrary, $\mu^*\bigl(\bigcup A_n\bigr) \le \sum \mu^*(A_n)$. Finally, the segment $[a, b]$ is covered by one interval $(a - \delta, b + \delta)$ of length $b - a + 2\delta$ for any $\delta > 0$, so $\mu^*([a, b]) \le b - a$; and by Borel’s lemma every cover is longer than $b - a$.
Outer measure can do everything except the main thing: for disjoint sets it doesn’t always add up, and Vitali’s theorem forbids it to. In his 1902 thesis Integral, Length, Area, Henri Lebesgue proposed measuring not all sets but only “good” ones, and showed that there are enough good ones for the whole of analysis.
A set $A$ is Lebesgue measurable if for every $\varepsilon > 0$ it can be enclosed in an open set $U$ (a union of intervals) so that $\mu^*(U \setminus A) < \varepsilon$: the set can be approached from outside by intervals with almost nothing to spare. For measurable sets the outer measure is called the Lebesgue measure and written simply $\mu(A)$.
All intervals and segments are measurable. The complement of a measurable set and the union of countably many measurable sets are measurable. On measurable sets Lebesgue measure is countably additive.
The idea of the proof, and why the whole of it won’t fit here
The hardest step is additivity. For a union of disjoint intervals it follows from Borel’s lemma; for open sets, from the fact that each of them splits into a union of countably many disjoint intervals; and for the other measurable sets, from approximation by open sets from outside, with estimates like the one in the proof of subadditivity. Together with checking that complements and countable unions don’t lead out of the class of measurable sets, this is a few pages of careful work with $\varepsilon$ and covers, with no new ideas. A modern account (following Carathéodory, 1914) can be found in A. N. Kolmogorov and S. V. Fomin’s book Elements of the Theory of Functions and Functional Analysis and in Terence Tao’s An Introduction to Measure Theory (2011).
A family of sets with these properties, closed under complements and countable unions, is called a sigma-algebra, and a countably additive function on it a measure.
A sigma-algebra of subsets of a set $X$ is a family that contains $X$, contains the complement of each of its sets, and contains the union of each countable collection of its sets. A measure on a sigma-algebra is a function $\mu \ge 0$ (the value $+\infty$ is allowed) with $\mu(\varnothing) = 0$ that’s countably additive.
Now the fat Cantor set gets an honest length. Its complement in the segment is the union of the removed intervals, with total length $\frac12$. By additivity $1 = \mu([0, 1]) = \mu(\text{the set}) + \frac12$, and the measure of the fat dust is $\frac12$. The set of fractions has measure $0$, and the set of irrational numbers in the segment measure $1$: almost all numbers are irrational.
A property holds almost everywhere if it holds at all points except a set of measure zero. The Dirichlet function is zero almost everywhere; so is Thomae’s function.
Call a point of the segment $[0, 1]$ “sevenless” if its decimal expansion has no digit $7$. What’s the measure of the set of such points?
After the first digit $9$ segments out of $10$ remain, that is, a share of $\frac{9}{10}$; after the second, $\left(\frac{9}{10}\right)^2$; after the $n$th, $\left(\frac{9}{10}\right)^n$. The set lies in each of these unions of segments, and $0.9^n \to 0$: at $n = 44$ it’s already below $0.01$. The measure is zero, though there are as many points as in the whole segment. It’s a decimal relative of the Cantor set.
Counting by denomination
The Dirichlet function has no integral, and its integral is zero.
The Riemann integral cuts the $x$-axis into pieces and in each piece takes a height at random. If the function darts about within a piece, like the Dirichlet function, the choice of height decides everything, and the sums don’t converge. Lebesgue proposed cutting the axis of values instead. He explained the difference himself like this:
…we would act like a merchant without method who counts coins and notes in the order in which they come to hand. We, however, proceed like the methodical merchant who says: I have $m(E_1)$ coins of one crown, that’s $1 \cdot m(E_1)$; I have $m(E_2)$ coins of two crowns, that’s $2 \cdot m(E_2)$; I have $m(E_5)$ coins of five crowns, that’s $5 \cdot m(E_5)$, and so on. Both ways will lead the merchant to the same result, because however rich he is, he has only finitely many notes. But for us, who have to add up an infinite number of indivisibles, the difference between them is decisive.
The denominations are the values of the function, and the “number of coins” of a given denomination is the measure of the set where the function takes that value. For a function with many values it’s more convenient to count in layers: at each height $t$ take the set $\{x : f(x) > t\}$, where the graph is above the level $t$, and measure it. For such a set to have a measure, not much is asked of the function.
A function $f$ is measurable if the set $\{x : f(x) > t\}$ is measurable for every $t$. Continuous functions are measurable: for them this set is a union of at most countably many intervals. The Dirichlet function is measurable too: its layers are the empty set, the set of fractions, or the whole line. Limits of measurable functions are measurable: if $f_n(x) \to f(x)$ at every point, then $\{f > t\} = \bigcup_{k} \bigcup_{N} \bigcap_{n \ge N} \{f_n > t + \frac1k\}$, countable unions and intersections of measurable sets. In the same way, through layers, one checks that sums, maxima and minima of measurable functions are measurable; from now on we’ll use this without reminders.
The Lebesgue integral of a measurable function $f \ge 0$ is the number $\int f\,d\mu = \int_0^\infty \mu\{f > t\}\,dt$, possibly equal to $+\infty$. A function of any sign is written as a difference $f = f^+ - f^-$ of two non-negative ones (its positive and negative parts), and one puts $\int f\,d\mu = \int f^+ d\mu - \int f^- d\mu$ if both integrals are finite; then $f$ is called Lebesgue integrable.
For ordinary functions the new integral breaks nothing.
If a function $f \ge 0$ is continuous on $[a, b]$, its Lebesgue integral equals its Riemann integral.
For a step function the columns and the layers are the same rectangles, only cut differently. A continuous function we’ll squeeze between step functions.
A function $g$ on the segment $[0, 1]$ equals $x^2$ at irrational points and $5$ at rational ones. Find $\int_0^1 g\,d\mu$.
The function $g$ differs from $x^2$ only on the set of fractions, whose measure is $0$. At any height $t$ the layers of $g$ and $x^2$ differ only by fractions, and their measures are equal. So the integrals are equal: $\int_0^1 x^2\,dx = \frac13$. Changing a function on a set of measure zero doesn’t change its Lebesgue integral. This function has no Riemann integral: the sums with fractions as the chosen points are at least $5$.
You can practise measures of sets and integrals by layers.
A limit under the integral sign
The functions tend to zero at every point, while the areas under them tend to one half.
The running bump from chapter 53: $f_n(x) = n x (1 - x^2)^n$ on $[0, 1]$. At every point $f_n(x) \to 0$, but the area under the graph is $\frac{n}{2(n + 1)}$ and tends to $\frac12$. The limit of the integrals isn’t the integral of the limit. For the Riemann integral there’s another problem as well: a limit of integrable functions can be non-integrable. Let $g_n$ equal one at the first $n$ fractions of the segment and zero at all other points: each $g_n$ has a Riemann integral, equal to zero, but their limit is the Dirichlet function. The Lebesgue integral gets on with limits much better. It all rests on one lemma.
If measurable sets are nested, $A_1 \subset A_2 \subset \ldots$, then $\mu\bigl(\bigcup A_n\bigr) = \lim\limits_{n \to \infty} \mu(A_n)$.
Cut the union into rings: $B_1 = A_1$, $B_n = A_n \setminus A_{n-1}$. The rings don’t overlap, $A_n = B_1 \cup \ldots \cup B_n$, and the union of all the rings is the union of all the $A_n$. By countable additivity $\mu\bigl(\bigcup A_n\bigr) = \sum \mu(B_k)$, and the sum of a series is the limit of its partial sums $\mu(B_1) + \ldots + \mu(B_n) = \mu(A_n)$.
If measurable functions increase, $0 \le f_1 \le f_2 \le \ldots$, and $f_n(x) \to f(x)$ at every point, then $\int f_n\,d\mu \to \int f\,d\mu$.
The idea: as the functions increase, so do their layers, and the lemma on continuity of measure lifts the measures of the layers to the limit.
Fix a height $t$. The layers $\{f_n > t\}$ are nested, because the functions increase, and their union is the layer $\{f > t\}$: if $f(x) > t$, then $f_n(x) > t$ for large $n$, and if $f(x) \le t$, then all $f_n(x) \le f(x) \le t$. By the lemma $\varphi_n(t) = \mu\{f_n > t\}$ increases and tends to $\varphi(t) = \mu\{f > t\}$.
It remains to pass to the limit in the integrals over $t$. The integrals $\int_0^\infty \varphi_n$ increase and are at most $\int_0^\infty \varphi$, so they have a limit $I \le \int \varphi$. Conversely, take $T > 0$ and split $[0, T]$ into $m$ equal pieces with ends $t_j = \frac{jT}{m}$. The function $\varphi_n$ doesn’t increase, so on the $j$th piece it’s at least $\varphi_n(t_j)$, and $\int_0^\infty \varphi_n \ge \sum_{j=1}^m \varphi_n(t_j)\frac Tm$. As $n \to \infty$ the right-hand side, a finite sum, tends to $\sum_{j=1}^m \varphi(t_j)\frac Tm$, and this sum is at least $\int_{T/m}^{T} \varphi$, because $\varphi$ doesn’t increase. We’ve got $I \ge \int_{T/m}^T \varphi$ for all $T$ and $m$, and in the limit $I \ge \int_0^\infty \varphi$. Infinite values are no hindrance here: inequalities involving $+\infty$ read naturally.
The bump is no obstacle to this theorem: its functions don’t increase, they run. The theorem gives the most needed property of the integral, additivity, which the definition by layers doesn’t provide for free.
A simple function is a measurable function with finitely many values: $c_1$ on a set $A_1$, …, $c_k$ on $A_k$. Its layer at height $t$ is the union of those $A_i$ with $c_i > t$, and, as for a step function, $\int s\,d\mu = c_1\mu(A_1) + \ldots + c_k\mu(A_k)$: that’s “counting by denomination”.
For measurable $f, g \ge 0$ we have $\int (f + g)\,d\mu = \int f\,d\mu + \int g\,d\mu$. As a consequence, for measurable $f_k \ge 0$ the integral of a series equals the series of integrals: $\int \sum_k f_k\,d\mu = \sum_k \int f_k\,d\mu$.
For simple functions it’s counting by denomination. If $s$ equals $c_i$ on $A_i$ and $u$ equals $d_j$ on $B_j$, then the sum $s + u$ equals $c_i + d_j$ on the pieces $A_i \cap B_j$, and $\sum_{i,j} (c_i + d_j)\,\mu(A_i \cap B_j) = \sum_i c_i \mu(A_i) + \sum_j d_j \mu(B_j)$, because the measure of $A_i$ is made up of the measures of its pieces $A_i \cap B_j$. Any measurable $f \ge 0$ is the limit of increasing simple functions $s_n = \min\bigl(n,\ \frac{\lfloor 2^n f \rfloor}{2^n}\bigr)$: the values are rounded down to multiples of $\frac{1}{2^n}$ and cut off at height $n$. Take such $s_n \uparrow f$ and $u_n \uparrow g$; then $s_n + u_n \uparrow f + g$, and by the monotone convergence theorem we can pass to the limit in the equation $\int (s_n + u_n) = \int s_n + \int u_n$. For a series: the partial sums increase, the integral of a finite sum is the sum of the integrals, and the monotone convergence theorem works again.
The last statement is exactly what was used in chapter 48 to compute the average number of the walker’s returns: the expectation of a sum of infinitely many non-negative terms equals the sum of their expectations.
For measurable $f_n \ge 0$ we have $\int \liminf\limits_{n \to \infty} f_n\,d\mu \le \liminf\limits_{n \to \infty} \int f_n\,d\mu$.
Here the $\liminf$ of a sequence is the limit of its “lower envelopes”: put $h_k(x) = \inf_{n \ge k} f_n(x)$. The functions $h_k$ increase with $k$, and their limit is by definition $\liminf f_n$. For any $n \ge k$ we have $h_k \le f_n$, and so $\int h_k \le \int f_n$ and $\int h_k \le \inf_{n \ge k} \int f_n$. Pass to the limit as $k \to \infty$: on the left, by the monotone convergence theorem, we get $\int \liminf f_n$; on the right, $\liminf \int f_n$.
Let measurable functions $f_n$ converge to $f$ at every point, and let all of them be bounded in absolute value by one integrable function: $|f_n| \le g$, $\int g\,d\mu < \infty$. Then $\int f_n\,d\mu \to \int f\,d\mu$.
Take the main case $0 \le f_n \le g$; functions of any sign split into positive and negative parts, and the argument is the same for each. Fatou’s lemma for the $f_n$ gives $\int f \le \liminf \int f_n$. Fatou’s lemma for the non-negative functions $g - f_n$, which tend to $g - f$, gives $\int (g - f) \le \liminf \int (g - f_n)$. By the theorem on the integral of a sum $\int (g - f_n) = \int g - \int f_n$ and $\int (g - f) = \int g - \int f$, where $\int g$ is a finite number. Cancelling it, we get $\limsup \int f_n \le \int f$. Together: $\limsup \int f_n \le \int f \le \liminf \int f_n$, so the limit of the integrals exists and equals $\int f$.
Lebesgue proved the theorem in 1908; his 1902 thesis contained the special case for bounded functions. The running bump doesn’t violate it: the smallest function that’s greater than all the $f_n$ at once behaves near zero like $\frac{1}{e x}$, the area under it is infinite, and there’s no integrable dominating function. The condition is shorter and simpler than the uniform convergence of chapter 53, and it works wherever a limit and an integral have to be swapped: in probability theory, in Fourier series, in the Riesz–Fischer theorem on the completeness of the space $L^2$ (chapter 55).
A ball from a ball
A ball can be cut into five pieces and, just by moving and rotating them, reassembled into two balls identical to the first.
Vitali’s theorem showed that non-measurable sets exist. In 1924 Stefan Banach and Alfred Tarski showed what they’re capable of in space. Their construction rests on a remarkable object from algebra: a group that doubles itself.
The free group on two generators $F_2$ is the set of words in the letters $a$, $a^{-1}$, $b$, $b^{-1}$ in which no letter ever stands next to its own inverse, together with the empty word $e$. Multiplication is appending the second word to the first and cancelling neighbouring pairs like $a\,a^{-1}$. For example, $(ab^{-1}a) \cdot (a^{-1}ba) = aa$. It’s a group (chapter 40), and there are no other relations between $a$ and $b$ in it.
Write $W(a)$ for the set of words beginning with the letter $a$; likewise $W(a^{-1})$, $W(b)$, $W(b^{-1})$. Together with the empty word these four pieces make up the whole group.
$F_2 = W(a) \cup a\,W(a^{-1})$ and $F_2 = W(b) \cup b\,W(b^{-1})$. In other words, two of the four pieces, after a shift by multiplication, give the whole group, and the other two give the whole group too.
Draw the group as a tree: a word is a path from the centre, each letter a step in its own direction, and the steps get shorter and shorter. Multiplying by $a$ on the left moves the centre of the tree and blows up one branch.
The rest is a matter of technique, though a sophisticated one. Take two rotations of space by the angle $\arccos\frac13$ about two perpendicular axes. No reduced word in them and their inverses gives the identity rotation, so they generate a copy of the free group. The points of the sphere split into orbits: points that these rotations carry into one another fall into one orbit. The axiom of choice takes one point from each orbit, and the splitting of the group is transferred to the sphere. What remains is to deal with the countable set of points that some rotation leaves fixed, and to pass from the sphere to the ball along radii.
A ball in space can be split into finitely many pieces, and two balls of the same radius can be assembled from them by moving and rotating the pieces.
The idea of the proof, and why the whole of it won’t fit here
The steps are listed above: a free group of rotations, a choice of representatives of the orbits, transferring the splitting to the sphere without fixed points, absorbing the countable set of fixed points, and passing to the ball. Each step needs careful work; for example, the freeness of the group of rotations is proved by examining the rotation matrices modulo $3$. Altogether it’s some fifteen pages. A full account is in Stan Wagon’s book The Banach–Tarski Paradox (1985). Felix Hausdorff in 1914 proved the doubling of the sphere minus a countable set of points, and Banach and Tarski took it all the way to the ball. Raphael Robinson showed in 1947 that five pieces suffice, and four don’t.
Volume doesn’t double in the process: the pieces simply don’t have any. If all five pieces were measurable, their volumes would add up both to one ball and to two, and the volume of the ball would equal twice itself. The paradox doesn’t prove that mathematics is contradictory, but that non-measurable sets inevitably behave wildly: they have no volume that would be preserved under cutting.
In the plane this can’t happen. In 1923 Banach built a function on all subsets of the plane that agrees with area on measurable sets, doesn’t change under rigid motions and adds up over finitely many pieces (though not over countably many). With it, a plane “doubling paradox” is impossible: the area of two discs is twice the area of one, however the pieces are cut. The reason lies in the group of motions of the plane: it’s too close to commutative (solvable) and contains no free subgroup on two generators.
The circle and the square
A disc can’t be cut with scissors and reassembled into a square. But it can be cut into pieces and reassembled into a square by translations alone.
In chapter 20 we proved that a disc doesn’t turn into a square by straight cuts, and learned that cuts along any curves won’t help either (Dubins, Hirsch and Karush, 1963). In chapter 6 and chapter 43, that a square of the same area can’t be constructed with compass and straightedge. One last option remained, proposed by Tarski in 1925: allow pieces that are arbitrary sets of points, as long as there are finitely many of them, and allow them to be moved. Are a disc and a square of equal area equidecomposable in this broad sense?
The plane, unlike space, doesn’t allow two discs to be made from one: Banach’s measure forbids it. So the question could only be about figures of equal area, and there was still a chance. For sixty-five years the problem resisted.
The final answer: yes, it can be done. In 1990 the Hungarian mathematician Miklós Laczkovich proved that a disc can be cut into finitely many pieces and a square of the same area assembled from them, and the pieces don’t even need to be rotated, only translated. There are about $10^{50}$ pieces, and the proof relies on the axiom of choice, so the pieces exist but can’t be drawn, and nothing is known about their measurability in this proof. Area isn’t violated: the areas of the disc and the square are equal, and there’s no doubling in the plane. With scissors, or with compass and straightedge, it can’t be done; with “clouds of points”, it can.
The story didn’t end there. In 2017 Łukasz Grabowski, András Máthé and Oleg Pikhurko proved that the pieces can be made measurable, and then the areas of the pieces literally add up to the area of the square. In the same year Andrew Marks and Spencer Unger managed without the axiom of choice: their pieces are Borel sets, which can be described explicitly, though about $10^{200}$ pieces were needed. In a paper of 2022 (published in 2026) Máthé, Jonathan Noel and Pikhurko obtained pieces whose boundaries have zero area. They still can’t be cut out, as the 1963 theorem forbids, but they no longer look anything like Vitali’s indescribable clouds.
What does the Banach–Tarski paradox actually prove?
If all sets had a volume, additive at least over finitely many pieces and unchanged by motions, then splitting the ball into five pieces would show that the volume of the ball equals twice itself. So there’s no such volume in space, and non-measurable sets are the price of the axiom of choice. On the plane and the line such a volume exists (Banach, 1923), and there’s no paradox there.
Probability is a measure
A random point of a segment is bound to land somewhere, even though the probability of landing on any given point is zero.
In 1933 Andrey Kolmogorov, in his book Foundations of the Theory of Probability, put probability theory on the foundation of measure theory. Outcomes are the points of a set $\Omega$, events are sets from a sigma-algebra, and probability is a measure $P$ with $P(\Omega) = 1$. Kolmogorov’s third axiom is countable additivity (chapter 47), and without it you can’t build probability even for an infinite series of coin tosses.
Here’s how it’s built. Toss a fair coin infinitely many times and write heads as $1$ and tails as $0$. The result is the infinite binary expansion of some number $x = 0.x_1x_2x_3\ldots_2$ in the segment $[0, 1]$. Dyadic rationals like $\frac12 = 0.1000\ldots_2 = 0.0111\ldots_2$ have two expansions, but there are countably many such numbers, and this has no effect on the probabilities. All the outcomes in which the first $n$ tosses are fixed correspond to a dyadic segment of length $\frac1{2^n}$, and their probability is exactly $\frac1{2^n}$. So the probability of any event described by the tosses is the Lebesgue measure of the corresponding set of numbers, and all its properties, including countable additivity, come for free. A random series of tosses is the same thing as a random point of the segment.
The paradox is resolved by additivity: the probability of landing on a point is zero, but there are uncountably many points, and their probabilities can’t be added up. The probability of landing on a fraction is zero: the fractions have measure zero. Events of probability $1$ are said to happen almost surely. In 1909 Émile Borel proved that almost every number in the segment is normal: in its expansion in any base, all the digits and all blocks of digits occur with the same frequency. In terms of the coin this is the law of large numbers: the share of heads almost surely tends to $\frac12$. And yet normality hasn’t been proved for a single “famous” number, $\sqrt2$, $\pi$ or $e$; explicit normal numbers have to be built on purpose, like David Champernowne’s $0.123456789101112\ldots$ (1933).
A point is chosen at random, uniformly, on the segment $[0, 1]$. With what probability does it land in the fat Cantor set?
Probability is a measure. The measure of the fat Cantor set is $1 - \frac12 = \frac12$: intervals of total length $\frac12$ have been removed from the segment. So the probability is $\frac12$, even though the set contains no segment. For the ordinary Cantor set the answer would be $0$.
Where next
Lebesgue gave us an integral that gets on with limits: functions that converge almost everywhere and stay under one integrable dominating function carry the limit under the integral sign. He also suggested a new way to look at functions. If two functions agree almost everywhere, their integrals are the same, and there’s no point telling them apart: they can be regarded as the same point. The distance between such points is the area between the graphs, $\int |f - g|\,d\mu$, or $\sqrt{\int (f - g)^2\,d\mu}$ if you want Pythagoras’ theorem. The result is a space with infinitely many dimensions in which sequences that “converge in themselves” have limits, precisely thanks to the theorems of this chapter. Can you work with functions as with vectors: measure angles, project, expand in a basis? That’s chapter 55.