2.1 集合與集合運算

集合是用來描述一批對象的基本語言。在這一科之中，集合不是旁支內容， 而是邏輯、函數、關係，以及之後的數系構造的共同語言。

如果你現在覺得符號有些陌生，這是正常的。這一單元的目標就是令這套語言 變得足夠精確，使後面章節可以直接使用。

集合、屬於、相等

定義

集合

集合是一批對象所組成的整體。

如果 $x$ 是集合 $A$ 的元素，我們寫 $x \in A$；如果不是，就寫 $x \notin A$。

例子：

• $\{1, 2, 3\}$ 是集合。
• {香港島、九龍、新界} 是集合。
• $\varnothing$ 是空集合，也就是沒有任何元素的集合。

同一個集合可以有不同寫法，但集合本身只由元素決定。

定理

外延性

兩個集合相等，當且僅當它們擁有完全相同的元素。

符號上寫成：

$$A = B \iff \forall x\, (x \in A \leftrightarrow x \in B).$$

所以證明集合相等的標準方法是先證兩個包含關係：

1. 證 $A \subset B$
2. 證 $B \subset A$

常見錯誤

不要將集合相等與描述相等混淆

$\{1, 2, 3\}$ 同 $\{3, 2, 1\}$ 是同一個集合，因為元素完全一樣。列出順序 不重要。

常見錯誤

子集符號要留意本地慣例

本課程用 $A \subset B$ 表示「A 的每個元素都在 B 之中」。有些書會用 $A \subseteq B$ 表示這個意思，而將 $A \subset B$ 保留給 strict subset。 看書時要先確認慣例。

集合列式與有界謂詞

學過謂詞邏輯後，最常見的定義集合方式，是先指定一個已知集合，再保留當中 滿足某個條件的元素：

$$\{x \in S \mid P(x)\}.$$

這個記號要仔細讀。直線前面的部分說明變量可在哪個集合內取值；直線後面的 謂詞說明哪些元素會被留下。例如

$$\{n \in \mathbb{Z} \mid n \text{ is even}\}$$

就是所有偶整數的集合。

常見錯誤

不要忽略所在集合

$\{x \mid P(x)\}$ 有時是方便的簡寫，但嚴謹版本應該把變量限制在某個已知集合 之內。這樣做可以避免把任何文字描述都當成自動產生良好數學對象。

常見錯誤

集合不是 multiset

集合只記住某個對象是否出現，不記住它在列表中出現多少次。因此 $\{1,1,2,3\}$ 和 $\{1,2,3\}$ 描述同一個集合；若討論 multiset，兩者才會不同。

建立新集合

知道幾個集合之後，我們通常會想造出更多集合。標準運算就是用來做這件事。

補集一定要先指定全集 $E$。在這一單元之中，我們通常默認所有集合都在某個 固定 $E$ 之中，所以 $A^c$ 也就是 $E \setminus A$。

例題

追蹤元素如何經過幾個運算

設

$$A = \{1, 2, 4\}, \qquad B = \{2, 3, 4\},$$

而全集取作

$$E = \{1, 2, 3, 4, 5\}.$$

那麼就有：

• $A \cup B = \{1, 2, 3, 4\}$
• $A \cap B = \{2, 4\}$
• $A \setminus B = \{1\}$
• $B \setminus A = \{3\}$
• $A^c = \{3, 5\}$
• $(A \cup B)^c = \{5\}$

$A^c$ 不是 $A$ 自身的絕對性質。在不同「全集」之下，同一個集合的補集會不同。 所以一定要先知道目前正在使用哪一個全集。

這些等式如何證

本單元的集合恆等式不是靠背誦，而是靠逐個元素追蹤去證明。

定理

基本集合代數

對集合 $A$、$B$、$C$：

• $A \cup \varnothing = A$
• $A \cup B = B \cup A$
• $A \cup (B \cup C) = (A \cup B) \cup C$
• $A \cup A = A$
• $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$
• $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
• $(A \cup B)^c = A^c \cap B^c$
• $(A \cap B)^c = A^c \cup B^c$
• $(A^c)^c = A$
• $A \cap A^c = \varnothing$
• $A \cup A^c = E$
• $A \subset B$ 當且僅當 $A \cup B = B$
• $A \subset B$ 當且僅當 $A \cap B = A$
• $A \subset B$ 當且僅當 $B^c \subset A^c$

