1159242
Bổ đề Sauer–Shelah
https://vi.wikipedia.org/wiki?curid=1159242
Title: Bổ đề Sauer–Shelah
Đặ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).