In 1917, Luzin announced that every analytic set of real numbers is Lebesgue measurable, a result that remains a cornerstone of descriptive set theory and measure theory. Typical expositions characterize analytic sets in terms of :Suslin’s operation and prove that the operation preserves measurability. Being good logicians, however, one likes to think of the analytic sets as defined by \(\Sigma^1_1\) formulas (with parameter) in the language of second-order arithmetic, and coanalytic set as those defined by \(\Pi^1_1\) formulas. This facilitates the strucutral theory of these sets via ill-founded and well-founded trees, a perspective that we’ll conveniently exploit in the following two alternative proofs of analytic measurability.

The forcing proof

(see, e.g., Judah, Haim. “Absoluteness for projective sets.” Logic colloquium. Vol. 90. 1990.):

Theorem. Every \(\mathbf{\Sigma}^1_1\) set of reals is Lebesgue measurable.

Proof. Suppose \(A:=\{x\in\mathbb{R}\mid \varphi(x,a)\}\), where \(\varphi\) is \(\Sigma_1^1\) and \(a\in \mathbb{R}\). Now consider the random forcing poset \(\mathcal{B}/\mathrm{Null}\). Let \(X\) be a \(G_\delta\) set that forces \(\varphi(\dot r, \check a)\) (or rather, its equivalence class in the random forcing algebra does), where \(\dot{r}\) is a canonical name of the random real added.

Claim: \(\mu(X\triangle A)=0\). (This is just the equivalent formulation of the measurability of \(A\).).

To see the claim, assume towards a contradiction that, say, \(B=A\smallsetminus X\) has positive outer measure (the case where \(X\smallsetminus A\) has positive outer measure is similar). Pick some \(H_\kappa\) large enough, so that it contains \(a,A,X\) and reflects the relevant facts, such as that \(H_\kappa \vDash [\mathbb{R}\smallsetminus X]\Vdash \neg\varphi(\dot r,\check a)\). Now let \(\pi: N\to H_\kappa\) be an elementary embedding where \(N\) is countable transitive with \(a,X,A,B\in\mathrm{ran}(\pi)\). Write \(\pi(\bar A)=A, \pi(\bar X)=X, \pi(\bar B)=B\).

It follows that there is a real \(r\in B\) random over \(N\). Notice that \([B]\) is a stronger condition than \([\mathbb{R}\smallsetminus X]\). And we have \(N[r]\vDash \varphi(r, a)\), since \(r\in A\) by assumption and \(\Sigma^1_1\) formulas are absolute between \(V\) and \(N[r]\). But this last fact contradicts that \(N\vDash [\bar B]\Vdash \neg\varphi(\dot r, \check a)\), because with \(r\in B\) we would also have \(N[r]\vDash \neg\varphi(r,a)\).

The recursion-theoretic proof

(except for the proof itself, all the ingredients appeared in Sacks, Gerald E. “Measure-theoretic uniformity in recursion theory and set theory.” Transactions of the American Mathematical Society 142 (1969): 381-420.)

Theorem. Every \(\mathbf{\Pi}^1_1\) set of reals is Lebesgue measurable.

Proof. We prove the lightface version of this claim. The general case generalizes straightforwardly.

So let \(A\) be a \(\Pi^1_1\) set of reals. By standard facts in descriptive set theory (e.g., see my notes), there is a recursive tree \(T\) on \(\omega\times\omega\) such that \(x\in A\) iff \(T_x\) is well-founded, where \(T_x:=\{\sigma\in\omega^{<\omega}\mid (x\upharpoonright \|\sigma\|,\sigma)\in T\}\). Let \(r:\mathbb{R}\to \omega_1\cup\{\infty\}\) map \(x\) to the rank of \(T_x\) if \(x\in A\) and to \(\infty\) otherwise.

Now, the rank of \(T_x\) is bounded by \(\omega_1^{CK}(x)\). This means that for all \(x\), \(x\in A\) iff \(r(x)<\omega_1^{CK}(x)\). But a classic result by Sacks shows that the set \(\{x\mid \omega_1^{CK}(x)=\omega_1^{CK}\}\) has measure one, which in turn implies that for measure one many reals, we have \(x\in A\) iff \(r(x)=\omega_1^{CK}\).

Finally, since the set \(\{x\mid r(x)=\omega_1^{CK}\}\) is Borel, the previous paragraph amounts to showing that the symmetric difference between \(A\) and this set has measure zero, which is equivalent to saying that \(A\) is measurable.