核心證法是 element chasing。譬如：

$$x \in A \cap (B \cup C) \iff x \in A \text{ 且 } (x \in B \text{ 或 } x \in C)$$

等價於

$$(x \in A \text{ 且 } x \in B) \text{ 或 } (x \in A \text{ 且 } x \in C),$$

所以又等價於

$$x \in (A \cap B) \cup (A \cap C).$$

證明：為甚麼 $A \subset B$ 會推出 $A \cup B = B$

假設 $A \subset B$。

要證 $A \cup B = B$，只要證兩個包含。

先證 $A \cup B \subset B$：如果 $x \in A \cup B$，那麼 $x \in A$ 或 $x \in B$。 若 $x \in A$，由 $A \subset B$ 得 $x \in B$。所以無論哪一種情況，都有 $x \in B$。

再證 $B \subset A \cup B$：如果 $x \in B$，那麼當然 $x \in A \cup B$。

所以 $A \cup B = B$。

證明：一個有條件的分配恆等式

命題

$$(A \cap B) \cup C = A \cap (B \cup C)$$

成立，當且僅當 $C \subset A$。

先證充分性。假設 $C \subset A$。若 $x$ 屬於左邊，則或者 $x \in A \cap B$，或者 $x \in C$。後一種情況由 $C \subset A$ 給出 $x \in A$，所以兩種情況都有 $x \in A$ 且 $x \in B \cup C$。因此左邊包含於右邊。反過來，若 $x \in A \cap (B \cup C)$，則 $x \in A$，並且或者 $x \in B$，或者 $x \in C$。前一種情況給出 $x \in A \cap B$，後一種情況給出 $x \in C$，所以 $x$ 屬於左邊。這就證明兩個集合相等。

再證必要性。假設等式成立，任取 $c \in C$。因為 $c \in (A \cap B) \cup C$，由等式可知 $c \in A \cap (B \cup C)$， 特別有 $c \in A$。因此 $C$ 的每一個元素都在 $A$ 中，即 $C \subset A$。 等價地，若存在 $c \in C \setminus A$，它會在左邊而不在右邊， 從而直接反駁該等式。

證明：對稱差滿足結合律

定義

$$A \mathbin{\triangle} B=(A\setminus B)\cup(B\setminus A).$$

對每個元素 $x$，

$$x\in A\mathbin{\triangle}B \iff (x\in A\text{ 且 }x\notin B)\text{ 或 }(x\notin A\text{ 且 }x\in B)$$

所以 $x$ 屬於對稱差，當且僅當 $A$、$B$ 中恰有一個包含 $x$。 再次應用這個規則可知，$x$ 屬於 $(A\mathbin{\triangle}B)\mathbin{\triangle}C$ 當且僅當 $x\in A$、$x\in B$、$x\in C$ 三個命題中恰有奇數個為真： 第一次對稱差記錄前兩個命題的奇偶性，第二次在 $x\in C$ 時翻轉這個奇偶性。 改變括號得到的 $A\mathbin{\triangle}(B\mathbin{\triangle}C)$ 也正好由同一個 奇偶條件刻畫。因此

$$(A\mathbin{\triangle}B)\mathbin{\triangle}C =A\mathbin{\triangle}(B\mathbin{\triangle}C)$$

這是逐元素證明，不依賴某一幅特定的 Venn 圖。

證明：補集反轉包含方向

設 $A,B\subseteq E$ 且 $A\subseteq B$。對 $x\in E\setminus B$，若 $x\in A$，包含關係會推出 $x\in B$，矛盾。所以 $x\in E\setminus A$，即 $B^c\subseteq A^c$。共同全集 $E$ 保證兩個補集比較的是同一範圍內的元素。

反例模式

聯集不能直接消去

$A\subseteq B\Rightarrow A\cup C\subseteq B\cup C$ 成立，但逆命題失敗。取 $A=\{1\}$、$B=\varnothing$、$C=\{1\}$，兩個聯集都等於 $\{1\}$，卻有 $A\nsubseteq B$。加入 $C$ 遮住了見證 1。一種正確修補是再假設 $A\cap C=\varnothing$：任意 $x\in A$ 屬於 $B\cup C$ 卻不屬於 $C$，因此屬於 $B$。

其他常見構造

