Non Measurable Sets and the Cost of Choice

For the forward implication, assume $E$ is Lebesgue measurable and fix a real $\epsilon >0$. By [L1] choose a closed $F\subseteq E$ with ${\lambda }^{\ast }(E\setminus F)<\epsilon$; since $E$ is bounded, so is $F$, hence [L3] makes $F$ compact. The set $F$ is Borel and therefore measurable by [L4], so $\lambda (F)\le {\lambda }_{\ast }(E)\le {\lambda }^{\ast }(E)$ by [F1]; and $E=F\bigsqcup (E\setminus F)$ with both pieces measurable by [L4] and [L5], so ${\lambda }^{\ast }(E)=\lambda (E)=\lambda (F)+\lambda (E\setminus F)<{\lambda }_{\ast }(E)+\epsilon$. As $\epsilon >0$ was arbitrary, ${\lambda }^{\ast }(E)\le {\lambda }_{\ast }(E)$; together with ${\lambda }_{\ast }(E)\le {\lambda }^{\ast }(E)$ from [F1], this gives ${\lambda }_{\ast }(E)={\lambda }^{\ast }(E)$.

For the converse implication, assume ${\lambda }_{\ast }(E)={\lambda }^{\ast }(E)$ and fix a real $\epsilon >0$. By [F1] choose a compact $K\subseteq E$ with $\lambda (K)>{\lambda }_{\ast }(E)-\epsilon \mathrm{/}2$, and by [L2] choose an open $U\supseteq E$ with $\lambda (U)<{\lambda }^{\ast }(E)+\epsilon \mathrm{/}2$. The compact set $K$ is Borel by [L3], hence measurable by [L4], and $K\subseteq E\subseteq U$; therefore $U\setminus E\subseteq U\setminus K$, so [L5] gives ${\lambda }^{\ast }(U\setminus E)\le \lambda (U\setminus K)=\lambda (U)-\lambda (K)<{\lambda }^{\ast }(E)-{\lambda }_{\ast }(E)+\epsilon =\epsilon$.

Step 1.2 gives open supersets of arbitrarily small outer excess, so [L1] makes $E$ Lebesgue measurable. This is the reverse implication.

Let $\mathcal{F}$ be the family of all sets of the form $(x+\mathbb{Q})\cap [0,1]$ with $x\in [0,1]$. Each member of $\mathcal{F}$ is nonempty because it contains its defining point, and distinct members are exactly the equivalence classes of the relation in [F1].

By [A1] and [F2] there is a choice function $g$ on $\mathcal{F}$. Put $V:=\{g(S):S\in \mathcal{F}\}\subseteq [0,1]$. Then $V$ meets every member of $\mathcal{F}$, and it meets each of them in exactly one point because $g$ assigns one value to each set in its domain.

Since the members of $\mathcal{F}$ are exactly the equivalence classes of $x\sim y⟺x-y\in \mathbb{Q}$ on $[0,1]$, step 2.1 says precisely that $V$ is a Vitali set on $[0,1]$.

AC supplies countable choice: for a sequence of nonempty sets $(X_n)$, apply AC to $\{X_n:n\in \mathbb{N}\}$ and put $f(n)=g(X_n)$ for its choice function $g$. Thus [L7] and the countable-choice hypotheses in [L2] and [L3] apply. Finite additivity follows from [L5] by padding with empty sets; monotonicity follows by writing a measurable $B\supseteq A$ as $A\bigsqcup (B\setminus A)$.

Take a repetition-free enumeration of $\mathbb{Q}$ from [L4] and retain its terms in $[-1,1]$ in their original order, obtaining $(q_k{)}_{k\in \mathbb{N}}$. There are infinitely many retained terms, since $1\mathrm{/}(j+1)$ are distinct members for $j\in \mathbb{N}$; taking successive least retained indices requires no choice. The translates $V+q_k$ are pairwise disjoint: an equality $v_1+q_i=v_2+q_j$ gives $v_1-v_2\in \mathbb{Q}$, so [L1] gives $v_1=v_2$ and then $i=j$. They cover $[0,1]$, since each $x\in [0,1]$ has a representative $v\in V$ with $x-v\in \mathbb{Q}\cap [-1,1]$, and all lie inside $[-1,2]$.

