绍尔-谢拉赫引理

设${\displaystyle \textstyle {\mathcal {F}}=\{S_{1},S_{2},\dots \}}$ 为一族集合，${\displaystyle T}$ 为另一集，此时所谓${\displaystyle T}$ 为${\displaystyle {\mathcal {F}}}$ 的碎裂集（英语：shattered set），意思是${\displaystyle T}$ 的每个子集（包括空集和${\displaystyle T}$ 本身），皆可表示成${\displaystyle T}$ 与该族某集之交${\displaystyle T\cap S_{i}}$ 。${\displaystyle {\mathcal {F}}}$ 的VC维是其打碎的最大集的大小。

利用以上术语，绍尔-谢拉赫引理可以写成：

若${\displaystyle {\mathcal {F}}}$ 是一族集合，且各集合中，合共衹有${\displaystyle n}$ 个不同元素，但 ${\displaystyle \textstyle |{\mathcal {F}}|>\sum _{i=0}^{k-1}{\binom {n}{i}}}$ ，则${\displaystyle {\mathcal {F}}}$ 打碎某个${\displaystyle k}$ 元集合。

所以，若${\displaystyle {\mathcal {F}}}$ 的VC维为${\displaystyle k}$ （故不打碎任何${\displaystyle k+1}$ 元集），则${\displaystyle {\mathcal {F}}}$ 中至多衹有${\displaystyle \textstyle \sum _{i=0}^{k}{\binom {n}{i}}=O(n^{k})}$ 个集合。

引理所给的界已是最优：考虑${\displaystyle n}$ 元集${\displaystyle \{1,2,\dots ,n\}}$ 中，所有小于${\displaystyle k}$ 个元素的子集，所成的族${\displaystyle {\mathcal {F}}}$ 。该族的大小恰为${\displaystyle \textstyle \sum _{i=0}^{k-1}{\binom {n}{i}}}$ ，但是不打碎任何${\displaystyle k}$ 元集。^[10]

帕约尔将绍尔-谢拉赫引理加强为：^[12]

有限族${\displaystyle {\mathcal {F}}}$ 必打碎至少${\displaystyle |{\mathcal {F}}|}$ 个集合。

绍尔-谢拉赫引理为其直接推论，因为${\displaystyle n}$ 元全集的子集中，衹有${\displaystyle \textstyle \sum _{i=0}^{k-1}{\binom {n}{i}}}$ 个的元素个数小于${\displaystyle k}$ 。故${\displaystyle \textstyle |{\mathcal {F}}|>\sum _{i=0}^{k-1}{\binom {n}{i}}}$ 时，即使全部小集皆已打碎，仍不足${\displaystyle |{\mathcal {F}}|}$ 个，故必有打碎某个不少于${\displaystyle k}$ 元的集合。

亦可将“碎裂”的概念加以限缩，变成“顺序碎裂”（order-shattered）。此时，任意集族顺序打碎的集合数，必恰好等于该族的大小。^[11]

绍尔-谢拉赫引理的帕约尔变式可使用数学归纳法证明，此证法一说出自诺加·阿隆^[13]，一说出自朗·阿哈罗尼（英语：Ron Aharoni）及朗·霍尔兹曼（Ron Holzman）^[11]。

作为归纳法的起始步骤，单一个集合组成的族${\displaystyle {\mathcal {F}}}$ ，能打碎空集，已足${\displaystyle |{\mathcal {F}}|}$ 个。

至于递推步骤，可假设引理对任意少于${\displaystyle |{\mathcal {F}}|}$ 个集合组成的族皆成立，且族${\displaystyle {\mathcal {F}}}$ 有至少两个集合，故可选取元素${\displaystyle x}$ 为其一的元素，但不属于另一集。如此便可将${\displaystyle {\mathcal {F}}}$ 的集合分成两类：包含${\displaystyle x}$ 的集合归入子族${\displaystyle {\mathcal {F}}_{1}}$ ，不含${\displaystyle x}$ 的则归入${\displaystyle {\mathcal {F}}_{0}}$ 。

由归纳假设，两子族各自打碎的集合数，其和至少为${\displaystyle |{\mathcal {F}}_{0}|+|{\mathcal {F}}_{1}|=|{\mathcal {F}}|}$ 。

该些碎裂集不能有元素${\displaystyle x}$ ，因为若要打碎某个有${\displaystyle x}$ 的集合${\displaystyle A}$ ，则族中需要有含${\displaystyle x}$ 的集合，也需要有不含${\displaystyle x}$ 的集合，才能使该族各集与${\displaystyle A}$ 的交集出齐${\displaystyle A}$ 的全体子集。

