Borel sets, Cantor sets and non-measurable sets

Lesson 3 produced Lebesgue measure on a σ-algebra that contains every Borel set. This lesson explores the landscape of measurable sets. We start with the Cantor set, the most important example in the subject: an uncountable set of measure zero, compact and nowhere dense. Varying its construction gives fat Cantor sets, nowhere dense yet of positive measure. The Cantor function built on the Cantor set is continuous, increasing and constant almost everywhere, and it lets us show that there are Lebesgue measurable sets that are not Borel. Finally we prove Vitali's theorem: there is a subset of the line that is not Lebesgue measurable at all, so the restriction to a σ-algebra in lesson 2 was unavoidable.

The Cantor set

Start with \(C_0 = [0, 1]\). Remove the open middle third \((\frac{1}{3}, \frac{2}{3})\) to get \(C_1 = [0, \frac{1}{3}] \cup [\frac{2}{3}, 1]\). From each of the two remaining intervals remove its open middle third, leaving \(C_2\), a union of four intervals of length \(\frac{1}{9}\). Continuing, \(C_n\) is a union of \(2^n\) disjoint closed intervals of length \(3^{-n}\). The Cantor set is \(C = \bigcap_{n=0}^{\infty} C_n\).

Properties. (a) \(C\) is closed, as an intersection of closed sets, and bounded, hence compact. (b) \(m(C) = 0\): since \(C \subseteq C_n\), \(m(C) \le m(C_n) = \big(\frac{2}{3}\big)^n \to 0\). Equivalently, the removed intervals have total length \(\sum_{n=1}^{\infty} 2^{n-1} 3^{-n} = 1\). (c) \(C\) is nowhere dense: it contains no interval, since any interval of length \(\delta > 0\) is longer than the components of \(C_n\) once \(3^{-n} < \delta\). (d) \(C\) has no isolated points, since every point of \(C\) is an endpoint limit of intervals of \(C_n\).

(e) \(C\) is uncountable. Every \(x \in [0, 1]\) has a ternary expansion \(x = \sum_{k=1}^{\infty} a_k 3^{-k}\) with digits \(a_k \in \{0, 1, 2\}\). Removing the middle third at stage \(k\) removes exactly the points whose \(k\)th digit must be \(1\). One checks that \(C\) is precisely the set of numbers having a ternary expansion with no digit \(1\); for example \(\frac{1}{3} = 0.1000\ldots_3 = 0.0222\ldots_3\) is in \(C\) through its second expansion. The map \(\sum a_k 3^{-k} \mapsto (a_1/2, a_2/2, \ldots)\) is a bijection from \(C\) onto the set of all infinite binary sequences, which is uncountable by Cantor's diagonal argument. In fact \(C\) has the same cardinality as \([0, 1]\).

So a set can be as large as the whole interval in cardinality and yet have measure zero. Measure zero means negligible for integration, not small in the sense of counting. Since every subset of a null set is Lebesgue measurable, every one of the \(2^{\mathfrak{c}}\) subsets of \(C\) is Lebesgue measurable, where \(\mathfrak{c}\) is the cardinality of the continuum. By contrast there are only \(\mathfrak{c}\) Borel sets, a fact we accept from set theory. Hence most subsets of \(C\) are Lebesgue measurable but not Borel. Below we exhibit such a set more concretely.

Fat Cantor sets

Change the construction so that less is removed. At stage \(n\), remove from the middle of each of the \(2^{n-1}\) remaining intervals an open interval of length \(4^{-n}\) (the first removal is \((\frac{3}{8}, \frac{5}{8})\)). One checks inductively that each removed interval fits inside the interval it is taken from. The total length removed is \(\sum_{n=1}^{\infty} 2^{n-1} 4^{-n} = \frac{1}{2}\), so the resulting set \(S\), often called the Smith–Volterra–Cantor set, has measure \(\frac{1}{2}\). Like \(C\) it is closed, uncountable and has no isolated points. It is also nowhere dense: the remaining intervals at stage \(n\) have length less than \(2^{-n}\), so \(S\) contains no interval.

A fat Cantor set is a closed set with empty interior and positive measure. Its complement is a dense open set of measure \(\frac{1}{2}\) in \([0, 1]\). Thus a dense open subset of \([0, 1]\) need not have full measure, and its indicator function, discontinuous on \(S\), is the example of lesson 1 of a function that is not Riemann integrable although it is the \(L^1\) limit of step functions. By removing intervals of lengths \(\alpha 4^{-n}\) with \(0 < \alpha \le 1\) one obtains nowhere dense sets of measure \(1 - \frac{\alpha}{2}\), so a nowhere dense set can have measure as close to \(1\) as we like.

