集合是數學中最基本的概念

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

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

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

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

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

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

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

8、為真命題，所以也為真。推論 空集是唯一的。證：假設存在空集和，由定理6.1有，。根據集合相等的定義，有。含有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元子集有個。子集總數為個。全集與空集在本章中起重要作用，注意掌握它們的基本概念。注意：與的聯系與區(qū)別。(1) 表示集合的元素（可以為集

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

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

11、。2. 集合補運算的性質：(1) 矛盾律 ； (2) 排中律 ；(3) 德摩根律 ， ， ， ；(4) 雙重否定律（的補的補是）：；(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(因為xE是恒真命題)，所以AEA。注意：以上證明的基本思想是：設P，Q為集合公式，欲證PQ，即證PQQP為真。也就是要證對于任意的x有 xPxQ和xQxP成立。對于某些恒等式可以

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

13、B(因為ABB)，所以AB。(2) 證ABABA。顯然有ABA，下面證AAB，對于任意的x，xAxAxAxAxB(因為AB) xAB，由集合相等的定義有ABA。(3) 證ABAAB。ABAB(AB)B(因為ABA)A(BB)A。(4) 證ABABB。ABB(AB)BB。注意：上式給出了AB的另外三種等價的定義，這不僅為證明兩個集合之間的包含關系提供了新方法，同時也可以用于集合公式的化簡。例：化簡(ABC)(AB)(A(BC)A)。解因為ABABC，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)積的性質：(1) ，(2) ， ， (3) ， ；(4) ， ，(5) ，(6) , , ，(7) ， .例：已知ABAC，證明BC。證 已知ABAC，所以有A(AB)A(AC) (AA)B(AA)CBCBCBC。3. 集合運算的文氏圖表示（教材P62圖2.2-1）注意：如果沒有特殊說明，任何兩個集合都畫成相交的。2.2.4 冪集合定義：設是一個集合，的冪集是的所有子集的集合，即。若是元集，則有個元素。例：若，則；若，則。對任意集合：，。集合運算的順序：為了使得集合表達式更為簡潔，我們對集合運算的優(yōu)先順序做如下規(guī)定：稱廣義交，廣義并，冪集，絕對補運算為一類運算，交，并，補，環(huán)和，環(huán)

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

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

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

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

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

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

21、為真。例：教材P77例11。本節(jié)要求：(1) 掌握集合和自然數的歸納定義方法；(2) 掌握并熟練運用數學歸納法第一原理和第二原理。2.5 集合的笛卡爾乘積 由兩個元素x和y（允許x=y）組成的序列記作<x,y>，稱為二重組或有序對或序偶，其中x是它的第一元素（分量），y是它的第二元素（分量）。有序對<x,y>具有以下性質：1當xy時，<x,y><y,x>； 2<x,y>=<u,v>的充分必要條件是x=u且y=v。注意：這些性質是二元集x,y所不具備的。例如當xy時有x,y=y,x。原因在于有序對中的元素是有序的，而集合中的

22、元素是無序的。 已知<x+2,4>=<5,2x+y>，求x和y。解 由有序對相等的充要條件有x+2=5，2x+y=4，解得x=3，y=-2。 設是個元素，定義為重組。注意：重組是一個二重組，其中第一個分量是重組。如代表而不代表，按定義后者不是三重組，并且。重組與相等當且僅當，。 設A，B為集合，用A中元素為第一元素，B中元素為第二元素構成有序對。所有這樣的有序對組成的集合叫做A和B的笛卡兒積（叉積），記作A×B。笛卡兒積的符號化表示為A×B=<x,y>|xAyB。集合（）的叉積記為或，定義為設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。笛卡兒積的運算性質(1).對任意集合A，根據定義有 A×=, ×A=；(2).一般地說，笛卡兒積運算不滿足交換律，即A×BB×A(當ABAB時)；(3)笛卡兒積運算不

24、滿足結合律，即(A×B)×CA×(B×C)(當ABC時)；(4).笛卡兒積運算對并和交運算滿足分配律，即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