第3章-集合論.ppt

1、第二篇 集合論,集合論是現(xiàn)代各科數(shù)學的基礎，它的起源可追溯到16世紀末期，那時為了建立微積分的可靠基礎，人們對數(shù)集進行了研究。直到19世紀末，Cantor發(fā)表了一系列有關集合的論文，基本奠定了集合論的基礎。不過，隨后數(shù)學哲學中提出各種悖論，致使集合論的發(fā)展一度陷入困境。幸好不久，策墨羅(Zermelo)出現(xiàn)了，他提出了集合論的一整套公理體系，使數(shù)學哲學中所產(chǎn)生的悖論基本得到統(tǒng)一。從此集合論的發(fā)展進入飛速發(fā)展的時代。 第3章 集合 第4章 關系 第5章 函數(shù)。,題外話： 三個在數(shù)學發(fā)展中產(chǎn)生了巨大影響的悖論畢達哥拉斯悖論、貝克萊悖論、羅素悖論。 什么是悖論？籠統(tǒng)地說，是指這樣的推理過程：它看上去

2、是合理的，但結(jié)果卻得出了矛盾。 悖論是數(shù)學的一部分，在歷史上曾為數(shù)學的發(fā)展提供了重要而持久的助推力。 一個悖論的數(shù)學本質(zhì)被揭露了，它似乎就失去了被繼續(xù)研究的價值。但是，在數(shù)學發(fā)展的歷史上，它功不可沒。,畢達哥拉斯是公元前五世紀古希臘的著名數(shù)學家與哲學家。他曾創(chuàng)立了一個合政治、學術、宗教三位一體的神秘主義派別：畢達哥拉斯學派。由畢達哥拉斯提出的著名命題“萬物皆數(shù)”是該學派的哲學基石。而“一切數(shù)均可表成整數(shù)或整數(shù)之比”則是這一學派的數(shù)學信仰。然而，具有戲劇性的是由畢達哥拉斯建立的畢達哥拉斯定理卻成了畢達哥拉斯學派數(shù)學信仰的“掘墓人”。,畢達哥拉斯定理提出后，其學派中的一個成員希帕索斯考慮了一個問題

3、：邊長為1的正方形其對角線長度是多少呢？他發(fā)現(xiàn)這一長度既不能用整數(shù)，也不能用分數(shù)表示，而只能用一個新數(shù)來表示。希帕索斯的發(fā)現(xiàn)導致了數(shù)學史上第一個無理數(shù)2 的誕生。 一直到18世紀，當數(shù)學家證明了基本常數(shù)如圓周率是無理數(shù)時，擁護無理數(shù)存在的人才多起來。到十九世紀下半葉，現(xiàn)在意義上的實數(shù)理論建立起來后，無理數(shù)本質(zhì)被徹底搞清，無理數(shù)在數(shù)學園地中才真正扎下了根。無理數(shù)在數(shù)學中合法地位的確立，一方面使人類對數(shù)的認識從有理數(shù)拓展到實數(shù)，另一方面也真正徹底、圓滿地解決了第一次數(shù)學危機。,微積分這一銳利無比的數(shù)學工具為牛頓、萊布尼茲各自獨立發(fā)現(xiàn)。這一工具一問世，就顯示出它的非凡威力。許許多多疑難問題運用這一工

4、具后變得易如翻掌。但是不管是牛頓，還是萊布尼茲所創(chuàng)立的微積分理論都是不嚴格的。兩人的理論都建立在無窮小分析之上，但他們對作為基本概念的無窮小量的理解與運用卻是混亂的。因而，從微積分誕生時就遭到了一些人的反對與攻擊。其中攻擊最猛烈的是英國大主教貝克萊。 貝克萊悖論可以表述為“無窮小量究竟是否為0”的問題：就無窮小量在當時實際應用而言，它必須既是0，又不是0。但從形式邏輯而言，這無疑是一個矛盾。這一問題的提出在當時的數(shù)學界引起了一定的混亂，由此導致了第二次數(shù)學危機的產(chǎn)生。,下面僅舉一無窮級數(shù)為例。無窮級數(shù)S11111到底等于什么？當時人們認為 一方面 S（11）（11）0；另一方面，S1（11）（

