第2章集合ppt課件

1、第二章 集 合 第二章 集 合 2.1 集合論的根本概念集合論的根本概念2.2 集合上的運(yùn)算集合上的運(yùn)算2.3 歸納法和自然數(shù)歸納法和自然數(shù)2.4 言語上的運(yùn)算言語上的運(yùn)算2.5 集合的笛卡兒乘積集合的笛卡兒乘積第二章 集 合 2.1 集合論的根本概念集合論的根本概念 2.1.1 集合的概念集合的概念 集合在某些場所又稱為類、族或搜集集合在某些場所又稱為類、族或搜集, 它是數(shù)學(xué)中最根本它是數(shù)學(xué)中最根本的概念之一的概念之一, 好像幾何中的好像幾何中的“點(diǎn)、點(diǎn)、 “線等概念一樣線等概念一樣, 不可準(zhǔn)確定不可準(zhǔn)確定義義, 現(xiàn)描如下現(xiàn)描如下: 一個集合是能作為整體論述的事物的集體。如一個集合是能作為整

2、體論述的事物的集體。如 ;(1) “高二高二(1)班的學(xué)生是一集合。班的學(xué)生是一集合。 ;(2) 硬幣有兩面硬幣有兩面正面和反面正面和反面, “正面、正面、 反面構(gòu)成一集合。反面構(gòu)成一集合。 ;(3) 計(jì)算機(jī)內(nèi)存之全體單元構(gòu)成一集合。計(jì)算機(jī)內(nèi)存之全體單元構(gòu)成一集合。 ;(4) 1, 2, 3, , n, 構(gòu)成正整數(shù)集合。構(gòu)成正整數(shù)集合。 ;(5) 一切三角形構(gòu)成三角形集合。一切三角形構(gòu)成三角形集合。 ;(6) 坐標(biāo)滿足方程坐標(biāo)滿足方程x2+y2R2的全部點(diǎn)構(gòu)成圖的全部點(diǎn)構(gòu)成圖 2.1-1所示的點(diǎn)集。所示的點(diǎn)集。 第二章 集 合 圖 2.1-1 第二章 集 合 組成集合的每個事物叫做這個集合的元

3、素或成員。 通常用大寫字母A, B, C, 代表集合; 用小寫字母a, b, c, 代表元素。 假設(shè)a是集合A的一個元素, 那么記為 aA讀做“a屬于A, 或說“a在A中。 ; 假設(shè)a不是集合A的一個元素, 那么記為 a A讀做“a不屬于A, 或說“a不在A中。 ; 任一元素, 對某一集合而言, 或?qū)儆谠摷? 或不屬于該集合, 二者必居其一, 不可兼得。第二章 集 合 通常采用3種方法表示集合。 ; 第一種是列舉法。就是把集合中的元素一一列舉出來。例如“一切小于5的正整數(shù)這個集合的元素為1, 2, 3, 4, 除這4個元素外, 再沒有別的元素了。假設(shè)把這個集合命名為A, 就可記為A=1, 2

4、, 3, 4 在能清楚表示集合成員的情況下可運(yùn)用省略號, 例如, 從1 到50 的整數(shù)集合可記為1, 2, 3, , 50, 偶數(shù)集合可記為,-4,-2,0,2,4,。 第二章 集 合 第二種是描畫法。就是用謂詞描畫出集合元素的公共特征來表示這個集合。例如, 上述各例可分別寫成A=a|aI0aa5, a|aI1a50和這里I表示整數(shù)集合。普通地S=a|P(a)表示aS當(dāng)且僅當(dāng)P(a)是真。 )2(|yxIyyx第二章 集 合 集合的元素可以是一個集合, 例如A=a,b,c,D, 而 D=0,1。 僅含有一個元素的集合稱為單元素集合。 應(yīng)把單元素集合與這個元素區(qū)別開來。例如A與A不同, A表示僅

5、以A為元素的集合, 而A對A而言僅是一個元素, 當(dāng)然這個元素也可以是一個集合, 如A=1,2。 稱含有有限個元素的集合為有限集合。稱不是有限集合的集合為無限集合或無窮集。有限集合的元素個數(shù)稱為該集合的基數(shù)或勢第五章將給出有限集、無限集、基數(shù)等概念的更精致的陳說。集合A的基數(shù)記為|A|, 例如假設(shè) A=a, b, 那么 |A|=2, 又|A|=1 第二章 集 合 外延公理 兩個集合A和B相等, 即A=B, 當(dāng)且僅當(dāng)它們有一樣的成員(也就是, A的每一元素是B的一個元素而B的每一元素也是A的一個元素)。 ; 用邏輯符號表達(dá)是: )(BxAxxBA或 )()(AxBxxBxAxxBA第二章 集 合

6、外延公理斷言外延公理斷言: 假設(shè)兩個集合有一樣的元素假設(shè)兩個集合有一樣的元素, 那么不論集合那么不論集合是如何表示的是如何表示的, 它們都相等。因此它們都相等。因此, (1) 列舉法中列舉法中, 元素的次序是無關(guān)緊要的。例如元素的次序是無關(guān)緊要的。例如x,y,z與與z,x,y相等。相等。 (2) 元素的反復(fù)出現(xiàn)無足輕重。例如元素的反復(fù)出現(xiàn)無足輕重。例如, x,y,x、 x,y、 x,x,x,y是一樣的集合。是一樣的集合。 (3) 集合的表示不是獨(dú)一的。例如集合的表示不是獨(dú)一的。例如, x|x2-3x+2=0、 x|xI1x2 和和1, 2均表示同一集合。均表示同一集合。 第二章 集 合 2.1

7、.2 羅素悖論羅素悖論 1901年羅素(Bertrand Russell)提出以下悖論: 設(shè)論述域是一切集合的集合, 并定義S為下述集合 |AAAS 這樣, S是不以本身為元素的全體集合的集合, 我們?nèi)缃駟枴癝是不是它本人的元素? ; 假設(shè)S不是它本人的元素, 那么S滿足謂詞A A, 而該謂詞定義了集合S, 所以SS。 另一方面, 假設(shè)SS, 那么S必需滿足定義S的謂詞, 所以SS。 第二章 集 合 這樣, 我們導(dǎo)致了一個類似于謊言悖論的矛盾: 既非SS也非SS是真。 一個“集合, 諸如S, 它能導(dǎo)致矛盾的稱為非良定的。 羅素悖論原因于不受限制的定義集合的方法, 特別, 集合可以是本人的元素的

