集合的概念與運(yùn)算

集合的概念與運(yùn)算第一頁，共五十一頁，編輯于2023年，星期五集合論(settheory)十九世紀(jì)數(shù)學(xué)最偉大成就之一集合論體系樸素(naive)集合論公理(axiomatic)集合論創(chuàng)始人康托(Cantor)GeorgFerdinand

PhilipCantor1845~1918德國數(shù)學(xué)家,集合論創(chuàng)始人.

第二頁，共五十一頁，編輯于2023年，星期五什么是集合(set)集合：不能精確定義。一些對象的整體就構(gòu)成集合，這些對象稱為元素(element)或成員(member)用大寫英文字母A,B,C,…表示集合用小寫英文字母a,b,c,…表示元素aA：表示a是A的元素，讀作“a屬于A”

aA：表示a不是A的元素，讀作“a不屬于A”第三頁，共五十一頁，編輯于2023年，星期五集合的表示列舉法描述法特征函數(shù)法第四頁，共五十一頁，編輯于2023年，星期五列舉法(roster)列出集合中的全體元素，元素之間用逗號分開，然后用花括號括起來，例如A={a,b,c,d,…,x,y,z}B={0,1,2,3,4,5,6,7,8,9}集合中的元素不規(guī)定順序C={2,1}={1,2}集合中的元素各不相同(多重集除外)C={2,1,1,2}={2,1}第五頁，共五十一頁，編輯于2023年，星期五多重集(multipleset)多重集:允許元素多次重復(fù)出現(xiàn)的集合元素的重復(fù)度:元素的出現(xiàn)次數(shù)(0).例如:設(shè)A={a,a,b,b,c}是多重集元素a,b的重復(fù)度是2元素c的重復(fù)度是2元素d的重復(fù)度是0第六頁，共五十一頁，編輯于2023年，星期五描述法(definingpredicate)用謂詞P(x)表示x具有性質(zhì)P，用{x|P(x)}表示具有性質(zhì)P的集合，例如P1(x):

x是英文字母A={x|P1(x)}={x|x是英文字母}={a,b,c,d,…,x,y,z}P2(x):

x是十進(jìn)制數(shù)字B={x|P2(x)}={x|x是十進(jìn)制數(shù)字}={0,1,2,3,4,5,6,7,8,9}第七頁，共五十一頁，編輯于2023年，星期五描述法（續(xù)）兩種表示法可以互相轉(zhuǎn)化，例如E={2,4,6,8,…}={x|x>0且x是偶數(shù)}={x|x=2(k+1)，k為非負(fù)整數(shù)}={2(k+1)|k為非負(fù)整數(shù)}有些書在列舉法中用:代替|,例如{2(k+1):k為非負(fù)整數(shù)}第八頁，共五十一頁，編輯于2023年，星期五特征函數(shù)法(characteristicfunction)集合A的特征函數(shù)是A(x):

1，若xA

A

(x)=

0，若xA對多重集,A(x)=x在A中的重復(fù)度第九頁，共五十一頁，編輯于2023年，星期五數(shù)的集合N：自然數(shù)(naturalnumbers)集合N={0,1,2,3,…}Z：整數(shù)(integers)集合Z={0,1,2,…}={…,-2,-1,0,1,2,…}Q：有理數(shù)(rationalnumbers)集合R：實(shí)數(shù)(realnumbers)集合C：復(fù)數(shù)(complexnumbers)集合第十頁，共五十一頁，編輯于2023年，星期五集合之間的關(guān)系子集、相等、真子集空集、全集冪集、n元集、有限集集族第十一頁，共五十一頁，編輯于2023年，星期五子集(subset)

子集:若B中的元素也都是A中的元素,則稱B為A的子集,或說B包含于A,或說A包含B,記作BABAx(xBxA)若B不是A的子集,則記作BABAx(xBxA)x(xBxA)x(xBxA)x(xBxA)x(xBxA)第十二頁，共五十一頁，編輯于2023年，星期五子集(舉例)設(shè)A={a,b,c},B={a,b,c,d},C={a,b},則AB,CA,CBACBabcdefghij…………第十三頁，共五十一頁，編輯于2023年，星期五相等(equal)相等:互相包含的集合是相等的.A=BABBAA=Bx(xAxB)A=BABBA(=定義)x(xAxB)x(xBxA)(定義)x((xAxB)(xBxA))(量詞分配)x(xAxB)(等值式)第十四頁，共五十一頁，編輯于2023年，星期五包含()的性質(zhì)AA證明:AAx(xAxA)1若AB,且AB,則BA

證明:AB

(A=B)

(ABBA)(定義)(AB)

(BA)(德?摩根律)AB(已知)BA(即BA)(析取三段論)#第十五頁，共五十一頁，編輯于2023年，星期五包含()的性質(zhì)(續(xù))若AB,且BC,則AC證明:ABx(xAxB)x,xAxB(AB)xC(BC)x(xAxC),即AC.#第十六頁，共五十一頁，編輯于2023年，星期五真子集(propersubset)

