[proofplan] We first invoke the Martin-Solovay measurability theorem in its Cantor-space form: under $\mathrm{AD}$, every subset of $2^{\mathbb{N}}$ is measurable for the fair-coin product measure. This avoids any appeal to a maximal almost-disjoint family, which would require choice beyond $\mathrm{DC}$ if constructed by [Zorn's lemma](/theorems/1226). Binary coding then transfers the Cantor-space result to $[0,1]$ up to the countable dyadic ambiguity, and a countable affine decomposition transfers the result to all of $\mathbb{R}$. [/proofplan]

[step:Apply the Martin-Solovay theorem on Cantor space]Let $2^{\mathbb{N}}$ denote Cantor space with its product Borel $\sigma$-algebra $\mathcal{B}(2^{\mathbb{N}})$ and fair-coin product probability measure $\mu$. Let $\mu^*$ denote the outer measure induced by $\mu$, and let $C \subseteq 2^{\mathbb{N}}$ be arbitrary. We use the following precise external result, the Martin-Solovay measurability theorem for Cantor space: working in $\mathrm{ZF}+\mathrm{DC}$, if $\mathrm{AD}$ holds for all length-$\omega$ games with moves in $\mathbb{N}$ and payoff sets contained in $\mathbb{N}^{\mathbb{N}}$, then for every set $C \subseteq 2^{\mathbb{N}}$ there exists a Borel set $B_C \subseteq 2^{\mathbb{N}}$ such that \begin{align*} \mu^*(C \triangle B_C)=0. \end{align*} The hypotheses match the present setting. A play in $2^{\mathbb{N}}$ is a play with moves in $\{0,1\}$, hence is coded as a play with moves in $\mathbb{N}$. Since $2^{\mathbb{N}} \subseteq \mathbb{N}^{\mathbb{N}}$, the arbitrary payoff set $C \subseteq 2^{\mathbb{N}}$ is a payoff set of the kind covered by $\mathrm{AD}$ after this inclusion. Therefore the Martin-Solovay theorem applies to the present arbitrary set $C$, and it gives a Borel $B_C \subseteq 2^{\mathbb{N}}$ with null symmetric difference. Hence every subset of Cantor space is measurable for the fair-coin product measure.[/step]

[guided]The proof should not construct a maximal family of positive Borel conditions by Zorn's lemma, because the ambient theory is only $\mathrm{ZF}+\mathrm{DC}$. Instead, we use the standard Martin-Solovay theorem as the deep determinacy input in exactly the strength needed here. The theorem says the following. Work in $\mathrm{ZF}+\mathrm{DC}$ and assume $\mathrm{AD}$ for length-$\omega$ games whose moves are natural numbers and whose payoff sets are subsets of $\mathbb{N}^{\mathbb{N}}$. Then for every subset $C \subseteq 2^{\mathbb{N}}$, there is a Borel set $B_C \subseteq 2^{\mathbb{N}}$ such that \begin{align*} \mu^*(C \triangle B_C)=0. \end{align*} We verify the hypotheses rather than merely naming the theorem. The space $2^{\mathbb{N}}$ consists of sequences with entries in $\{0,1\}$, so every play producing an element of $2^{\mathbb{N}}$ is a play with moves in $\mathbb{N}$. Also $2^{\mathbb{N}}$ is a subset of $\mathbb{N}^{\mathbb{N}}$, so the arbitrary set $C \subseteq 2^{\mathbb{N}}$ is a legitimate payoff set after viewing it as a subset of $\mathbb{N}^{\mathbb{N}}$. Thus the determinacy assumption in the theorem statement is exactly strong enough to cover the Martin-Solovay games associated to $C$. Applying the Martin-Solovay theorem gives a Borel set $B_C \subseteq 2^{\mathbb{N}}$ whose symmetric difference with $C$ has $\mu$-outer measure zero. This is precisely $\mu$-measurability of $C$. Since $C \subseteq 2^{\mathbb{N}}$ was arbitrary, every subset of Cantor space is measurable for the fair-coin product measure.[/guided]

[step:Transfer measurability from Cantor space to the unit interval]Define the binary coding map \begin{align*} \pi:2^{\mathbb{N}} &\to [0,1] \end{align*} \begin{align*} x &\mapsto \sum_{n=1}^{\infty} x_n 2^{-n}. \end{align*} Let $D \subseteq [0,1]$ be the [countable set](/page/Countable%20Set) of dyadic rationals, namely those points having two binary expansions. The map $\pi$ is Borel, sends $\mu$ to [Lebesgue measure](/page/Lebesgue%20Measure) $\mathcal{L}^1$ on $[0,1]$, and restricts to a Borel bijection from $2^{\mathbb{N}} \setminus \pi^{-1}(D)$ onto $[0,1]\setminus D$. We use the following precise external result, the binary-coding transfer theorem: if $S \subseteq 2^{\mathbb{N}}$ has a Borel set $B_S \subseteq 2^{\mathbb{N}}$ with $\mu^*(S \triangle B_S)=0$, then for every $E \subseteq [0,1]$ satisfying $S=\pi^{-1}(E\setminus D)$ there exists a Borel set $B_E \subseteq [0,1]$ such that \begin{align*} \mathcal{L}^{1,*}((E \setminus D) \triangle B_E)=0. \end{align*} Let $E \subseteq [0,1]$ be arbitrary. Since $D$ is countable, $\mathcal{L}^{1,*}(D)=0$. Define the set $C_E \subseteq 2^{\mathbb{N}}$ by \begin{align*} C_E := \pi^{-1}(E \setminus D). \end{align*} By the Cantor-space result there is a Borel set $B_{C_E} \subseteq 2^{\mathbb{N}}$ such that \begin{align*} \mu^*(C_E \triangle B_{C_E})=0. \end{align*} The binary-coding transfer theorem applies with $S=C_E$ because $\pi$ pushes $\mu$ forward to $\mathcal{L}^1$ on $[0,1]$ and is a Borel isomorphism off the null dyadic ambiguity set $D$. Hence there is a Borel set $B_E \subseteq [0,1]$ such that \begin{align*} \mathcal{L}^{1,*}((E \setminus D) \triangle B_E)=0. \end{align*} Since $E \triangle B_E \subseteq ((E \setminus D) \triangle B_E) \cup D$, [countable subadditivity](/theorems/1108) of outer measure and $\mathcal{L}^{1,*}(D)=0$ give \begin{align*} \mathcal{L}^{1,*}(E \triangle B_E)=0. \end{align*} Therefore every subset of $[0,1]$ is Lebesgue measurable.[/step]

[guided]We now transfer the Cantor-space conclusion to the usual Lebesgue measure on the unit interval. The binary coding map is the Borel map $\pi:2^{\mathbb{N}} \to [0,1]$ given by \begin{align*} \pi(x)=\sum_{n=1}^{\infty} x_n 2^{-n}. \end{align*} The only obstruction to injectivity is the countable set $D \subseteq [0,1]$ of dyadic rationals, namely the points with two binary expansions. This set is countable, so $\mathcal{L}^{1,*}(D)=0$. Off this null ambiguity set, $\pi$ is a Borel bijection from $2^{\mathbb{N}} \setminus \pi^{-1}(D)$ onto $[0,1]\setminus D$, and $\pi$ pushes the fair-coin product measure $\mu$ forward to $\mathcal{L}^1$ on $[0,1]$. We use the binary-coding transfer theorem in the following explicit form: if $S \subseteq 2^{\mathbb{N}}$ is $\mu$-measurable modulo a null set, and if $S=\pi^{-1}(E\setminus D)$ for some $E \subseteq [0,1]$, then $E\setminus D$ is Lebesgue measurable modulo a null set. More precisely, there is a Borel set $B_E \subseteq [0,1]$ such that \begin{align*} \mathcal{L}^{1,*}((E \setminus D) \triangle B_E)=0. \end{align*} Now let $E \subseteq [0,1]$ be arbitrary and define $C_E \subseteq 2^{\mathbb{N}}$ by \begin{align*} C_E := \pi^{-1}(E \setminus D). \end{align*} The Cantor-space result already proved applies to this particular subset $C_E$. Hence there is a Borel set $B_{C_E} \subseteq 2^{\mathbb{N}}$ such that \begin{align*} \mu^*(C_E \triangle B_{C_E})=0. \end{align*} The hypotheses of the binary-coding transfer theorem are therefore satisfied with $S=C_E$: the set has a Borel approximation modulo $\mu$-null sets, and it is exactly the preimage of $E\setminus D$ under $\pi$. Thus we obtain a Borel set $B_E \subseteq [0,1]$ satisfying \begin{align*} \mathcal{L}^{1,*}((E \setminus D) \triangle B_E)=0. \end{align*} Finally we restore the dyadic points. Since $E \triangle B_E \subseteq ((E \setminus D) \triangle B_E) \cup D$, countable subadditivity of outer measure gives \begin{align*} \mathcal{L}^{1,*}(E \triangle B_E) \leq \mathcal{L}^{1,*}((E \setminus D) \triangle B_E)+\mathcal{L}^{1,*}(D)=0. \end{align*} Thus $E$ differs from the Borel set $B_E$ by a Lebesgue null set. Since $E \subseteq [0,1]$ was arbitrary, every subset of $[0,1]$ is Lebesgue measurable.[/guided]

[step:Cover the real line by countably many unit intervals]Let $\mathbb{Z}$ denote the set of integers, and let $A \subseteq \mathbb{R}$ be arbitrary. For each $k \in \mathbb{Z}$, define the affine map \begin{align*} \tau_k:[0,1) &\to [k,k+1) \end{align*} \begin{align*} t &\mapsto k+t. \end{align*} Define \begin{align*} A_k := \tau_k^{-1}(A \cap [k,k+1)). \end{align*} Since $A_k \subseteq [0,1) \subseteq [0,1]$, the unit-interval result gives a Borel set $F_k \subseteq [0,1]$ such that \begin{align*} \mathcal{L}^{1,*}(A_k \triangle F_k)=0. \end{align*} Define $E_k := F_k \cap [0,1)$. Then $E_k$ is Borel in $[0,1)$, and because $F_k \setminus E_k \subseteq \{1\}$, countable subadditivity gives \begin{align*} \mathcal{L}^{1,*}(A_k \triangle E_k)=0. \end{align*} The family of nonempty choices of such $F_k$ is indexed by the countable set $\mathbb{Z}$, so the countable choice supplied by $\mathrm{DC}$ permits choosing the sequence $(E_k)_{k \in \mathbb{Z}}$. Set \begin{align*} B := \bigcup_{k \in \mathbb{Z}} \tau_k(E_k). \end{align*} Each $\tau_k(E_k)$ is Borel in $[k,k+1)$, and hence $B$ is a countable union of Borel subsets of $\mathbb{R}$. Thus $B$ is Borel. [Translation invariance](/theorems/4911) of Lebesgue outer measure gives \begin{align*} \mathcal{L}^{1,*}((A \cap [k,k+1)) \triangle \tau_k(E_k)) = \mathcal{L}^{1,*}(A_k \triangle E_k)=0. \end{align*} Using the countable decomposition $\mathbb{R}=\bigcup_{k \in \mathbb{Z}}[k,k+1)$ and countable subadditivity, \begin{align*} \mathcal{L}^{1,*}(A \triangle B) \leq \sum_{k \in \mathbb{Z}} \mathcal{L}^{1,*}((A \cap [k,k+1)) \triangle \tau_k(E_k))=0. \end{align*} Therefore $\mathcal{L}^{1,*}(A \triangle B)=0$ with $B$ Borel. Hence $A$ is Lebesgue measurable. Since $A \subseteq \mathbb{R}$ was arbitrary, $\mathrm{AD}$ implies that every set of [real numbers](/page/Real%20Numbers) is Lebesgue measurable.[/step]

[guided]We finish by decomposing the real line into countably many half-open unit intervals. Let $\mathbb{Z}$ denote the set of integers, and fix an arbitrary set $A \subseteq \mathbb{R}$. For each $k \in \mathbb{Z}$, define the affine map $\tau_k:[0,1) \to [k,k+1)$ by $\tau_k(t)=k+t$, and define \begin{align*} A_k := \tau_k^{-1}(A \cap [k,k+1)). \end{align*} Then $A_k \subseteq [0,1) \subseteq [0,1]$. The unit-interval result applies to $A_k$ as a subset of $[0,1]$, so there is a Borel set $F_k \subseteq [0,1]$ with \begin{align*} \mathcal{L}^{1,*}(A_k \triangle F_k)=0. \end{align*} Because the target interval for $\tau_k$ is $[0,1)$ rather than $[0,1]$, we remove the endpoint by setting $E_k:=F_k\cap[0,1)$. The removed part lies in $\{1\}$, which has Lebesgue outer measure zero, so \begin{align*} \mathcal{L}^{1,*}(A_k \triangle E_k)=0. \end{align*} The choices are indexed by the countable set $\mathbb{Z}$, and the ambient theory includes $\mathrm{DC}$, which supplies countable choice for this sequence of selections. Now define \begin{align*} B := \bigcup_{k \in \mathbb{Z}} \tau_k(E_k). \end{align*} Each $\tau_k(E_k)$ is Borel in the half-open interval $[k,k+1)$, and hence Borel as a subset of $\mathbb{R}$ after intersecting with that Borel interval. Since $\mathbb{Z}$ is countable, $B$ is a countable union of Borel subsets of $\mathbb{R}$, so $B$ is Borel. Translation invariance of Lebesgue outer measure under the affine translation $\tau_k$ gives, for each $k \in \mathbb{Z}$, \begin{align*} \mathcal{L}^{1,*}((A \cap [k,k+1)) \triangle \tau_k(E_k)) = \mathcal{L}^{1,*}(A_k \triangle E_k)=0. \end{align*} Finally, the half-open intervals $[k,k+1)$ cover $\mathbb{R}$, so countable subadditivity of outer measure yields \begin{align*} \mathcal{L}^{1,*}(A \triangle B) \leq \sum_{k \in \mathbb{Z}} \mathcal{L}^{1,*}((A \cap [k,k+1)) \triangle \tau_k(E_k))=0. \end{align*} Thus $A$ differs from the Borel set $B$ by a Lebesgue null set. Since $A \subseteq \mathbb{R}$ was arbitrary, every set of real numbers is Lebesgue measurable under $\mathrm{AD}$.[/guided]