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