3.23 VC-dimension of intersection concepts.

(a) Let C1 and C2 be two concept classes. Show that for any concept class C = fc1 \ c2 : c1 2 C1; c2 2 C2g,

C(m)  C1 (m)C2 (m): (3.53)

(b) Let C be a concept class with VC-dimension d and let Cs be the concept class formed by all intersections of s concepts from C, s  1. Show that the VC-dimension of Cs is bounded by 2ds log2(3s). (Hint: show that log2(3x) <

9x=(2e) for any x  2.)