集合是數(shù)學(xué)中最基本的概念

1、第二章 集合集合是數(shù)學(xué)中最基本的概念，又是數(shù)學(xué)各分支、自然科學(xué)及社會科學(xué)各領(lǐng)域的最普遍采用的描述工具。集合論是離散數(shù)學(xué)的重要組成部分，是現(xiàn)代數(shù)學(xué)中占有獨(dú)特地位的一個分支。G. Cantor(康脫)是作為數(shù)學(xué)分支的集合論的奠基人。1870年前后，他關(guān)于無窮序列的研究導(dǎo)致集合論的系統(tǒng)發(fā)展。1874年他發(fā)表了關(guān)于實(shí)數(shù)集合不能與自然數(shù)集合建立一一對應(yīng)的有名的證明。1878年，他引進(jìn)了兩個集合具有相等的“勢”的概念。然而，樸素集合論中包含著悖論。第一個悖論是布拉利-福爾蒂的最大序數(shù)悖論。1901年羅素發(fā)現(xiàn)了有名的羅素悖論。1932年康脫也發(fā)表了關(guān)于最大基數(shù)的悖論。集合論的現(xiàn)代公理化開始于1908年策梅羅

2、所發(fā)表的一組公理，經(jīng)過弗蘭克爾的加工，這個系統(tǒng)稱為策梅羅-弗蘭克爾集合論（ZF），其中包括1904年策梅羅引入的選擇公理。另外一種系統(tǒng)是馮·諾伊曼-伯奈斯-哥德爾集合論。公理集合論中一個有名的猜想是連續(xù)統(tǒng)假設(shè)（CH）。哥德爾證明了連續(xù)統(tǒng)假設(shè)與策梅羅-弗蘭克爾集合論的相容性，科恩證明了連續(xù)統(tǒng)假設(shè)與策梅羅-弗蘭克爾集合論的獨(dú)立性?，F(xiàn)在把策梅羅-弗蘭克爾集合論與選擇公理一起稱為ZFC系統(tǒng)。本部分主要介紹樸素集合論的主要內(nèi)容，其中包括集合代數(shù)（第二章）、二元關(guān)系（第三章）、函數(shù)（第四章）、無限集合（集合的基數(shù)）（第五章）等。2.1 集合論的基本概念2.1.1 集合的概念集合不能精確定義。集合

3、可以描述為：一個集合把世間萬物分成兩類,一些對象屬于該集合，是組成這個集合的成員，另一些對象不屬于該集合?？梢哉f，由于一個集合的存在，世上的對象可分成兩類，任一對象或?qū)儆谠摷匣虿粚儆谠摷?，二者必居其一也只居其一。直觀地說，把一些事物匯集到一起組成一個整體就叫集合，而這些事物就是這個集合的元素或成員。例如：方程x210的實(shí)數(shù)解集合；26個英文字母的集合；坐標(biāo)平面上所有點(diǎn)的集合；集合通常用大寫的英文字母A,B,C,來標(biāo)記，元素通常用小寫字母a,b,c,來表示。例如自然數(shù)集合N(在離散數(shù)學(xué)中認(rèn)為0也是自然數(shù))，整數(shù)集合Z，有理數(shù)集合Q，實(shí)數(shù)集合R，復(fù)數(shù)集合C等。集合的表示方法：表示一個集合的方法

4、通常有三種：列舉法、描述法和歸納定義法。(1) 列舉法 列出集合的所有元素，元素之間用逗號隔開，并把它們用花括號括起來。在能清楚地表示集合成員的情況下可使用省略號。例如 A=a，b，c，z，Z=0，±1，±2，都是合法的表示。(2) 描述法 用謂詞來概括集合中元素的屬性來表示這個集合。例如 Bx|xRx210表示方程x210的實(shí)數(shù)解集。許多集合可以用兩種方法來表示，如B也可以寫成-1，1。但是有些集合不可以用列元素法表示，如實(shí)數(shù)集合。(3) 歸納定義法：2.3節(jié)再討論。屬于、不屬于：元素和集合之間的關(guān)系是隸屬關(guān)系，即屬于或不屬于，屬于記作，不屬于記作。例如Aa，b，c，d，

