ABSTRACT
The trace of a set F on another set X is F ∩ X, and is denoted by F|X . The trace of a family F https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429440809/2714d8f8-ef71-44f4-80bb-22c5d5471b0d/content/eq7319.tif"/> of sets on X is F | X = { F | X : F ∈ F } https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429440809/2714d8f8-ef71-44f4-80bb-22c5d5471b0d/content/eq7320.tif"/> . No matter how many sets F have the same trace, it is counted only once in F https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429440809/2714d8f8-ef71-44f4-80bb-22c5d5471b0d/content/eq7321.tif"/> | X . We say that a family traces a set X (the terminology shatters is also used very often), if F | X = 2 X https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429440809/2714d8f8-ef71-44f4-80bb-22c5d5471b0d/content/eq7322.tif"/> . The collection of sets that are traced by F https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429440809/2714d8f8-ef71-44f4-80bb-22c5d5471b0d/content/eq7323.tif"/> is denoted by tr( F https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429440809/2714d8f8-ef71-44f4-80bb-22c5d5471b0d/content/eq7324.tif"/> ). The Vapnik-Chervonenkis dimension (or VC-dimension for short) of F https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429440809/2714d8f8-ef71-44f4-80bb-22c5d5471b0d/content/eq7325.tif"/> is the size of the largest set in tr( F https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429440809/2714d8f8-ef71-44f4-80bb-22c5d5471b0d/content/eq7326.tif"/> ), and is denoted by dim VC ( F https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429440809/2714d8f8-ef71-44f4-80bb-22c5d5471b0d/content/eq7327.tif"/> ).
