A set family shatters when every subset of occurs as a trace of a set family. The largest finite shattered-set size is its VC dimension. The Sauer-Shelah lemma bounds the number of traces when no set of a given size is shattered.
Partition an infinite countable set into disjoint finite blocks of unbounded size. The union of their power sets consists entirely of finite sets and shatters each block, so it has unbounded finite VC dimension. Every infinite set meets two different blocks. The pair formed by one point from each can never occur as a trace, since each family member stays in one block. Thus no infinite set has traces realizing all its finite subsets.

Articles by others on the same topic (0)

There are currently no matching articles.