這個課程後面亦會反覆用到以下幾種集合構造。

笛卡兒積

$A \times B$ 是所有有序對 $(a, b)$ 的集合，其中 $a \in A$ 而 $b \in B$。 次序是有意思的：$(a, b)$ 同 $(b, a)$ 一般不同。

如果 $|A| = 5$ 而 $|B| = 3$，那麼 $|A \times B| = 15$。

$R \times R = R^2$ 就是平面。

有限次積

$A^n$ 表示 $A$ 同自己做 $n$ 次笛卡兒積，也就是所有 $n$-tuple。

冪集

$P(A)$ 是 $A$ 的所有子集所組成的集合。

如果 $A$ 有 $n$ 個元素，那麼 $P(A)$ 就有 $2^n$ 個元素。另一個好用的理解方式 是 indicator function：每個子集都可以對應到一個 $A \to {0,1}$ 的函數。

例如

$$P(\{a, b\}) = \{\varnothing, \{a\}, \{b\}, \{a, b\}\}.$$

不交聯集

有時兩個集合在原來的寫法上可能有重疊，但我們又想保留每個元素的來源。 不交聯集就是透過標籤記住每件元素原本屬於哪一個集合。

直觀上，$A \sqcup B$ 就是「加上標記 1 的 $A$」和「加上標記 2 的 $B$」。

反例：乘積分配不一定成立

不一定存在

$$A \cup (B \times C) \quad\text{與}\quad (A \cup B) \times (A \cup C)$$

之間的雙射。取 $A = \{0,1\}$ 且 $B=C=\varnothing$。左邊就是 $A$， 有兩個元素；右邊是 $A \times A$，有四個有序對。基數不同，所以這個例子 中不存在雙射。

如何仔細證明集合恆等式

去到這一步，集合恆等式應該被理解成「屬元條件相同」的命題，而不是單靠 圖形背出來。

標準證法通常是：

1. 任取一個元素 $x$；
2. 將 $x \in$ 兩邊集合翻譯成邏輯條件；
3. 逐步化簡，直到兩邊變成同一句說話。

例題

證明 $A \cap (B \setminus C) = (A \cap B) \setminus C$

由

$$x \in A \cap (B \setminus C)$$

出發，就表示：

• $x \in A$，
• $x \in B$，
• $x \notin C$。

而這三個條件加埋，正正就是

$$x \in (A \cap B) \setminus C$$

的意思。

由於推理可以雙向讀回，所以兩邊集合相等。

這種逐元素追蹤的方法，之後會再次出現在德摩根律、關係，與數系構造之中。

如何正確閱讀 Venn 圖

Venn 圖適合用來整理情況，但證明仍然要回到屬元條件。圖形可以提示某個區域 為空、包含在另一個區域內，或被切成幾部分；正式文字則要說清楚這對應哪一個 包含關係、不交條件或計數等式。

對三個集合而言，$A \subset (B \cup C)$ 表示 $A$ 的每個元素都至少落在 $B$ 或 $C$ 其中之一。它不表示 $A \subset B$，也不表示 $A \subset C$。能否分清 這些可能性，是檢查自己是否真正用邏輯方式閱讀圖形的好方法。

例題

把四種 Venn 圖條件翻譯成區域語言

假設 $A$、$B$、$C$ 都是非空集合。以下常見練習條件，最好先讀成區域指令， 而不是只憑圖形印象處理。

條件	圖中必須呈現的意思
$A \subset B$、$C \subset B$，且 $A \cap C = \varnothing$	$A$ 與 $C$ 都在 $B$ 之內，但二者互不相交。$B$ 仍然可以有不屬於 $A$ 或 $C$ 的元素。
$A \cap B \ne \varnothing$、$A \cap C \ne \varnothing$、$B \cap C \ne \varnothing$，且 $A \cap B \cap C = \varnothing$	每兩個集合都有交集，但三者共同交集為空。因此三個 pairwise overlap 必須是分開的區域。
$A \subset (B \cap C)$，且 $B \subset C$	因為 $B \subset C$，所以 $B \cap C$ 其實就是 $B$。於是 $A$ 在 $B$ 之內，而 $B$ 又在 $C$ 之內。
$A \subset (B \cup C)$、並非 $A \subset B$、並非 $A \subset C$	$A$ 沒有元素落在 $B \cup C$ 之外，但 $A$ 必須至少有一個元素在 $C \setminus B$，亦至少有一個元素在 $B \setminus C$。

