(已经回高三了,但是依稀记得单老写过
证:考察集合A的某一元素b与某一子集B,b或属于B,记为1,或不属于B,记为0.我们容易看出,在对集合A赋予顺序后,A的所有子集与n位二进制数建立双射.
事实1:定义某一二进制数B的对偶是这样的一个数B′,若将B中的所有1置为0,所有0置为1.易见B与B′不可共存于同一相交族F中.于是相交族F的基数最大为power(2,n-1).
事实2:易见这个基数最大的相交族F存在,且必含有集合A,其余集合之间若存在矛盾,考虑将出现矛盾的两个集合B,C任取其一换成其对偶即可消除矛盾.
故这样的最大相交族存在,因而总可以将其换成适当的形式,使其包含扩充前的相交族.