Bổ đề Sauer–Shelah

Bổ đề Sauer–Shelah (còn gọi là bổ đề hàm phá vỡ) là một mệnh đề toán học về số cách khác nhau một lớp giả thuyết với số chiều VC nhỏ có thể chia đôi một tập hợp cho trước. Bổ đề được chứng minh bởi Vapnik–Chervonenkis và sau đó được chứng minh lại bởi Sauer và Shelah.

Phát biểu

Giả sử H là một lớp giả thuyết có số chiều VC bằng d (một giả thuyết là một hàm số nhận giá trị 0 hoặc 1). Định nghĩa hình chiếu của H trên tập hợp S={x₁, x₂,..., x_m}, ký hiệu là Π_H(S), là tập hợp các vectơ {⟨h(X₁,X₂,...,X_m⟩|h∈H}. Một cách tương đương, có thể định nghĩa Π_H(S)={h∩S|h∈H}. Bổ đề Sauer–Shelah khẳng định rằng |Π_H(S)| ≤ O(m^d).

Chứng minh

Có nhiều cách chứng minh bổ đề này. Dưới đây là một vài cách chứng minh phổ biến.

Chứng minh quy nạp

Không mất tính tổng quát, chỉ cần xét lớp giả thuyết H gồm các tập hợp con của S. Trong trường hợp này Π_H(S) = H.

Ta chứng minh một mệnh đề mạnh hơn: mọi lớp giả thuyết H đều phá vỡ nhiều tập hợp hơn |H|. Giả sử mệnh đề đúng cho |S| ≤ m-1. Nay cần chứng minh mệnh đề trên đúng cho |S|=m. Đặt H₀ là tập hợp con của H gồm các tập hợp không chứa x₁. Theo giả thuyết quy nạp, H₀ phá vỡ ít nhất |H₀| tập hợp con của S' = {x₂,...,x_m}. Đặt H₁ là tập hợp con của H gồm các tập hợp có chứa x₁ và đặt $H_{1}'=\{h\setminus \{x_{1}\}|h\in H_{1}\}$. Theo giả thuyết quy nạp, H₁' phá vỡ ít nhất |H₁'| tập hợp con của S' . Như vậy tổng số tập hợp con của S' bị phá vỡ bởi H₀ và H₁' (và do đó H₁) là |H₀|+|H₁'| = |H|. Tuy nhiên có một số tập hợp R bị đếm hai lần vì R bị phá vỡ bởi cả H₀ và H₁'. Trong trường hợp này, ta nhận thấy cả R và $R\cup \{x_{1}\}$ đều bị phá vỡ bởi H. Do đó, H luôn phá vỡ ít nhất |H| tập hợp.

Từ mệnh đề trên có thể suy ra bổ đề như sau. Nếu $|H|>\sum _{i=0}^{d}{m \choose d}$ thì H phá vỡ ít nhất một tập hợp có kích thước lớn hơn d vì chỉ có $\sum _{i=0}^{d}{m \choose d}$ có kích thước không quá d (mâu thuẫn với giả thuyết H có số chiều VC là d).

Chứng minh bằng phương pháp chiều

Chứng minh này là của Peter Frankl và Janos Pach.

Đặt K=Π_H(S). Đặt D là tập hợp các tập hợp con của S có lực lượng không quá d. Với mỗi tập hợp $X\in K$ định nghĩa hàm $f_{X}:D\rightarrow \Re$ như sau: $f_{X}(Y)$ nhận giá trị 1 nếu $Y\subset X$ và 0 trong trường hợp còn lại. Ta sẽ chứng minh các hàm này là độc lập tuyến tính bằng phương pháp phản chứng. Vì các hàm này nằm trong không gian $\sum _{i=0}^{d}{m \choose i}=O(m^{d})$ chiều, nên nếu chúng độc lập tuyến tính thì số lượng hàm (chính là lực lượng của Π_H(S)) là không quá số chiều. Từ đó ta thu được kết quả cần chứng minh.

Giả thiết vì mục đích phản chứng là tồn tại các hệ số $c_{X}$ không đồng thời bằng 0 sao cho $\sum _{X\in K}c_{X}f_{X}=0$. Với mọi tập hợp Y với lực lượng không quá d, $0=\sum _{X\in K}c_{X}f_{X}(Y)=\sum _{X\in K,Y\subset X}c_{X}$. Tồn tại tập hợp $Y$ sao cho $\sum _{X\in K,Y\subset X}c_{X}\neq 0$, chẳng hạn tập hợp $Y$ có lực lượng lớn nhất với $c_{Y}\neq 0$. Như vậy bằng phương pháp cực trị, xét Y là tập hợp nhỏ nhất có $\sum _{X\in K,Y\subset X}c_{X}\neq 0$. Theo lập luận trên, ta đã biết lực lượng của Y là ít nhất d+1. Ta sẽ hoàn thành chứng minh phản chứng bằng cách chứng minh H phá vỡ Y (mâu thuẫn với giả thiết chiều VC của H là d).

Xét một tập hợp con Z tùy ý của Y. Đặt $s(T)=\sum _{A\in K,T\subset A}c_{A}$. Có thể chứng minh

$\sum _{A\in K,A\cap Y=Z}c_{A}=\sum _{A\in H,Z\subset W\subset Y}(-1)^{|W-Z|}s(W)$

Tuy nhiên vì Y là tập hợp nhỏ nhất nên tổng vế phải chỉ có đúng một số hạng là $(-1)^{|Y-Z|}s(Y)\neq 0$. Do đó, tồn tại tập hợp A trong H sao cho $A\cap Y=Z$. Vì điều này đúng cho Z bất kì nên H phá vỡ Y (mâu thuẫn).