Suppose, for contradiction, that $V$ is Lebesgue measurable with $\lambda (V)=0$. Then every translate $V+q_k$ is measurable with measure $0$ by [L2], and countable additivity applied to the pairwise disjoint family of step 1.2 gives $1=\lambda ([0,1])\le \lambda \text{\hspace{0.17em}⁣}({\bigcup }_{k\in \mathbb{N}}(V+q_k))={\sum }_{k=0}^{\mathrm{\infty }}\lambda (V+q_k)=0$, contradicting [L3].

Suppose instead that $V$ is Lebesgue measurable with $\lambda (V)>0$. Since $V\subseteq [0,1]$, step 1.1 and [L3] give $0<\lambda (V)\le 1$. Apply [L6] to the real number $3\mathrm{/}\lambda (V)$ to choose $m\ge 1$ with $3<m\lambda (V)$. The first $m$ translates from step 1.2 are disjoint and lie in $[-1,2]$, so finite additivity and translation invariance give $3\ge {\sum }_{k<m}\lambda (V+q_k)=m\lambda (V)$, a contradiction.

Steps 2.1 and 2.2 rule out both possible values of the measure of a measurable Vitali set, so $V$ is not Lebesgue measurable.

By [L1] fix a Vitali set $V\subseteq [0,1]$, and enumerate $\mathbb{Q}\cap [-1,1]$ as $(q_k{)}_{k\in \mathbb{N}}$ by [L2]. Exactly as in the Vitali argument, the translates $V+q_k$ are pairwise disjoint, they cover $[0,1]$, and they all lie inside $[-1,2]$.

Since $[-1,2]\subseteq [-1,0]\cup [0,1]\cup [1,2]$, translation invariance and finite subadditivity from [L3] give $\mu ([-1,2])\le 3\mu ([0,1])<+\mathrm{\infty }$.

If $\mu (V)=0$, then every translate $V+q_k$ has measure $0$ and countable additivity on the disjoint family of step 1.1 gives $\mu ([0,1])=0$, contradicting the hypotheses.

If $\mu (V)>0$, choose a natural number $m\ge 1$ with $\mu ([-1,2])<m\mu (V)$ by [L4]. The first $m$ translates from step 1.1 are pairwise disjoint subsets of $[-1,2]$, so [L3] gives $\mu ([-1,2])\ge {\sum }_{k<m}\mu (V+q_k)=m\mu (V)$, contradicting the choice of $m$.

Steps 2.1 and 2.2 rule out both possibilities for $\mu (V)$, so no such translation-invariant measure $\mu$ exists.

By [L0] fix a Vitali set $V\subseteq [0,1]$. For each rational $q$ put $A_q:=A\cap (V+q)$. The sets $A_q$ are pairwise disjoint because the translates $V+q$ are, and they cover $A$ because the rational translates of a Vitali selector cover all of $\mathbb{R}$.

Suppose some $A_q$ were Lebesgue measurable with positive measure. Then [L2] would give an open interval about $0$ inside $A_q-A_q$. But if $x,y\in A_q\subseteq V+q$, then $x-y\in \mathbb{Q}$ implies $(x-q)-(y-q)\in \mathbb{Q}$ with both terms in $V$, so the selector property forces $x=y$; thus $A_q-A_q$ contains no nonzero rational. Every open interval about $0$ contains a nonzero rational, contradiction. Hence every measurable $A_q$ has measure $0$.

Suppose, for contradiction, that every $A_q$ is Lebesgue measurable. Then step 2.1 gives $\lambda (A_q)=0$ for every rational $q$, and by [L4] each $A_q$ is measurable with outer measure $0$. Since the family is pairwise disjoint and covers $A$, countable additivity from [L5] gives $\lambda (A)=0$, hence ${\lambda }^{\ast }(A)=0$, contradicting the hypothesis. Therefore at least one set $A_q$ is not Lebesgue measurable, and it is a subset of $A$.

