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

【答案】證明見解析

【解析】

記|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é)束.將這些鏈“接”起來就將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滿足要求的映射.

練習(xí)冊(cè)系列答案
相關(guān)習(xí)題

科目：高中數(shù)學(xué) 來源： 題型：

【題目】在矩形ABCD中，AB＝1，AD＝2，△ABD沿對(duì)角線BD翻折，形成三棱錐A﹣BCD．

①當(dāng)時(shí)，三棱錐A﹣BCD的體積為；

②當(dāng)面ABD⊥面BCD時(shí)，AB⊥CD；

③三棱錐A﹣BCD外接球的表面積為定值．

以上命題正確的是_____．

查看答案和解析>>

科目：高中數(shù)學(xué) 來源： 題型：

【題目】如圖，四棱錐的底面為直角梯形，，，，為的中點(diǎn)．

（Ⅰ）求證：平面

（Ⅱ）若平面平面，異面直線與所成角為60°，且是鈍角三角形，求二面角的正弦值

查看答案和解析>>

科目：高中數(shù)學(xué) 來源： 題型：

【題目】如圖，在正三棱柱（側(cè)棱垂直于底面，且底面三角形是等邊三角形）中，，分別是的中點(diǎn).

（1）求證：平面∥平面；

（2）在線段上是否存在一點(diǎn)使平面？若存在，確定點(diǎn)的位置；若不存在，也請(qǐng)說明理由.

查看答案和解析>>

科目：高中數(shù)學(xué) 來源： 題型：

【題目】在平面直角坐標(biāo)系中，圓：，直線：.為圓內(nèi)一點(diǎn)，弦過點(diǎn)，過點(diǎn)作的垂線交于點(diǎn).

（1）若，求的面積；

（2）判斷直線與圓的位置關(guān)系，并證明.

查看答案和解析>>

科目：高中數(shù)學(xué) 來源： 題型：

【題目】橢圓的離心率是，過點(diǎn)做斜率為的直線，橢圓與直線交于兩點(diǎn)，當(dāng)直線垂直于軸時(shí)．

（Ⅰ）求橢圓的方程；

（Ⅱ）當(dāng)變化時(shí)，在軸上是否存在點(diǎn)，使得是以為底的等腰三角形，若存在求出的取值范圍，若不存在說明理由．

查看答案和解析>>

科目：高中數(shù)學(xué) 來源： 題型：

【題目】定義：從數(shù)列{an}中抽取m（m∈N，m≥3）項(xiàng)按其在{an}中的次序排列形成一個(gè)新數(shù)列{bn}，則稱{bn}為{an}的子數(shù)列；若{bn}成等差（或等比），則稱{bn}為{an}的等差（或等比）子數(shù)列．

（1）記數(shù)列{an}的前n項(xiàng)和為Sn，已知．

①求數(shù)列{an}的通項(xiàng)公式；

②數(shù)列{an}是否存在等差子數(shù)列，若存在，求出等差子數(shù)列；若不存在，請(qǐng)說明理由．

（2）已知數(shù)列{an}的通項(xiàng)公式為an＝n+a（a∈Q+），證明：{an}存在等比子數(shù)列．

查看答案和解析>>

科目：高中數(shù)學(xué) 來源： 題型：

【題目】已知函數(shù).

（1）若存在極值，求實(shí)數(shù)a的取值范圍；

（2）設(shè)，設(shè)是定義在上的函數(shù).

（ⅰ）證明：在上為單調(diào)遞增函數(shù)(是的導(dǎo)函數(shù))；

（ⅱ）討論的零點(diǎn)個(gè)數(shù).

查看答案和解析>>

科目：高中數(shù)學(xué) 來源： 題型：

【題目】過正四面體ABCD的頂點(diǎn)A作一個(gè)形狀為等腰三角形的截面，且使截面與底面BCD所成的角為，這樣的截面有（ ）

A.6個(gè)B.12個(gè)C.16個(gè)D.18個(gè)

查看答案和解析>>

同步練習(xí)冊(cè)答案