3.24 VC-dimension of union of concepts. Let A and B be two sets of functions mapping from X into f0; 1g, and assume that both A and B have nite VCdimension, with VCdim(A) = dA and VCdim(B) = dB. Let C = A [ B be the union of A and B.

(a) Prove that for all m, C(m)  A(m) + B(m).

(b) Use Sauer's lemma to show that for m  dA + dB + 2, C(m) < 2m; and give a bound on the VC-dimension of C.