The map $\psi$ is continuous on $[0,1]$, being the sum of the identity map and the continuous function $c$.

If $0\le x<y\le 1$, then $c(x)\le c(y)$ by [L1], so $\psi (y)-\psi (x)=(y-x)+(c(y)-c(x))>0$. Therefore $\psi$ is strictly increasing and hence injective.

By [L1], $\psi (0)=0$ and $\psi (1)=2$. Also $0\le x\le 1$ and $0\le c(x)\le 1$ for every $x\in [0,1]$, so $\psi ([0,1])\subseteq [0,2]$. Since step 1.1 makes $\psi$ continuous, [L2] makes $\psi ([0,1])$ an interval, and the same step shows that this interval contains the endpoints $0$ and $2$, so it is exactly $[0,2]$.

The interval $[0,1]$ is compact by [L4], and $[0,2]$ is a Hausdorff subspace of $\mathbb{R}$. Steps 1.1, 1.2 and 2.1 therefore make $\psi$ a continuous bijection from a compact space to a Hausdorff space, so [L3] gives that $\psi$ is a homeomorphism.

The complement $(0,1)\setminus C$ is open, because $C$ is closed by the definition of the Cantor set. By [L4] write it as a countable disjoint union ${⨆}_{k\in \mathbb{N}}{I}_k$ of nonempty open intervals. For each $k$ there are endpoints $u_k<v_k$ in $C$ with $I_k=(u_k,v_k)$ and $(u_k,v_k)\cap C=\mathrm{\varnothing }$.

Fix $k$. By [L3] the Cantor function is constant on $[u_k,v_k]$; write that value as ${\alpha }_k$. Then $\psi (x)=x+{\alpha }_k$ for every $x\in I_k$, so $\psi [I_k]=(u_k+{\alpha }_k,v_k+{\alpha }_k)$ is an open interval and $\lambda (\psi [I_k])=\lambda (I_k)=v_k-u_k$ by [L5].

The intervals $\psi [I_k]$ are pairwise disjoint because $\psi$ is injective by [L1]. They cover $\psi [(0,1)\setminus C]$, so countable additivity on the disjoint family and step 2.1 give $\lambda (\psi [(0,1)\setminus C])={\sum }_{k=0}^{\mathrm{\infty }}\lambda (\psi [I_k])={\sum }_{k=0}^{\mathrm{\infty }}\lambda (I_k)=\lambda ((0,1)\setminus C)=1$, because [L2] says $\lambda (C)=0$ and [L5] says $\lambda ([0,1])=1$.

The set $K=\psi [C]$ is compact: $C$ is closed and bounded, hence compact by [L8], and the continuous map $\psi$ carries compact sets to compact sets by [L1]. Also $[0,2]=K\bigsqcup \psi [(0,1)\setminus C]$, with disjointness from injectivity of $\psi$, so [L5] and step 3.1 give $2=\lambda ([0,2])=\lambda (K)+1$. Therefore $\lambda (K)=1$.

By [L2] the set $K$ has positive outer measure, so [L1] supplies a subset $N\subseteq K$ that is not Lebesgue measurable.

Let $E:={\psi }^{-1}[N]\subseteq C$. Since $C$ is measurable and has measure $0$ by [L3], completeness from [L4] makes every subset of $C$, and in particular $E$, Lebesgue measurable.

The restriction $f:=\psi {\mathrm{\mid }}_E:E\to \mathbb{R}$ is continuous, because $E\subseteq [0,1]$ and $\psi$ is continuous by [L5]. Its image is $f[E]=N$, which is not Lebesgue measurable by step 1.1.

By [L2] the compact set $K$ has positive outer measure, so [L1] supplies a nonmeasurable subset $N\subseteq K$.

Let $E:={\psi }^{-1}[N]\subseteq C$. Since $C$ is measurable and has measure $0$ by [L3], completeness from [L4] makes $E$ Lebesgue measurable.