5、11）1，那么豈非01？ 這一矛盾竟使傅立葉那樣的數(shù)學家困惑不解，甚至連被后人稱之為數(shù)學家之英雄的歐拉在此也犯下難以饒恕的錯誤。他在得到1 + x + x2 + x3 + . = 1/(1- x) 后，令 x = 1，得出S1111112！由此一例，即不難看出當時數(shù)學中出現(xiàn)的混亂局面了 。,把分析重新建立在邏輯基礎之上就成為數(shù)學家們迫在眉睫的任務。 經(jīng)過數(shù)學家柯西，魏爾斯特拉斯、戴德金、康托爾各自獨立深入的研究，終于從不同的角度建立起來的嚴謹?shù)臉O限理論與實數(shù)理論，完成了分析學的邏輯奠基工作。數(shù)學分析的無矛盾性問題歸納為實數(shù)論的無矛盾性，從而使微積分學這座人類數(shù)學史上空前雄偉的大廈建在了牢固可靠

6、的基礎之上。重建微積分學基礎，這項重要而困難的工作就這樣經(jīng)過許多杰出學者的努力而勝利完成了。微積分學堅實牢固基礎的建立，結(jié)束了數(shù)學中暫時的混亂局面，同時也宣布了第二次數(shù)學危機的徹底解決。,十九世紀下半葉，康托爾創(chuàng)立了著名的集合論，在集合論剛產(chǎn)生時，曾遭到許多人的猛烈攻擊。但不久這一開創(chuàng)性成果就為廣大數(shù)學家所接受了，并且獲得廣泛而高度的贊譽。數(shù)學家們發(fā)現(xiàn)，從自然數(shù)與康托爾集合論出發(fā)可建立起整個數(shù)學大廈。因而集合論成為現(xiàn)代數(shù)學的基石?！耙磺袛?shù)學成果可建立在集合論基礎上”這一發(fā)現(xiàn)使數(shù)學家們?yōu)橹兆怼?900年，國際數(shù)學家大會上，法國著名數(shù)學家龐加萊就曾興高采烈地宣稱：“借助集合論概念，我們可以建造整

7、個數(shù)學大廈今天，我們可以說絕對的嚴格性已經(jīng)達到了。,可是，好景不長。1903年，一個震驚數(shù)學界的消息傳出：集合論是有漏洞的！這就是英國數(shù)學家羅素提出的著名的羅素悖論。 設性質(zhì)P(x)表示 ，現(xiàn)假設由性質(zhì)P確定了一個類A也就是說 。 那麼現(xiàn)在的問題是： 是否成立？首先，若 ，則x是A的元素，那麼x具有性質(zhì)P，由性質(zhì)P知 ；其次，若 ，也就是說x具有性質(zhì)P，而A是由所有具有性質(zhì)P的類組成的，所以 。,理發(fā)師悖論：在某個城市中有一位理發(fā)師，他的廣告詞是這樣寫的：“本人的理發(fā)技藝十分高超，譽滿全城。我將為本城所有不給自己刮臉的人刮臉，我也只給這些人刮臉。我對各位表示熱誠歡迎！”來找他刮臉的人絡繹不絕，

