Shattered Set
Let 
be a set and 
a collection of subsets of 
. A subset 
is shattered by 
if each subset 
of 
can be expressed as the intersection of 
with a subset 
in 
. Symbolically, then, 
is shattered by 
if for all 
, there exists some 
for which 
.
If 
is shattered by 
, one says that 
shatters 
.
There are a number of equivalent ways to define shattering. One can easily verify that the above definition is equivalent to saying that 
shatters 
if
![P(A)=<span style=]() {T intersection A:T in S} " src="https://mathworld.wolfram.com/images/equations/ShatteredSet/NumberedEquation1.gif" style="height:15px; width:134px" /> |
where 
denotes the power set of 
. Yet another way to express this concept is to say that a set 
of cardinality 
is shattered by a set 
if 
where here,
![Pi_S(A)=<span style=]() {s intersection A:s in S}. " src="https://mathworld.wolfram.com/images/equations/ShatteredSet/NumberedEquation2.gif" style="height:15px; width:139px" /> |
In the field of machine learning theory, one usually considers the set 
to be a sample of outcomes drawn according to a distribution 
with the set 
representing a collection of "known" concepts or laws. In this context, saying that 
is shattered by 
intuitively means that all of the constituent outcomes in 
can be known by knowing only the laws in 
.
REFERENCES:
Bhaskar, A. and Sukhar, I. "VC-Dimension." 2008. http://www.cs.cornell.edu/courses/cs683/2008sp/lecture%20notes/683notes_0428.pdf.
Shashua, A. "Lecture 11: PAC II." 2009. http://www.cs.huji.ac.il/~shashua/papers/class11-PAC2.pdf.
