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. 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à ΠH(S), 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). 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. 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 ∖ { x 1 } | h ∈ H 1 } {\displaystyle 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 ∪ { x 1 } {\displaystyle 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 | > ∑ i = 0 d ( m d ) {\displaystyle |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ó ∑ i = 0 d ( m d ) {\displaystyle \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 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 ∈ K {\displaystyle X\in K} định nghĩa hàm f X : D → ℜ {\displaystyle f_{X}:D\rightarrow \Re } như sau: f X ( Y ) {\displaystyle f_{X}(Y)} nhận giá trị 1 nếu Y ⊂ X {\displaystyle 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 ∑ i = 0 d ( m i ) = O ( m d ) {\displaystyle \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 {\displaystyle c_{X}} không đồng thời bằng 0 sao cho ∑ X ∈ K c X f X = 0 {\displaystyle \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 = ∑ X ∈ K c X f X ( Y ) = ∑ X ∈ K , Y ⊂ X c X {\displaystyle 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 {\displaystyle Y} sao cho ∑ X ∈ K , Y ⊂ X c X ≠ 0 {\displaystyle \sum _{X\in K,Y\subset X}c_{X}\neq 0} , chẳng hạn tập hợp Y {\displaystyle Y} có lực lượng lớn nhất với c Y ≠ 0 {\displaystyle 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ó ∑ X ∈ K , Y ⊂ X c X ≠ 0 {\displaystyle \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 ) = ∑ A ∈ K , T ⊂ A c A {\displaystyle s(T)=\sum _{A\in K,T\subset A}c_{A}} . Có thể chứng minh ∑ A ∈ K , A ∩ Y = Z c A = ∑ A ∈ H , Z ⊂ W ⊂ Y ( − 1 ) | W − Z | s ( W ) {\displaystyle \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 ) ≠ 0 {\displaystyle (-1)^{|Y-Z|}s(Y)\neq 0} . Do đó, tồn tại tập hợp A trong H sao cho A ∩ Y = Z {\displaystyle 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). ^ a b Sauer, Norbert (1972). “On the Density of Families of Sets”. J. Comb. Theory, Ser. A. 13 (1): 145–147. ^ Vapnik, V. N.; Chervonenkis, A. Ya. (1971). “On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities”. Theory Probab. Appl. 16 (2): 264–280. ^ Shelah, Saharon (1972). “A combinatorial problem; stability and order for models and theories in infinitary languages”. Pacific J. Math. 41 (1): 247–261. ^ “Dimension arguments in combinatorics”.