8、自然都是那些不給自己刮臉的人。可是，有一天，這位理發(fā)師從鏡子里看見自己的胡子長了，他本能地抓起了剃刀，你們看他能不能給他自己刮臉呢？如果他不給自己刮臉，他就屬于“不給自己刮臉的人”，他就要給自己刮臉，而如果他給自己刮臉呢？他又屬于“給自己刮臉的人”，他就不該給自己刮臉。,理發(fā)師悖論與羅素悖論是等價的： 因為，如果把每個人看成一個集合，這個集合的元素被定義成這個人刮臉的對象。那么，理發(fā)師宣稱，他的元素，都是城里不屬于自身的那些集合，并且城里所有不屬于自身的集合都屬于他。那么他是否屬于他自己？這樣就由理發(fā)師悖論得到了羅素悖論。反過來的變換也是成立的。,世界文學名著唐吉訶德中有這樣一個故事： 唐吉訶

9、德的仆人桑喬潘薩跑到一個小島上，成了這個島的國王。他頒布了一條奇怪的法律：每一個到達這個島的人都必須回答一個問題：“你到這里來做什么？”如果回答對了，就允許他在島上游玩，而如果答錯了，就要把他絞死。對于每一個到島上來的人，或者是盡興地玩，或者是被吊上絞架。有多少人敢冒死到這島上去玩呢？,一天，有一個膽大包天的人來了，他照例被問了這個問題，而這個人的回答是：“我到這里來是要被絞死的?！?請問桑喬潘薩是讓他在島上玩，還是把他絞死呢？ 如果應該讓他在島上游玩，那就與他說“要被絞死”的話不相符合，這就是說，他說“要被絞死”是錯話。既然他說錯了，就應該被處絞刑。 但如果桑喬潘薩要把他絞死呢？這時他說的“

10、要被絞死”就與事實相符，從而就是對的，既然他答對了，就不該被絞死，而應該讓他在島上玩。 小島的國王發(fā)現(xiàn)，他的法律無法執(zhí)行，因為不管怎么執(zhí)行，都使法律受到破壞。他思索再三，最后讓衛(wèi)兵把他放了，并且宣布這條法律作廢。這又是一條悖論。,1908年，策梅羅（Ernst Zermelo)在自己這一原則基礎上提出第一個公理化集合論體系，后來這一公理化集合系統(tǒng)很大程度上彌補了康托爾樸素集合論的缺陷。這一公理系統(tǒng)在通過Abraham Fraenkel的該進后被稱為Zermelo-Fraenkel(ZF) axioms。在該公理系統(tǒng)中，由于限制公理（The Axion Schema of Comprehensi

11、on或Subset Axioms)：P(x)是x的一個性質(zhì)，對任意已知集合A，存在一個集合B使得對所有元素xB當且僅當xA且P(x)；因此xx是一個集合并不能在該系統(tǒng)中寫成一個集合，由于它并不是任何已知集合的子集；并且通過該公理，存在集合A=xx是一個集合在ZF系統(tǒng)中能被證明是矛盾的。因此羅素悖論在該系統(tǒng)中被避免了。,除ZF系統(tǒng)外，集合論的公理系統(tǒng)還有多種，如諾伊曼（von Neumann)等人提出的NBG系統(tǒng)等。在the von Neumann-Bernays alternative中，所有包含集合的collection都能被稱為類(class)，因此某些集合也能被稱為class，但是某些c

12、ollection太大了（比如一個collection包含所有集合）以至于不能是一個集合，因此僅僅是個class。這同樣也避免了羅素悖論。 公理化集合系統(tǒng)的建立，成功排除了集合論中出現(xiàn)的悖論，從而比較圓滿地解決了第三次數(shù)學危機。,不管一個數(shù)學問題叫不叫悖論，它總是一個問題。問題是數(shù)學的心臟，對問題的研究推動著數(shù)學的發(fā)展，對“悖論”的研究當然也會推動數(shù)學的發(fā)展。 把某些悖論的出現(xiàn)叫做數(shù)學危機，不知道是誰第一個說的。不過，多數(shù)數(shù)學家看來，數(shù)學沒有危機，也不會有危機。但是數(shù)學家忙著自己的研究，一般不太關心數(shù)學危機的說法。研究數(shù)學哲學的人，對于有沒有數(shù)學危機，也是各有不同的看法。但既然有了這個說法，又