5、d，這里aA，b，cA，dA，dA，但bA，dA。b和d是A的元素的元素。外延公理：兩個集合A和B相等，當(dāng)且僅當(dāng)它們有相同的成員。集合的元素是彼此不同的：如果同一個元素在集合中多次出現(xiàn)應(yīng)該認(rèn)為是一個元素。如 1，1，2，2，31，2，3。集合的元素是無序的：如1，2，33，1，2。2.1.2 羅素悖論1901年羅素提出以下悖論：設(shè)論述域是所有集合的集合，并定義集合。這樣，S是不以自身為元素的全體集合的集合，那么“S”是不是它自己的元素呢？假設(shè)S不是自己的元素，那么S滿足謂詞，而該謂詞定義了集合S，所以。另一方面，如果，那么S必須滿足定義S的謂詞，所以。這樣導(dǎo)致了一個類似于謊言悖論的矛盾：既非，

6、也非。羅素悖論起因于集合可以是自己的元素的概念。康脫以后創(chuàng)立的許多公理化集合論都直接或間接地限制集合成為它自己的元素，因而避免了羅素悖論。2.1.3 集合間的包含關(guān)系 設(shè)A，B為集合，如果B中的每個元素都是A中的元素，則稱B是A的子集合，簡稱子集。這時(shí)也稱B被A包含，或A包含B，記作BA。稱B是A的擴(kuò)集。包含的符號化表示為：BAx(xBxA)。如果B不被A包含，則記作BA。例如 NZQRC，但ZN。顯然對任何集合A都有AA。注意：屬于關(guān)系和包含關(guān)系都是兩個集合之間的關(guān)系，對于某些集合可以同時(shí)成立這兩種關(guān)系。例如Aa，a和a，既有aA，又有aA。前者把它們看成是不同層次上的兩個集合，后者把它們看

7、成是同一層次上的兩個集合，都是正確的。 設(shè)A，B為集合，如果BA且BA，則稱B是A的真子集，記作BA。如果B不是A的真子集，則記作BA。真子集的符號化表示為：BABABA。例如 NZQRC，但NN。為方便起見，所討論的全部集合和元素是限于某一論述域中，即使這個論述域有時(shí)沒有明確地指出，但表示集合元素的變元只能在該域中取值。此論述域常用U表示，并稱為全集。 不含任何元素的集合叫空集，記作?？占梢苑柣硎緸閤|xx。例如x|xRx2+1=0是方程x2+1=0的實(shí)數(shù)解集，因?yàn)樵摲匠虩o實(shí)數(shù)解，所以是空集。定理2.1-1 空集是一切集合的子集。證：對任何集合A，由子集定義有，右邊的蘊(yùn)涵式因前件為假而

8、為真命題，所以也為真。推論 空集是唯一的。證：假設(shè)存在空集和，由定理6.1有，。根據(jù)集合相等的定義，有。含有n個元素的集合簡稱n元集，它的含有m(mn)個元素的子集叫做它的m元子集。任給一個n元集，怎樣求出它的全部子集呢？舉例說明如下。例 A1,2,3，將A的子集分類：0元子集，也就是空集，只有一個：；1元子集，即單元集：1，2，3；2元子集：1,2，1,3，2,3； 3元子集：1,2,3。一般地說，對于n元集A，它的0元子集有個，1元子集有個，m元子集有個，n元子集有個。子集總數(shù)為個。全集與空集在本章中起重要作用，注意掌握它們的基本概念。注意：與的聯(lián)系與區(qū)別。(1) 表示集合的元素（可以為集

9、合）與集合本身的從屬關(guān)系，(2) 表示兩個集合之間的包含關(guān)系。例如：對于集合A=a,b,c,a是A的子集：aA，a是A的元素：aA。注意：不要寫成aA和aA。，但；是一元集，而不是空集。，。本節(jié)要求：熟練掌握集合、集合的子集、包含、相等、空集、全集、冪集等概念及其符號化表示。2.2 集合上的運(yùn)算2.2.1 集合的交、并和差運(yùn)算1. 集合交、并、差運(yùn)算的定義（注意集合運(yùn)算與邏輯運(yùn)算的對應(yīng)關(guān)系） 設(shè)和是集合，(1) 和的交記為，定義為：；(2) 和的并記為，定義為：；(3) 和的差記為，定義為：。例：設(shè)，則，定義：如果是兩個集合，那么稱和是不相交的。如果是一個集合的族，且中的任意兩個不同元素都不相

