Теорема Бонди

В математике теорема Бонди представляет собой ограничение количества элементов, необходимых для того, чтобы отличить множества в семействе множеств друг от друга. Она относится к области комбинаторики и названа в честь Джона Адриана Бонди , опубликовавшего ее в 1972 году.

Заявление

Теорема заключается в следующем:

Пусть X — множество из n элементов и пусть A ₁ , A ₂ , ..., An _— различные подмножества X . Тогда существует подмножество S из X из n − 1 элементов такое, что все множества A _i ∩ S различны.

Другими словами, если у нас есть матрица 0–1 с n строками и n столбцами, каждая из которых различна, мы можем удалить один столбец так, чтобы строки полученной матрицы n × ( n − 1) были различны.

Пример

Рассмотрим матрицу 4 × 4

${\begin{bmatrix}1&1&0&1\\0&1&0&1\\0&0&1&1\\0&1&1&0\end{bmatrix}}$

где все строки попарно различны. Если удалить, например, первый столбец, то полученная матрица

${\begin{bmatrix}1&0&1\\1&0&1\\0&1&1\\1&1&0\end{bmatrix}}$

больше не имеет этого свойства: первая строка идентична второй строке. Тем не менее, по теореме Бонди мы знаем, что всегда можно найти столбец, который можно удалить, не вводя одинаковых строк. В этом случае мы можем удалить третий столбец: все строки матрицы 3×4.

${\begin{bmatrix}1&1&1\\0&1&1\\0&0&1\\0&1&0\end{bmatrix}}$

различны. Другой возможностью было бы удалить четвертый столбец.

Применение теории обучения

С точки зрения теории вычислительного обучения теорему Бонди можно перефразировать следующим образом:

Пусть C — класс понятий области X. в конечной Тогда существует подмножество S в X размером не более | С | − 1 такое, что S является набором-свидетелем для каждого понятия в C .

Это означает, что каждый конечный класс понятий C имеет обучающее измерение, ограниченное | С | − 1.