proving our extension we will have to confront several new difficulties.  Firstly, the concept classes $S$ that we want to consider can now contain a *continuum* of functions—so Lemma \[majcer\], which assumed that $S$ was finite and constructed certificates of size $O\left(  \log\left\vert
S\right\vert \right)  $, is not going to work.  In Section \[LEARNBACK\], we review notions from computational learning theory, including fat-shattering dimension and $\varepsilon$-covers, which (combined with results of Alon et al. [@abch] and Bartlett and Long [@bartlettlong]) can be used to get around this difficulty.  Secondly, it is no longer enough to isolate a function $f_{i}\in S$ that we are interested in; instead we will need to ‘safely’ isolate $f_{i}$, which roughly speaking means that (i) $f_{i}$ is consistent with some certificate $C$, and (ii) any $f\in S$ that is even *approximately* consistent with $C$ is close to $f_{i}$.  In Section \[SAFEWINNOW\], we prove a ‘safe winnowing lemma’ that can be used for this purpose.  Finally, in Section \[THELEMMA\], we put the pieces together to prove a real-valued majority-certificates lemma.

Background from Learning Theory\[LEARNBACK\]
--------------------------------------------

A *p-concept class* $S$ is a family of functions $f:\left\{
0,1\right\}  ^{n}\rightarrow\left[  0,1\right]  $ (as usual, quantification over all $n$ is understood).  