Let $g:={\psi }^{-1}{\mathrm{\mid }}_K:K\to \mathbb{R}$. The map $g$ is continuous because $\psi$ is a homeomorphism by [L5]. For every $x\in K$, one has $g(x)\in E$ exactly when $x\in N$, because $g$ is the inverse of $\psi$ on $K$. Therefore $g^{-1}[E]=N$, and this preimage is not Lebesgue measurable.

By [L2] the compact set $K$ has positive outer measure, so [L1] supplies a nonmeasurable subset $N\subseteq K$.

Let $E:={\psi }^{-1}[N]\subseteq C$. Since $C$ is measurable of measure $0$ by [L3], completeness [L4] makes $E$ Lebesgue measurable.

If $E$ were Borel in $\mathbb{R}$, then [L5] would make $E$ Borel as a subset of the subspace $C$. The inverse homeomorphism ${\psi }^{-1}{\mathrm{\mid }}_K:K\to C$ is continuous by [L8], so [L6] would make $N=({\psi }^{-1}{\mathrm{\mid }}_K{)}^{-1}[E]$ Borel in the subspace $K$. Applying [L5] again, there would be a Borel set $B\subseteq \mathbb{R}$ with $N=K\cap B$. Now [L7] makes $B$ Lebesgue measurable, [L2] makes $K$ Lebesgue measurable, and measurable sets are closed under intersection; hence $N$ would be Lebesgue measurable, contradicting step 1.1. Therefore $E$ is not Borel.

Splitting claim. Let $J=(a,b)$ be a nonempty open interval with $J\cap P\mathrm{\ne }\mathrm{\varnothing }$, and let $\eta >0$ be real. Choose $x\in J\cap P$. Since $x$ is not isolated in $P$, there is $y\in P\cap J$ with $y\mathrm{\ne }x$; after swapping if necessary, take $x<y$. Put $\delta :=\min \{\eta \mathrm{/}4,(y-x)\mathrm{/}4,(x-a)\mathrm{/}2,(b-y)\mathrm{/}2\}$, a positive real. By [L1] choose rationals $r_0<s_0<r_1<s_1$ with $x\in (r_0,s_0)$, $y\in (r_1,s_1)$, each interval contained in $(x-\delta ,x+\delta )$ or $(y-\delta ,y+\delta )$ respectively. Then $J_0:=(r_0,s_0)$ and $J_1:=(r_1,s_1)$ are disjoint nonempty open intervals, their closures lie inside $J$, each meets $P$, and each has length $<\eta$.

Fix an enumeration of the rational quadruples using [L3]. By recursion on $n\in \mathbb{N}$, construct for every binary word $s:n\to \{0,1\}$ a nonempty open interval $J_s$ with rational endpoints such that: $J_s\cap P\mathrm{\ne }\mathrm{\varnothing }$; if $t$ extends $s$ then $\overline{J_t}\subseteq J_s$; sibling closures are disjoint; and every $J_s$ at level $n$ has length $<1\mathrm{/}(n+1)$. At level $0$, take the first rational interval in the enumeration that meets $P$ and has length $<1$. At the successor stage, for each of the finitely many parent words in lexicographic order, take the first rational quadruple in the enumeration that gives the two children supplied by step 1.1 with $\eta =1\mathrm{/}(n+2)$. The “first” rule makes the successor operation a function, so recursion produces one coherent family through all levels without any choice principle.

Let $\alpha :\mathbb{N}\to \{0,1\}$ be a binary sequence, and for each $n$ let $I_n:=\overline{J_{\alpha \mathrm{\mid }n}}$, where $\alpha \mathrm{\mid }n$ is the restriction of $\alpha$ to $n$. By step 2.1 the intervals $I_n$ are nonempty, closed and bounded, nested, and have lengths $<1\mathrm{/}(n+1)$; [L5] therefore makes their lengths tend to $0$, so [L4] gives a unique point $x_{\alpha }\in {\bigcap }_n{I}_n$. Each $I_n$ meets $P$ and $P$ is closed, so $x_{\alpha }\in P$. If $\alpha \mathrm{\ne }\beta$, let $n$ be the first index at which they differ; then $I_{n+1}$ for $\alpha$ and $\beta$ are closures of disjoint siblings from step 2.1, so $x_{\alpha }\mathrm{\ne }{x}_{\beta }$. Thus $\alpha \mapsto x_{\alpha }$ is an injection from $\{0,1{\}}^{\mathbb{N}}$ into $P$.