真子集:B真包含A:ABABABAB(ABAB)(定義)(AB)(A=B)(德?摩根律)x(xAxB)(A=B)(定義)第十七頁，共五十一頁，編輯于2023年，星期五真包含()的性質(zhì)AA證明:AAAAAA100.#若AB,則BA

證明:(反證)設(shè)BA,則

ABABABAB(化簡)BABABABA所以ABBAA=B(=定義)但是ABABABAB(化簡)矛盾!

#第十八頁，共五十一頁，編輯于2023年，星期五真包含()的性質(zhì)(續(xù))若AB,且BC,則AC證明:ABABABAB(化簡),同理BCBC,所以AC.假設(shè)A=C,則BCBA,又AB,故A=B,此與AB矛盾,所以AC.

所以,AC.

#第十九頁，共五十一頁，編輯于2023年，星期五空集(emptyset)空集:沒有任何元素的集合是空集,記作例如,{xR|x2+1=0}定理1:對任意集合A,A

證明:Ax(xxA)x(0xA)1.#推論:空集是唯一的.證明:設(shè)1與2都是空集,則12211=2.#第二十頁，共五十一頁，編輯于2023年，星期五全集全集:如果限定所討論的集合都是某個集合的子集,則稱這個集合是全集,記作E全集是相對的,視情況而定,因此不唯一.例如,討論(a,b)區(qū)間里的實(shí)數(shù)性質(zhì)時,可以選E=(a,b),E=[a,b),E=(a,B],E=[a,b],E=(a,+),E=(-,+)等第二十一頁，共五十一頁，編輯于2023年，星期五冪集(powerset)冪集:A的全體子集組成的集合,稱為A的冪集,記作P(A)P(A)={x|xA}注意:xP(A)xA例子:A={a,b},P(A)={,{a},,{a,b}}.#第二十二頁，共五十一頁，編輯于2023年，星期五n元集(n-set)

n元集:含有n個元素的集合稱為n元集0元集:1元集(或單元集),如{a},,{},{{}},…|A|:表示集合A中的元素個數(shù),

A是n元集|A|=n有限集(fimiteset):|A|是有限數(shù),|A|<,也叫有窮集第二十三頁，共五十一頁，編輯于2023年，星期五冪集(續(xù))定理:|A|=n|P(A)|=2n.證明:每個子集對應(yīng)一種染色,一共有2n

種不同染色.#A{a1}a1a2a3………an{a1,a3}……第二十四頁，共五十一頁，編輯于2023年，星期五集族(setfamily)集族:由集合構(gòu)成的集合.冪集都是集族.指標(biāo)集(indexset):

