2.1 集合與集合運算

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

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

集合、屬於、相等

定義

集合

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

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

例子：

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

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

定理

外延性

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

符號上寫成：

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

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

證 $A \subset B$
證 $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，兩者才會不同。

建立新集合

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

運算	記號	定義
聯集	$A \cup B$	屬於 $A$ 或 $B$ 的元素
交集	$A \cap B$	同時屬於 $A$ 同 $B$ 的元素
差集	$A \setminus B$	屬於 $A$ 但不屬於 $B$ 的元素
補集	$A^c$	在所選全集內，不屬於 $A$ 的元素

補集一定要先指定全集 $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$ 、 $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 \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$ 」。

如何仔細證明集合恆等式

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

標準證法通常是：

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

例題

證明 $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^c$ 是「在全集外面的部分」。 $A \setminus B$ 是「A 之中但不在 B 之中的部分」。兩者有關，但不同。

常見錯誤

沒有全集就不可以寫補集

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

常見錯誤

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

解答

答案

為甚麼這一單元重要

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

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

邊讀邊試

比較一對集合

互動探索器讓你把元素加入或移出 A 與 B，並即時看見運算結果改變。

集合 A

集合 B

聯集

{1, 2, 3, 4}

交集

{2, 4}

差集 A \ B

{1}

2.1 集合與集合運算

MATH1090：集合論

集合、屬於、相等

集合

外延性

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

子集符號要留意本地慣例

集合列式與有界謂詞

不要忽略所在集合

集合不是 multiset

建立新集合

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

為甚麼補集一定要有全集

這些等式如何證

基本集合代數

示範：為甚麼 A⊂BA \subset BA⊂B 會推出 A∪B=BA \cup B = BA∪B=B

其他常見構造

笛卡兒積

有限次積

冪集

不交聯集

如何仔細證明集合恆等式

證明 A∩(B∖C)=(A∩B)∖CA \cap (B \setminus C) = (A \cap B) \setminus CA∩(B∖C)=(A∩B)∖C

如何正確閱讀 Venn 圖

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

有限集合如何計數

計一個聯集同冪集

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

子集證明檢查表

常見錯誤

補集不等於差集

沒有全集就不可以寫補集

積集順序有意義

小檢查

如果 A=a,b,cA = {a, b, c}A=a,b,c 而 B=b,c,dB = {b, c, d}B=b,c,d，A∩BA \cap BA∩B 是甚麼？

答案

為甚麼未指定全集之前，AcA^cAc 不夠清楚？

答案

十位學生去遠足。七位使用防曬，六位戴帽，兩位兩者皆沒有。多少位兩者皆有？

答案

如果 A⊂BA \subset BA⊂B，那麼 A∪BA \cup BA∪B 同 A∩BA \cap BA∩B 會簡化成甚麼？

答案

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

答案

為甚麼這一單元重要

比較一對集合

本節掌握 checkpoint

先備知識

本單元重點詞彙

Premium learning add-ons

本系列更多筆記

示範：為甚麼 $A \subset B$ 會推出 $A \cup B = B$

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

如果 $A = {a, b, c}$ 而 $B = {b, c, d}$ ， $A \cap B$ 是甚麼？

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

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

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