2.1 集合與集合運算

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

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

集合、屬於、相等

例子：

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

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

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

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

建立新集合

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

| 運算 | 記號 | 定義 | | --- | --- | --- | | 聯集 | $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$。

這些等式如何證

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

核心證法是 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 \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$」。

如何仔細證明集合恆等式

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

標準證法通常是：

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

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

有限集合如何計數

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

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

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

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

子集證明檢查表

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

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

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

常見錯誤

小檢查

為甚麼這一單元重要

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

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