集合（Set）
將數個物件依照某個特性集合成的群體，群體中的個體稱為「元素」（element），常以大寫字母 A、B、C、S 等表示，元素則多以小寫字母 a、b、c、s 表示。
「集合」與「元素」的關係
若一元素 a 屬於某集合 A，記為「a∈A」；若另一元素 b 不屬於集合 A，記為「b∉A」。例如「√3」屬於「實數」這個集合，可記為「√3∈R」；「√3」不屬於「整數」這個集合，可記為「√3∉Z」。
若用 a、b、c、s 這四個元素屬於「A」這個集合，記為「A={a,b,c,s}」，也可以用謂詞搭配量詞表示，例如「B={x|(∀x)[x>5，x∈Z]} 代表「對於所有大於 5 的整數 x」這個集合。
集合的「基數（cardinal number）」
代表集合中元素的數量，如果一集合的基數為零，稱為「空集（empty set）」，記為「∅」或「{}」。
表示一集合 A 的基數可用下列符號表示，本文將以第一種為主：
- |A|
- #A
- A̅
- A̿
- Card(A)
集合間的關係
當有一個以上的集合時，可探討不同集合間的關係，一般常用「文氏圖（Venn diagram）」表示。
一、子集（subset）
若一集合 A 屬於另一集合 B，A 的每個元素都是 B 的元素，但 B 的元素不一定全部屬於 A，則 A 稱為 B 的「子集（subset）」，記為「A⊆B」，B 是 A 的「超集（superset）」，記為「B⊇A」。
在表示「子集」與「超集」的關係時，符號開口端固定朝向元素數量較多的「超集」。
A⊆B、B⊇A
「數」的集合關係
在數學中，有「N⊆Z⊆Q⊆R⊆C」這層關係，每個符號分別代表的意義如下：
- N：代表「自然數（natural number）」
- Z：代表「整數（integer）」
- Q：代表「有理數（rational number）」
- R：代表「實數（real number）」
- C：代表「複數（complex number）」
NZQRC關係圖
二、宇集／全集（universe） & 補集（complement）
「宇集」指一包含所有研究對象的集合，未包含在其特定子集者形成的集合稱為「補集／絕對差集（absolute complement）」。
宇集與補集的關係
給定一宇集 U，補集代表屬於 U、但不屬於 U 中另一集合 A 的元素所成的集合，記為「Aᶜ」。
例如若要研究複數時，以「C」這個集合為宇集，選擇當中的實數「R」為子集，「屬於複數，但不屬於實數」的集合「Rᶜ」即為「補集」。
複數（C）為宇集，Rᶜ 為實數（R）的補集
三、交集（intersection）& 聯集（union）
概念與「命題」類似，但符號較為圓滑，以「∩」表示「交集」、「∪」表示「聯集」。
左圖深藍處代表「A∩B」、右圖深藍處代表「A∪B」
有了「交集」與「聯集」表示兩集合間的關係，則可以整理出下列特性：
一集合 A 與空集 ∅ 及宇集 S 的關係：
- (Aᶜ ∩ A) = ∅
- (Aᶜ ∪ A) = S
- (A ∩ S) = A
- (A ∪ ∅) = S
兩集合 A、B 間的笛摩根定律：
- (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ
- (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ
四、差集／相對差集（relative complement）
指數個集合中，屬於某集合但不屬於其他集合的元素所成的集合，記為「\」或「–」。
例如有兩個集合 A、B，若集合 A 代表 30 的因數、集合 B 代表 20 的因數，則 B 在 A 的差集代表「是 30 的因數、但不是 20 的因數」這個集合，記為「A\B」或「A–B」，又可以記為「A∩Bᶜ」，該差集為 {3,6,15,30}。
相對的，A 在 B 的差集代表「是 20 的因數、但不是 30 的因數」這個集合，記為「B\A」或「B–A」，又可以記為「B∩Aᶜ」，該差集為 {4,20}。
左圖深藍處為「A\B」、右圖深藍處為「B\A」
五、對稱差集（symmetric difference）
指僅屬於單一集合、不屬於其他集合的集合，也就是聯集扣除交集形成的集合，計為「Δ」。
以上述「30 的因數為 A 集合、20 的因數為 B 集合」來說，兩者的對稱差集「AΔB」即為「(A∪B)–(A∩B)」，代表「僅為 30 的因數」與「僅為 20 的因數」形成的集合，包含 {3,4,6,15,20,30}。
深藍處代表「AΔB」
排容原理（inclusion–exclusion principle）
數個集合中，若要找到其聯集基數，可用反覆扣除交集、再加回反覆扣除的交集求得。
一、兩個集合的排容
將兩集合 A、B 相加後，扣除重複計算的交集部分，可得聯集「A∪B」，即「(|A∪B|)=(|A|+|B|)–(|A∩B|)」。
二、三個集合的排容
將兩集合 A、B 相加後，扣除兩集合間的交集，再加回重複扣除的三集合交集可得聯集「A∪B∪C」，即「(|A∪B∪C|)=(|A|+|B|+|C|)–(|A∩B|+|B∩C|+|A∩C|)+(|A∩B∩C|)」。
三、n 個集合的排容
將所有集合相加後，扣除重複計算的交集、再加回反覆扣除的交集，重複操作到每個交集都剛好計算到一次為止。
對於集合 A₁、A₂、...、Aₙ 而言，其排容過程可用下列公式表示：
四、排容原理應用－歐拉函數（Euler’s totient function）
「歐拉函數」代表對於一個正整數 n，所有小於等於 n 的正整數中，與 n 互質的數的數量，記為「φ」，例如 10 有 1、3、7、9 四個正整數與其互質，因此 φ(10)=4。
當一個正整數變得很大時，若要一一透過找出與其互質的數來求得其 φ 值，將會顯得不切實際，此時便可用「排容原理」與「補集」的觀念求解。
用「排容原理」求歐拉函數
舉例來說，如果要求 φ(120)，可以先將 120 做質因數分解，求得 120=2³·3¹·5¹，根據算術基本定理，這樣的分解方式是唯一的。
所有與 120 互質的數必不是 2 的倍數、不是 3 的倍數、也不是 5 的倍數，即下圖淺色底的外圍區域。
根據上圖，與 120 互質的數即在宇集為 1~120 的集合中，「A∪B∪C」的補集，即 φ(120)=120–[(|A|+|B|+|C|)–(|A∩B|+|B∩C|+|A∩C|)+(|A∩B∩C|)]。
- |A|=120/2=60、|B|=120/3=40、|C|=120/5=24
- |A∩B|=120/6=20、|B∩C|=120/15=8、|A∩C|=120/10=12
- |A∩B∩C|=120/30=4
φ(120)=120–[(60+40+24)–(20+8+12)+(4)]=120–88=32
用「排容原理」求歐拉函數的推廣
根據上述 φ(120) 的範例，可以假設若一數有三個質因數，則可以寫成下列關係式：
根據上述集合論關係圖，可得下列關係式：
將每一項通分，得：
將n提出來，得：
分子經整理，可得下列關係式：
這就是 n 有三個質因數時的歐拉函數公式！
類似的概念可推廣至一正整數 n 有 k 個質因數 P₁、P₂、…、Pₖ 時，該正整數 n=P₁ˣ¹ · P₂ˣ² ‧ … ‧ Pₖˣᵏ，則其歐拉函數公式如下：
上述公式的完整證明過程可參考維基百科。
笛卡爾積（Cartesian product）
代表全部有序對形成的集合，該有序對中的對象分別為不同集合的元素，以「×」表示，如「A 集合與 B 集合的笛卡爾積」記為「A × B」。
舉例來說，若 A 集合為 {1,2}、B 集合為 {a,b,c}，則 A × B = {{1,a},{1,b},{1,c},{2,a},{2,b},{2,c}}，「A 集合中的每個元素」各自與「B 集合中的每個元素」配對。
範例 A 集合與範例 B 集合的「笛卡爾積」
笛卡爾積的應用：SQL
在「結構化查詢語言（SQL）」中使用「交叉連接（cross join）」時，將回傳兩筆資料的笛卡爾積。
鴿巢原理（pigeonhole principle）
若 A 集合有 (n+1) 個元素、B 集合有 n 個元素，則不存在 A 到 B 的單射（injection）。
也就是說，B 集合中一定會有元素跟兩個以上 A 集合中的元素配對。
這樣講起來有點抽象，現在我們回歸原理名稱，換個生活化的情境理解：現假設 n=9，A 集合有 (9+1)=10 隻鴿子、B 集合有 9 個巢，那麼 B 集合中必定有一個巢會有兩隻鴿子。
「鴿巢原理」示意圖（取自維基百科）
鴿巢原理的應用：雜湊表／哈希表（hash table）
雜湊表可以依照鍵（key）值找到一資料的記憶體儲存位置，若記憶體共有 m 個儲存空間、資料共有 n 筆，則可定義「載荷因子（load factor）」如下：
如果 n 比 m 大，即載荷因子大於 1，要儲存的資料比可供儲存的空間還多，就會產生「雜湊衝突（collision）」，這就是「鴿巢原理」的應用情境。解決衝突的方式有封閉尋址（closed addressing / chaining）、開放定址（open addressing）等，詳細資訊可參考奮 game 王紫楓教學影片。
小結
- 集合：一具有特定相似特徵的母體，由元素組成其個體，若一元素屬於某集合，可用「∈」表示兩者間關係，反之用「∉」，符號開口端皆朝集合。
- 基數：代表集合內元素的數量。
- 空集（∅）：基數為零的集合。
- 子集：一集合中的另一集合，寫在「⊆」或「⊇」符號閉口端。
- 超集：包含另一集合的集合，寫在「⊆」或「⊇」符號開口端。
- 「數」的集合關係：N⊆Z⊆Q⊆R⊆C。
- 宇集／全集：所有探討對象皆為其元素的集合。
- 補集／絕對差集：宇集中，不包含在宇集內特定集合的集合。
- 交集（∩）：數個集合間重疊處。
- 聯集（∪）：包含數個集合間的重疊處與非重疊處。
- 差集／相對差集（\ 或 –）：數個集合中，僅屬於特定集合、不屬於其他集合處。
- 對稱差集（Δ）：數個集合間，所有僅屬於一個集合處加總。
- 排容原理：計算數個集合聯集時，反覆扣除重複計算的交集、再加回重複扣除的交集，直到每個交集都只被計算一次。
- 歐拉函數（φ）：表示與某一正整數互質的正整數數量，可用排容原理搭配補集觀念求解。
- 笛卡爾積（×）：不同集合間的有序對形成的集合，可應用於 SQL。
- 鴿巢原理：若一集合 A 的基數多於另一集合 B，則不存在 A 到 B 的單射，可應用於雜湊表。
