Just found out that "Learnability (in machine learning) can be undecidable, that is, independent of set theory". From the abstract:

Consider the following statistical estimation problem: given a family F of real valued random variables over some domain X and an i.i.d. sample drawn from an unknown distribution P over X, find f in F such that its expectation w.r.t. P is close to the supremum expectation over all members of F. We show that, in some cases, a solution to the ‘estimating the maximum’ problem is equivalent to the continuum hypothesis and is therefore independent of the set theory ZFC axioms.

Details (which I haven't read) are here and here.