The Cantor function

Define \(c : [0, 1] \to [0, 1]\) first on \(C\): if \(x = \sum a_k 3^{-k}\) with all \(a_k \in \{0, 2\}\), put \(c(x) = \sum \frac{a_k}{2} 2^{-k}\), reading the ternary digits as binary digits. The two endpoints of each removed interval have the same image; for instance \(\frac{1}{3} = 0.0222\ldots_3\) and \(\frac{2}{3} = 0.2000\ldots_3\) both map to \(0.0111\ldots_2 = 0.1000\ldots_2 = \frac{1}{2}\). Extend \(c\) to each removed interval as the constant equal to its value at the endpoints. The result is the Cantor function, also called the devil's staircase.

Properties. The function \(c\) is nondecreasing and surjective onto \([0, 1]\), since every binary expansion arises. A nondecreasing function whose image is an interval cannot jump, so \(c\) is continuous. It is constant on each removed interval, so \(c^\prime(x) = 0\) for all \(x\) outside \(C\), that is, almost everywhere. Yet \(c(1) - c(0) = 1\). The fundamental theorem of calculus in the form \(c(1) - c(0) = \int_0^1 c^\prime\) fails, although \(c\) is continuous and differentiable almost everywhere. The capstone lesson identifies the missing hypothesis: absolute continuity.

The Cantor function also defines a measure. Since \(c\) is nondecreasing and continuous, the Lebesgue–Stieltjes construction of lesson 3 gives a probability measure \(\mu_c\) with \(\mu_c((a, b]) = c(b) - c(a)\). It assigns measure zero to each removed interval and to each point, so it lives entirely on the Lebesgue null set \(C\). Measures of this kind, with no atoms but concentrated on a set of Lebesgue measure zero, are called singular continuous; they reappear in the Lebesgue decomposition of lesson 12.

A Lebesgue measurable set that is not Borel

Let \(h(x) = x + c(x)\) on \([0, 1]\). It is continuous and strictly increasing from \(h(0) = 0\) to \(h(1) = 2\), so it is a homeomorphism of \([0, 1]\) onto \([0, 2]\), and images and preimages of Borel sets under \(h\) are Borel. On each removed interval \(I\), \(c\) is constant, so \(h(I)\) is a translate of \(I\), with the same length. The removed intervals have total length \(1\), so their images have total length \(1\), and therefore \(m(h(C)) = 2 - 1 = 1\).

The homeomorphism \(h\) has transformed a set of measure zero into a set of measure one. Now take a non-measurable set \(V \subseteq h(C)\); Vitali's theorem below provides one, since every set of positive measure contains a non-measurable subset. The set \(A = h^{-1}(V)\) lies inside \(C\), so it is a Lebesgue null set and in particular Lebesgue measurable. If \(A\) were Borel, then \(V = h(A)\) would be Borel, hence measurable, which it is not. So \(A\) is Lebesgue measurable but not Borel. The example also shows that a homeomorphism can map a measurable set to a non-measurable one; measurability is not a topological property.

Vitali's non-measurable set

Theorem 4.1 (Vitali, 1905). There is a subset of \([0, 1)\) that is not Lebesgue measurable.

Proof. Define an equivalence relation on \([0, 1)\) by \(x \sim y\) when \(x - y \in \mathbb{Q}\). Each equivalence class is a countable set \(x + \mathbb{Q}\) intersected with \([0, 1)\), and the classes partition \([0, 1)\). By the axiom of choice, there is a set \(V \subseteq [0, 1)\) containing exactly one point from each class.

For each rational \(r \in [0, 1)\) define the translate modulo one, \(V_r = \{x + r : x \in V, x + r < 1\} \cup \{x + r - 1 : x \in V, x + r \ge 1\}\). Two facts follow from the choice of \(V\). The sets \(V_r\) are pairwise disjoint: if \(y \in V_r \cap V_s\), then \(y - r\) and \(y - s\) are points of \(V\) up to integers, differing by a rational, so they lie in the same class, hence are equal, which forces \(r = s\). And their union is \([0, 1)\): every \(y \in [0, 1)\) is equivalent to some \(x \in V\), and \(y - x\), reduced modulo one, is a rational \(r\) with \(y \in V_r\).