10、交，那么稱是（兩兩）不相交集合的族。2. 集合的并和交運(yùn)算的推廣（廣義交、廣義并）個集合 ，無窮可數(shù)個集合： ，一般情形： （），3. 集合交、并、差運(yùn)算的性質(zhì)：(1) 交換律 ， ，(2) 結(jié)合律 ， .(3) 分配律 ， (4) 冪等律 , ,(5) 同一律 , ，(6) 零 律 ,(7) 吸收律 ， ，(8) 德摩根律 (9) (a) , (b) , (c), (d),(e) 若，,則，,(f) 若，則, (g) 若，則，(h) 。證：利用運(yùn)算的定義（與邏輯運(yùn)算的關(guān)系）或已證明的性質(zhì)。2.2.2 集合的補(bǔ)運(yùn)算1. 集合的補(bǔ)運(yùn)算的定義定義：設(shè)是論述域而是的子集，則的（絕對）補(bǔ)為：當(dāng)且僅當(dāng)和

11、。2. 集合補(bǔ)運(yùn)算的性質(zhì)：(1) 矛盾律 ； (2) 排中律 ；(3) 德摩根律 ， ， ， ；(4) 雙重否定律（的補(bǔ)的補(bǔ)是）：；(5) 若，則。例：證明A(BC)(AB)( AC)。證對任意的x，xA(BC) xAxBC xA(xBxC) xA(xBxC) xAxBxC (xAxB)(xAxC) xAB)xAC x(AB)(AC)所以 A(BC)(AB)( AC)。例：證明AEA。證對任意的x，xAExAxExA(因?yàn)閤E是恒真命題)，所以AEA。注意：以上證明的基本思想是：設(shè)P，Q為集合公式，欲證PQ，即證PQQP為真。也就是要證對于任意的x有 xPxQ和xQxP成立。對于某些恒等式可以

12、將這兩個方向的推理合到一起，就是 xPxQ。不難看出，集合運(yùn)算的規(guī)律和命題演算的某些規(guī)律是一致的，所以命題演算的方法是證明集合恒等式的基本方法。證明集合恒等式的另一種方法是利用已知的恒等式來代入。例：證明A(AB)A。證 A(AB)(AE)(AB)A(EB)A(BE)AEA。例：證明等式ABAB。證對于任意的x，xABxAxBxAxBxAB，所以ABAB。注意：上式把相對補(bǔ)運(yùn)算轉(zhuǎn)換成交運(yùn)算，這在證明有關(guān)相對補(bǔ)的恒等式中是很有用的。例：證明(AB)BAB證 (AB)B(AB)B(AB)(BB)(AB)EAB。例：證明命題ABBABAAB。證(1) 證ABBAB，對于任意的x，xAxAxBxABx

13、B(因?yàn)锳BB)，所以AB。(2) 證ABABA。顯然有ABA，下面證AAB，對于任意的x，xAxAxAxAxB(因?yàn)锳B) xAB，由集合相等的定義有ABA。(3) 證ABAAB。ABAB(AB)B(因?yàn)锳BA)A(BB)A。(4) 證ABABB。ABB(AB)BB。注意：上式給出了AB的另外三種等價(jià)的定義，這不僅為證明兩個集合之間的包含關(guān)系提供了新方法，同時(shí)也可以用于集合公式的化簡。例：化簡(ABC)(AB)(A(BC)A)。解因?yàn)锳BABC，AA(BC)，故有(ABC)(AB)(A(BC)A)(AB)ABA。2.2.3 環(huán)和與環(huán)積定義：兩集合的環(huán)和（對稱差）和環(huán)積定義為：環(huán)和： 環(huán)積：2

14、. 環(huán)和與環(huán)積的性質(zhì)：(1) ，(2) ， ， (3) ， ；(4) ， ，(5) ，(6) , , ，(7) ， .例：已知ABAC，證明BC。證 已知ABAC，所以有A(AB)A(AC) (AA)B(AA)CBCBCBC。3. 集合運(yùn)算的文氏圖表示（教材P62圖2.2-1）注意：如果沒有特殊說明，任何兩個集合都畫成相交的。2.2.4 冪集合定義：設(shè)是一個集合，的冪集是的所有子集的集合，即。若是元集，則有個元素。例：若，則；若，則。對任意集合：，。集合運(yùn)算的順序：為了使得集合表達(dá)式更為簡潔，我們對集合運(yùn)算的優(yōu)先順序做如下規(guī)定：稱廣義交，廣義并，冪集，絕對補(bǔ)運(yùn)算為一類運(yùn)算，交，并，補(bǔ)，環(huán)和，環(huán)

