You are currently browsing the tag archive for the ‘axiom of choice’ tag.

In the prologue for this course, we recalled the classical theory of Jordan measure on Euclidean spaces ${{\bf R}^d}$. This theory proceeded in the following stages:

1. First, one defined the notion of a box ${B}$ and its volume ${|B|}$.
2. Using this, one defined the notion of an elementary set ${E}$ (a finite union of boxes), and defines the elementary measure ${m(E)}$ of such sets.
3. From this, one defined the inner and outer Jordan measures ${m_{*,(J)}(E), m^{*,(J)}(E)}$ of an arbitrary bounded set ${E \subset {\bf R}^d}$. If those measures match, we say that ${E}$ is Jordan measurable, and call ${m(E) = m_{*,(J)}(E) = m^{*,(J)}(E)}$ the Jordan measure of ${E}$.

As long as one is lucky enough to only have to deal with Jordan measurable sets, the theory of Jordan measure works well enough. However, as noted previously, not all sets are Jordan measurable, even if one restricts attention to bounded sets. In fact, we shall see later in these notes that there even exist bounded open sets, or compact sets, which are not Jordan measurable, so the Jordan theory does not cover many classes of sets of interest. Another class that it fails to cover is countable unions or intersections of sets that are already known to be measurable:

Exercise 1 Show that the countable union ${\bigcup_{n=1}^\infty E_n}$ or countable intersection ${\bigcap_{n=1}^\infty E_n}$ of Jordan measurable sets ${E_1, E_2, \ldots \subset {\bf R}}$ need not be Jordan measurable, even when bounded.

This creates problems with Riemann integrability (which, as we saw in the preceding notes, was closely related to Jordan measure) and pointwise limits:

Exercise 2 Give an example of a sequence of uniformly bounded, Riemann integrable functions ${f_n: [0,1] \rightarrow {\bf R}}$ for ${n=1,2,\ldots}$ that converge pointwise to a bounded function ${f: [0,1] \rightarrow {\bf R}}$ that is not Riemann integrable. What happens if we replace pointwise convergence with uniform convergence?

These issues can be rectified by using a more powerful notion of measure than Jordan measure, namely Lebesgue measure. To define this measure, we first tinker with the notion of the Jordan outer measure

$\displaystyle m^{*,(J)}(E) := \inf_{B \supset E; B \hbox{ elementary}} m(B)$

of a set ${E \subset {\bf R}^d}$ (we adopt the convention that ${m^{*,(J)}(E) = +\infty}$ if ${E}$ is unbounded, thus ${m^{*,(J)}}$ now takes values in the extended non-negative reals ${[0,+\infty]}$, whose properties we will briefly review below). Observe from the finite additivity and subadditivity of elementary measure that we can also write the Jordan outer measure as

$\displaystyle m^{*,(J)}(E) := \inf_{B_1 \cup \ldots \cup B_k \supset E; B_1,\ldots, B_k \hbox{ boxes}} |B_1| + \ldots + |B_k|,$

i.e. the Jordan outer measure is the infimal cost required to cover ${E}$ by a finite union of boxes. (The natural number ${k}$ is allowed to vary freely in the above infimum.) We now modify this by replacing the finite union of boxes by a countable union of boxes, leading to the Lebesgue outer measure ${m^*(E)}$ of ${E}$:

$\displaystyle m^*(E) := \inf_{\bigcup_{n=1}^\infty B_n \supset E; B_1, B_2, \ldots \hbox{ boxes}} \sum_{n=1}^\infty |B_n|,$

thus the Lebesgue outer measure is the infimal cost required to cover ${E}$ by a countable union of boxes. Note that the countable sum ${\sum_{n=1}^\infty |B_n|}$ may be infinite, and so the Lebesgue outer measure ${m^*(E)}$ could well equal ${+\infty}$.

(Caution: the Lebesgue outer measure ${m^*(E)}$ is sometimes denoted ${m_*(E)}$; this is for instance the case in Stein-Shakarchi.)

Clearly, we always have ${m^*(E) \leq m^{*,(J)}(E)}$ (since we can always pad out a finite union of boxes into an infinite union by adding an infinite number of empty boxes). But ${m^*(E)}$ can be a lot smaller:

