Can the fact that all analytic sets are Lebesgue measurable be proven in $Z\_2$, or in some weak subsystem such as $\Pi^1\_1\text{-CA}\_0$? Conversely, can certain set existence axioms be derived from the assumption that all analytic sets are Lebesgue measurable?



reverse mathematics of the Lebesgue measurability of analytic sets
I believe $\Delta^1\_2$-CA$\_0$ does indeed suffice; however, I don't see a way to pull this down to $\Pi^1\_1$-CA$\_0$.


*This is contrary to my previous claim; my error was with respect to the strength of the relevant choice principle.*




---


Let me briefly outline the classical proof:


* First, we show a version of Lebesgue regularity: that for any analytic set $A$, the outer measure of $A$ exists and that there is a $G\_\delta$ (and hence measurable) set $B$ with $A\subseteq B\subseteq cl(A)$ and $m(X)=0$ for all measurable $X\subseteq B\setminus A$.
* Next, let $A$ be an analytic set. Fixing a continuous function $f$ whose image is $A$, we let $A\_\sigma$ be the image of $f$ restricted to the set of reals beginning with $\sigma$ (for $\sigma\in\omega^{<\omega}$) and we let $B\_\sigma$ be the set corresponding to $A\_\sigma$ per the bulletpoint above.
* Looking to the $B\_\sigma$s for a moment, it's not hard to show that for all $\sigma\in\omega^{<\omega}$, the set $$Z\_\sigma:=B\_\sigma\setminus\bigcup\_{n\in\omega}B\_{\sigma n}$$ is measurable and is contained in $B\_\sigma\setminus A\_\sigma$. But from this it follows that $Z\_\sigma$ is null.
* Elementary set-juggling shows that $$B\setminus A\subseteq\bigcup\_{\sigma\in\omega^{<\omega}}Z\_\sigma.$$ Since the union of countably many null sets is null, we have that $B\setminus A$ is measurable; since $B$ is measurable, this implies that $A$ is also measurable, and so we're done.




---


Now, translating this into the context of reverse mathematics, we run into three important points:


* We need to talk about *codes* for sets of reals, rather than sets of reals themselves. Luckily, we're basically looking here at the first couple levels of the Borel hierarchy and at analytic sets, so we have reasonable coding notions.
* We need to be able to do basic "set-juggling" with these codes. But this winds up being straightforward.
* Finally, we need to be able to prove basic facts about Lebesgue measure: in particular, that the measurable (coded) sets are closed under countable Boolean combinations and that the union of countably many null sets is null. **This is the difficult bit:** it involves choosing "nearly optimal" covers in a concrete way: e.g. to show that $\bigcup\_{n\in\omega} X\_n$ is null if each $X\_n$ is null, we really want a sequence $(\mathcal{O}\_{n,k})\_{n,k\in\omega}$ such that $\mathcal{O}\_{n,k}$ is an open cover of $X\_n$ with total measure ${1\over k+1}$. When the $X\_n$s are given uniformly by analytic codes - as in our situation here - the set of legal choices for $\mathcal{O}\_{n,k}$ is a nonempty $\Pi^1\_1$ set uniformly in $n,k$.


So the question now is: how strong is $\Pi^1\_1$ choice? Unfortunately (and contra my original claim) it turns out that it is rather strong indeed. In fact, it is equivalent to $\Delta^1\_2$-CA$\_0$; this follows from Theorem VII.$6.9(1)$, page $298$, in Simpson's book together with Carl's observation that $\Pi^1\_1$-choice is equivalent to $\Sigma^1\_2$-choice.


So the above argument gives a proof of the result in a weak-but-not-too-weak subsystem of Z$\_2$.