15、積運(yùn)算為二類運(yùn)算。一類運(yùn)算優(yōu)先于二類運(yùn)算；一類運(yùn)算之間由右向左順序進(jìn)行；二類運(yùn)算之間由括號決定先后順序。2.2.5 有限集的計(jì)數(shù)定理2.2-1 設(shè)都是有限集合，則以下公式成立：(a) , (b) ,(c) ，(d) , (e) , (f) 。使用文氏圖可以很方便地解決有窮集的計(jì)數(shù)問題。首先根據(jù)已知條件把對應(yīng)的文氏圖畫出來。一般地說，每一條性質(zhì)決定一個集合。有多少條性質(zhì)，就有多少個集合。如果沒有特殊說明，任何兩個集合都畫成相交的，然后將已知集合的元素?cái)?shù)填入表示該集合的區(qū)域內(nèi)。通常從個集合的交集填起，根據(jù)計(jì)算的結(jié)果將數(shù)字逐步填入所有的空白區(qū)域。如果交集的數(shù)字是未知的，可以設(shè)為。根據(jù)題目中的條件，列

16、出一次方程或方程組，就可以求得所需要的結(jié)果。例：對24名會外語的科技人員進(jìn)行掌握外語情況的調(diào)查。其統(tǒng)計(jì)結(jié)果如下：會英、日、德和法語的人分別為13，5，10和9人，其中同時(shí)會英語和日語的有2人，會英、德和法語中任兩種語言的都是4人。已知會日語的人既不懂法語也不懂德語，分別求只會一種語言(英、德、法、日)的人數(shù)和會三種語言的人數(shù)。解：設(shè)，同時(shí)會英、法和德語的人為個，只會英、法和德語的人分別為個，根據(jù)題意畫出文氏圖如圖2.1所示。由已知條件列出方程組如下：解得，。 圖2.1 圖2.2例：求1到1000之間(包含1和1000在內(nèi))既不能被5和6，也不能被8整除的數(shù)有多少個。 解 設(shè)，用表示小于等于的最

17、大整數(shù)，表示的最小公倍數(shù)，則， ， ， ， 。將這些數(shù)字依次填入文氏圖，得到圖2.2，由圖可知，不能被5，6和8整除的數(shù)有1000(200+1003367)600 個。本節(jié)要求：(1) 熟練掌握集合的交、并、差、補(bǔ)、廣義交、廣義并、環(huán)和、環(huán)積等運(yùn)算的定義及性質(zhì)；(2) 掌握集合的文氏圖的畫法及利用文氏圖解決有限集的計(jì)數(shù)問題的方法；(3) 牢記基本的集合恒等式，并能準(zhǔn)確地用邏輯演算或利用已知的集合恒等式或包含式證明新的等式或包含式。2.3 歸納法2.3.1 集合的歸納定義一個集合的歸納定義由部分組成：（1） 基礎(chǔ)條款（簡稱基礎(chǔ)）：它指出某些事物屬于集合，它的功能是給集合以基本元素，使所定義的集合

18、非空。（2） 歸納條款（簡稱歸納）：它指出由集合的已有元素構(gòu)造新元素的方法。歸納條款的形式總是斷言：如果事物是集合的元素，那么用某種方法組合它們而成的一種新事物也在集合中。它的功能是指出為了構(gòu)造集合的新元素，能夠在事物上進(jìn)行的運(yùn)算。（3） 極小性條款（簡稱極小性）：它斷言一個事物除非能有限次應(yīng)用基礎(chǔ)和歸納條款構(gòu)成外，那么這個事物不是集合的成員。例：教材P70-72例1例6。2.3.2 自然數(shù)自然數(shù)可以應(yīng)用后繼集合的概念歸納地定義。定義：設(shè)是任意集合，的后繼集合記為，定義為。例：的后繼集合是。的后繼集合是；的后繼集合是。定義：自然數(shù)是如下集合：(1) （基礎(chǔ)）；(2) （歸納）如果，那么；(3)

19、 （極小性）如果，且滿足條款(1)和(2)，那么。皮亞諾(Peano)公設(shè)： 自然數(shù)可以按如下定義：(1) ；(2) 如果，那么恰存在一個的后繼者；(3) 不是任何自然數(shù)的后繼者；(4) 如果，那么；(5) 如果，使(i)，(ii)若，則；那么。2.3.3 歸納證明對于形式的命題，如果其論述域是歸納定義的集合，則歸納法往往是有效的證明方法。歸納法證明通常由基礎(chǔ)步驟和歸納步驟兩部分組成，它們分別對應(yīng)于的定義的基礎(chǔ)和歸納條款。（1） 基礎(chǔ)步驟：這一步證明的定義中的基礎(chǔ)條款指定的每一元素，是真；（2） 歸納步驟：證明如果事物有性質(zhì)，那么用歸納條款指定的方法，組合它們所得的新元素也具有性質(zhì)。歸納定義的

