ボンディの定理

数学において、ボンディの定理は、集合族内の集合を互いに区別するために必要な要素の数の上限である。これは組合せ論の分野に属し、 1972年に発表したジョン・エイドリアン・ボンディにちなんで名付けられた。 ^[1]

定理は次のとおりです。

X をn個の要素を持つ集合とし、A 1 、 A 2 、 ...、 A n を X の異なる部分集合とします。_すると、n ₋ 1個_の要素を持つXの部分集合S が存在し 、集合A _i  ∩  S はすべて異なります。

言い換えれば、各行が異なるn行n列の0-1行列がある場合、1つの列を削除して、結果として得られるn  ×( n  −1)行列の行が異なるようにすることができます。^{[2] [3]}

4×4行列を考える

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

ここで、すべての行はペアごとに異なる。例えば、最初の列を削除すると、結果の行列は

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

行列はもはやこの性質を持たない。最初の行は2番目の行と同一である。しかし、ボンディの定理により、同一の行を生じさせずに削除できる列が常に見つかることが分かっている。この場合、3列目を削除できる。3×4行列のすべての行である。

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

区別されます。別の可能性としては、4 番目の列を削除することが挙げられます。

計算学習理論の観点から見ると、ボンディの定理は次のように言い換えることができる。^[4]

C を有限領域X上の概念クラスとします。このとき、 XのサブセットS が存在し、そのサイズは最大で | C | − 1 であり、SはC内のすべての概念の証拠集合となります。

これは、すべての有限概念クラスCの教育次元が| C | − 1で制限されることを意味します。