8、概念值得疑心?？得撘院髣?chuàng)建的許多公理化集合論都直接地或間接地限制集合成為它本人的元素, 因此防止了羅素悖論。 公理化集合論用某個方法防止了羅素悖論, 但怎能確信沒有其它悖論埋伏在這些方式構(gòu)造中呢? 回答是悲觀的, 業(yè)已證明, 運(yùn)用現(xiàn)今有效的數(shù)學(xué)技術(shù), 沒有方法能證明新的悖論不會產(chǎn)生。 第二章 集 合 2.1.3 集合間的包含關(guān)系集合間的包含關(guān)系 定義定義2.1-1 設(shè)設(shè)A和和B是集合是集合, 假設(shè)假設(shè)A的每一元素是的每一元素是B的一個元的一個元素素, 那么那么A是是B的子集合的子集合, 記為記為AB, 讀做讀做“B包含包含A或或“A包含于包含于B中。中。 用邏輯符表示為用邏輯符表示為: BxA

9、xxBABA有時(shí)也記作 , 稱B是A的擴(kuò)集。 AB 第二章 集 合 定義定義2.1-2 假設(shè)假設(shè)AB且且AB, 那么稱那么稱A是是B的真子集的真子集,記作記作AB , 讀作讀作“B真包含真包含A。 ; 用邏輯符表示為用邏輯符表示為: )()()()(AxBxxBxAxxBABABA 要留意區(qū)分從屬關(guān)系“及包含關(guān)系“。 從屬關(guān)系是集合元素與集合本身的關(guān)系, 包含關(guān)系是集合與集合之間的關(guān)系。 第二章 集 合 定理定理 2.1-1 對恣意集合對恣意集合A有有 UA證證 對恣意元素對恣意元素x, xU是真是真, 所以所以 UxAx是真。由全稱推行規(guī)那么得 )(UxAxx所以 UA(這是一個平凡證明的例

10、子) 第二章 集 合 定理定理 2.1-2 設(shè)設(shè)A和和B是集合是集合, A=B當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)AB和和BA。證證ABBAAxBxxBxAxxBA)()(第二章 集 合 推論推論 2.1-2 對任何集合對任何集合A, 恒有恒有AA。 ;定理定理 2.1-3 設(shè)設(shè)A、B、C是集合是集合, 假設(shè)假設(shè)AB且且BC, 那么那么AC。證證 設(shè)設(shè)x是論述域中恣意元素是論述域中恣意元素, 由于由于 )()(CxBxxCBBxAxxBA所以,xAxB= xBxC由前提三段論得 xAxC由全稱推行規(guī)那么得 )(CxAxx即 CA 第二章 集 合 定義定義 2.1-3 沒有元素的集合叫空集或零集沒有元素的集合叫空集

11、或零集, 記為記為 。定理定理 2.1-4 對恣意集合對恣意集合A有有 。證證 設(shè)設(shè)x是論述域中恣意元素是論述域中恣意元素, 那么那么 Ax常假, 所以 Axx無義地真，由全稱推行規(guī)那么得 )(Axxx即 A第二章 集 合 定理定理 2.1-5 空集是獨(dú)一的?？占仟?dú)一的。 證證 設(shè)設(shè)和和 都是空集都是空集, 由定理由定理2.1-4得得 和和 , 根根據(jù)定理據(jù)定理2.1-2得得 。 留意留意與與不同不同, 后者是以空集為元素的一個集合后者是以空集為元素的一個集合, 前者沒前者沒有元素。有元素。 能用空集構(gòu)造不同集合的無限序列。在序列能用空集構(gòu)造不同集合的無限序列。在序列中中, 每一集合除第一個

12、外都確實(shí)有一元素每一集合除第一個外都確實(shí)有一元素, 即序列中前面的集合。即序列中前面的集合。 在序列在序列中中, 假設(shè)我們從假設(shè)我們從0開場計(jì)算開場計(jì)算, 那么第那么第i項(xiàng)有項(xiàng)有i個元素。個元素。 這一序列的每這一序列的每一集合一集合, 以序列中在它之前的一切集協(xié)作為它的元素。以序列中在它之前的一切集協(xié)作為它的元素。 , , , , , , , ,第二章 集 合 例例 1 (a) 集合集合p,q有有4個不同子集個不同子集: p,q、p、q和和, 留意留意pp,q但但pp,q, pp,q但但pp,q。再者。再者p,q, 但但 (b) 集合集合q是單元素集合是單元素集合, 它的獨(dú)一元素是集合它的獨(dú)

13、一元素是集合q。每一。每一單元素集合恰有兩個子集單元素集合恰有兩個子集, q的子集是的子集是q和和 。 普通地普通地, n個元素的集合有個元素的集合有2n個不同的子集合個不同的子集合.,qp第二章 集 合 2.2 集合上的運(yùn)算集合上的運(yùn)算 2.2.1 并、并、 交和差運(yùn)算交和差運(yùn)算;定義定義 2.2-1 設(shè)設(shè)A和和B是集合。是集合。 (a) A和和B的并記為的并記為AB, 是集合。是集合。 AB=x|xAxB(b) A和和B的交記為的交記為AB, 是集合。是集合。 AB=x|xAxB (c) A和和B的差的差, 或或B關(guān)于關(guān)于A的相對補(bǔ)的相對補(bǔ), 記為記為A-B, 是集合。是集合。A-B=x|

14、xAxB 第二章 集 合 例例 1 設(shè)設(shè)A=a,b,c,d)和和B=b,c,e, 那么那么AB=a, b, c, d, e AB=b, c ;A-B=a, d ;B-A=e 第二章 集 合 定義定義 2.2-2 假設(shè)假設(shè)A和和B是集合是集合, AB=, 那么稱那么稱A和和B是不相是不相交的。假設(shè)交的。假設(shè)C是一個集合的族是一個集合的族, 使使C的恣意兩個不同元素都不相交的恣意兩個不同元素都不相交, 那么那么C是是(兩兩兩兩)不相交集合的族。不相交集合的族。 ; 例例 2 假設(shè)假設(shè)C=0, 1, 2, =i|iN, 那么那么C是不相交集是不相交集合的族。合的族。 定理定理 2.2-1 集合的并和

