離散數(shù)學(xué)-集合(10.13版)

1、第二章 集 合 2.1 集合論的基本概念2.2 集合上的運(yùn)算2.3 歸納法和自然數(shù) (自學(xué))2.4 語言上的運(yùn)算 （自學(xué)）2.5 集合的笛卡兒乘積2.1 集合論的基本概念 2.1.1 集合的概念 集合在某些場合又稱為類、族或搜集, 它是數(shù)學(xué)中最基本的概念之一, 但 不可精確定義, 現(xiàn)描如下: 一個(gè)集合是能作為整體論述的事物的集體。 組成集合的每個(gè)事物叫做這個(gè)集合的元素或成員。 通常用大寫字母A, B, C, 代表集合; 用小寫字母a, b, c, 代表元素。 如果a是集合A的一個(gè)元素, 則記為 aA讀做“a屬于A”, 或說“a在A中”。 ; 如果a不是集合A的一個(gè)元素, 則記為 a A讀做“a

2、不屬于A”, 或說“a不在A中”。 ; 任一元素, 對某一集合而言, 或?qū)儆谠摷? 或不屬于該集合, 二者必居其一, 不可兼得。 僅含有一個(gè)元素的集合稱為單元素集合。 應(yīng)把單元素集合與這個(gè)元素區(qū)別開來。例如A與A不同, A表示僅以A為元素的集合, 而A對A而言僅是一個(gè)元素, 當(dāng)然這個(gè)元素也可以是一個(gè)集合, 如A=1,2。 稱含有有限個(gè)元素的集合為有限集合。稱不是有限集合的集合為無限集合或無窮集。有限集合的元素個(gè)數(shù)稱為該集合的基數(shù)或勢。第五章將給出有限集、無限集、基數(shù)等概念的更精致的陳述。集合A的基數(shù)記為|A|, 例如若 A=a, b, 則 |A|=2, 又|A|=1 外延公理 兩個(gè)集合A和B

3、相等, 即A=B, 當(dāng)且僅當(dāng)它們有相同的成員(也就是, A的每一元素是B的一個(gè)元素而B的每一元素也是A的一個(gè)元素)。 ; 用邏輯符號(hào)表達(dá)是: 外延公理斷言: 如果兩個(gè)集合有相同的元素, 那么不管集合是如何表示的, 它們都相等。因此, (1) 列舉法中, 元素的次序是無關(guān)緊要的。例如x,y,z與z,x,y相等。 (2) 元素的重復(fù)出現(xiàn)無足輕重。例如, x,y,x、 x,y、 x,x,x,y是相同的集合。 (3) 集合的表示不是唯一的。例如, x|x2-3x+2=0、 x|xI1x2 和1, 2均表示同一集合。 2.1.2 羅素悖論 1901年羅素(Bertrand Russell)提出以下悖論:

4、 設(shè)論述域是所有集合的集合, 并定義S為下述集合 這樣, S是不以自身為元素的全體集合的集合, 我們現(xiàn)在問“S是不是它自己的元素?” ; 假設(shè)S不是它自己的元素, 那么S滿足謂詞A A, 而該謂詞定義了集合S, 所以SS。 另一方面, 如果SS, 那么S必須滿足定義S的謂詞, 所以SS。 這樣, 我們導(dǎo)致了一個(gè)類似于謊言悖論的矛盾: 既非SS也非SS是真。 一個(gè)“集合”, 諸如S, 它能導(dǎo)致矛盾的稱為非良定的。 羅素悖論起因于不受限制的定義集合的方法, 特別, 集合可以是自己的元素的概念值得懷疑?？得撘院髣?chuàng)立的許多公理化集合論都直接地或間接地限制集合成為它自己的元素, 因而避免了羅素悖論。 公

5、理化集合論用某個(gè)方法避免了羅素悖論, 但怎能確信沒有其它悖論潛伏在這些形式結(jié)構(gòu)中呢? 回答是悲觀的, 業(yè)已證明, 應(yīng)用現(xiàn)今有效的數(shù)學(xué)技術(shù), 沒有方法能證明新的悖論不會(huì)產(chǎn)生。 2.1.3 集合間的包含關(guān)系 定義2.1-1 設(shè)A和B是集合, 如果A的每一元素是B的一個(gè)元素, 那么A是B的子集合, 記為AB, 讀做“B包含A”或“A包含于B中。 用邏輯符表示為: 有時(shí)也記作 , 稱B是A的擴(kuò)集。 定義2.1-2 如果AB且AB, 那么稱A是B的真子集,記作AB , 讀作“B真包含A”。 ; 推論 2.1-2 對任何集合A, 恒有AA。 定義 2.1-3 沒有元素的集合叫空集或零集, 記為 。定理 2

6、.1-4 對任意集合A有 。 定理 2.1-5 空集是唯一的。 證 設(shè)和 都是空集, 由定理2.1-4得 和 , 根據(jù)定理2.1-2得 。 注意與不同, 后者是以空集為元素的一個(gè)集合, 前者沒有元素。 能用空集構(gòu)造不同集合的無限序列。在序列中, 每一集合除第一個(gè)外都確實(shí)有一元素, 即序列中前面的集合。 在序列中, 如果我們從0開始計(jì)算, 則第i項(xiàng)有i個(gè)元素。 這一序列的每一集合, 以序列中在它之前的所有集合作為它的元素。 2.2 集合上的運(yùn)算 2.2.1 并、 交和差運(yùn)算;定義 2.2-1 設(shè)A和B是集合。 (a) A和B的并記為AB, 是集合。 AB=x|xAxB(b) A和B的交記為AB,

