In mathematics, Bondy's theorem is a bound on the number of elements needed to distinguish the sets in a family of sets from each other.
It belongs to the field of combinatorics, and is named after John Adrian Bondy, who published it in 1972.
Nevertheless, by Bondy's theorem we know that we can always find a column that can be deleted without introducing any identical rows.
In this case, we can delete the third column: all rows of the 3 × 4 matrix are distinct.
From the perspective of computational learning theory, Bondy's theorem can be rephrased as follows:[4] This implies that every finite concept class C has its teaching dimension bounded by |C| − 1.