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"1, "x"2..., "x"m}, 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 "H"0 là tập hợp con của "H" gồm các tập hợp không chứa "x"1. Theo giả thuyết quy nạp, "H"0 phá vỡ ít nhất |"H"0| tập hợp con của "S' " = {"x"2...,"x"m}. Đặt "H"1 là tập hợp con của "H" gồm các tập hợp có chứa "x"1 và đặt formula_1. Theo giả thuyết quy nạp, "H"1' phá vỡ ít nhất |"H"1'| 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"0 và "H"1' (và do đó "H"1) là |"H"0|+|"H"1'| = |"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"0 và "H"1'. Trong trường hợp này, ta nhận thấy cả "R" và formula_2 đề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 formula_3 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ó formula_4 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 formula_5 định nghĩa hàm formula_6 như sau: formula_7 nhận giá trị 1 nếu formula_8 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 formula_9 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ố formula_10 không đồng thời bằng 0 sao cho formula_11. Với mọi tập hợp "Y" với lực lượng không quá "d", formula_12. Tồn tại tập hợp formula_13 sao cho formula_14, chẳng hạn tập hợp formula_13 có lực lượng lớn nhất với formula_16. Như vậy bằng phương pháp cực trị, xét là tập hợp nhỏ nhất có formula_14. 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 formula_18. Có thể chứng minh
formula_19
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à formula_20. Do đó, tồn tại tập hợp "A" trong "H" sao cho formula_21. Vì điều này đúng cho "Z" bất kì nên "H" phá vỡ "Y" (mâu thuẫn).