15、交運(yùn)算是可交換和可結(jié)合的。也就是集合的并和交運(yùn)算是可交換和可結(jié)合的。也就是對恣意對恣意A、B和和C。 ;(a) AB=BA ;(b) AB=BA ;(c) (AB)C=A(BC) ;(d) (AB)C=A(BC) ; 我們僅證明我們僅證明(a)和和(c), (b)和和(d)是類似的。是類似的。 第二章 集 合 證證(a) 設(shè)設(shè)x是論述域是論述域U的恣意元素的恣意元素, 那么那么 ABxAxBxBxAxBAx的定義 的可交換性 的定義 由于x是恣意的, 得 )(ABxBAxx即AB=BA 第二章 集 合 (c) 設(shè)x是恣意元素, 那么 xA(BC) xAx(BC) 的定義 xA(xBxC) 的定

16、義 (xAxB)xC 的結(jié)合律 x(AB)xC 的定義 x(AB)C 的定義由于x是恣意的, 得出 x(xA(BC)x(AB)C)因此, A(BC)=(AB)C。 第二章 集 合 定理定理 2.2-2 對恣意集合對恣意集合A、B和和C有有: ; (a) A(BC)=(AB)(AC) ; (b) A(BC)=(AB)(AC) =即集合運(yùn)算即集合運(yùn)算和和, 在在上可分配上可分配, 在在上可分配。上可分配。 ; 證證 設(shè)設(shè)x是恣意元素是恣意元素, 那么那么 xA(BC) xAx(BC) 的定義的定義 xA(xBxC) 的定義的定義 (xAxB)(xAxC) 在在上可分配上可分配 (xAB)(xAC)

17、 的定義的定義 x(AB)(AC) 的定義的定義因此因此, A(BC)=(AB)(AC)。 第二章 集 合 定理定理 2.2-3 設(shè)設(shè)A、B、C和和D是論述域是論述域U的恣意子集合的恣意子集合, 那么以那么以下斷言是真下斷言是真: ;(a) AA=A ;(b) AA=A ;(c) A=A ;(d) A= ;(e) A-=A ;(f) A-BA ;(g) 假設(shè)假設(shè)AB和和CD, 那么那么, (AC)(BD) ;(h) 假設(shè)假設(shè)AB和和CD, 那么那么, (AC)(BD) ;(i) AAB ;(j) ABA ;(k) 假設(shè)假設(shè)AB, 那么那么, AB=B ;(l) 假設(shè)假設(shè)AB, 那么那么, AB

18、=A 第二章 集 合 ABAAxBAxAxBxAxBAxfAAAAxxAAxxAxxxAxxAeAAAxAxAxxAxxxAxAxcAAAAxAxAxAAxa得因此即所以因此常真但所以因此于是常假因因此,.)(.,|,.|)(,.,)(.,)(第二章 集 合 (g) 設(shè)x是AC的恣意元素, 那么xAxC。如今分情況證明。 情況1: 設(shè)xA, 由于AB, 得xB, 所以xBxD, 因此xBD。 情況2: 設(shè)xC, 用與情況1類似的論證得xBD。 因此, xAC, 那么xBD。 所以ACBD。 (k) 因AB, 又BB根據(jù)(g)得ABBB, 但BB=B, 因此ABB。 另一方面由(i)得BAB。

19、所以, AB=B。 第二章 集 合 推論推論2.2-3 (a) AU=U, (b) AU=A。 ;本推論可由定理本推論可由定理2.2-3的的(k)(l)部分得出。部分得出。 ;2.2.2 補(bǔ)運(yùn)算補(bǔ)運(yùn)算 定義定義2.2-3 設(shè)設(shè)U是論述域而是論述域而A是是U的子集。的子集。A的的(絕對絕對)補(bǔ)補(bǔ), 記作記作A, 是集合是集合。 例例 3(a) 假設(shè)假設(shè)U=p,q,r,s和和A=p,q, 那么那么A =r,s。 (b) 假設(shè)假設(shè)U=N和和A=x|x0, 那么那么A=0。 (c) 假設(shè)假設(shè)U=I和和A=2x+1|xI, 那么那么A=2x|xI。 .|AxxAxUxxAUA第二章 集 合 定理 2.2

20、-4 設(shè)A是某論述域U的恣意子集, 那么AAbUAAa)()(證證 .,)(.,)(AAxFAxAxAAxaUAAUxTAxAAAxa所以所以第二章 集 合 定理 2.2-5 (補(bǔ)的獨(dú)一性)設(shè)A和B是論述域U的子集,那么B=A當(dāng)且僅當(dāng)AB=U和AB=。 證 必要性從定理 2.2-4 直接得到?，F(xiàn)證明充分性。 ; 設(shè)AB=和AB=U, 那么 B=UB =(A )B =(AB)( B) =( B) =( A)( B) = (AB) = U = AAAAAAAA第二章 集 合 推論推論2.2-5 證證 因因U=U和和U=, 所以所以, 。定理定理 2.2-6 設(shè)設(shè)A是是U的恣意子集的恣意子集, 那么

21、那么 。也就是說。也就是說, A的補(bǔ)的補(bǔ)的補(bǔ)是的補(bǔ)是A。 證證 由于由于 A=U和和 A=, 根據(jù)上一定理根據(jù)上一定理A是是 的補(bǔ)的補(bǔ),但但 A 也是的補(bǔ)也是的補(bǔ), 而補(bǔ)是獨(dú)一的而補(bǔ)是獨(dú)一的, 所以所以, 。UbUa)( ,)( AA AAUU和AA A第二章 集 合 定理定理2.2-7 (德德摩根定律摩根定律)設(shè)設(shè)A和和B是是U的恣意子集的恣意子集, 那么那么 BABAbBABAa_)()(證證 UBABBAABABABBAABABABA)()()()()()()()(a) 根據(jù)定理2.2-5, 是AB的補(bǔ), 但AB也是AB的補(bǔ), 而補(bǔ)是獨(dú)一的, 所以 (b)的證明是類似的, 故略。 )(B

22、ABABA_第二章 集 合 定理定理 2.2-8 設(shè)設(shè)A、B是是U的恣意子集的恣意子集, 假假設(shè)設(shè) ABBA則,證證 知由)(BxAxxBABxAx根據(jù)逆反律得 AxBxAxBxx是恣意的, 所以 ABAxBxx即)(第二章 集 合 圖 2.2-1 第二章 集 合 另外, 根據(jù)并、交、補(bǔ)等定義, 亦知命題演算中的、 、 、T、F等分別與集合論中的、-、 、U、 等有對應(yīng)關(guān)系, 因此, 有關(guān)它們的公式也有類似性。 例如命題演算中有公式 (PQ) PQ, PTP, 集合論中有對應(yīng)公式 ,_AUABABA又如命題演算中有范式等概念 PQR(PQR)(PQR)(PQR)假設(shè)需求, 在集合論中也可引入范

23、式等概念, 使 ABC=(ABC)(ABC)(ABC) 第二章 集 合 2.2.3 并和交運(yùn)算的擴(kuò)展并和交運(yùn)算的擴(kuò)展 擴(kuò)展后并和交運(yùn)算都定義在集合的搜集上。擴(kuò)展后并和交運(yùn)算都定義在集合的搜集上。 ; 定義定義 2.2-4 設(shè)設(shè)C是某論述域子集的搜集。是某論述域子集的搜集。 ; (a) C的成員的并、記為的成員的并、記為 , 是由下式指定的集合是由下式指定的集合 SCS)(|SxCSsxSCS(b) 假設(shè)C, C的成員的交, 記為 , 是下式指定的集合 SCS)(|SxCSsxSCS第二章 集 合 定義闡明假設(shè) , 那么x至少是一個子集SC的元素; 假設(shè) , 那么x是每一個子集SC的元素。留意對

24、 的定義來說, C必需非空, 否那么, 由于 , 蘊(yùn)含式SCxS對每一S將是無義地真。這樣, 謂詞 s(SCxS)對每一x是真。因此, 所定義的集合就是選集合U。要求 , 這個能夠消除。 SxCS SxCS SCSCC第二章 集 合 設(shè)D是一集合, 假設(shè)給定D的任一元素d, 就能確定一個集合Ad, 那么d叫做Ad的索引, 搜集C=Ad|dD叫做集合的加索引搜集; 而D叫做搜集的索引集合。當(dāng)D是一個搜集C的索引集合, 符號 表示 , 而 表示 。 dDdAdDdASCSSCS第二章 集 合 假設(shè)加索引搜集C的索引集合是前n+1個自然數(shù)0, 1, 2, , n, 或全體自然數(shù)0, 1, 2, ,

25、那么C的成員的并和交能用類似于和式概念的符號表示。 例如 常寫成時(shí)SAAAACCSn,210niniiniAAAAAA21000,或常寫成時(shí)SAAACCS,2102100,AAAAAiNiii或 普通地, 索引集合不用需是N的子集, 可以是恣意集合, 例如R+。第二章 集 合 例4 設(shè)論述域是實(shí)數(shù)R。 ; (a) 假設(shè)C=1,2,4,3,4,5,4,6,那么 =1, 2, 3, 4, 5, 6和 。 (b) 我們用0, a)表示集合x|0 xa。假設(shè)Sa=0,a), aR+, C=Sa|aR+, 那么 假設(shè)Sa=0,a), aI+, C=Sa|aI+, 那么 (c) 設(shè)C=Ai|ip,q,r,