20、極小性條款保證的所有元素僅僅應(yīng)用基礎(chǔ)條款和歸納條款才能構(gòu)成，因此證明了以上兩步，就足以推出。自然數(shù)具有以下歸納特征：（1）（基礎(chǔ)）；（2）（歸納）如果，那么；（3）（極小性）如果，且滿足：(i)，(ii) 對，若，則；那么。數(shù)學(xué)歸納法第一原理：利用數(shù)學(xué)歸納法第一原理的歸納證明過程：（1） （基礎(chǔ)）先證明是真，可用任意證明技術(shù)；（2） （歸納）證明是真。數(shù)學(xué)歸納法第一原理作為推理規(guī)則的形式如下：例：教材P75-76例8-例10。數(shù)學(xué)歸納法第二原理：作為推理規(guī)則的形式如下：證明過程：（1）（基礎(chǔ)）證明是真，（時(shí)，對一切永假，所以永真，所以證明是真等價(jià)于證明是真）（2）（歸納）證明當(dāng)對一切，為真時(shí)，

21、為真。例：教材P77例11。本節(jié)要求：(1) 掌握集合和自然數(shù)的歸納定義方法；(2) 掌握并熟練運(yùn)用數(shù)學(xué)歸納法第一原理和第二原理。2.5 集合的笛卡爾乘積 由兩個元素x和y（允許x=y）組成的序列記作<x,y>，稱為二重組或有序?qū)蛐蚺?，其中x是它的第一元素（分量），y是它的第二元素（分量）。有序?qū)?lt;x,y>具有以下性質(zhì)：1當(dāng)xy時(shí)，<x,y><y,x>； 2<x,y>=<u,v>的充分必要條件是x=u且y=v。注意：這些性質(zhì)是二元集x,y所不具備的。例如當(dāng)xy時(shí)有x,y=y,x。原因在于有序?qū)χ械脑厥怯行虻?，而集合中?/p>

22、元素是無序的。 已知<x+2,4>=<5,2x+y>，求x和y。解 由有序?qū)ο嗟鹊某湟獥l件有x+2=5，2x+y=4，解得x=3，y=-2。 設(shè)是個元素，定義為重組。注意：重組是一個二重組，其中第一個分量是重組。如代表而不代表，按定義后者不是三重組，并且。重組與相等當(dāng)且僅當(dāng)，。 設(shè)A，B為集合，用A中元素為第一元素，B中元素為第二元素構(gòu)成有序?qū)?。所有這樣的有序?qū)M成的集合叫做A和B的笛卡兒積（叉積），記作A×B。笛卡兒積的符號化表示為A×B=<x,y>|xAyB。集合（）的叉積記為或，定義為設(shè)A=a,b, B=0,1,2，則A×

23、B=<a,0>,<a,1>,<a,2>,<b,0>,<b,1>,<b,2>；B×A=<0,a>,<0,b>,<1,a>,<1,b>,<2,a>,<2,b>。由排列組合的知識不難證明，如果|A|=m，|B|=n，則|A×B|=mn。笛卡兒積的運(yùn)算性質(zhì)(1).對任意集合A，根據(jù)定義有 A×=, ×A=；(2).一般地說，笛卡兒積運(yùn)算不滿足交換律，即A×BB×A(當(dāng)ABAB時(shí))；(3)笛卡兒積運(yùn)算不

24、滿足結(jié)合律，即(A×B)×CA×(B×C)(當(dāng)ABC時(shí))；(4).笛卡兒積運(yùn)算對并和交運(yùn)算滿足分配律，即A×(BC)=(A×B)(A×C)； (BC)×A=(B×A)(C×A)；A×(BC)=(A×B)(A×C)； (BC)×A=(B×A)(C×A)。我們證明其中第一個等式。證 任取<x,y>，<x,y>A×(BC) xAyBCxA(yByC)(xAyB)(xAyC)<x,y>A×B<x,y>A×C<x,y>(A×BA×C)所以有 A×(BC