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