Abstract

For a set system S and given sequence of length l we define the index of S over the sequence as the number of classes of sets from S that are undifferentiated by the sequence. The growth function is defined as the maximum of this index over all sequences of length  l. For infinite VC-dimension systems the growth function is always equal to 2^l. Log expectation of the index over all sequences of length l we call the entropy of the system S for sequences of length l. There always exists a limit of entropy per element with l going to infinity. If this limit is zero, then uniform convergence of frequencies to probabilities holds. The opposite case, when this limit is nonzero is also interesting. If this limit is c>0, then there exists a set T of measure c, such that index is equal to 2^l for almost all sequences with elements of T. This result makes it quite obvious why in this case uniform convergence does not hold.