Question

【題目】設(shè)X是有限集，t為正整數(shù)，F是包含t個(gè)子集的子集族：F=.如果F中的部分子集構(gòu)成的集族S滿足：對(duì)S中任意兩個(gè)不相等的集合A、B，均不成立，則稱S為反鏈.設(shè)S1為包含集合最多的反鏈，S2是任意反鏈.證明：存在S2到S1的單射f，滿足或成立.

Answer 1

【答案】證明見(jiàn)解析

【解析】

記|S1|=r，稱包含r個(gè)元素的反鏈為最大反鏈，最大反鏈可能不唯一

稱F的子集P為鏈，如果之一成立.

我們證明結(jié)論：F可以拆分為r個(gè)鏈的并(即Dilworth定理).

對(duì)t進(jìn)行歸納證明.t=1時(shí)顯然成立.設(shè)命題對(duì)t－1成立，先假設(shè)存在一個(gè)最大反鏈S，使得F中既有集合真包含S中的某個(gè)集合，也有集合是S中的某個(gè)集合的真子集.記前者的全體為F1，后者的全體為F2，即

包含S中的某個(gè)集合，

是S中的某個(gè)集合的子集，

則均是F的真子集，從而由歸納假設(shè)可將都可以拆成r個(gè)鏈的并.中的鏈以S中的元素開始，中的鏈以S中的元素結(jié)束.將這些鏈“接”起來(lái)就將F分成了r條鏈.

現(xiàn)在假設(shè)不存在這樣的反鏈，從而每個(gè)最大反鏈要么滿足，要么滿足.前者意味著S中的子集都是“極大”子集(不是另一個(gè)Ai的真子集)，后者意味著S中的子集都是“極小”子集(不真包含另一個(gè)Ai)，從而至多有兩個(gè)最大反鏈.如果極大子集構(gòu)成的反鏈和極小子集構(gòu)成的反鏈均為最大反鏈，則任取極大子集A，以及極小子集，將A、B都去掉用歸納假設(shè)將剩下的集合拆分成r－1條鏈，再加上鏈即可如果其中之一不是最大反鏈，不妨設(shè)極大子集構(gòu)成的反鏈?zhǔn)俏ㄒ坏臉O大反鏈，任意去掉一個(gè)極大子集歸納即可.結(jié)論證畢.

現(xiàn)在將F拆分成r條鏈，則每條鏈中恰有一個(gè)S1中的子集，且至多有一個(gè)S2中的子集.將每個(gè)S2中的子集對(duì)應(yīng)到所在鏈中S1的元素，就得到了從S2到S1滿足要求的映射.