Question

【题目】设X是有限集，t为正整数，F是包含t个子集的子集族：F=.如果F中的部分子集构成的集族S满足：对S中任意两个不相等的集合A、B，均不成立，则称S为反链.设S1为包含集合最多的反链，S2是任意反链.证明：存在S2到S1的单射f，满足或成立.

Answer 1

【答案】证明见解析

【解析】

记|S1|=r，称包含r个元素的反链为最大反链，最大反链可能不唯一

称F的子集P为链，如果之一成立.

我们证明结论：F可以拆分为r个链的并(即Dilworth定理).

对t进行归纳证明.t=1时显然成立.设命题对t－1成立，先假设存在一个最大反链S，使得F中既有集合真包含S中的某个集合，也有集合是S中的某个集合的真子集.记前者的全体为F1，后者的全体为F2，即

包含S中的某个集合，

是S中的某个集合的子集，

则均是F的真子集，从而由归纳假设可将都可以拆成r个链的并.中的链以S中的元素开始，中的链以S中的元素结束.将这些链“接”起来就将F分成了r条链.

现在假设不存在这样的反链，从而每个最大反链要么满足，要么满足.前者意味着S中的子集都是“极大”子集(不是另一个Ai的真子集)，后者意味着S中的子集都是“极小”子集(不真包含另一个Ai)，从而至多有两个最大反链.如果极大子集构成的反链和极小子集构成的反链均为最大反链，则任取极大子集A，以及极小子集，将A、B都去掉用归纳假设将剩下的集合拆分成r－1条链，再加上链即可如果其中之一不是最大反链，不妨设极大子集构成的反链是唯一的极大反链，任意去掉一个极大子集归纳即可.结论证毕.

现在将F拆分成r条链，则每条链中恰有一个S1中的子集，且至多有一个S2中的子集.将每个S2中的子集对应到所在链中S1的元素，就得到了从S2到S1满足要求的映射.