紹爾-謝拉赫引理

設${\displaystyle \textstyle {\mathcal {F}}=\{S_{1},S_{2},\dots \}}$為一族集合，${\displaystyle T}$為另一集，此時所謂${\displaystyle T}$為${\displaystyle {\mathcal {F}}}$的碎裂集，意思是${\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}$元的集合。

亦可將「碎裂」的概念加以限縮，變成「順序碎裂」（）。此時，任意集族順序打碎的集合數，必恰好等於該族的大小。[11]

紹爾-謝拉赫引理的帕約爾變式可使用数学归纳法證明，此證法一說出自諾加·阿隆[13]，一說出自朗·阿哈羅尼及朗·霍爾茲曼（）[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}}|}$。

紹爾-謝拉赫引理的原始形式還有另一種證明，利用线性代数及容斥原理，該證法由弗龍克爾·彼得和保奇·亞諾什給出。[8][10]

VC二氏原先將引理應用於證明，若考慮一族VC維固定的事件，則衹需有限多個取樣點，即可近似任意的概率分佈（使取樣所得的事件概率近似該分佈下的事件概率），且取樣點的個數衹取決於VC維數。具體而言，有兩種意義下的近似，各由參數${\displaystyle \varepsilon }$定義：

1. 取樣集${\displaystyle S}$上的概率分佈定義為原分佈的「${\displaystyle \varepsilon }$近似」（英語：），意思是每個事件被${\displaystyle S}$以該分佈取樣的概率，與原概率所差不過${\displaystyle \varepsilon }$。
2. 取樣集${\displaystyle S}$（不設權重）定義為「ε網」，意思是概率不小於${\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 }$近似兩概念本身，皆在机器学习和概率近似正確學習方面有應用。[16]计算几何方面的應用則有範圍搜索[14]、去随机化[17]、近似算法[18][19]。

Kozma & Moran (2013)利用紹爾-謝拉赫引理的推廣，證明若干圖論結果，例如：圖的強定向[註 2]方案數介於其連通子圖數與邊雙連通子圖數之間。[9]