第四行最容易被誤讀。它不只是說 $A$ 同時碰到 $B$ 與 $C$；它還說 $A$ 完全 被 $B$ 與 $C$ 覆蓋，但又不能只由其中一個集合單獨覆蓋。

有限集合如何計數

集合語言不只用來分類，還直接控制計數。

如果 $A$、$B$ 都是有限集合，那麼：

• $|A \times B| = |A|\,|B|$；
• $|P(A)| = 2^\{|A|\}$；
• $|A \cup B| = |A| + |B| - |A \cap B|$。

聯集公式之所以要減交集，是因為交集之中的元素如果直接相加，會被計兩次。

例題

計一個聯集同冪集

假設 $|A| = 6$、$|B| = 5$、$|A \cap B| = 2$。

那麼就有

$$|A \cup B| = 6 + 5 - 2 = 9$$

再設 $S = \{a,b,c\}$。每個元素都只有兩個選擇：入某個子集，或者不入。 所以總共有

$$2 \cdot 2 \cdot 2 = 2^3 = 8$$

個子集。因此 $|P(S)| = 8$。

例題

不用畫圖也可以完成的 Venn 圖計數

十位學生去遠足。七位使用防曬，六位戴帽，兩位沒有任何防曬保護。

設 $S$ 是使用防曬的集合，$H$ 是戴帽的集合。由於兩位學生不在兩個集合之中，

$$|S \cup H| = 10 - 2 = 8.$$

由 inclusion-exclusion，

$$|S \cap H| = |S| + |H| - |S \cup H| = 7 + 6 - 8 = 5.$$

所以五位學生同時使用防曬並戴帽。

子集證明檢查表

子集證明會反覆出現，所以最好令它變成固定套路。

如果要證 $A \subseteq B$，就由任取 $x \in A$ 開始，再用 $A$ 的定義推出 足夠資訊，最後證明同一個 $x$ 其實都在 $B$ 之中。由於 $x$ 是任取，結論 就對 $A$ 的每個元素成立。

這個 direct proof 模式，之後在關係、偏序，與等價類之中也會再見到。

常見錯誤

常見錯誤

補集是相對於全集的差集

當 $A\subseteq E$ 時，補集 $A^c=E\setminus A$ 是「在指定全集 $E$ 內、但不屬於 $A$ 的部分」。 而 $A\setminus B$ 是「屬於 $A$、但不屬於 $B$ 的部分」。因此，補集是以全集為左運算元的差集， 不是全集以外的部分。

常見錯誤

沒有全集就不可以寫補集

如果你寫補集，一定要知道你是在甚麼全集之中做運算。否則 $^c$ 是含糊的。

常見錯誤

積集順序有意義

$A \times B$ 同 $B \times A$ 一般包含不同有序對。這個就是為甚麼函數與關係要用積集語言。

小檢查

思考檢查

為甚麼未指定全集之前，$A^c$ 不夠清楚？

先問補集是「在甚麼範圍內」取外面。

解答 · 答案

因為同一個集合在不同全集之中，補集可以完全不同。

思考檢查

如果 $A \subset B$，那麼 $A \cup B$ 同 $A \cap B$ 會簡化成甚麼？

用上面的 absorption laws。

解答 · 答案

$A \cup B = B$，而 $A \cap B = A$。

思考檢查

假設 $A \subset (B \cup C)$，但 $A$ 不是 $B$ 的子集，也不是 $C$ 的子集。$A$ 的哪兩個部分必須非空？

把每一個「不是子集」的敘述翻譯成存在某個元素。

解答 · 答案

必須至少有一個 $A$ 的元素在 $C \setminus B$，並且至少有一個 $A$ 的元素在 $B \setminus C$。條件 $A \subset (B \cup C)$ 則排除了 $A$ 有元素同時不在 $B$ 和 $C$ 的可能。

為甚麼這一單元重要

這一單元是後面數系構造的語言基礎。

• $N^2$ 會用來構造整數。
• 等價類會用來構造有理數。
• 一個集合上的關係會變成偏序和等價關係的語言。
• 冪集和笛卡兒積會在之後說明 family、tuple、以及各種構造時再出現。