7、 是集合。 AB=x|xAxB (c) A和B的差, 或B關(guān)于A的相對補(bǔ), 記為A-B, 是集合。A-B=x|xAxB 例 1 設(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 對任意集合A、B和C有: ; (a) A(BC)=(AB)(AC) ; (b) A(BC)=(AB)(AC) =即集合運(yùn)算和, 在上可分配, 在上可分配。 ; 證 設(shè)x是任意元素, 那么 xA(BC) xAx(BC) 的定義 xA(xBxC) 的定義 (xAxB)(xAxC) 在上可分配 (xAB)(xAC) 的定義 x(

8、AB)(AC) 的定義因此, A(BC)=(AB)(AC)。 定理 2.2-3 設(shè)A、B、C和D是論述域U的任意子集合, 那么下列斷言是真: (a) AA=A ;(b) AA=A ;(c) A=A ;(d) A= ;(e) A-=A ;(f) A-BA ;(g) 如果AB和CD, 那么, (AC)(BD) ;(h) 如果AB和CD, 那么, (AC)(BD) ;(i) AAB ;(j) ABA ;(k) 如果AB, 那么, AB=B ;(l) 如果AB, 那么, AB=A 定理 2.2-6 設(shè)A是U的任意子集, 那么 。也就是說, A的補(bǔ)的補(bǔ)是A。 定理2.2-7 (德摩根定律)設(shè)A和B是U的

9、任意子集, 那么 圖 2.2-1 另外, 根據(jù)并、交、補(bǔ)等定義, 亦知命題演算中的、 、 、T、F等分別與集合論中的、-、 、U、 等有對應(yīng)關(guān)系, 因此, 有關(guān)它們的公式也有相似性。 例如命題演算中有公式 (PQ) PQ, PTP, 集合論中有對應(yīng)公式 又如命題演算中有范式等概念 PQR(PQR)(PQR)(PQR)如果需要, 在集合論中也可引入范式等概念, 使 ABC=(ABC)(ABC)(ABC) 2.2.4 環(huán)和與環(huán)積 定義 2.2-5 A、B兩集合的環(huán)和AB, 是集合 參看圖 2.2-2。環(huán)和又叫對稱差(Symmetric Difference)。 定理 2.2-9 證 因?yàn)?但 所以

10、, 推論 2.2-9定理 2.2-10 定理 2.2-11 以上兩個(gè)定理留給讀者自證。但注意并在環(huán)和上不可分配, 環(huán)和在交上不可分配。即, 通常 定義 2.2-6 A、B兩集合的環(huán)積AB, 是集合 圖 2.2 - 2 定理 2.2-12 定理 2.2-13 證 所以, 根據(jù)定理2.2-10 得 兩邊取補(bǔ), 即得 定理 2.2-14 請讀者自證2.2.5 冪集合 定義 2.2-7 設(shè)A是一集合, A的冪集(A), 是A的所有子集的集合, 即 一個(gè)給定集合的冪集是唯一的, 因此求一個(gè)集合的冪集是以集合為運(yùn)算對象的一元運(yùn)算。 2.5 集合的笛卡兒乘積 定義2.5-1 (1) 兩個(gè)元素a1、a2組成的

11、序列記作a1,a2, 稱為二重組或序偶。a1和a2分別稱為二重組a1,a2的第一和第二個(gè)分量。 (2) 兩個(gè)二重組a,b和c,d相等當(dāng)且僅當(dāng)a=c并且b=d。 (3) 設(shè)a1,a2,an是n個(gè)元素, 定義 a1,a2,an=a1,a2,an-1,an為n重組, 這里n2。 (1) 由兩個(gè)二重組相等的定義可以看出, 二重組中元素的次序是重要的, 例如 2,33,2, 這一點(diǎn)和集合相等的定義不同, 在集合中元素的次序是無關(guān)緊要的, 例如2,3=3,2。 (2) n重組是一個(gè)二重組, 其第一分量是n-1重組。2,3,5代表2,3,5而不代表2,3,5, 按定義后者不是三重組, 并且2,3,52,3,

12、5。 定義2.5-2 (1)集合A和B的叉積記為AB, 是二重組集合a,b|aAbB。 (2) 集合A1,A2,An的叉積記為A1A2An或 , 定義為這里n2。 ; 叉積又叫做集合的笛卡兒乘積。 ; 由定義可看出, 是n重組集合 a1,a2,an|aiAi1in另外, 對一切i, Ai=A時(shí), 可簡記為An。 例1 設(shè)A=a,b, B=1,2,3, C=p,q, D=0, E= 。 (a) AB=a,1,a,2,a,3,b,1,b,2,b,3 (b)ABC=a,1,p,a,1,q,a,2,p,a,2,q,a,3,p,a,3,q,b,1,p,b,1,q,b,2,p,b,2,q,b,3,p,b,3,q, 如圖2.5-1所示。 (c) CD=p,o,q,o。