Suppose \(V\) were measurable. Each \(V_r\) is made of two translates of measurable pieces of \(V\), so it is measurable with \(m(V_r) = m(V)\) by translation invariance. Countable additivity over the countably many rationals in \([0, 1)\) gives \[1 = m([0, 1)) = \sum_{r \in \mathbb{Q} \cap [0, 1)} m(V_r) = \sum_{r} m(V).\] A countable sum of equal terms is either \(0\) or \(\infty\), never \(1\). This contradiction shows \(V\) is not measurable. \(\blacksquare\)

Refinements. The same argument, applied to the intersections \(E \cap V_r\), shows that every set \(E\) of positive outer measure contains a non-measurable subset; this is the fact used in the previous section. The argument also proves that outer measure is not additive on all disjoint sets: if it were, the \(V_r\) would give the same contradiction. In three dimensions, the Banach–Tarski paradox of 1924 goes further: a solid ball can be cut into finitely many pieces that can be moved by rotations and translations and reassembled into two balls of the same size. The pieces are necessarily non-measurable.

The axiom of choice is essential. Robert Solovay showed in 1970 that, assuming the consistency of an inaccessible cardinal, there is a model of set theory without the full axiom of choice (but with countable dependent choice, enough for analysis) in which every subset of the line is Lebesgue measurable. So no explicit construction of a non-measurable set is possible; every example must invoke choice in some form. In practice this means that every set and function you will meet in applications is measurable, and the σ-algebra bookkeeping, though necessary for the logic, rarely obstructs a calculation.

# The Cantor set: remaining length, ternary membership, and the Cantor function.
from fractions import Fraction as F

def remaining(n, removed):
    """Length left after n stages when stage k removes removed(k) from each of 2^(k-1) intervals."""
    return 1 - sum(2 ** (k - 1) * removed(k) for k in range(1, n + 1))

for n in (1, 5, 20, 60):
    print(f"stage {n:2d}: middle-thirds left {float(remaining(n, lambda k: F(1, 3 ** k))):.3e}"
          f"   fat Cantor left {float(remaining(n, lambda k: F(1, 4 ** k))):.6f}")

def in_cantor(x, depth=40):
    """Test a Fraction x in [0, 1]: can its ternary digits avoid 1 for depth steps?"""
    for _ in range(depth):
        x *= 3
        d = int(x)
        if d == 1 and x != 1:
            return False
        if x == 1:          # 0.1000... equals 0.0222..., inside the set
            return True
        x -= d
    return True

for x in (F(1, 4), F(3, 4), F(1, 2), F(1, 3), F(1, 10)):
    print("x =", x, "in C:", in_cantor(x))

def cantor_fn(x, depth=50):
    """Cantor function: read ternary digits until the first 1, mapping 2 -> 1 in binary."""
    total, scale = F(0), F(1, 2)
    for _ in range(depth):
        x *= 3
        d = int(x)
        x -= d
        if d == 1:
            return float(total + scale)
        total += scale * (d // 2)
        scale /= 2
    return float(total)

print("c(1/4) =", round(cantor_fn(F(1, 4)), 6), " c(1/3) =", cantor_fn(F(1, 3)), " c(1/2) =", cantor_fn(F(1, 2)))

stage  1: middle-thirds left 6.667e-01   fat Cantor left 0.750000
stage  5: middle-thirds left 1.317e-01   fat Cantor left 0.515625
stage 20: middle-thirds left 3.007e-04   fat Cantor left 0.500000
stage 60: middle-thirds left 2.720e-11   fat Cantor left 0.500000
x = 1/4 in C: True
x = 3/4 in C: True
x = 1/2 in C: False
x = 1/3 in C: True
x = 1/10 in C: True
c(1/4) = 0.333333  c(1/3) = 0.5  c(1/2) = 0.5

The point \(\frac{1}{4} = 0.020202\ldots_3\) is in the Cantor set though it is not an endpoint of any removed interval, and the Cantor function sends it to \(0.0101\ldots_2 = \frac{1}{3}\). This illustrates that the Cantor set contains far more than the countably many endpoints of its construction, consistent with its uncountability.

A map of the measurable world

The picture that emerges has several layers. Intervals generate the Borel sets by countable operations; every set describable by an explicit countable procedure is Borel. Adding all subsets of Borel null sets gives the Lebesgue measurable sets, a strictly larger σ-algebra. Outside it lie the non-measurable sets, whose existence depends on the axiom of choice. For analysis, Borel sets suffice for defining measurable functions and integrals, while completeness of Lebesgue measure is convenient because it lets us ignore what happens on null sets without checking measurability. The theorems in the rest of the course hold for either choice of σ-algebra, with small adjustments that we will point out when they matter, notably for product measures in lesson 10.