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&ndash;Chervonenkis và sau đó được chứng minh lại bởi Sauer

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={x1, x2,..., xm}, ký hiệu là , là tập hợp các vectơ {⟨h(X1,X2,...,Xm⟩|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(md).

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 H0 là tập hợp con của H gồm các tập hợp không chứa x1. Theo giả thuyết quy nạp, H0 phá vỡ ít nhất |H0| tập hợp con của S' = {x2,...,xm}. Đặt H1 là tập hợp con của H gồm các tập hợp có chứa x1 và đặt H_1' = \{h\setminus\{x_1\}|h\in H_1\}. Theo giả thuyết quy nạp, H1' phá vỡ ít nhất |H1'| 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 H0 và H1' (và do đó H1) là |H0|+|H1'| = |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ả H0 và H1'. 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=. Đặ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 ) 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\ne 0, chẳng hạn tập hợp Y có lực lượng lớn nhất với c_Y\ne 0. Như vậy bằng phương pháp cực trị, xét là tập hợp nhỏ nhất có \sum_{X\in K, Y\subset X} c_X\ne 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)^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)^s(Y)\ne 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).

Ghi chú