紹爾-謝拉赫引理

组合数学和中，紹爾-謝拉赫引理（）斷言，若集合族的VC维低，則該族不能有太多個集合。引理得名於諾貝特·紹爾和，兩人分別獨立於1972年發表此結果。較之略早，在1971年，弗拉基米尔·瓦普尼克和亞歷克塞·澤范蘭傑斯合著的論文已有此結果（「VC維」即以兩人為名）。謝拉赫發表引理時，亦歸功於，故引理又稱為佩爾萊斯-紹爾-謝拉赫引理。

布萨格洛等人稱其為「關於VC維的最根本結論之一」。引理在若干方面有應用，就各發現者的研究動機而言，紹爾是研究集族的組合學，謝拉赫研究模型论，VC二氏則研究统计学。後來，引理亦用於离散几何和图论。

定義及敍述
設為一族集合，為另一集，此時所謂為的，意思是的每個子集（包括空集和本身），皆可表示成與該族某集之交。的VC維是其打碎的最大集的大小。

利用以上術語，紹爾-謝拉赫引理可以寫成：
若是一族集合，且各集合中，合共衹有個不同元素，但
，則打碎某個元集合。

所以，若的VC維為（故不打碎任何元集），則中至多衹有個集合。

引理所給的界已是最優：考慮元集中，所有小於個元素的子集，所成的族。該族的大小恰為，但是不打碎任何元集。

打碎多少集合
帕约尔將紹爾-謝拉赫引理加強為：

有限族必打碎至少個集合。
紹爾-謝拉赫引理為其直接推論，因為元全集的子集中，衹有個的元素個數小於。故時，即使全部小集皆已打碎，仍不足個，故必有打碎某個不少於元的集合。

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

證 
紹爾-謝拉赫引理的帕約爾變式可使用数学归纳法證明，此證法一說出自諾加·阿隆，一說出自及朗·霍爾茲曼（）。

作為歸納法的起始步驟，單一個集合組成的族，能打碎空集，已足個。

至於遞推步驟，可假設引理對任意少於個集合組成的族皆成立，且族有至少兩個集合，故可選取元素為其一的元素，但不屬於另一集。如此便可將的集合分成兩類：包含的集合歸入子族，不含的則歸入。

由歸納假設，兩子族各自打碎的集合數，其和至少為。 

該些碎裂集不能有元素，因為若要打碎某個有的集合，則族中需要有含的集合，也需要有不含的集合，纔能使該族各集與的交集出齊的全體子集。

若集衹被一個子族打碎，則數算兩子族打碎的集合時，計為一個，數打碎的集合時亦計為一個。但也可能同時被兩子族打碎，如此，數算兩子族打碎的集合時，會將計兩次；不過既打碎，也打碎，所以（和）在數打碎的集合時，也計為兩次。由此，打碎的集合數，不小於兩子族各自打碎集合數之和，從而不小於。

紹爾-謝拉赫引理的原始形式還有另一種證明，利用线性代数及容斥原理，該證法由和給出。

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

取樣集上的概率分佈定義為原分佈的「近似」（），意思是每個事件被以該分佈取樣的概率，與原概率所差不過。
取樣集（不設權重）定義為「」，意思是概率不小於的任一事件中，必含中至少一點。

由定義，近似必為網，反之則不一定。

VC二氏以此引理證明，若某集族的VC維為，則必有大小不過的近似。其後，和等發表了類似的結果，證明必存在大小為的網，具體上界為。證明存在小網的主要方法是，先揀選個點的隨機樣本，再獨立揀選另個點的隨機樣本，然後證明以下的不等式：存在某個較大事件與不交的概率，與存在同樣的事件，且該事件與相交點數大於中位值的概率，兩概率之比至多為。若固定和，則不交而與相交點數多於中位值的概率很小。由紹爾-謝拉赫引理，與的交集的可能情況並不太多，計算「存在滿足條件」的概率時，衹需對每種交集的可能性考慮一個，因此由併集上界，可得，故有非零概率為網。

以上論證說明隨機取樣足夠多個點就可能是網。此性質以及網、近似兩概念本身，皆在机器学习和方面有應用。计算几何方面的應用則有、、近似算法。

利用紹爾-謝拉赫引理的推廣，證明若干圖論結果，例如：圖的方案數介於其連通子圖數與子圖數之間。

註

參考文獻 

集合族
引理