13、比較能吸引大眾的目光，讓大家對數(shù)學有更多的興趣，也是好事。,第三章 集 合,3.1 集合論基本概念 3.2 集合運算及其性質(zhì) 3.3 集合的笛卡兒積與無序積,退出,3.1 集合論基本概念,1. 集合與元素 所謂集合，是指某些可辨別的不同對象的全體，或者說把具有一些確定的事物作為一個整體看待時，這個整體就是一個集合。集合是難于給出精確定義的一個概念，只能作上述形式的描述。 將用大寫字母A，B，X，Y，表示之。組成集合的對象稱為集合的元素或成員，將用小寫字母a，b，x，y表示之。a是A的元素或a屬于A，記作aA；a不屬于A或a不是A的元素，記作aA，或者(aA)。,集合的元素一旦給定，這一集合便完

14、全確立。這一事實被形式地敘述為外延公理。 外延公理：兩集合A和B相等，當且僅當它們有相同的元素。 若A與B相等，記為A=B；否則，記為AB。,外延公理可形式表為： A=B(x)(xAxB) 或者 A=B(x)(xAxB)(x)(xBxA) 順便指出，在應用外延公理證明集合A與B相等時，只需考察： 對于任意元素x，應有下式 xAxB 成立即可。這就是說，證明兩集合相等時可按此法行事。,集合的表示： 表示一個特定集合，基本上有兩種方法： 一是枚舉法，在可能時列出它的元素，元素之間用逗號分開，再用花括號括起。如 A=a,e,i,o,u (1) 表明集合A是由字母a, e, I ,o和u為元素構(gòu)成的。