Example 1 Let ${E = \{ x_1, x_2, x_3, \ldots \} \subset {\bf R}^d}$ be a countable set. We know that the Jordan outer measure of ${E}$ can be quite large; for instance, in one dimension, ${m^{*,(J)}({\bf Q})}$ is infinite, and ${m^{*,(J)}({\bf Q} \cap [-R,R]) = m^{*,(J)}([-R,R]) = 2R}$ since ${{\bf Q} \cap [-R,R]}$ has ${[-R,R]}$ as its closure (see Exercise 18 of the prologue). On the other hand, all countable sets ${E}$ have Lebesgue outer measure zero. Indeed, one simply covers ${E}$ by the degenerate boxes ${\{x_1\}, \{x_2\}, \ldots}$ of sidelength and volume zero.

Alternatively, if one does not like degenerate boxes, one can cover each ${x_n}$ by a cube ${B_n}$ of sidelength ${\epsilon/2^n}$ (say) for some arbitrary ${\epsilon > 0}$, leading to a total cost of ${\sum_{n=1}^\infty (\epsilon/2^n)^d}$, which converges to ${C_d \epsilon^d}$ for some absolute constant ${C_d}$. As ${\epsilon}$ can be arbitrarily small, we see that the Lebesgue outer measure must be zero. We will refer to this type of trick as the ${\epsilon/2^n}$ trick; it will be used many further times in this course.

From this example we see in particular that a set may be unbounded while still having Lebesgue outer measure zero, in contrast to Jordan outer measure.

As we shall see later in this course, Lebesgue outer measure (also known as Lebesgue exterior measure) is a special case of a more general concept known as an outer measure.

In analogy with the Jordan theory, we would also like to define a concept of “Lebesgue inner measure” to complement that of outer measure. Here, there is an asymmetry (which ultimately arises from the fact that elementary measure is subadditive rather than superadditive): one does not gain any increase in power in the Jordan inner measure by replacing finite unions of boxes with countable ones. But one can get a sort of Lebesgue inner measure by taking complements; see Exercise 18. This leads to one possible definition for Lebesgue measurability, namely the Carathéodory criterion for Lebesgue measurability, see Exercise 17. However, this is not the most intuitive formulation of this concept to work with, and we will instead use a different (but logically equivalent) definition of Lebesgue measurability. The starting point is the observation (see Exercise 5 of the prologue) that Jordan measurable sets can be efficiently contained in elementary sets, with an error that has small Jordan outer measure. In a similar vein, we will define Lebesgue measurable sets to be sets that can be efficiently contained in open sets, with an error that has small Lebesgue outer measure:

Definition 1 (Lebesgue measurability) A set ${E \subset {\bf R}^d}$ is said to be Lebesgue measurable if, for every ${\epsilon > 0}$, there exists an open set ${U \subset {\bf R}^d}$ containing ${E}$ such that ${m^*(U \backslash E) \leq \epsilon}$. If ${E}$ is Lebesgue measurable, we refer to ${m(E) := m^*(E)}$ as the Lebesgue measure of ${E}$ (note that this quantity may be equal to ${+\infty}$). We also write ${m(E)}$ as ${m^d(E)}$ when we wish to emphasise the dimension ${d}$.

(The intuition that measurable sets are almost open is also known as Littlewood’s first principle, this principle is a triviality with our current choice of definitions, though less so if one uses other, equivalent, definitions of Lebesgue measurability.)

As we shall see later, Lebesgue measure extends Jordan measure, in the sense that every Jordan measurable set is Lebesgue measurable, and the Lebesgue measure and Jordan measure of a Jordan measurable set are always equal. We will also see a few other equivalent descriptions of the concept of Lebesgue measurability.

In the notes below we will establish the basic properties of Lebesgue measure. Broadly speaking, this concept obeys all the intuitive properties one would ask of measure, so long as one restricts attention to countable operations rather than uncountable ones, and as long as one restricts attention to Lebesgue measurable sets. The latter is not a serious restriction in practice, as almost every set one actually encounters in analysis will be measurable (the main exceptions being some pathological sets that are constructed using the axiom of choice). In the next set of notes we will use Lebesgue measure to set up the Lebesgue integral, which extends the Riemann integral in the same way that Lebesgue measure extends Jordan measure; and the many pleasant properties of Lebesgue measure will be reflected in analogous pleasant properties of the Lebesgue integral (most notably the convergence theorems).

We will treat all dimensions ${d=1,2,\ldots}$ equally here, but for the purposes of drawing pictures, we recommend to the reader that one sets ${d}$ equal to ${2}$. However, for this topic at least, no additional mathematical difficulties will be encountered in the higher-dimensional case (though of course there are significant visual difficulties once ${d}$ exceeds ${3}$).

