7 The Measurability Layer

Up to Chapter 3 the fundamental theorem of statistical learning has been stated as if measurability were a side condition. It is not. The symmetrization argument in the forward direction picks up a set on \(X^m \times X^m\) whose regularity determines whether Hoeffding’s inequality can be applied pointwise and lifted to a supremum over the growth-function-many effective labelings. The literature, following Krapp and Wirth  [ , states this regularity as a Borel hypothesis on the ghost-gap bad event. Every bad event in practice is then checked against the Borel \(\sigma \)-algebra on the product space, and everything goes through.

This chapter establishes that the Borel hypothesis is stronger than the proof needs. The actual sufficient condition is weaker: the bad event must be null-measurable with respect to the completion of the product measure. Section 7.1 identifies the point in the symmetrization chain where the weakening applies and names the kernel’s refined hypothesis WellBehavedVCMeasTarget. Section 7.2 shows that every Borel-parameterized concept class automatically satisfies the refinement via a classical theorem of descriptive set theory (Choquet capacitability, Kechris GTM 156  [ ). Finally, Section 7.3 exhibits a concrete concept class whose ghost-gap bad event is analytic and null-measurable but not Borel, and which therefore witnesses that the refinement is strict.

None of this material appears in the companion textbook: the discoveries are tied to the formalization work, and their home is this chapter. The formalized chain is

five theorems in FLT_Proofs.Theorem.BorelAnalyticSeparation, proved sorry-free against mathlib4 fde0cc5.