PAC learnability versus VC dimension: a footnote to a basic result of
  statistical learning
  A fundamental result of statistical learnig theory states that a concept
class is PAC learnable if and only if it is a uniform Glivenko-Cantelli class
if and only if the VC dimension of the class is finite. However, the theorem is
only valid under special assumptions of measurability of the class, in which
case the PAC learnability even becomes consistent. Otherwise, there is a
classical example, constructed under the Continuum Hypothesis by Dudley and
Durst and further adapted by Blumer, Ehrenfeucht, Haussler, and Warmuth, of a
concept class of VC dimension one which is neither uniform Glivenko-Cantelli
nor consistently PAC learnable. We show that, rather surprisingly, under an
additional set-theoretic hypothesis which is much milder than the Continuum
Hypothesis (Martin's Axiom), PAC learnability is equivalent to finite VC
dimension for every concept class.
