2.1 簡介
在討論數學的任何分支時，使用集合論的符號和術語都是很有幫助的。這門學科由布林（Boole）和康托爾（Cantor）在 19 世紀後半葉發展起來，對 20 世紀數學的發展產生了深遠的影響。它將許多看似無關的概念統一起來，並以優雅且系統化的方式，幫助將許多數學概念簡化至其邏輯基礎。
我們不會試圖對集合論進行系統性的處理，而是僅限於討論一些更基本的概念。希望進一步探索該主題的讀者可以參考本章末尾的參考文獻。
將一組物件視為單一實體的收集將被稱為「集合（set）」。該收集中的物件將被稱為集合的「元素（elements）」或「成員（members）」，並說它們「屬於（belong to）」或「包含於（be contained in）」該集合。反過來，集合將被說成「包含（contain）」或「由其元素組成（be composed of）」。在大多數情況下，我們感興趣的是數學物件的集合；也就是說，數字、點、函數、曲線等物件的集合。然而，由於集合論的許多內容並不依賴於收集中個別物件的性質，因此透過討論其元素可以是任何種類物件的集合，我們在思維上獲得了極大的精簡。正是因為這種一般性的特質，集合論在推動數學發展方面才有了如此強大的影響力。
2.2 符號
集合通常用大寫字母表示：
$A, B, C, ..., X, Y, Z$
而元素用小寫字母表示：$a, b, c, ..., x, y, z$。我們寫作 $x \in S$ 來表示「x 是 S 的一個元素」或「x 屬於 S」。如果 x 不屬於 S，我們寫作 $x \notin S$。我們有時透過在大括號中顯示元素來指定集合；例如，小於 10 的正偶數集合記為 $\{2, 4, 6, 8\}$。如果 S 是所有滿足性質 P 的 x 的收集，我們藉由寫出以下符號來簡要地表示：
$S = \{x : x \text{ 滿足 } P\}$
從一個給定的集合中，我們可以形成新的集合，稱為給定集合的「子集（subsets）」。例如，由小於 10 且可被 4 整除的正整數所組成的集合，即 $\{4, 8\}$，是小於 10 的偶數集合的子集。一般來說，我們說集合 A 是 B 的一個子集，並寫作 $A \subseteq B$，只要 A 的每一個元素也屬於 B。陳述 $A \subseteq B$ 並不排除 $B \subseteq A$ 的可能性。事實上，我們同時有 $A \subseteq B$ 和 $B \subseteq A$ 若且唯若 A 和 B 具有相同的元素。在這種情況下，我們將稱集合 A 和 B 相等，並寫作 $A = B$。如果 A 和 B 不相等，我們寫作 $A \ne B$。如果 $A \subseteq B$ 但 $A \ne B$，那麼我們說 A 是 B 的一個「真子集（proper subset）」。
考慮一個不包含任何元素的集合是方便的；這個集合被稱為「空集合（empty set）」，我們同意稱其為每一個集合的子集。讀者可能會發現將集合想像為一個包含某些物件（其元素）的盒子會有所幫助。那麼空集合就是一個空盒子。我們用符號 $\emptyset$ 來表示空集合。
2.3 有序對
假設我們有一個由兩個元素 a 和 b 組成的集合；也就是集合 $\{a, b\}$。根據我們對相等的定義，這個集合與集合 $\{b, a\}$ 是相同的，因為不涉及順序問題。然而，也有必要考慮順序很重要的兩個元素的集合。例如，在平面的解析幾何中，點的座標 $(x, y)$ 代表一對有序的數字。點 $(3, 4)$ 與點 $(4, 3)$ 是不同的，而集合 $\{3, 4\}$ 則與集合 $\{4, 3\}$ 相同。當我們希望將兩個元素 a 和 b 的集合視為有順序時，我們將把元素括在括號中：$(a, b)$。那麼 a 稱為第一個元素，b 稱為第二個元素。給出有序對物件 $(a, b)$ 概念的純集合論定義是可能的。其中一個定義如下：
定義 2.1. $(a, b) = \{\{a\}, \{a, b\}\}$。
這個定義指出 $(a, b)$ 是一個包含兩個元素的集合，即 $\{a\}$ 和 $\{a, b\}$。使用這個定義，我們可以證明以下定理：
定理 2.2. $(a, b) = (c, d)$ 若且唯若 $a = c$ 且 $b = d$。
這個定理表明定義 2.1 是一個「合理」的有序對定義，意思是物件 a 已經與物件 b 區分開來。定理 2.2 的證明是一個有益的習題。（參見習題 2.1。）
2.4 兩個集合的笛卡兒乘積 (Cartesian Product)
定義 2.3. 給定兩個集合 A 和 B，所有使得 $a \in A$ 且 $b \in B$ 的有序對 $(a, b)$ 所組成的集合，被稱為 A 和 B 的笛卡兒乘積，並記為 $A \times B$。
例子。如果 R 表示所有實數的集合，那麼 $R \times R$ 就是所有複數的集合。
2.5 關係與函數 (Relations and Functions)
令 x 和 y 表示實數，使得有序對 $(x, y)$ 可以被認為代表 xy 平面上一個點（或一個複數）的直角座標。我們經常會遇到像這樣的表達式
$xy = 1$,
$x^2 + y^2 = 1$,
$x^2 + y^2 \le 1$,
$x < y$.
這些表達式中的每一個都定義了實數有序對 $(x, y)$ 的某個集合，也就是所有滿足該表達式的對 $(x, y)$ 所組成的集合。這樣的一個有序對集合被稱為「平面關係（plane relation）」。在 xy 平面上繪製出的對應點集合被稱為該關係的「圖形（graph）」。
「關係」的概念可以相當一般化地闡述，使得對 $(x, y)$ 中的物件 x 和 y 不必是數字，而可以是任何種類的物件。
定義 2.4. 任何有序對的集合都被稱為關係。
如果 S 是一個關係，在 S 中的對 $(x, y)$ 作為第一個成員出現的所有元素 x 的集合被稱為 S 的「定義域（domain）」，記為 $\mathfrak{D}(S)$。第二個成員 y 的集合被稱為 S 的「值域（range）」，記為 $\mathfrak{R}(S)$。
像方程式 $xy=1$ 這樣定義的關係是一種稱為「函數（function）」的特殊關係。
定義 2.5. 函數 F 是一個有序對 $(x, y)$ 的集合，其中沒有任何兩個有序對具有相同的第一個成員。也就是說，如果 $(x, y) \in F$ 且 $(x, z) \in F$，那麼 $y = z$。
函數的定義要求，對於 F 的定義域中的每一個 x，都恰好存在一個 y 使得 $(x, y) \in F$。我們習慣稱 y 為 F 在 x 的「值（value）」，並寫成
$y = F(x)$
而不是 $(x, y) \in F$ 來表示對 $(x, y)$ 在集合 F 中。
除了藉由指定函數 F 包含的有序對來描述函數之外，通常更好的做法是描述 F 的定義域，然後對於定義域中的每個 x，描述函數值 $F(x)$ 是如何取得的。在這方面，我們有以下定理，其證明留作練習。
定理 2.6. 兩個函數 F 和 G 相等若且唯若：
a) $\mathfrak{D}(F) = \mathfrak{D}(G)$ （F 和 G 具有相同的定義域），並且
b) 對於 $\mathfrak{D}(F)$ 中的每一個 x，都有 $F(x) = G(x)$。
2.6 關於函數的進一步術語
當定義域 $\mathfrak{D}(F)$ 是 R 的一個子集時，F 被稱為一個實變數的函數（function of one real variable）。如果 $\mathfrak{D}(F)$ 是 C（複數系統）的一個子集，那麼 F 被稱為複變函數（function of a complex variable）。
如果 $\mathfrak{D}(F)$ 是笛卡兒乘積 $A \times B$ 的一個子集，那麼 F 被稱為雙變數函數（function of two variables）。在這種情況下，我們將函數值記為 $F(a, b)$ 而不是 $F((a, b))$。一個兩個實變數的函數是指其定義域為 $R \times R$ 子集的函數。
如果 S 是 $\mathfrak{D}(F)$ 的一個子集，我們說 F 定義在 S 上。在這種情況下，使得 $x \in S$ 的 $F(x)$ 的集合被稱為 S 在 F 下的「像（image）」，並記為 $F(S)$。如果 T 是任何包含 $F(S)$ 的集合，那麼 F 也被稱為從 S 到 T 的一個「映射（mapping）」。這通常藉由寫出
$F : S \rightarrow T$
來表示。如果 $F(S) = T$，該映射被說成是「映成（onto）」T。S 到自身的映射有時稱為「轉換（transformation）」。
例如，考慮由方程式 $F(z) = z^2$ 定義的複變函數。這個函數將複數 z 平面上形式為 $0 \le \arg(z) \le \alpha \le \pi/2$ 的每一個扇形 S 映射到由不等式 $0 \le \arg[F(z)] \le 2\alpha$ 所描述的扇形 $F(S)$ 上。
如果兩個函數 F 和 G 滿足包含關係 $G \subseteq F$，我們說 G 是 F 的「限制（restriction）」或 F 是 G 的「擴張（extension）」。特別是，如果 S 是 $\mathfrak{D}(F)$ 的一個子集，並且如果 G 由方程式
$G(x) = F(x)$ 對於所有 S 中的 x
所定義，那麼我們稱 G 為 F 到 S 的限制。該函數 G 由那些使得 $x \in S$ 的對 $(x, F(x))$ 組成。它的定義域是 S 且它的值域是 $F(S)$。
2.7 一對一函數與反函數 (One-to-one Functions and Inverses)
定義 2.7. 令 F 為定義在 S 上的一個函數。我們說 F 在 S 上是「一對一的（one-to-one）」，若且唯若對於 S 中的每一個 x 和 y，
$F(x) = F(y)$ 蘊含 $x = y$。
這等同於說，在 S 上一對一的函數會將不同的函數值分配給 S 中不同的成員。這樣的函數也被稱為單射（injective）。它們很重要，因為正如我們馬上就會看到的，它們具有反函數。然而，在陳述反函數的定義之前，先引入一個更一般的概念，即「反關係（converse of a relation）」的概念是很方便的。
定義 2.8. 給定一個關係 S，由以下所定義的新關係 $\tilde{S}$：
$\tilde{S} = \{(a, b) : (b, a) \in S\}$
被稱為 S 的反關係。
因此，一個有序對 $(a, b)$ 屬於 $\tilde{S}$ 若且唯若元素互換後的對 $(b, a)$ 屬於 S。當 S 是一個平面關係時，這僅僅意味著 $\tilde{S}$ 的圖形是 S 的圖形關於直線 $y = x$ 的反射。在由 $x < y$ 定義的關係中，其反關係由 $y < x$ 所定義。
定義 2.9. 假設關係 F 是一個函數。考慮其反關係 $\tilde{F}$，它可能是一個函數，也可能不是。如果 $\tilde{F}$ 也是一個函數，那麼 $\tilde{F}$ 被稱為 F 的「反函數（inverse）」，並記為 $F^{-1}$。
下一個定理告訴我們，在其定義域上一對一的函數總是具有反函數。
定理 2.10. 如果函數 F 在其定義域上是一對一的，那麼 $\tilde{F}$ 也是一個函數。
證明. 為了證明 $\tilde{F}$ 是一個函數，我們必須證明如果 $(x, y) \in \tilde{F}$ 且 $(x, z) \in \tilde{F}$，那麼 $y = z$。但是 $(x, y) \in \tilde{F}$ 意味著 $(y, x) \in F$；也就是說，$x = F(y)$。類似地，$(x, z) \in \tilde{F}$ 意味著 $x = F(z)$。因此 $F(y) = F(z)$，而且由於我們假設 F 是一對一的，這蘊含了 $y = z$。因此，$\tilde{F}$ 是一個函數。
註：相同的論證顯示，如果 F 在 $\mathfrak{D}(F)$ 的一個子集 S 上是一對一的，那麼 F 到 S 的限制具有一個反函數。
2.8 合成函數 (Composite Functions)
定義 2.11. 給定兩個函數 F 和 G，使得 $\mathfrak{R}(F) \subseteq \mathfrak{D}(G)$，我們可以形成一個新函數，即 G 和 F 的合成 $G \circ F$，定義如下：對於 F 定義域中的每一個 x，$(G \circ F)(x) = G[F(x)]$。
由於 $\mathfrak{R}(F) \subseteq \mathfrak{D}(G)$，元素 $F(x)$ 在 G 的定義域中，因此考慮 $G[F(x)]$ 是有意義的。一般來說，$G \circ F = F \circ G$ 並不成立。事實上，$F \circ G$ 可能是沒有意義的，除非 G 的值域包含在 F 的定義域中。然而，結合律
$H \circ (G \circ F) = (H \circ G) \circ F$
只要方程式的兩邊都有意義，就總是成立的。（驗證這一點對讀者來說將是一個有趣的習題。參見習題 2.4。）
2.9 數列 (Sequences)
在定義於整數子集上的函數中，有幾個重要的例子。
定義 2.12. 所謂 n 項的有限數列，我們指的是一個定義域為數字集合 $\{1, 2, ..., n\}$ 的函數 F。
F 的值域是集合 $\{F(1), F(2), F(3), ..., F(n)\}$，習慣上寫作 $\{F_1, F_2, F_3, ..., F_n\}$。值域的元素稱為數列的「項（terms）」，當然，它們可以是任何種類的任意物件。
定義 2.13. 所謂無窮數列，我們指的是一個定義域為所有正整數集合 $\{1, 2, 3, ...\}$ 的函數 F。F 的值域，也就是集合 $\{F(1), F(2), F(3), ...\}$，也寫作 $\{F_1, F_2, F_3, ...\}$，且函數值 $F_n$ 被稱為數列的第 n 項。
為了簡潔起見，我們經常使用符號 $\{F_n\}$ 來表示第 n 項為 $F_n$ 的無窮數列。
令 $S = \{s_n\}$ 為一個無窮數列，並令 k 是一個定義域為正整數集合、值域為正整數子集的函數。假設 k 是「保序的（order-preserving）」，也就是說，假設
$k(m) < k(n)$，如果 $m < n$。
那麼合成函數 $s \circ k$ 對於所有整數 $n \ge 1$ 都有定義，並且對於每一個這樣的 n，我們有
$(s \circ k)(n) = s_{k(n)}$
這樣的一個合成函數被稱為 s 的一個「子數列（subsequence）」。同樣地，為了簡潔，我們經常使用符號 $\{s_{k(n)}\}$ 或 $\{s_{k_n}\}$ 來表示 $\{s_n\}$ 的這個第 n 項為 $s_{k(n)}$ 的子數列。
例子。令 $s = \{1/n\}$ 並令 k 定義為 $k(n) = 2^n$。那麼 $s \circ k = \{1/2^n\}$。
2.10 對等（等勢）集合 (Similar (Equinumerous) Sets)
定義 2.14. 兩個集合 A 和 B 被稱為相似或等勢的（similar, or equinumerous），且我們寫作
$A \sim B$
若且唯若存在一個一對一函數 F，其定義域為集合 A，值域為集合 B。
我們也說 F 在集合 A 和 B 之間建立了一對一的對應關係。顯然，每一個集合 A 都與其自身相似（取 F 為「恆等」函數，使得對於所有 A 中的 x，$F(x) = x$）。此外，如果 $A \sim B$，那麼 $B \sim A$，因為如果 F 是一個使 A 與 B 相似的一對一函數，那麼 $F^{-1}$ 就會使 B 與 A 相似。同樣地，如果 $A \sim B$ 且 $B \sim C$，那麼 $A \sim C$。
2.11 有限與無限集合 (Finite and Infinite Sets)
一個集合 S 被稱為有限的（finite），並且被說成包含 n 個元素，如果
$S \sim \{1, 2, ..., n\}$。
整數 n 被稱為 S 的基數（cardinal number）。證明如果 $\{1, 2, ..., n\} \sim \{1, 2, ..., m\}$ 那麼 $m = n$ 是一個簡單的練習。因此，有限集合的基數是良好定義的。空集合也被認為是有限的。它的基數被定義為 0。
非有限的集合被稱為無限集合（infinite sets）。兩者之間主要的差異在於，無限集合必然與其本身的某個真子集相似，而有限集合不可能與其本身的任何真子集相似。例如，所有正整數的集合 $Z^+$ 與由 2 的次方組成的真子集 $\{2, 4, 8, 16, ...\}$ 是相似的。使它們相似的一對一函數 F 由對於 $Z^+$ 中的每一個 x，$F(x) = 2^x$ 來定義。
2.12 可數與不可數集合 (Countable and Uncountable Sets)
一個集合 S 如果與所有正整數的集合等勢，則被稱為可數無限的（countably infinite）；也就是說，如果
$S \sim \{1, 2, 3, ...\}$。
在這種情況下，存在一個函數 f 在正整數與 S 的元素之間建立了一對一的對應關係；因此集合 S 可以如下展示：
$S = \{f(1), f(2), f(3), ...\}$
我們經常使用下標並將 $f(k)$ 記為 $a_k$（或類似符號），然後寫作 $S = \{a_1, a_2, a_3, ...\}$。這裡重要的是，這個對應關係使我們能夠使用正整數作為 S 中元素的「標籤（labels）」。一個可數無限的集合被說成具有基數 $\aleph_0$（讀作：aleph nought）。
定義 2.15. 一個集合 S 被稱為「可數的（countable）」，如果它是有限的或是可數無限的。一個不可數的集合被稱為「不可數的（uncountable）」。
定理 2.16. 可數集合的每一個子集都是可數的。
證明. 令 S 為給定的可數集合，並假設 $A \subseteq S$。如果 A 是有限的，就沒有什麼需要證明的了，所以我們可以假設 A 是無限的（這意味著 S 也是無限的）。令 $S = \{s_n\}$ 是一個具有不同項的無窮數列，使得
$S = \{s_1, s_2, ...\}$
在正整數上定義一個函數如下：
令 $k(1)$ 為使得 $s_m \in A$ 的最小正整數 m。假設 $k(1), k(2), ..., k(n-1)$ 已經被定義，令 $k(n)$ 為使得 $s_m \in A$ 的最小正整數 $m > k(n-1)$。那麼 k 是保序的：$m > n$ 蘊含 $k(m) > k(n)$。形成合成函數 $s \circ k$。$s \circ k$ 的定義域是正整數集合，而 $s \circ k$ 的值域是 A。此外，$s \circ k$ 是一對一的，因為
$s[k(n)] = s[k(m)]$
蘊含
$s_{k(n)} = s_{k(m)}$，
這蘊含 $k(n) = k(m)$，而這又蘊含 $n = m$。這證明了本定理。
2.13 實數系統的不可數性
下一個定理表明存在著不可數的無限集合。
定理 2.17. 所有實數的集合是不可數的。
證明. 我們只需證明滿足 $0 < x < 1$ 的 x 的集合是不可數的即可。如果這個區間內的實數是可數的，那麼就會有一個數列 $s = \{s_n\}$，其各項構成了整個區間。我們將藉由在該區間內構造一個不是這個數列中的項的實數，來證明這是不可能的。將每一個 $s_n$ 寫成無限小數：
$s_n = 0.u_{n,1}u_{n,2}u_{n,3}...$
其中每個 $u_{n,i}$ 是 $0, 1, ..., $ 或 9。考慮具有以下小數展開式的實數 y
$y = 0.v_1v_2v_3...$
其中
$v_n = \begin{cases} 1, & \text{如果 } u_{n,n} \ne 1, \\ 2, & \text{如果 } u_{n,n} = 1. \end{cases}$
那麼數列 $\{s_n\}$ 中的任何項都不可能等於 y，因為 y 在第一位小數上與 $s_1$ 不同，在第二位小數上與 $s_2$ 不同，...，在第 n 位小數上與 $s_n$ 不同。（像 $s_n = 0.1999...$ 和 $y = 0.2000...$ 這樣的情況在這裡不可能發生，因為 $v_n$ 的選取方式。）由於 $0 < y < 1$，定理得證。
定理 2.18. 令 $Z^+$ 表示所有正整數的集合。那麼笛卡兒乘積 $Z^+ \times Z^+$ 是可數的。
證明. 在 $Z^+ \times Z^+$ 上定義一個函數 f 如下：
如果 $(m, n) \in Z^+ \times Z^+$，則 $f(m, n) = 2^m 3^n$。
那麼 f 在 $Z^+ \times Z^+$ 上是一對一的，且 f 的值域是 $Z^+$ 的一個子集。
2.14 集合代數 (Set Algebra)
給定兩個集合 $A_1$ 和 $A_2$，我們定義一個新集合，稱為 $A_1$ 和 $A_2$ 的聯集，記為 $A_1 \cup A_2$，如下所示：
定義 2.19. 聯集 $A_1 \cup A_2$ 是由那些屬於 $A_1$ 或屬於 $A_2$ 或同時屬於兩者的元素所組成的集合。
這等於說 $A_1 \cup A_2$ 由那些至少屬於集合 $A_1$、$A_2$ 其中之一的元素所組成。因為在這個定義中不涉及順序問題，所以聯集 $A_1 \cup A_2$ 與 $A_2 \cup A_1$ 是相同的；也就是說，集合的加法滿足交換律。該定義的措辭也使得集合的加法滿足結合律：
$A_1 \cup (A_2 \cup A_3) = (A_1 \cup A_2) \cup A_3$。
聯集的定義可以擴展到任何有限或無限的集合收集：
定義 2.20. 如果 F 是一個任意的集合收集，那麼 F 中所有集合的聯集被定義為由那些至少屬於 F 中的一個集合的元素所組成的集合，並記為
$\bigcup_{A \in F} A$。
如果 F 是一個有限的集合收集，$F = \{A_1, ..., A_n\}$，我們寫作
$\bigcup_{A \in F} A = \bigcup_{k=1}^n A_k = A_1 \cup A_2 \cup \cdot\cdot\cdot \cup A_n$。
如果 F 是一個可數收集，$F = \{A_1, A_2, ...\}$，我們寫作
$\bigcup_{A \in F} A = \bigcup_{k=1}^{\infty} A_k = A_1 \cup A_2 \cup \cdot\cdot\cdot$
定義 2.21. 如果 F 是一個任意的集合收集，F 中所有集合的交集被定義為由那些屬於 F 中的每一個集合的元素所組成的集合，並記為
$\bigcap_{A \in F} A$。
兩個集合 $A_1$ 和 $A_2$ 的交集記為 $A_1 \cap A_2$，並由那些兩集合所共有的元素組成。如果 $A_1$ 和 $A_2$ 沒有共同的元素，那麼 $A_1 \cap A_2$ 就是空集合，且 $A_1$ 和 $A_2$ 被稱為「互斥的（disjoint）」。如果 F 是一個有限收集（如上），我們寫作
$\bigcap_{A \in F} A = \bigcap_{k=1}^n A_k = A_1 \cap A_2 \cap \cdot\cdot\cdot \cap A_n$
而如果 F 是一個可數收集，我們寫作
$\bigcap_{A \in F} A = \bigcap_{k=1}^{\infty} A_k = A_1 \cap A_2 \cap \cdot\cdot\cdot$
如果收集中的集合沒有共同的元素，它們的交集就是空集合。當然，即使 F 不是可數的，我們關於聯集和交集的定義仍然適用。由於我們定義聯集和交集的方式，交換律和結合律會自動得到滿足。
定義 2.22. A 相對於 B 的「補集（complement）」，記為 $B - A$，被定義為集合
$B - A = \{x : x \in B, 但 x \notin A\}$。
請注意，只要 $A \subseteq B$，就有 $B - (B - A) = A$。同時請注意，如果 $B \cap A$ 是空集合，則 $B - A = B$。
定理 2.23. 令 F 為一個集合的收集。那麼對於任何集合 B，我們有
$B - \bigcup_{A \in F} A = \bigcap_{A \in F} (B - A)$
以及
$B - \bigcap_{A \in F} A = \bigcup_{A \in F} (B - A)$。
證明. 令 $S = \bigcup_{A \in F} A$，$T = \bigcap_{A \in F} (B - A)$。如果 $x \in B - S$，那麼 $x \in B$，但 $x \notin S$。因此，x 屬於 F 中的至少一個 A 是不正確的；因此 x 不屬於 F 中的任何 A。因此，對於 F 中的每一個 A，$x \in B - A$。但這蘊含 $x \in T$，所以 $B - S \subseteq T$。反轉這些步驟，我們得到 $T \subseteq B - S$，這證明了 $B - S = T$。為了證明第二個陳述，使用類似的論證即可。
2.15 可數集合的可數收集
定義 2.24. 如果 F 是一個集合的收集，使得 F 中任意兩個不同的集合都是互斥的，那麼 F 就被稱為一個互斥集合的收集。
定理 2.25. 如果 F 是一個由互斥集合組成的可數收集，比方說 $F = \{A_1, A_2, ...\}$，使得每一個集合 $A_n$ 都是可數的，那麼聯集 $\bigcup_{k=1}^{\infty} A_k$ 也是可數的。
證明. 令 $A_n = \{a_{1,n}, a_{2,n}, a_{3,n} ...\}$，$n = 1, 2, ...$，並令 $S = \bigcup_{k=1}^{\infty} A_k$。那麼 S 中的每一個元素 x 都在 F 的至少一個集合中，因此對於某一對整數 $(m, n)$，有 $x = a_{m,n}$。因為 F 是一個互斥集合的收集，所以對 $(m, n)$ 被 x 唯一決定。因此，藉由如果 $x = a_{m,n}$ （$x \in S$）則 $f(x) = (m, n)$ 所定義的函數 f，其定義域為 S。值域 $f(S)$ 是 $Z^+ \times Z^+$（其中 $Z^+$ 是正整數集合）的一個子集，因此是可數的。但 f 是一對一的，因此 $S \sim f(S)$，這意味著 S 也是可數的。
定理 2.26. 如果 $F = \{A_1, A_2, ...\}$ 是一個可數的集合收集，令 $G = \{B_1, B_2, ...\}$，其中 $B_1 = A_1$，且對於 $n > 1$，
$B_n = A_n - \bigcup_{k=1}^{n-1} A_k$
那麼 G 是一個互斥集合的收集，並且我們有
$\bigcup_{k=1}^{\infty} A_k = \bigcup_{k=1}^{\infty} B_k$。
證明. 每個集合 $B_n$ 的建構方式使其與先前的集合 $B_1, B_2, ..., B_{n-1}$ 沒有共同的元素。因此 G 是一個互斥集合的收集。令 $A = \bigcup_{k=1}^{\infty} A_k$ 且 $B = \bigcup_{k=1}^{\infty} B_k$。我們將證明 $A = B$。首先，如果 $x \in A$，那麼對於某個 k，有 $x \in A_k$。如果 n 是最小的這樣一個 k，那麼 $x \in A_n$ 但 $x \notin \bigcup_{k=1}^{n-1} A_k$，這意味著 $x \in B_n$ 從而 $x \in B$。因此 $A \subseteq B$。反之，如果 $x \in B$，那麼對於某個 n，有 $x \in B_n$，因此對於同一個 n，也有 $x \in A_n$。因此 $x \in A$，這證明了 $B \subseteq A$。
利用定理 2.25 和 2.26，我們立即得到
定理 2.27. 如果 F 是可數集合的一個可數收集，那麼 F 中所有集合的聯集也是一個可數集合。
例子 1. 所有有理數的集合 Q 是一個可數集合。
證明. 令 $A_n$ 表示所有分母為 n 的正有理數集合。所有正有理數的集合等於 $\bigcup_{k=1}^{\infty} A_k$。由此可知 Q 是可數的，因為每一個 $A_n$ 都是可數的。
例子 2. 具有有理端點的區間的集合 S 是一個可數集合。
證明. 令 $\{x_1, x_2, ...\}$ 表示有理數的集合，並令 $A_n$ 為左端點為 $x_n$ 且右端點為有理數的所有區間的集合。那麼 $A_n$ 是可數的且 $S = \bigcup_{k=1}^{\infty} A_k$。
習題
2.1 證明定理 2.2。提示：$(a, b) = (c, d)$ 意味著 $\{\{a\}, \{a, b\}\} = \{\{c\}, \{c, d\}\}$。現在求助於集合相等的定義。
2.2 令 S 為一個關係，並令 $\mathfrak{D}(S)$ 為其定義域。關係 S 被說成是：
i) 具反身性的（reflexive），如果 $a \in \mathfrak{D}(S)$ 蘊含 $(a, a) \in S$。
ii) 具對稱性的（symmetric），如果 $(a, b) \in S$ 蘊含 $(b, a) \in S$。
iii) 具遞移性的（transitive），如果 $(a, b) \in S$ 且 $(b, c) \in S$ 蘊含 $(a, c) \in S$。
一個同時具備對稱性、反身性和遞移性的關係被稱為「等價關係（equivalence relation）」。如果 S 是由所有滿足下列條件的實數對 $(x, y)$ 組成的集合，判斷 S 具有上述哪些性質：
a) $x \le y$
b) $x < y$
c) $x < |y|$
d) $x^2 + y^2 = 1$
e) $x^2 + y^2 < 0$
f) $x^2 + x = y^2 + y$
2.3 下列函數 F 和 G 是由給定的方程式對所有實數 x 所定義。在可以形成合成函數 $G \circ F$ 的每種情況下，給出 $G \circ F$ 的定義域，以及 $(G \circ F)(x)$ 的公式（或多個公式）：
a) $F(x) = 1 - x$, $G(x) = x^2 + 2x$.
b) $F(x) = x + 5$, $G(x) = |x|/x$（如果 $x \ne 0$）, $G(0) = 1$.
c) $F(x) = \begin{cases} 2x, & \text{如果 } 0 \le x \le 1, \\ 1, & \text{其他情況}, \end{cases}$
$G(x) = \begin{cases} x^2, & \text{如果 } 0 \le x \le 1, \\ 0, & \text{其他情況}. \end{cases}$
如果 $G(x)$ 和 $G[F(x)]$ 給定如下，求 $F(x)$：
d) $G(x) = x^3$, $G[F(x)] = x^3 - 3x^2 + 3x - 1$.
e) $G(x) = 3 + x + x^2$, $G[F(x)] = x^2 - 3x + 5$.
2.4 給定三個函數 F, G, H，為了使下列四個合成函數能被定義，必須對它們的定義域施加什麼限制？
$G \circ F$, $H \circ G$, $H \circ (G \circ F)$, $(H \circ G) \circ F$.
假設 $H \circ (G \circ F)$ 和 $(H \circ G) \circ F$ 可以被定義，證明結合律：
$H \circ (G \circ F) = (H \circ G) \circ F$.
2.5 證明下列聯集和交集的集合論恆等式：
a) $A \cup (B \cup C) = (A \cup B) \cup C$, $A \cap (B \cap C) = (A \cap B) \cap C$.
b) $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$.
c) $(A \cup B) \cap (A \cup C) = A \cup (B \cap C)$.
d) $(A \cup B) \cap (B \cup C) \cap (C \cup A) = (A \cap B) \cup (A \cap C) \cup (B \cap C)$.
e) $A \cap (B - C) = (A \cap B) - (A \cap C)$.
f) $(A - C) \cap (B - C) = (A \cap B) - C$.
g) $(A - B) \cup B = A$ 若且唯若 $B \subseteq A$.
2.6 令 $f: S \rightarrow T$ 是一個函數。如果 A 和 B 是 S 的任意子集，證明
$f(A \cup B) = f(A) \cup f(B)$ 且 $f(A \cap B) \subseteq f(A) \cap f(B)$.
推廣至任意的聯集與交集。
2.7 令 $f: S \rightarrow T$ 是一個函數。如果 $Y \subseteq T$，我們用 $f^{-1}(Y)$ 表示 S 中被 f 映射到 Y 裡的最大子集。也就是說，
$f^{-1}(Y) = \{x : x \in S \text{ 且 } f(x) \in Y\}$.
集合 $f^{-1}(Y)$ 被稱為 Y 在 f 下的「反像（inverse image）」。對於 S 的任意子集 X 和 T 的任意子集 Y，證明下列陳述：
a) $X \subseteq f^{-1}[f(X)]$,
b) $f[f^{-1}(Y)] \subseteq Y$,
c) $f^{-1}[Y_1 \cup Y_2] = f^{-1}(Y_1) \cup f^{-1}(Y_2)$,
d) $f^{-1}(Y_1 \cap Y_2) = f^{-1}(Y_1) \cap f^{-1}(Y_2)$,
e) $f^{-1}(T - Y) = S - f^{-1}(Y)$.
f) 將 (c) 和 (d) 推廣至任意的聯集與交集。
2.8 參考習題 2.7。證明對於 T 的每一個子集 Y 都有 $f[f^{-1}(Y)] = Y$，若且唯若 $T = f(S)$。
2.9 令 $f: S \rightarrow T$ 是一個函數。證明下列陳述是等價的。
a) f 在 S 上是一對一的。
b) 對於 S 的所有子集 A, B，都有 $f(A \cap B) = f(A) \cap f(B)$。
c) 對於 S 的每一個子集 A，都有 $f^{-1}[f(A)] = A$。
d) 對於 S 的所有互斥子集 A 和 B，它們的像 $f(A)$ 和 $f(B)$ 也是互斥的。
e) 對於 S 的所有滿足 $B \subseteq A$ 的子集 A 和 B，我們有 $f(A - B) = f(A) - f(B)$。
2.10 證明如果 $A \sim B$ 且 $B \sim C$，則 $A \sim C$。
2.11 如果 $\{1, 2, ..., n\} \sim \{1, 2, ..., m\}$，證明 $m = n$。
2.12 如果 S 是一個無限集合，證明 S 包含一個可數無限的子集。提示：在 S 中選擇一個元素 $a_1$ 並考慮 $S - \{a_1\}$。
2.13 證明每一個無限集合 S 都包含一個與 S 相似的真子集。
2.14 如果 A 是一個可數集合而 B 是一個不可數集合，證明 $B - A$ 與 B 相似。
2.15 如果一個實數是代數方程式 $f(x) = 0$ 的根，其中 $f(x) = a_0 + a_1x + \cdot\cdot\cdot + a_nx^n$ 是一個具有整數係數的多項式，則稱該實數為「代數數（algebraic number）」。證明所有具整數係數的多項式集合是可數的，並由此推導出代數數集合也是可數的。
2.16 令 S 為一個包含 n 個元素的有限集合，並令 T 為 S 的所有子集之收集。證明 T 是一個有限集合並求 T 中元素的數量。
2.17 令 R 表示實數集合，並令 S 表示定義域為 R 的所有實值函數的集合。證明 S 和 R 不是等勢的。提示：假設 $S \sim R$ 並令 f 是一個使得 $f(R) = S$ 的一對一函數。如果 $a \in R$，令 $g_a = f(a)$ 為 S 中對應於實數 a 的實值函數。現在由方程式 $h(x) = 1 + g_x(x)$ (若 $x \in R$) 定義 h，並證明 $h \notin S$。
2.18 令 S 為其項均為整數 0 和 1 的所有數列的收集。證明 S 是不可數的。
2.19 證明下列集合是可數的：
a) 複數平面上具有有理數半徑和有理數座標圓心的所有圓的集合，
b) 任何由長度為正的互斥區間所組成的收集。
2.20 令 f 為對區間 $0 \le x \le 1$ 中每一個 x 有定義的實值函數。假設存在一個正數 M 具有以下性質：對於區間 $0 \le x \le 1$ 中任意有限個點 $x_1, x_2, ..., x_n$ 的選擇，其總和
$|f(x_1) + \cdot\cdot\cdot + f(x_n)| \le M$
令 S 為在 $0 \le x \le 1$ 中使得 $f(x) \ne 0$ 的那些 x 的集合。證明 S 是可數的。
2.21 找出以下證明「所有正長度區間的集合為可數」的謬誤之處：
令 $\{x_1, x_2, ...\}$ 表示有理數的可數集合，並令 I 為任何長度為正的區間。那麼 I 包含無限多個有理點 $x_n$，但在這些點中，會存在一個下標 n 最小的點。藉由方程式 $F(I) = n$ 定義一個函數 F，其中 $x_n$ 是區間 I 中具有最小下標的有理數。這個函數在所有區間的集合與正整數的一個子集之間建立了一對一的對應關係。因此，所有區間的集合是可數的。
2.22 令 S 表示給定集合 T 的所有子集的收集。令 $f : S \rightarrow R$ 為一個定義在 S 上的實值函數。函數 f 如果只要 A 和 B 是 T 的互斥子集就滿足 $f(A \cup B) = f(A) + f(B)$，則稱其為「加性的（additive）」。如果 f 是加性的，證明對於任意兩個子集 A 和 B，我們有
$f(A \cup B) = f(A) + f(B - A)$
並且
$f(A \cup B) = f(A) + f(B) - f(A \cap B)$
2.23 參考習題 2.22。假設 f 是加性的，並假設下列關係對 T 的兩個特定子集 A 和 B 成立：
$f(A \cup B) = f(A') + f(B') - f(A')f(B')$
$f(A \cap B) = f(A)f(B)$, $f(A) + f(B) \ne f(T)$
其中 $A' = T - A$，$B' = T - B$。證明這些關係決定了 $f(T)$，並計算 $f(T)$ 的值。
沒有留言:
張貼留言