A shattered set relative to a set 
of subsets of a set 
is a subset 
such
that each subset 
can be expressed as the intersection
of 
with a subset 
in 
. Symbolically, 
is shattered by 
if for all 
, there exists some 
for which 
(Bhaskar and Sukhar 2008, p. 1).
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
 |
where 
denotes the power set of 
. Equivalently, a finite set 
with cardinal
number 
is shattered by a set 
if 
, where
 |
In machine learning theory, 
is a finite sample
and 
is a class of binary concepts, represented by subsets
of 
. Shattering means that every assignment
of one of two labels to the elements of 
is realized by some member of 
.