設(shè)A是集族,若A={A|S},則S稱為A的指標(biāo)集.S中的元素與A中的集合是一一對應(yīng)的.也記作A={A|S}={A}S例1:{A1,A2}的指標(biāo)集是{1,2}第二十五頁，共五十一頁，編輯于2023年，星期五集族(舉例)例2:An={xN|x=n},A0={0},A1={1},…{An|nN}={{0},{1},{2},…}{An|nN}的指標(biāo)集是N例3:設(shè)R+={xR|x>0},Aa=[0,a),{Aa|aR+}的指標(biāo)集是R+0a第二十六頁，共五十一頁，編輯于2023年，星期五集合之間的運(yùn)算并集、交集相對補(bǔ)集、對稱差、絕對補(bǔ)廣義并集、廣義交集第二十七頁，共五十一頁，編輯于2023年，星期五并集(union)并集:AB={x|(xA)(xB)}xAB(xA)(xB)初級并:第二十八頁，共五十一頁，編輯于2023年，星期五并集(舉例)例1:設(shè)An={xR|n-1xn},n=1,2,…,10,則例2:設(shè)An={xR|0x1/n},n=1,2,…,則第二十九頁，共五十一頁，編輯于2023年，星期五交集(intersection)交集:AB={x|(xA)(xB)}xAB(xA)(xB)初級交:第三十頁，共五十一頁，編輯于2023年，星期五交集(舉例)例1:設(shè)An={xR|n-1xn},n=1,2,…,10,則例2:設(shè)An={xR|0x1/n},n=1,2,…,則第三十一頁，共五十一頁，編輯于2023年，星期五不相交(disjoint)不相交:AB=互不相交:設(shè)A1,A2,…是可數(shù)多個集合,若對于任意的ij,都有AiBj=,則說它們互不相交例:設(shè)An={xR|n-1<x<n},n=1,2,…,10,則A1,A2,…是不相交的第三十二頁，共五十一頁，編輯于2023年，星期五相對補(bǔ)集(setdifference)相對補(bǔ)集:屬于A而不屬于B的全體元素,稱為B對A的相對補(bǔ)集,記作A-BA-B={x|(xA)(xB)}A-BAB第三十三頁，共五十一頁，編輯于2023年，星期五對稱差(symmetricdifference)對稱差:屬于A而不屬于B,或?qū)儆贐而不屬于A的全體元素,稱為A與B的對稱差,記作ABAB={x|(xAxB)(xAxB)}AB=(A-B)(B-A)=(AB)-(AB)ABAB第三十四頁，共五十一頁，編輯于2023年，星期五絕對補(bǔ)(complement)絕對補(bǔ):~A=E-A,E是全集,AE~A={x|(xExA)}~A={xE|xA)}~AA第三十五頁，共五十一頁，編輯于2023年，星期五相對補(bǔ)、對稱差、補(bǔ)(舉例)例:設(shè)A={xR|0x<2},A={xR|1x<3},則A-B={xR|0x<1}=[0,1)B-A={xR|2x<3}=[2,3)AB={xR|(0x<1)(2x<3)}=[0,1)[2,3)[)[))[第三十六頁，共五十一頁，編輯于2023年，星期五廣義并集(bigunion)廣義并:設(shè)A是集族,A中所有集合的元素的全體,稱為A的廣義并,記作∪A.∪A

={x|z(xzzA}當(dāng)是以S為指標(biāo)集的集族時∪A

=∪{A|S}=∪

AS例:設(shè)A={{a,b},{c,d},{d,e,f}},則

∪A={a,b,c,d,e,f}第三十七頁，共五十一頁，編輯于2023年，星期五廣義交集(bigintersection)廣義交:設(shè)A是集族,A中所有集合的公共元素的全體,稱為A的廣義交,記作∩A.∩A

={x|z(zAxz)}當(dāng)是以S為指標(biāo)集的集族時∩A

=∩{A|S}=∩

AS例:設(shè)A={{1,2,3},{1,a,b},{1,6,7}},則

∩A={1}第三十八頁，共五十一頁，編輯于2023年，星期五廣義交、廣義并(舉例)設(shè)A1={a,b,{c,d}},

A2={{a,b}},

A3={a},

A4={,{}},A5=a(a),A6=,則∪A1=a∪b∪{c,d},∩A1=a∩b∩{c,d},∪A2={a,b},∩A2={a,b},∪A3=a,∩A3=a∪A4=∪{}={},∩A4=∩{}=,∪A5=∪a,∩A5=∩a∪A6=,∩A6=E第三十九頁，共五十一頁，編輯于2023年，星期五文氏圖(Venndiagram)文氏圖:平面上的n個圓(或橢圓),使得任何可能的相交部分,都是非空的和連通的JohnVenn,1834~1923例:第四十頁，共五十一頁，編輯于2023年，星期五文氏圖(應(yīng)用)文氏圖可表示集合運(yùn)算(結(jié)果用陰影表示)ABABA-BAB~AAAAAAABBBBBAB=第四十一頁，共五十一頁，編輯于2023年，星期五文氏圖(問題)Venn曾經(jīng)構(gòu)造出4個橢圓的文氏圖,并且斷言:沒有5個橢圓的文氏圖PeterHamburger&RaymondPippert,1996,構(gòu)造出5個橢圓的文氏圖Canyoutryit?第四十二頁，共五十一頁，編輯于2023年，星期五文氏圖(續(xù))試試n=4:14<16第四十三頁，共五十一頁，編輯于2023年，星期五文氏圖(續(xù))試試n=517+5<32第四十四頁，共五十一頁，編輯于2023年，星期五容斥原理(principleofinclusion/exclusion)容斥原理(或包含排斥原理)第四十五頁，共五十一頁，編輯于2023年，星期五容斥原理(證明)n=2時的情況:|AB|=|A|+|B|-|AB|

歸納證明:以n=3為例:|ABC|=|(AB)C|=|AB|+|C|-|(AB)C|=|A|+|B|-|AB|+|C|-|(AC)(BC)|=|A|+|B|-|AB|+|C|-(|AC|+|BC|-|(AC)(BC)|)=|A|+|B|+|C|-|AB|-|AC|-|BC|+|ABC|ABBCA第四十六頁，共五十一頁，編輯于2023年，星期五容斥原理(舉例)例1:在1到10000之間既不是某個整數(shù)的平方,也不是某個整數(shù)的立方的數(shù)有多少?解:設(shè)E={xN|1x10000},|E|=10000

A={xE|x=k2kZ},|A|=100

B={xE|x=k3kZ},|B|=21

則|~(AB)|=|E|-|AB|=|E|-(|A|+|B|-|AB|)=10000-100-21+4=9883注意AB={xE|x=k6kZ},|AB|=4.#第四十七頁，共五十一頁，編輯于2023年，星期五容斥原理(舉例、續(xù))例2:在24名科技人員中,會說英,日,德,法語的人數(shù)分別為13,5,10,和9,其中同時會說英語,德語,或同時會說