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

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

Теорема выглядит следующим образом:

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

Другими словами, если у нас есть матрица 0-1 с n строками и n столбцами, такая, что каждая строка различна, мы можем удалить один столбец так, чтобы строки результирующей матрицы n  × ( n  − 1) были различны. ^{[2] [3]}

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

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

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

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

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

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

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

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

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

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