Bổ đề Sauer–Shelah

Bách khoa toàn thư mở Wikipedia
Bước tới điều hướng Bước tới tìm kiếm

Bổ đề Sauer–Shelah[1] (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 VapnikChervonenkis[2] và sau đó được chứng minh lại bởi Sauer[1]Shelah[3].

Phát biểu[sửa | sửa mã nguồn]

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).

Chứng minh[sửa | sửa mã nguồn]

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[sửa | sửa mã nguồ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 . 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 H0H1' (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ả H0H1'. Trong trường hợp này, ta nhận thấy cả R đề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 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ó 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[sửa | sửa mã nguồn]

Chứng minh này là của Peter Frankl và Janos Pach.[4]

Đặ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 định nghĩa hàm như sau: nhận giá trị 1 nếu 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 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ố không đồng thời bằng 0 sao cho . Với mọi tập hợp Y với lực lượng không quá d, . Tồn tại tập hợp sao cho , chẳng hạn tập hợp có lực lượng lớn nhất với . Như vậy bằng phương pháp cực trị, xét Y là tập hợp nhỏ nhất có . 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 Hd).

Xét một tập hợp con Z tùy ý của Y. Đặt . Có thể chứng minh

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à . Do đó, tồn tại tập hợp A trong H sao cho . Vì điều này đúng cho Z bất kì nên H phá vỡ Y (mâu thuẫn).

Ghi chú[sửa | sửa mã nguồn]

  1. ^ a ă Sauer, Norbert (1972). “On the Density of Families of Sets”. J. Comb. Theory, Ser. A. 13 (1): 145–147.
  2. ^ 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.
  3. ^ Shelah, Saharon (1972). “A combinatorial problem; stability and order for models and theories in infinitary languages”. Pacific J. Math. 41 (1): 247–261.
  4. ^ “Dimension arguments in combinatorics”.