Twierdzenie Bondy'ego

W matematyce twierdzenie Bondy'ego ogranicza liczbę elementów potrzebnych do odróżnienia zbiorów w rodzinie zbiorów od siebie. Należy do dziedziny kombinatoryki i nosi imię Johna Adriana Bondy'ego , który opublikował ją w 1972 roku.

Oświadczenie

Twierdzenie jest następujące:

Niech X będzie zbiorem o n elementach i niech A ₁ , A ₂ , ..., An _będą odrębnymi podzbiorami X . Wtedy istnieje podzbiór S od X z n − 1 elementami takimi, że wszystkie zbiory A _i ∩ S są różne.

Innymi słowy, jeśli mamy macierz 0-1 z n wierszami i n kolumnami, tak że każdy wiersz jest odrębny, możemy usunąć jedną kolumnę tak, że wiersze wynikowej macierzy n × ( n − 1) są różne.

Przykład

Rozważ macierz 4 × 4

$\ Displaystyle {\ rozpocząć {bmatrix} 1 i 1 i 0 i 1 \\ 0 i 1 i 0 i 1 \\ 0 i 0 i 1 i 1 \\ 0 i 1 i 1 i 0 \ koniec {bmatrix}}}$

gdzie wszystkie wiersze są różne parami. Jeśli usuniemy na przykład pierwszą kolumnę, wynikowa macierz

${\ Displaystyle {\ rozpocząć {bmatrix} 1 i 0 i 1 \\ 1 i 0 i 1 \\ 0 i 1 i 1 \\ 1 i 1 i 0 \ koniec {bmatrix}}}$

nie ma już tej właściwości: pierwszy wiersz jest identyczny z drugim. Niemniej jednak z twierdzenia Bondy'ego wiemy, że zawsze możemy znaleźć kolumnę, którą można usunąć bez wprowadzania identycznych wierszy. W takim przypadku możemy usunąć trzecią kolumnę: wszystkie wiersze macierzy 3 × 4

${\ Displaystyle {\ rozpocząć {bmatrix} 1 i 1 i 1 \\ 0 i 1 i 1 \\ 0 i 0 i 1 \\ 0 i 1 i 0 \ koniec {bmatrix}}}$

są odrębne. Inną możliwością byłoby usunięcie czwartej kolumny.

Zastosowanie teorii uczenia się

Z perspektywy teorii obliczeniowego uczenia się twierdzenie Bondy'ego można sformułować w następujący sposób:

Niech C będzie klasą pojęciową nad skończoną dziedziną X . Wtedy istnieje podzbiór S od X o rozmiarze co najwyżej | C | − 1 takie, że S jest zbiorem świadków dla każdego pojęcia w C .

Oznacza to, że każda skończona klasa pojęć C ma swój wymiar nauczania ograniczony przez | C | − 1.