離散數(shù)學(xué)（集合論）
集合的基本概念
集合的元素
屬于\(\in\)
空集\(\varnothing\) 全集
有限集 、無限集
集合的元素數(shù)（基數(shù)）：特別的：| \(\varnothing\) |=0，|{\(\varnothing\)}|=1
集合的特征：確定性、互異性、無序性、多樣性
集合相等：兩個集合A和B的元素完全一樣
子集(subset) ：設(shè)A，B是兩個集合，若A的元素都是B的元素，則稱A是B的子集，也稱B包含A，或A包含于B記以A \(\subseteq\)B
若A\(\subseteq\)B，且A\(\ne\)B，則稱A是B的真子集(proper subset)，也稱B真包含A，或A真包含于B，記以A\(\subset\)B
集合的運算及性質(zhì)：
并集(Union)：
交集(Intersection)：
差集(Difference)：
余集(Complement)：
環(huán)和（對稱差）：
環(huán)積：
集合的算律：
集合的證明題：
集合的冪與笛卡爾積：
冪集的性質(zhì)：
2.
3.
有序n元組(ordered n-tuple)：(a1,a2 ,… ,an)
有序?qū)?ordered pairs)：當(dāng)n=2 時，將其稱作有序?qū)?，也稱作序偶，或有序二元組
有序?qū)μ攸c：
- 若a\(\ne\)b,則（a，b）\(\ne\)（b，a）
- 兩個有序?qū)?a,b)和(c,d)相等當(dāng)且僅當(dāng)a=c，b=d
笛卡兒積(Cartesian product)：
笛卡兒積的性質(zhì)：
-
|A\(\times\)B|=|A| \(\times\)|B|；
-
對任意集合A，有A\(\times\)\(\varnothing\)=\(\varnothing\)，\(\varnothing\)\(\times\)A=\(\varnothing\)；
-
笛卡兒積運算不滿足交換律，即A\(\times\)B\(\ne\)B\(\times\)A；
-
笛卡兒積運算不滿足結(jié)合律，即(A\(\times\)B)\(\times\)C\(\ne\)A\(\times\)(B\(\times\)C)
-
笛卡兒積運算對并和交運算滿足分配律
-
設(shè)A，B，C，D是集合，若A\(\subseteq\)C且B\(\subseteq\)D，則A\(\times\)B \(\subseteq\) C\(\times\)D。
證明集合的包含關(guān)系的常用方法：
- 利用定義：首先任取x\(\in\)A，再演繹地證出x\(\in\)B成立
- 設(shè)法找到一個集合T,滿足A\(\subseteq\)T且T\(\subseteq\)B,由包含關(guān)系的傳遞性有A\(\subseteq\)B.
- 利用A\(\subseteq\)B的等價定義,即A\(\cup\)B=B,A\(\cap\)B=A或A-B=\(\varnothing\)來證.
- 利用已知包含式的并、交等運算得到新的包含式
- 反證法
證明集合相等的常用方法：
-
若A，B 是有限集，證明A=B可通過逐一比較兩集合所有元素均一一對應(yīng)相等，若A，B 是無限集，通過證明集合包含關(guān)系的方法證A \(\subseteq\) B，B \(\subseteq\) A即可
-
反證法
-
利用集合的基本算律以及已證明的集合等式，通過相等變換將待證明的等式左（右）邊的集合化到右（左）邊的集合，或者兩邊同時相等變換到同一集合
關(guān)系
非空集合中的空關(guān)系是反自反的、對稱的、反對稱的和傳遞的，但不是自反的；
空集合中的空關(guān)系則是自反的、反自反的、對稱的、反對稱的和傳遞的。
關(guān)系的定義：xRy
關(guān)系的特點：
-
A\(\times\)A的任一子集都是A上的一個關(guān)系
-
若|A|=n，則A上的關(guān)系有\(2^{\mathrm{n}^2}\)個
-
A上有三個特殊關(guān)系，即
空關(guān)系\(\varnothing\)；
全域關(guān)系EA=A\(\times\)A；
相等關(guān)系IA={(x,x)|x\(\in\)A}
關(guān)系的表示：
-
集合表示：
設(shè)A={1,2,3,4}， A上的關(guān)系R=
-
關(guān)系矩陣
-
關(guān)系圖：
關(guān)系作為集合的運算：
- 關(guān)系的交：R ∩ S={(x,y)|x\(\in\)A, y\(\in\)A,xRy且xSy}
- 關(guān)系的并：R∪ S={(x,y)| x\(\in\)A, y\(\in\)A ,xRy或xSy}
- 關(guān)系的差：R - S={(x,y)| x\(\in\)A, y\(\in\)A ,xRy并且xS/y}
逆關(guān)系：\(\mathrm{R}^{-1}\) ={(y, x)|x\(\in\)A, y\(\in\)A, 并且有xRy}
關(guān)系的乘積：稱關(guān)系R?S為關(guān)系R和S的乘積或合成
關(guān)系的乘法的結(jié)論：
- 關(guān)系的乘法不滿足交換律
- 關(guān)系的乘法滿足結(jié)合律
關(guān)系的冪
定理1.2.1 ：
- \(\mathrm{R}^{\mathrm{m}}\cdot \mathrm{R}^{\mathrm{n}}=\mathrm{R}^{\mathrm{m}+\mathrm{n}}\)
- \(\left( \mathrm{R}^{\mathrm{m}} \right) ^{\mathrm{n}}=\mathrm{R}^{\mathrm{mn}}\)
定理1.2.3：
幾種特殊關(guān)系及特點：
-
自反關(guān)系：
-
反自反關(guān)系
-
對稱關(guān)系
-
反對稱關(guān)系
-
傳遞關(guān)系
定理1.2.4 ：集合A上的關(guān)系R具有傳遞性的充要條件是\(\mathrm{R}^2\subseteq \mathrm{R}\)
常用結(jié)論：
集合A上的關(guān)系是對稱的，反對稱的，試指明關(guān)系R的結(jié)構(gòu)——\(\mathrm{I}_{\mathrm{A}}\)的任意子集
集合A有n個元素，則A上有多少個即具有對稱性又具有反對稱性的關(guān)系？ \(2^{\mathrm{n}}\)（取對角線元素）
關(guān)系的性質(zhì)總結(jié)：
關(guān)系的閉包：R 的自反閉包、對稱閉包和傳遞閉包分別記為r(R)，s(R)，t(R) ，也稱r， s，t為閉包運算，它們作用于關(guān)系R后，產(chǎn)生包含R的最小的自反、對稱、傳遞的關(guān)系。
等價關(guān)系：如果R具有自反性，對稱性，傳遞性，則稱R是一個等價關(guān)系
等價類
定理1.2.7：
劃分：
商集：設(shè)R是非空集合A上的等價關(guān)系，以R的所有不同等價類為元素作成的集合稱為A關(guān)于R的商集，簡稱A的商集，記作A/R
等價關(guān)系=>商集：
商集=>等價關(guān)系：
定理1.2.8 ：設(shè)A為一個非空集合。
(1)設(shè)R為A上的任意一個等價關(guān)系，則對應(yīng)R的商集A/R為A的一個劃分。
(2)設(shè)C為A的任一個劃分，令\(\mathrm{R}_{\mathrm{c}}\)={(x,y)|x, y\(\in\)A并且x, y屬于C的同一劃分塊}， 則\(\mathrm{R}_{\mathrm{c}}\)為A上的等價關(guān)系
第二類Stirling數(shù) ：
將n個不同的球放入r個相同的盒中去，并且要求無空盒，有多少種不同的放法？這里要求n\(\geqslant\)r。
不同的放球方法數(shù)即為將n元集合A分為r塊的不同的劃分數(shù)。
（1）特值：
（2）遞推公式：
加細：設(shè)C和C'都是集合A的劃分，若C的每個劃分塊都包含于C'的某個劃分塊中，則稱C是 C '的加細。
C是C'的加細當(dāng)且僅當(dāng)\(\mathrm{R}_{\mathrm{c}}\)$\subseteq $$\mathrm{R}_{\mathrm{c'}}$
綜合例題：
偏序關(guān)系：
自反性，反對稱性，傳遞性
偏序集(半序集、部分序集)。記作(A，R)
寫做“≤”
哈斯圖：
鏈：
對任意x, y\(\in\)A，如果x≤y，或y≤x，稱x與y可比
一個部分序集的子集，其中任意兩個元素都可比，稱該子集為一條鏈
全序集：一個部分序集(A, ≤)說是一個全序集，如果(A, ≤)本身是一條鏈
擬序關(guān)系：
反自反性，反對稱，傳遞性
最大(最小)元 極大(極小)元 ：只從給定集合里找
上(下)界，上(下)確界：從全體里找
上(下)確界：找所有上(下)界里距離所求集合最近的上(下)界。
上下界未必存在，存在時又未必唯一.
即使有上下界時，最小上界和最大下界也未必存在。
映 射
映射：設(shè)A，B是兩個集合，若對A的每個元素a，規(guī)定了B的一個確定元素b與之對應(yīng)，則稱此對應(yīng)為由A到B內(nèi)的一個映射
將此映射記為\(\mathrm{\sigma}\)，于是對任意a\(\in\)A，若\(\mathrm{\sigma}\)(a)= b，則b表示B中與a對應(yīng)之元素，b稱為a的映像(image)，a稱為b的原像(pre-image)
滿射：設(shè)\(\mathrm{\sigma}\)是A到B內(nèi)的映射，如果B中每一個元素都一定是A中某元素的映像，就稱\(\mathrm{\sigma}\)是A到B上的映射（滿射）
白話：B中所有元素都被箭頭指向。
特別，A到A上的映射，稱為變換
單射：設(shè)\(\mathrm{\sigma}\)是A到B內(nèi)的映射，如果對任意a\(\in\)A，b\(\in\)A且a\(\ne\)b，都有\(\mathrm{\sigma}\)(a) \(\ne\)\(\mathrm{\sigma}\)(b)，就稱\(\mathrm{\sigma}\)是A到B的單射
白話：B中的元素最多只能有一個箭頭指向。
注意：單射未必滿射；滿射未必單射
1-1映射（雙射）：既滿射，又單射。
逆映射
映射的乘積：\(\mathrm{\sigma}\cdot \mathrm{\tau}=\mathrm{\tau}*\mathrm{\sigma}\)（運算順序相反）
集合的基數(shù) ：有限集合的元素數(shù)(勢，濃度)。集合A的基數(shù)記為|A|
1-1映射，則稱A與B基數(shù)相同，也稱A與B對等（等勢，等濃），記為|A|=|B|
把自然數(shù)集合的基數(shù)記為\(\aleph _0\)（讀作阿列夫零），于是凡是與自然數(shù)集合對等的集合A，其基數(shù)|A|=\(\aleph _0\)
若A與B的某一子集有1-1對應(yīng)關(guān)系，則|A|\(\leqslant\)|B|；若A與B的某一子集有1-1對應(yīng)關(guān)系，且A與B不存在1-1對應(yīng)關(guān)系，則|A|<|B|
可數(shù)集合：
一個集合，如果它的元素為有限個，或者它與自然數(shù)集合之間存在一個1-1映射，則稱此集合為可數(shù)集合。否則稱該集合為不可數(shù)集合。元素個數(shù)不是有限的可數(shù)集合稱為可數(shù)無窮集合。
定理1.3.2：可數(shù)集合的子集仍為可數(shù)集合。
定理1.3.3： 設(shè)A，B是可數(shù)集合，A∩B= \(\varnothing\) ，則A∪B是可數(shù)集合
定理1.3.4：設(shè)A，B是可數(shù)無窮集合，則A\(\times\)B是可數(shù)集合。
常用結(jié)論：
有理數(shù)集合Q是可數(shù)集合
整數(shù)的集合Z是可數(shù)無窮集
可數(shù)無窮多個可數(shù)集合的并集是可數(shù)集合。
不可數(shù)集合：
定理1.3.5 ：全體實數(shù)做成的集合是不可數(shù)集合
推論：實數(shù)集合R，區(qū)間(a,+\(\infty\))、[a,b]、[a,b)、(a,b]，其中a≠b，都是不可數(shù)的，且與區(qū)間(0,1)等濃。
把(0,1)區(qū)間內(nèi)的實數(shù)集合的基數(shù)記為c，也記為\(\aleph _1\)。即c= \(\aleph _1\)
可數(shù)(無窮多)個基數(shù)為c的集合的并集基數(shù)仍為c
往期回顧
離散數(shù)學(xué)（集合論）
離散數(shù)學(xué)（古典數(shù)理邏輯）
離散數(shù)學(xué)（圖與網(wǎng)絡(luò)）
離散數(shù)學(xué)（數(shù)論基礎(chǔ)）
離散數(shù)學(xué)（格與布爾代數(shù)）
離散數(shù)學(xué)（群、環(huán)、域）
浙公網(wǎng)安備 33010602011771號