The material here is based on Sections 1.1-1.3 of the Stein-Shakarchi text, though it is arranged somewhat differently.

Notational convention: As in Notes 2, I will colour a statement red in this post if it assumes the axiom of choice.  We will, of course, rely on every other axiom of Zermelo-Frankel set theory here (and in the rest of the course).  $\diamond$

In this course we will often need to iterate some sort of operation “infinitely many times” (e.g. to create a infinite basis by choosing one basis element at a time).  In order to do this rigorously, we will rely on Zorn’s lemma:

Zorn’s Lemma. Let $(X, \leq)$ be a non-empty partially ordered set, with the property that every chain (i.e. a totally ordered set) in X has an upper bound.  Then X contains a maximal element (i.e. an element with no larger element).

Indeed, we have used this lemma several times already in previous notes.  Given the other standard axioms of set theory, this lemma is logically equivalent to

Axiom of choice. Let X be a set, and let ${\mathcal F}$ be a collection of non-empty subsets of X.  Then there exists a choice function $f: {\mathcal F} \to X$, i.e. a function such that $f(A) \in A$ for all $A \in {\mathcal F}$.

One implication is easy:

Proof of axiom of choice using Zorn’s lemma. Define a partial choice function to be a pair $({\mathcal F}', f')$, where ${\mathcal F}'$ is a subset of ${\mathcal F}$ and $f': {\mathcal F}' \to X$ is a choice function for ${\mathcal F'}$.  We can partially order the collection of partial choice functions by writing $({\mathcal F}', f') \leq ({\mathcal F}'', f'')$ if ${\mathcal F}' \subset {\mathcal F}''$ and f” extends f’.  The collection of partial choice functions is non-empty (since it contains the pair $(\emptyset, ())$ consisting of the empty set and the empty function), and it is easy to see that any chain of partial choice functions has an upper bound (formed by gluing all the partial choices together).  Hence, by Zorn’s lemma, there is a maximal partial choice function $({\mathcal F}_*, f_*)$.  But the domain ${\mathcal F}_*$ of this function must be all of ${\mathcal F}$, since otherwise one could enlarge ${\mathcal F}_*$ by a single set A and extend $f_*$ to A by choosing a single element of A.  (One does not need the axiom of choice to make a single choice, or finitely many choices; it is only when making infinitely many choices that the axiom becomes necessary.)  The claim follows. $\Box$

In the rest of these notes I would like to supply the reverse implication, using the machinery of well-ordered sets.  Instead of giving the shortest or slickest proof of Zorn’s lemma here, I would like to take the opportunity to place the lemma in the context of several related topics, such as ordinals and transfinite induction, noting that much of this material is in fact independent of the axiom of choice.  The material here is standard, but for the purposes of this course one may simply take Zorn’s lemma as a “black box” and not worry about the proof, so this material is optional.

Notational convention: In this post only, I will colour a statement red if it assumes the axiom of choice. (For the rest of the course, the axiom of choice will be implicitly assumed throughout.) $\diamond$

The famous Banach-Tarski paradox asserts that one can take the unit ball in three dimensions, divide it up into finitely many pieces, and then translate and rotate each piece so that their union is now two disjoint unit balls.  As a consequence of this paradox, it is not possible to create a finitely additive measure on ${\Bbb R}^3$ that is both translation and rotation invariant, which can measure every subset of ${\Bbb R}^3$, and which gives the unit ball a non-zero measure. This paradox helps explain why Lebesgue measure (which is countably additive and both translation and rotation invariant, and gives the unit ball a non-zero measure) cannot measure every set, instead being restricted to measuring sets that are Lebesgue measurable.

On the other hand, it is not possible to replicate the Banach-Tarski paradox in one or two dimensions; the unit interval in ${\Bbb R}$ or unit disk in ${\Bbb R}^2$ cannot be rearranged into two unit intervals or two unit disks using only finitely many pieces, translations, and rotations, and indeed there do exist non-trivial finitely additive measures on these spaces. However, it is possible to obtain a Banach-Tarski type paradox in one or two dimensions using countably many such pieces; this rules out the possibility of extending Lebesgue measure to a countably additive translation invariant measure on all subsets of ${\Bbb R}$ (or any higher-dimensional space).

In these notes I would like to establish all of the above results, and tie them in with some important concepts and tools in modern group theory, most notably amenability and the ping-pong lemma.  This material is not required for the rest of the course, but nevertheless has some independent interest.