26、 其中Ap=2,3, Aq=3,4, Ar=4,6; a,b表示x|axb, 那么SCS4SCS0), 0SSCSCS), 0)2 , 0) 1 , 01iiS).1 , 0)2 , 0) 1 , 01iiSirqpiirqpiAA,6 , 2第二章 集 合 2.2.4 環(huán)和與環(huán)積環(huán)和與環(huán)積 定義定義 2.2-5 A、B兩集合的環(huán)和兩集合的環(huán)和A B, 是集合是集合 |)()(AxBxBxAxxABBABA參看圖 2.2-2。環(huán)和又叫對稱差(Symmetric Difference)。 第二章 集 合 定理定理 2.2-9 )()()()(BABABABABA證證 由于由于 )()()()(B

27、ABAABABBAABBABA但 )()()()()(_BABABABABABA所以, )()()()(BABABABABA第二章 集 合 推論推論 2.2-9AAcABBAbBABAa)(,)(,)(定理定理 2.2-10 )()(CBACBA定理定理 2.2-11 )()()(BCACBAC第二章 集 合 以上兩個定理留給讀者自證。但留意并在環(huán)和上不可分配, 環(huán)和在交上不可分配。即, 通常 )()()()()()(CABACBACABACBA第二章 集 合 定義定義 2.2-6 A、B兩集合的環(huán)積兩集合的環(huán)積A B, 是集合是集合 |)()()()(_BxAxBxAxxBABAABBAAB

28、BABABA圖 2.2 - 2 第二章 集 合 定理定理 2.2-12 UAAcABBAbBABAa)( ,)( ,)(定理定理 2.2-13 )( )(CBACBA證證 )()()()()()()()()()(ABABBAABBABABABAABBABA所以所以, BABABA第二章 集 合 根據(jù)定理根據(jù)定理2.2-10 得得 )()(CBACBA兩邊取補(bǔ), 即得 )()(CBACBA定理定理 2.2-14 )()()(CABACBA請讀者自證第二章 集 合 2.2.5 冪集合冪集合 定義定義 2.2-7 設(shè)設(shè)A是一集合是一集合, A的冪集的冪集(A), 是是A的一切子集的的一切子集的集合集

29、合, 即即 |)(ABBA 一個給定集合的冪集是獨(dú)一的, 因此求一個集合的冪集是以集合為運(yùn)算對象的一元運(yùn)算。 第二章 集 合 例例 5 (a) 假設(shè)A=, 那么(A)=。(b) 假設(shè)A=a,b, 那么(A)=, a, b, a, b。 (c) 假設(shè)A是恣意自然數(shù)集合, 那么A(A), (A)。 下面闡明子集的二進(jìn)制數(shù)表示和冪集合的個數(shù)。 第二章 集 合 在集合的定義里, 沒有規(guī)定集合中元素的次序, 但為了便于在計(jì)算機(jī)上表示集合, 亦可給集合元素編定次序。例如,A=a,b,c, 無妨以為a, b, c分別是第一、 二、 三個元素。于是可用三位二進(jìn)制數(shù)做足標(biāo)表示A的恣意子集: 二進(jìn)制數(shù)的第i位表示

30、第i個元素能否屬于該子集, 1表示屬于, 0表示否。例如可用S101表示a,c, S011表 示 b , c , 三 位 二 進(jìn) 制 數(shù) 可 與 其 子 集 一 一 對 應(yīng) 。 因 此(A)=Si|iJ, 這里J=000,001,111。為了書寫方便, 可用十進(jìn)制數(shù)替代二進(jìn)制數(shù), 于是J=0,1, 2, , 7。普通地, n個元素的集合A, 可用n位二進(jìn)制數(shù)與其子集一一對應(yīng)。因此 12 , 2 , 1 , 0,|)(niJJiSA由此可知, n個元素的集合A, 其冪集的元素個數(shù)是 2n。 ; 假設(shè)A是無限集, 那么(A)的元素個數(shù)也是無限的。 第二章 集 合 *2.2.6 有限集的計(jì)數(shù)有限集的

31、計(jì)數(shù) 定理定理 2.2-15 設(shè)設(shè)A和和B都是有限集合都是有限集合, 那么以下公式成立那么以下公式成立: |2| )(|)(|)(|2|)(|)| |,min(|)(|)(AAeBABAdBABABAcBABAbBABABAa第二章 集 合 證證 A和和B之間能夠有公共元素之間能夠有公共元素, 公共元素個數(shù)是公共元素個數(shù)是|AB|, 在計(jì)在計(jì)算算|AB|時(shí)每個元素只計(jì)算一次時(shí)每個元素只計(jì)算一次, 但在計(jì)算但在計(jì)算|A|+|B|時(shí)時(shí), 公共元素計(jì)公共元素計(jì)算了二次算了二次, 一次在算一次在算|A| 時(shí)時(shí), 一次在算一次在算|B|時(shí)時(shí), 因此因此, 右邊減去右邊減去|AB|才干相等。證畢。才干相等

32、。證畢。 ; 公式公式(a)可以推行可以推行, 三個集合時(shí)為三個集合時(shí)為 |321313221321321AAAAAAAAAAAAAAA第二章 集 合 圖 2.2-3 第二章 集 合 普通地成立以下公式: |) 1(|21111121nnkjinkjininjijiinAAAAAAAAAAAA 證證 用歸納法證明用歸納法證明(未學(xué)過歸納法的同窗可在學(xué)完下節(jié)后未學(xué)過歸納法的同窗可在學(xué)完下節(jié)后, 再再看此證明看此證明)。 n=2時(shí)時(shí), 已證明成立已證明成立, 即即 |212121AAAAAA第二章 集 合 設(shè)n-1(n3)時(shí)公式成立, 現(xiàn)證明n時(shí)也成立。 |,|121121321nnnnnAAAA

33、AAAAAAAA根據(jù)歸納假設(shè)得|) 1(|) 1(|) 1(|211111121211111212111121nnjinjiniinnnnjinjinininnnjinjiniinAAAAAAAAAAAAAAAAAAAAAAAAA第二章 集 合 例例 6 (a) 在一個班級在一個班級50個學(xué)生中個學(xué)生中, 有有 26 人在第一次考試中得到人在第一次考試中得到A, 21人在第二次考試中得到人在第二次考試中得到A, 假設(shè)有假設(shè)有17 人兩次考試都沒有得到人兩次考試都沒有得到A, 問有多少學(xué)生在兩次考試中都得到問有多少學(xué)生在兩次考試中都得到A? 解解 設(shè)第一次考試得設(shè)第一次考試得A的是集合的是集合A

34、1, 第二次考試得第二次考試得A的是集合的是集合A2。那么那么 |331750|21212121AAAAAAAA但 所以 14332126|212121AAAAAA答: 兩次考試都得A的 14 人。 第二章 集 合 (b) 某教研室有30名教師, 可供他們選修的第二外語是日語、 法語、德語。知有 15 人進(jìn)修日語, 8 人選修法語, 6 人選修德語, 而且其中 3 人選修三門外語, 我們希望知道至少有多少人一門也沒有選修。 解 設(shè)A1、A2、A3分別表示選修日語、法語和德語的人, 因此 |323|6815|3| , 6| , 8| ,15|323121323121321321321AAAAAA

35、AAAAAAAAAAAAAAA第二章 集 合 由于 |321323213132121AAAAAAAAAAAAAAA我們得 2333332|321AAA即至多有 23 人在進(jìn)修第二外語, 因此至少有 7 人沒有進(jìn)修第二外語。第二章 集 合 2.3 歸納法和自然數(shù)歸納法和自然數(shù) 2.3.1 集合的歸納定義集合的歸納定義 在在2.1節(jié)引見了指定集合的兩種最常用方法節(jié)引見了指定集合的兩種最常用方法列列舉法和描畫法。但依然有許多集合難以用這兩種方法舉法和描畫法。但依然有許多集合難以用這兩種方法表示出來表示出來, 諸如算術(shù)表達(dá)式集合諸如算術(shù)表達(dá)式集合, 命題演算公式集合命題演算公式集合, ALGOL程序集

36、合等等程序集合等等, 這些集合用歸納定義來指定較這些集合用歸納定義來指定較為方便。歸納定義習(xí)慣上稱為遞歸定義。為方便。歸納定義習(xí)慣上稱為遞歸定義。 第二章 集 合 (1) 根底條款(簡稱根底)。 它指出某些事物屬于集合。它的功能是給集合以根本元素, 使所定義的集合非空。 ; (2) 歸納條款(簡稱歸納)。它指出由集合的已有元素構(gòu)造新元素的方法。 歸納條款的方式總是斷言: 假設(shè)事物 x,y, z是集合的元素, 那么用某種方法組合它們而成的一種新事物也在集合中。它的功能是指出為了構(gòu)造集合的新元素, 可以在事物上進(jìn)展的運(yùn)算。 (3) 極小性條款(簡稱極小性)。它斷言一個事物除非能有限次運(yùn)用根底和歸納

37、條款構(gòu)成外, 那么這個事物不是集合的成員。 第二章 集 合 集合S的歸納定義的極小性條款還有其它方式, 常見的有: ; (i) “集合S是滿足根底和歸納條款的最小集合。 ; (ii) “假設(shè)T是S的子集, 使T滿足根底和歸納條款, 那么T=S。 其意義是: S滿足根底和歸納條款, 但沒有S的真子集滿足它們。 這些極小性條款雖然方式不同, 結(jié)果是等價(jià)的, 全部效力于一個目的, 即指明崐所定義的集合是滿足根底和歸納條款的最小集合, 即通常所謂極小性。 第二章 集 合 例例 1 假設(shè)論述域是整數(shù)假設(shè)論述域是整數(shù)I, 那么能為那么能為3 整除的正整數(shù)集合整除的正整數(shù)集合S的謂詞定義如下的謂詞定義如下:

38、 )3(0|yxyxxS 同樣集合能歸納地定義如下: ; (1) (根底)3S, ; (2) (歸納)假設(shè)xS和yS, 那么x+yS, ; (3) (極小性)沒有一個整數(shù)是S的元素, 除非它是有限次運(yùn)用條款1和2得出的。 第二章 集 合 設(shè)表示一個有限的非空的符號(字符)集合、我們稱為字母表。由字母表中有限個字符拼接起來的符號串叫做字母表上的一個字(或叫串)。 例 2 (a) 假設(shè)=a,b, , z, 那么is, then都是上的字。 (b) 假設(shè)=他, 我, 人, 工, , 是, 那么“他是工人是上的串。 (c) 假設(shè)=a, b, , z, , 這里是代表空白。那么thatwaslongag

39、o是上的串, 習(xí)慣上印成that was long ago。 第二章 集 合 設(shè)x是上的一個字, 假設(shè)x=a1a2an, 這里nN, 對每一1in, ai, 那么x中的符號個數(shù)n稱為x的長度, 記為x。 長度為0的串表示為, 叫做空串。留意空串不是空白符, 前者長度為 0, 后者長度是1。假設(shè)x和y都是在上的符號串, x=a1a2an和y=b1b2bm, 這里, 對一切i和j, ai和bj, 那么x連結(jié)(或叫并置, 毗連)y, 記為xy, 是串 mnbbbaaaxy2121假設(shè)x=, 那么xy=y, 假設(shè)y=, 那么xy=x。假設(shè)z=xy, 那么x是z的詞頭, y是z的詞尾。假設(shè)xz, 那么x

40、是真詞頭; 假設(shè)yz, 那么y是真詞尾。假設(shè)w=xyz, 那么y是w的子串, 假設(shè)yw, 那么y是真子串。 第二章 集 合 定義定義2.3-1 設(shè)設(shè)是一個字母表是一個字母表, 上的非空串的集合上的非空串的集合+定義如定義如下下: (1) (根底根底)假設(shè)假設(shè)a, 那么那么a+。 (2) (歸納歸納)假設(shè)假設(shè)x+且且a, 那么那么ax+。 (ax表示串表示串, 它由它由符號符號a和串和串x連結(jié)組成連結(jié)組成)。 ; (3) (極小性極小性)集合集合+僅包含這些元素僅包含這些元素: 它能由有限次運(yùn)用條它能由有限次運(yùn)用條款款1和和2構(gòu)成。構(gòu)成。 集合集合+包含長度為包含長度為1, 2, 3, 的串的串

41、, 所以是無限集合。然而所以是無限集合。然而, 在在+中沒有一個串包含無限數(shù)目的符號中沒有一個串包含無限數(shù)目的符號, 這是極小性條款限制的這是極小性條款限制的結(jié)果。結(jié)果。 第二章 集 合 例例 3 假設(shè)假設(shè)=a,b, 那么那么+=a,b, aa,ab,ba,bb,aaa,aab,。 上的一切有限符號串的集合記為上的一切有限符號串的集合記為*。集合。集合*包含空串包含空串, 其其歸納定義如下歸納定義如下: 定義定義2.3-2 設(shè)設(shè)是字母表是字母表, 那么那么*定義如下定義如下: (1) (根底根底)*。 (2) (歸納歸納)假設(shè)假設(shè)x*和和a, 那么那么ax*。 (3) (極小性極小性)沒有一個

42、串可以是集合沒有一個串可以是集合*的元素的元素, 除非它能有限除非它能有限次運(yùn)用條款次運(yùn)用條款1和條款和條款2構(gòu)成。構(gòu)成。 當(dāng)然當(dāng)然, *也可這樣定義也可這樣定義: *=+ 第二章 集 合 例例 4 (a) 假設(shè)假設(shè)=a,b, 那么那么*=,a,b,aa,ab,。 (b) 假設(shè)假設(shè)=0,1, 那么那么*是有限二進(jìn)制序列的集合是有限二進(jìn)制序列的集合, 包括空包括空序列。序列。 歸納定義常用來描寫數(shù)學(xué)中的合式公式歸納定義常用來描寫數(shù)學(xué)中的合式公式, 或叫成形公式或叫成形公式(Well-Formed Formula)。這方面我們已見過一些例子。這方面我們已見過一些例子。 如第一如第一章的命題公式定義

43、和謂詞公式定義等。章的命題公式定義和謂詞公式定義等。第二章 集 合 例例 5 為簡明起見為簡明起見, 我們將算術(shù)表達(dá)式集合限制于僅包含整數(shù)我們將算術(shù)表達(dá)式集合限制于僅包含整數(shù), 一元運(yùn)算一元運(yùn)算+和和-, 和二元運(yùn)算和二元運(yùn)算+、 -、 *和和/。 (1) (根底根底) 假設(shè)假設(shè)D=0, 1, 2, 3, 4, 5, 6, 7, 8, 9和和xD+, 那么那么x是是一算術(shù)表達(dá)式。一算術(shù)表達(dá)式。 (2) (歸納歸納) 假設(shè)假設(shè)x和和y都是算術(shù)表達(dá)式都是算術(shù)表達(dá)式, 那么那么 (i) (+x) 是一算術(shù)表達(dá)式是一算術(shù)表達(dá)式, (ii) (-x) 是一算術(shù)表達(dá)式是一算術(shù)表達(dá)式, (iii) (x+y

44、) 是一算術(shù)表達(dá)式是一算術(shù)表達(dá)式, (iv) (x-y) 是一算術(shù)表達(dá)式是一算術(shù)表達(dá)式, (v) (x*y)是一算術(shù)表達(dá)式是一算術(shù)表達(dá)式, (vi) (x/y) 是一算術(shù)表達(dá)式。是一算術(shù)表達(dá)式。 第二章 集 合 (3) (極小性)一個符號序列是一算術(shù)表達(dá)式當(dāng)且僅當(dāng)它能得自有限次運(yùn)用條款1和2。 用 這 個 定 義 描 寫 的 算 術(shù) 表 達(dá) 式 集 合 包 括 4 5 , 0 0 0 , ( -321),(3+7),(3*(-35)和(+(-(+7/2)等, 不包括諸如+)和+6+之類的符號串。 有些歸納定義是以其它歸納定義的集協(xié)作根底建立起來的, 我們稱這樣的歸納定義為“二次歸納定義, 二次

45、歸納定義不需求極小性條款, 由于根底集合的極小性條款保證了所定義的集合的極小性。 作為根底集合最常見的是自然數(shù)集合N。因此, 以自然數(shù)集合為根底集合的歸納定義常不需極小性條款。 第二章 集 合 例例 6 設(shè)設(shè)aR+且且nN。an的歸納定義如下的歸納定義如下: (1) (根底根底)a0=1 (2) (歸納歸納)an+1=ana 這個歸納定義的根底集合是這個歸納定義的根底集合是N, 所以不需求極小性條款。所以不需求極小性條款。 程序設(shè)計(jì)言語程序設(shè)計(jì)言語, 諸如諸如ALGOL, 它們的語法也常用歸納定義它們的語法也常用歸納定義(以巴科斯范式方式給出以巴科斯范式方式給出)描畫描畫 第二章 集 合 2.

46、3.2 自然數(shù)自然數(shù)自然數(shù)可運(yùn)用后繼集合的概念歸納地定義。自然數(shù)可運(yùn)用后繼集合的概念歸納地定義。定義定義 2.3-3 設(shè)設(shè)A是恣意集合是恣意集合, A的后繼集合記為的后繼集合記為A, 定義為定義為 AAA第二章 集 合 例例 7 (a) a,b的后繼集合是的后繼集合是a,ba,b=a,b,a,b。(b) 的后繼集合是的后繼集合是=,。定義定義 2.3-4 自然數(shù)自然數(shù)N是如下集合是如下集合:(1) (根底根底)N。(2) (歸納歸納)假設(shè)假設(shè)nN, 那么那么nnN。(3) (極小性極小性)假設(shè)假設(shè) 且滿足條款且滿足條款1和和2, 那么那么S=N。 NS 第二章 集 合 按照這個定義, 自然數(shù)集

47、合的元素是: ,化簡后是 , , , , ,第二章 集 合 圖 2.3-1 第二章 集 合 能夠有人會想出這樣的定義: ;(1) (根底)0N, ;(2) (歸納)假設(shè)nN, 那么n+1N, ;(3) (極小性)假設(shè)SN且滿足條款(1)和(2), 那么S=N。 以上3條普通稱為歸納特征, 下邊可以看到它將協(xié)助我們對論述域N討論歸納證明, 但作為定義那么是不完善的。由于自然數(shù)的加法定義是建立在集合N上, 如今又用加法定義自然數(shù),這就犯了循環(huán)定義的錯誤, 所以定義自然數(shù)必需不用加法。 第二章 集 合 能夠有人會想: 用n來表示自然數(shù)n的“后繼者, 把第(2)條改為: (2) (歸納)假設(shè)nN, 那

48、么nN。 這樣總是可以了吧! 其實(shí)這樣也不行, 例如, 規(guī)定0=0, 即模型(圖2.3-2)也符合這個定義, 顯然不是自然數(shù)。 圖 2.3-2 第二章 集 合 這些想法也不是完全錯的, 只需再補(bǔ)上一些條款, 也可定義出自然數(shù)N?？蛇@樣定義: ; (1) 0N, (2) 假設(shè)nN, 那么恰存在一個n的后繼者nN, (3) 0 不是任何自然數(shù)的后繼者, ; (4) 假設(shè)n=m, 那么n=m, (5) 假設(shè)S是N的子集, 使, (i) 0S; ; (ii) 假設(shè)nS, 那么nS 第二章 集 合 那么, S=N。 ; 這就是有名的皮亞諾(Peano)公設(shè)。其中(2)保證后繼者是獨(dú)一的, (3)保證0只

49、作開端, (4)保證除0外的每一個自然數(shù)只需一個直接前趨。 常用(2)和(4)來檢查一個序列有沒有自然數(shù)性質(zhì)。例如, 序列0, 2, 4, , 1, 3, 5, 不具有自然數(shù)性質(zhì), 由于其中1沒有直接前趨。 第二章 集 合 2.3.3 歸納證明歸納證明 歸納定義不僅提供了定義無限集合的一種方法歸納定義不僅提供了定義無限集合的一種方法, 也為證明定也為證明定理構(gòu)成某些有效技術(shù)的根底。對于理構(gòu)成某些有效技術(shù)的根底。對于xP(x)方式的命題方式的命題, 假設(shè)其論述假設(shè)其論述域域S是歸納定義的集合是歸納定義的集合, 那么歸納法往往是有效的證明方法。歸那么歸納法往往是有效的證明方法。歸納法證明通常由根底

50、步驟和歸納步驟兩部分組成納法證明通常由根底步驟和歸納步驟兩部分組成, 它們分別對應(yīng)它們分別對應(yīng)于于S的定義的根底和歸納條款。的定義的根底和歸納條款。 (1) 根底步驟。這一步證明根底步驟。這一步證明S的定義中根底條款指定的每一元的定義中根底條款指定的每一元素素xS, P(x)是真。是真。 (2) 歸納步驟。這一步證明假設(shè)事物歸納步驟。這一步證明假設(shè)事物x,y,z,有性質(zhì)有性質(zhì)P, 那么用那么用歸納條款指定的方法歸納條款指定的方法, 組合它們所得的新元素也具有性質(zhì)組合它們所得的新元素也具有性質(zhì)P。 第二章 集 合 歸納定義的極小性條款保證S的一切元素僅僅運(yùn)用根底和歸納條款才干構(gòu)成, 因此證明了以

51、上兩步, 就足以推出 xP(x)。 如今舉例闡明這一方法?；叵攵ɡ?.2-1: “設(shè)A和A*是對偶式。 P1, P2, , Pn是出現(xiàn)于A和A*中的一切命題變元, 于是 A(P1,P2,Pn)A*( P1, P2, ,Pn) 第二章 集 合 由于根據(jù)對偶式定義, 公式A中僅含有結(jié)合詞、, 因此公式A可歸納定義如下: (1) Pi(1in)是公式; T是公式; F是公式。 (2) 假設(shè)A和B是公式, 那么A、(AB)、 (AB)是公式。 (3) 只需有限次運(yùn)用條款(1)和(2)生成的才是公式。 第二章 集 合 定理1.2-1是建立在歸納定義的公式集合上, 因此可以用上述普通的歸納法證明。 (1)

52、 (根底步驟)Pi Pi(1in), 所以當(dāng)A是由一個變元或常元構(gòu)成時(shí), 公式(1)成立。 (2) (歸納步驟) 設(shè)A1(P1,P2,Pn)、A2(P1,P2,Pn)對公式(1)成立, 即A1(P1,P2,Pn)A1* (P1, P2,Pn) A1(P1,P2,Pn)A1* (P1, P2,Pn)現(xiàn)證明: (A1A2) (A1A2) A1時(shí), 公式(1)也成立。 TFFT,第二章 集 合 情況情況1：.)()(2121AAAAA為記),(),(),(),(),(),(),(21*221*121221121221121nnnnnnnPPPAPPPAPPPAPPPAPPPAPPPAPPPAE11歸

53、納前提第二章 集 合 情況情況 2: (A1A2) 方法與情況方法與情況 1 類似類似, 留給讀者自證。留給讀者自證。情況情況3: A1記記A1為為A故對n個命題變元的一切公式, 公式(1)成立。 ),(),(),(),(21*21*121121nnnnPPPAPPPAPPPAPPPA第二章 集 合 但通常的歸納證明是涉及自然數(shù)的, 自然數(shù)具有以下歸納特征: (1) (根底)0N。 (2) (歸納)假設(shè)nN, 那么n+1N。 (3) (極小性)假設(shè) , 且S有以下性質(zhì): (i) 0S ; (ii) 對每一nN, 假設(shè)nS, 那么(n+1)S。那么, S=N。 NS 第二章 集 合 這里, 極小

54、性條款是習(xí)慣上用于自然數(shù)定義中的方式, 它叫做數(shù)學(xué)歸納法第一原理。我們適當(dāng)?shù)馗膭右幌逻@個條款的方式, 就可得到以自然數(shù)為論述域的xP(x)方式的斷言的歸納證明過程。 令S=n|P(n)是N的子集,于是極小性條款可改為“假設(shè)P(0)為真, n(P(n)P(n+1)為真, 那么, 對一切n, P(n)為真。根據(jù)這一條款, 立刻得出歸納證明的過程如下: 第二章 集 合 (1) (根底)先證明P(0)是真。可用恣意證明技術(shù)。 (2) (歸納)再證明n(P(n)P(n+1)是真。為此, 普通先假設(shè)“P(n)對恣意nN是真這叫歸納假設(shè)(或歸納前提), 由此再推出P(n+1) 也真, 一旦證明了P(n)P(

55、n+1)對恣意n是真, 用全稱推行規(guī)那么得n(P(n)P(n+1) 。 再根據(jù)數(shù)學(xué)歸納法第一原理得出xP(x)。 第二章 集 合 例例 8 證明對一切證明對一切nN , ninni02) 1(。 這里的定理是 nP(n)的方式。P(n)是斷言 ninni02) 1(證證(1) (根底根底)證明證明P(0)由于由于 nii0,2) 10(0即0=0, 顯然成立。 第二章 集 合 (2) (歸納)證明n(P(n)P(n+1)。 假設(shè)對一切nN,P(n)是真,即 我們希望證明P(n+1), 也就是ninni0,2) 1(102)2)(1(ninni由于 2)2)(1(2) 1() 1() 1(010

56、nnnnnininini第二章 集 合 而n是恣意的, 得出n(P(n)P(n+1), 運(yùn)用歸納法第一原理得 xP(x), 即對一切自然數(shù)n, 成立。 ninni02) 1( 數(shù)學(xué)歸納法第一原理, 現(xiàn)實(shí)上是自然數(shù)域上的一個推理規(guī)那么。 用1.5節(jié)的符號, 規(guī)那么的方式如下: )()1()()0(xxPnPnPnP第二章 集 合 )()()()1()()(knxPkxxnPnPnkP 規(guī)那么可以有各種變形, 例如, 我們通常希望證明對某整數(shù)k, 謂詞P對一切xk成立。這時(shí), 根底步驟必需換為證明P(k)。于是推理規(guī)那么是: 容易證明這兩種方式的推理規(guī)那么是等價(jià)的。 第二章 集 合 例例 9 證明

57、證明n4 時(shí)時(shí), 2nn2 證證(1) (根底根底)n=5 時(shí)時(shí), 2552, 顯然成立。顯然成立。 (2) (歸納歸納)設(shè)設(shè)n時(shí)時(shí), 2nn2成立成立, 現(xiàn)證現(xiàn)證n+1 時(shí)命題也成立時(shí)命題也成立, 這里這里n5。 由于由于 2n+1 =22n 2n2 (根據(jù)歸納假設(shè)根據(jù)歸納假設(shè)) n2+5n n+2n+1 =(n+1)2 所以所以, 對一切對一切n4, 2nn2。 征畢。征畢。 假設(shè)令假設(shè)令n=m+5, 上題就成為上題就成為“證明對一切自然數(shù)證明對一切自然數(shù)m, 2m+5(m+5)2, 這樣這樣, 此題就成為根本方式了。此題就成為根本方式了。 第二章 集 合 例例 10 設(shè)設(shè)an如本節(jié)例如本

58、節(jié)例6 所定義所定義, 試證明試證明 證證 設(shè)設(shè)m是恣意的是恣意的, 對對n作歸納作歸納, 證明斷言證明斷言n(aman=am+n)。 (1) (根底根底)假設(shè)假設(shè)n=0, 那么那么aman=ama0=am1=am=am+0=am+n (2) (歸納歸納)設(shè)設(shè)aman=am+n對恣意對恣意n成立成立, 那么那么anan+1=am(ana) an的定義的定義 =(aman)a 乘法結(jié)合律乘法結(jié)合律 =(am+n)a 歸納假設(shè)歸納假設(shè) =a (m+n)+1 an的定義的定義 =am+(n+1) 加法結(jié)合律加法結(jié)合律所以所以, naman=am+n。 )(nmnmaaanm第二章 集 合 由于m是恣

59、意的, 由全稱推行規(guī)那么得nmnmaaanm 自然數(shù)域上的歸納法證明還有另一方式, 稱為數(shù)學(xué)歸納法第二原理, 第二原理作為推理規(guī)那么的方式如下: )()()(xxPnPkPnkkn運(yùn)用這一推理規(guī)那么的證明的歸納假設(shè)是 )(kPnkk第二章 集 合 即對一切kn, P(k)是真。從這一假設(shè)出發(fā), 我們必需證明P(n)。 一旦在歸納假設(shè)的前提下證明了P(n), 就可得出 xP(x)。 ; 運(yùn)用第二原理僅需我們證明單一的前提, 但它通常需求分情況證明。 首先證明n=0的情況。 n=0時(shí), k0 對一切kN常假, 所以kk0P(k)常真。所以, 證明kk0P(k)P(0)是真, 等價(jià)于證明P(0)是真

60、。 第二章 集 合 其次證明: 對恣意n0, 假設(shè)P(k)對一切kn成立, 那么P(n)是真。 這樣, 用第二原理證明和用第一原理證明的獨(dú)一不同是: 用“對一切kn, P(k) 是真的歸納假設(shè)替代“P(n-1)是真的歸納假設(shè)。 雖然兩個數(shù)學(xué)歸納法原理是不同的, 但假設(shè)論述域是自然數(shù)N, 那么它們的前提是邏輯等價(jià)的, 因此它們也是等效的。 但有其它論述域存在, 那里第二原理更有效。 通常, 假設(shè)證明P(n+1)為真, 即證明元素n+1具有性質(zhì)P, 不僅能夠依賴于元素n的性質(zhì), 還能夠依賴于n以前各元素的性質(zhì)時(shí), 應(yīng)選用第二原理。第二原理和第一原理一樣, 也有各種變形。 第二章 集 合 例11 有