15、 B=1, 3, 5, (2),二是敘述法or謂詞法. 用謂詞公式來確定集合。即個體域中能使謂詞公式為真的那些元素，確定了一個集合，因為這些元素都具有某種特殊性質(zhì)。若P(x)含有一個自由變元的謂詞公式，則x | P(x)定義了集合S，并可表為 S=x | P(x) 由此可見，P(c)為真當且僅當cS。從而有 xSxP(x),例如，(1)、(2)可表為 A=x | x是英文字母表中元音字母； B=x | x是正奇數(shù)。 在用性質(zhì)來描述集合時，可表述為概括原理或子集合公理。 子集公理： 對于任給集合A和性質(zhì)P，存在集合B，使得B中元素恰為A中滿足P的那些元素。,子集公理可形式地表為 (B)(x)(x

16、BxA(x) 其中(x)為不含B自由出現(xiàn)。 子集公理的提出，避免了悖論，使集合論得以存在和發(fā)展。,應該指出的是：集合并不決定于它的元素展示方法。集合的元素被重復或重新排列，集合并不改變，即a, a ,e, i, o, u= a, u, e, o, i。但有時對重復出現(xiàn)的元素都認為是集合的元素，這種集合稱為多重集。即a, a, e, i, o, u, ua, e, i, o, u。 本書中集合在不特別指明時，都指前者，即中的集合。,集合的元素可以是具體事物，可以是抽象概念，也可以是集體，不是集合的元素稱為本元。如，一本書，一支筆，集合1,2,3可以組成集合B=一本書，一支筆，1,2,3 。特別地

17、，以集合為元素的集合稱為集合族或集合類如A=1,2,3, 8,9,6。 集合中元素之間可以有某種關聯(lián)，也可以彼此毫無關系。,2. 子集、全集與空集 子集是描述一個集合與另一個集合之間的關系，其定義如下。 定義3.1.1 設A和B是任意兩個集合，如果集合A的每個元素，都是集合B中的一個元素，則稱A是B的子集，或稱A被包含于B中，或者說B包含A，并記為AB。,本定義也可表成 AB(x)(xAxB) 這表明，要證明AB，只需對任意元素x，有下式 xAxB 成立即可。 此外，若集合B不包含集合A，記為AB。,/,定義3.1.2 設A和B是兩個集合，若AB且AB，則稱A是B的真子集，記為AB，也稱B真包

18、含A。該定義也可表為 AB(ABAB),定義3.1.3 如果一個集合包含了所要討論的每一個集合，則稱該集合為全集，記為U或E。它可形式地表為 U=x|P(x)P(x) 其中P(x)為任何謂詞公式。,顯然，全集U即是第二章中的全總論域。于是，每個元素x都屬于全集U，即命題(x)(xU)為真。由定義易知，對任意集合A，都有AU。 在實際應用中，常常把某個適當大的集合看成全集U。全集是個相對概念。,定義3.1.4 沒有任何元素的集合，稱為空集，記為，它可形式地表為： =x|P(x)P(x) 其中P(x)為任何謂詞公式。 由定義可知，對任何集合A，有A。這是因為任意元素x，公式xxA總是為真。,注意，

19、與是不同的。是以為元素的集合，而沒有任何元素，能用構(gòu)成集合的無限序列： (1)， 該序列除第一項外，每項均以前一項為元素的集合。,(2)， 該序列除第一項外，每項均以前面各項為元素的集合。它即是馮諾依曼在1924年使用空集給出自然數(shù)的集合表示： 0:=，1:=，2:= ,， 定理3.1.1 空集是唯一的 定理3.1.2 ()對任一集合A，有AA。 ()若AB且BC，則AC。 對任何一個集合A: A和稱為A的兩個平凡子集。,3集合的基數(shù) 表示集合中元素多少或度量集合大小的數(shù)，稱作集合的基數(shù)或勢。一個集合A的基數(shù)，記為|A|。 如果一個集合恰有m個不同的元素，且m是某個非負整數(shù)，稱該集合是有限的或

20、有窮的，否則稱這個集合為無限的或無窮的。例如，在本書中常用有窮集有： Nm=0,1,2,m-1,本書中常見的無窮集合有： N=0,1,2,3,，即自然數(shù)集合。 Z=,-2,-1,0,1,2,3,，即整數(shù)集合。 Z+=1,2,3,，即正整數(shù)集合。 Q=有理數(shù)集合。 R=實數(shù)集合。 C=復數(shù)集合。,4集合的冪集 一個集合的冪集是指該集合所有子集的集合，即是由這些子集所組成的集合族。 定義3.1.5 設A為一集合，A的冪集是一集合族，記為P(A)， P(A)=B|BA 由定義可知，P(A)，AP(A)。 若|A|=n, 則|P(A)|=2n,5文氏圖 文氏(Venn)圖是一種利用平面上的點構(gòu)成的圖形

21、來形象展示集合的一種方法。全集U用一個矩形的內(nèi)部表示，其他集合用矩形內(nèi)的園面或一封閉曲線圈成的面積來表示。,如果AB，則表示A的圓面一般將完全落在表示B的圓面內(nèi)，如圖1中(a)。如果A與B沒有公共元素，那么表示A的圓面將同表示B的圓面分開，如圖3-1中(b)。當A和B是兩個任意的集合時，可能會是：有些元素在A中但不在B中，有些元素在B中卻不在A中，有些元素同時在A和B中，有些元素則既不在A中也不在B中，因此用圖1中(c)表示任意兩個集合A和B。,圖 3-1,最后給出集合的形式定義結(jié)束本節(jié)。 定義3.1.6 A為集合=(x)(xAA=)。 這里等號“=”表示定義為的意義，是表示“定義為”還是表示

22、“一般相等”的意義，由上下文來區(qū)分。,3.2 集合運算及其性質(zhì),集合運算是指用已知的集合去生成新的集合。假設所有集合都是全集U的子集，即這些集合是利用子集公理得到的。下面依次介紹常見的集合運算。,1并、交和差運算 定義3.2.1 設A和B是任意兩個集合， A和B的并是集合，記為AB， AB=x|xAxB A和B的交是集合，記為AB， AB=x|xAxB A和B的差，或B關于A的相對補是集合，記為A-B， A-B=x|xAxB,定義3.2.2 若A和B是集合，且AB=，則稱A和B是不相交的。 如果C是個集合族，且C中任意兩個不同元素都不相交，則稱C中集合是兩個不相交的，或稱C是兩兩不相交的集合族

23、。,定理3.2.1 任給集合A，B和C，則： AB=BA AB=BA (AB)C=A(BC) (AB)C=A(BC) 該定理表明，集合并和交運算滿足交換律和結(jié)合律。,定理3.2.2 任給集合A、B和C，則 A(BC)=(AB)(AC) A(BC)=(AB)(AC) 該定理表明，集合運算并對交、交對并都是可分配的。,定理3.2.3 任給集合A，B，C和D，則 若AB，則AB=B，AB=A 若AB和CD，則ACBD，ACBD,推論3.2.3 AU=U，AU=A 定理3.2.4 任給集合A，B和C，則 A-(BC)=(A-B)(A-C) A-(BC)=(A-B)(A-C),定義3.2.3 設A是含有

24、元素為集合的集合，或者集合族。 A的并是集合，記為A， A=x|(B)(BAxB)= B A的交是集合，記為A， A=x|(B)(BAxB)= B,B A,B A,定義3.2.4 集合A的補是集合，記為A， A=U-A=x|xUxA =x|xA 這里稱為絕對補。相對補是指A-B稱為B相對于A的補集。 定理3.2.5 任給集合A，則 AA=U， AA=。,定理3.2.6 任給集合A和B，則 B=A iff AB=U 且 AB= 該定理表明了若A的補是B，則B的補是A，即A和B互補。補的唯一性。 推論3.2.5 U=，=U 定理3.2.7 任給集合A，則(A)=A。 該定理表明了，A的補的補是A。

25、,定理3.2.8 (德摩根律) 任給集合A和B，則 (AB)=AB， (AB)=AB。 定義3.2.5 任給集合A和B，A和B的對稱差是集合，記為AB， AB =(A-B)(B-A) =x|(xAxB)(xBxA),定理3.2.9 任給集合A和B，則 AB=(AB)(AB) =(AB) - (AB) 推論3.2.9 AB=AB AB=BA AA=,2集合代數(shù)與對偶原理 本小節(jié)將形式地討論由集合、集合變元、集合運算和圓括號所構(gòu)成的集合代數(shù)以及集合代數(shù)中的對偶原理。 與命題邏輯相似，對于給定集合實行集合運算，可以生成新的集合。同用大寫英文字母表示確定集合一樣，也用大寫字母表示不確定的集合，前者稱為

26、集合常元，后者稱為集合變元。集合變元用以集合常元代替后，才表示確定的集合。下面將給出集合的合式公式定義。,定義3.2.6 可按下列規(guī)則生成集合合式公式： 單個集合變元是集合合式公式。 若A是集合合式公式，則A也是集合合式公式。 若A和B是集合合式公式，則(AB)，(AB)，(A-B)和(AB)也都是集合合式公式。 只有有限次使用、和構(gòu)成的符號串才是集合合式公式。 為方便計，簡稱集合合式公式為公式。,定義3.2.7 用任意集合常元取代兩個集合公式中的各個集合變元，若所得集合是相等的，則稱該二集合公式是相等的，簡稱等式。 因為集合公式相等，不依賴于取代集合變元的集合，故常稱這些等式為集合恒等式，或集合定律。它們刻劃了集合運算的某些性質(zhì)，這些性質(zhì)描述一個代數(shù)，稱為集合代數(shù)。下面列出常用集合定律：,（1）等冪律AA=A AA=A （2）結(jié)合律 (AB)C=A(BC) (AB)C=A(BC) （3）交換律 AB=BA AB=BA （4）分配律 A(