若集${\displaystyle S}$ 衹被一个子族打碎，则数算两子族打碎的集合时，${\displaystyle S}$ 计为一个，数${\displaystyle {\mathcal {F}}}$ 打碎的集合时亦计为一个。但${\displaystyle S}$ 也可能同时被两子族打碎，如此，数算两子族打碎的集合时，会将${\displaystyle S}$ 计两次；不过${\displaystyle {\mathcal {F}}}$ 既打碎${\displaystyle S}$ ，也打碎${\displaystyle S\cup \{x\}}$ ，所以${\displaystyle S}$ （和${\displaystyle S\cup \{x\}}$ ）在数${\displaystyle {\mathcal {F}}}$ 打碎的集合时，也计为两次。由此，${\displaystyle {\mathcal {F}}}$ 打碎的集合数，不小于两子族各自打碎集合数之和，从而不小于${\displaystyle |{\mathcal {F}}|}$ 。

绍尔-谢拉赫引理的原始形式还有另一种证明，利用线性代数及容斥原理，该证法由弗龙克尔·彼得（英语：Péter Frankl）和保奇·亚诺什（英语：János Pach）给出。^[8][10]

VC二氏原先将引理应用于证明，若考虑一族VC维固定的事件，则衹需有限多个取样点，即可近似任意的概率分布（使取样所得的事件概率近似该分布下的事件概率），且取样点的个数衹取决于VC维数。具体而言，有两种意义下的近似，各由参数${\displaystyle \varepsilon }$ 定义：

1. 取样集${\displaystyle S}$ 上的概率分布定义为原分布的“${\displaystyle \varepsilon }$ 近似”（英语：${\displaystyle \varepsilon }$ -approximation），意思是每个事件被${\displaystyle S}$ 以该分布取样的概率，与原概率所差不过${\displaystyle \varepsilon }$ 。
2. 取样集${\displaystyle S}$ （不设权重）定义为“ε网（英语：ε-net (computational geometry)）”，意思是概率不小于${\displaystyle \varepsilon }$ 的任一事件中，必含${\displaystyle S}$ 中至少一点。

由定义，${\displaystyle \varepsilon }$ 近似必为${\displaystyle \varepsilon }$ 网，反之则不一定。

VC二氏以此引理证明，若某集族的VC维为${\displaystyle d}$ ，则必有大小不过${\displaystyle O({\tfrac {d}{\varepsilon ^{2}}}\log {\tfrac {d}{\varepsilon }})}$ 的${\displaystyle \varepsilon }$ 近似。其后，Haussler & Welzl (1987)^[14]和Komlós，Pach & Woeginger (1992)^[15]等发表了类似的结果，证明必存在大小为${\displaystyle O({\tfrac {d}{\varepsilon }}\log {\tfrac {1}{\varepsilon }})}$ 的${\displaystyle \varepsilon }$ 网，具体上界为${\displaystyle {\tfrac {d}{\varepsilon }}\ln {\tfrac {1}{\varepsilon }}+{\tfrac {2d}{\varepsilon }}\ln \ln {\tfrac {1}{\varepsilon }}+{\tfrac {6d}{\varepsilon }}}$ 。^[8]证明存在小${\displaystyle \varepsilon }$ 网的主要方法是，先拣选${\displaystyle O({\tfrac {d}{\varepsilon }}\log {\tfrac {1}{\varepsilon }})}$ 个点的随机样本${\displaystyle x}$ ，再独立拣选另${\displaystyle O({\tfrac {d}{\varepsilon }}\log ^{2}{\tfrac {1}{\varepsilon }})}$ 个点的随机样本${\displaystyle y}$ ，然后证明以下的不等式：存在某个较大事件${\displaystyle E}$ 与${\displaystyle x}$ 不交的概率${\displaystyle p_{1}}$ ，与存在同样的事件，且该事件与${\displaystyle y}$ 相交点数大于中位值的概率${\displaystyle p_{2}}$ ，两概率之比至多为${\displaystyle 2}$ 。若固定${\displaystyle E}$ 和${\displaystyle x\cup y}$ ，则${\displaystyle x}$ 不交${\displaystyle E}$ 而${\displaystyle y}$ 与${\displaystyle E}$ 相交点数多于中位值的概率很小。由绍尔-谢拉赫引理，${\displaystyle E}$ 与${\displaystyle x\cup y}$ 的交集的可能情况并不太多，计算“存在${\displaystyle E}$ 满足条件”的概率时，衹需对每种交集的可能性考虑一个${\displaystyle E}$ ，因此由并集上界，可得${\displaystyle p_{1}\leq 2p_{2}<1}$ ，故${\displaystyle x}$ 有非零概率为${\displaystyle \varepsilon }$ 网。^[8]

以上论证说明随机取样足够多个点就可能是${\displaystyle \varepsilon }$ 网。此性质以及${\displaystyle \varepsilon }$ 网、${\displaystyle \varepsilon }$ 近似两概念本身，皆在机器学习和概率近似正确学习（英语：probably approximately correct learning）方面有应用。^[16]计算几何方面的应用则有范围搜索（英语：range searching）^[14]、去随机化（英语：derandomization）^[17]、近似算法^[18][19]。

Kozma & Moran (2013)利用绍尔-谢拉赫引理的推广，证明若干图论结果，例如：图的强定向（英语：strong orientation）^{[注 2]}方案数介于其连通子图数与边双连通（英语：k-edge-connected graph）子图数之间。^[9]