Fix a bijection $e:\mathbb{N}\to \mathbb{Q}$ from [L2]. For each real $x$ define $S_x:=\{n\in \mathbb{N}:\widehat{e(n)}<x\}\mathrm{.}$ If $x<y$, [L1] gives a rational $q$ with $x<\widehat{q}<y$; writing $q=e(n)$ yields $n\in S_y\setminus S_x$, so $x\mapsto S_x$ is an injection $\mathbb{R}\to \mathcal{P}(\mathbb{N})$. Characteristic functions identify $\mathcal{P}(\mathbb{N})$ with $\{0,1{\}}^{\mathbb{N}}$, and step 3.1 gives an injection $\{0,1{\}}^{\mathbb{N}}\to P$; composing these two injections yields an injection $\mathbb{R}\to P$. The inclusion $P\hookrightarrow \mathbb{R}$ is also injective, so [L6] gives $P\approx \mathbb{R}$.

Let ${\mathcal{P}}_{\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{f}}$ be the family of nonempty perfect subsets of $\mathbb{R}$. Every such set is closed, so it is determined by the set of rational open intervals disjoint from it; since rational intervals are countably coded, [L2] gives an injection ${\mathcal{P}}_{\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{f}}\to \mathbb{R}$. Conversely the map $a\mapsto [a,a+1]$ is an injection $\mathbb{R}\to {\mathcal{P}}_{\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{f}}$, because each interval $[a,a+1]$ is nonempty and perfect in the sense of Perfect subset of $\mathbb{R}$: closed with no isolated points. Hence [L3] gives ${\mathcal{P}}_{\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{f}}\approx \mathbb{R}$. Let $\kappa :=\mathrm{\mid }\mathbb{R}\mathrm{\mid }$. The given well-order of $\mathbb{R}$ makes $\mathbb{R}$ well-orderable, so [L3] gives $\mathrm{\mid }{\mathcal{P}}_{\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{f}}\mathrm{\mid }=\kappa$ and shows that $\kappa$ is a cardinal. The interval $[0,1]$ is a nonempty perfect subset of $\mathbb{R}$, so [L1] shows $\kappa$ is infinite; therefore [L4] gives $\mathrm{\mid }{\mathcal{P}}_{\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{f}}\times 2\mathrm{\mid }=\kappa$. Fix a bijection $e:\kappa \to {\mathcal{P}}_{\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{f}}\times 2$.

For $\alpha \in \kappa$, write $e(\alpha )=(P_{\alpha },{\epsilon }_{\alpha })$ with ${\epsilon }_{\alpha }\in 2$. Suppose $z_{\beta }$ has been defined for every $\beta <\alpha$, and put $Z_{\alpha }:=\{z_{\beta }:\beta <\alpha \}$. By construction each new $z_{\beta }$ is chosen outside the earlier set $Z_{\beta }$, so the map $\beta \mapsto z_{\beta }$ is a bijection from $\alpha$ onto $Z_{\alpha }$. Hence $\mathrm{\mid }{Z}_{\alpha }\mathrm{\mid }=\mathrm{\mid }\alpha \mathrm{\mid }<\kappa$, because $\alpha \in \kappa$ and $\kappa$ is a cardinal. The set $P_{\alpha }$ is nonempty perfect, so [L1] and [L3] give $\mathrm{\mid }{P}_{\alpha }\mathrm{\mid }=\kappa$; therefore $P_{\alpha }\setminus Z_{\alpha }$ is nonempty. Let $z_{\alpha }$ be the $\prec$-least point of $P_{\alpha }\setminus Z_{\alpha }$. By transfinite recursion [L5], this defines a function $\alpha \mapsto z_{\alpha }$ on $\kappa$.