集合論

• 2022 年 8 月 22 日
• 筆記
• 數學, 數學分析

我們現在介紹集合論中的一些概念和記號，他們通常被廣泛而頻繁地被用到。幾乎所有數學分支領域都將集合論作為其基礎。因此在學習高級的數學領域之前，學習集合論中的一些基礎概念是非常重要的。我們下面給出公理集合論中的部分（較為初等）的內容，可以證明，我們將要建立的集合公理體系是等價於ZF公理集合論的。

3.1 基本事項

首先，集合是一個不加定義的原始概念，這意味着我們不打算構造出集合這個概念，而是使用公理來規範化它。我們並不會知道什麼是集合，我們只是列出集合可以進行的運算和性質。我們認為，一個集合始終是一個對象。

然後我們定義一個對象 \(o\) 和集合 \(A\) 之間的二元關係 \(\in\)，且稱 \(o\in A\) 為 「\(o\) 屬於 \(A\)」 或 「\(A\) 包含 \(o\)」 或 「\(o\) 是 \(A\) 的元素」。特別地，由於集合是對象，詢問一個集合是否屬於另一個集合是有意義的。

註：根據定義，「集合內不能有重複的元素」 這種說法是荒謬的。而下文中，「\(A\) 的每個元素都……」 的含義是 「對於任意的對象 \(x\) 滿足 \(x\) 是 \(A\) 的元素，\(x\) 都滿足……」。即，我想強調的是，「元素」描述的是一種關係，而不是一個對象。

純粹集合論認為一切對象都是集合。從邏輯學的角度來看，純粹集合論確實是一種更加簡單的理論，人們只需要處理集合，而無需考慮其他對象。然而我們從概念角度來說，不純粹的集合論的處理更加容易（例如，純粹集合論可以把 \(0\) 看做 \(\varnothing\)，\(1\) 看做 \(\left\{\varnothing\right\}\)，\(2\) 看做 \(\left\{\left\{\varnothing\right\}\right\}\)，以此類推）。單純從應用的角度來看，兩種想法集合是等價的。因此，對於一切對象是否都是集合，我們採取不可知的態度。即我們既不添加公理確認這一點，也不添加公理否認這一點，而在現在的公理體系中，命題「一切對象都是集合」是未決的（不能證明也不能推翻）。

我們先在 \(\in\) 的基礎之上擴展一些僅適用於集合間的二元關係。

• 定義 3.1.1（子集）：設 \(A,B\) 是集合，定義 \(A\subseteq B\)（稱為 「\(A\) 是 \(B\) 的子集」 或 「\(A\) 包含於 \(B\)」 或 「\(B\) 包含 \(A\)“），當且僅當 \(A\) 的每個元素都是 \(B\) 的元素。形式化地說 \(A\subseteq B\iff\forall_{x\in A}x\in B\)。

  定義 \(A\subsetneq B\)（稱為 「\(A\) 是 \(B\) 的真子集」 或 「\(A\) 真包含於 \(B\)」 或 「\(B\) 真包含 \(A\)“），當且僅當 \(A\subseteq B\) 且 \(B\nsubseteq A\)。

• 命題 3.1.2（集合的包含關係的基本性質）：設 \(A,B,C\) 為集合，那麼：

  • 自反性：\(A\subseteq A\)。

    證明：根據定義可得。

  • 傳遞性：若 \(A\subseteq B\) 且 \(B\subseteq C\)，則 \(A\subseteq C\)。

    證明：根據定義，\(A\) 的每個元素都是 \(B\) 的元素，\(B\) 的每個元素都是 \(C\) 的元素，那麼 \(A\) 的每個元素都是 \(C\) 的元素。

  • 混合傳遞性：若 \(A\subsetneq B\) 且 \(B\subseteq C\)，則 \(A\subsetneq C\)；若 \(A\subseteq B\) 且 \(B\subsetneq C\)，則 \(A\subsetneq C\)。

    證明：兩者類似，證前面那個。首先 \(A\subseteq B\) 且 \(B\subseteq C\) 可知 \(A\subseteq C\)，然後由於 \(B\nsubseteq A\)，故存在一個對象 \(x\) 滿足 \(x\) 是 \(B\) 的元素而非 \(A\) 的元素，又 \(B\) 的元素都是 \(C\) 的元素，故存在一個對象 \(x\) 滿足 \(x\) 是 \(C\) 的元素而非 \(A\) 的元素，故 \(C\nsubseteq A\)，那麼 \(A\subsetneq C\)。

集合的真包含關係顯然是一種偏序關係，因為我們知道對於任意兩個集合 \(A\) 和 \(B\)，不可能同時成立 \(A\subsetneq B\) 和 \(B\subsetneq A\)。但是真包含關係與我們定義在自然數上的小於關係 \(<\) 的不同之處在於，後者是一種全序關係。在滿足偏序性質的基礎上，我們還知道對於兩個不相等的數 \(a\) 和 \(b\)，要麼成立 \(a>b\)，要麼成立 \(b>a\)。對於集合的真包含關係而言，這一條性質是不滿足的。考慮集合 \(A=\left\{1,2\right\}\) 和 \(B=\left\{2,3\right\}\)，它們既不相等，也沒有哪一個是另一個的真子集。

• 定義 3.1.3（集合之相等）：設 \(A,B\) 是集合，定義 \(A=B\)（稱為 \(A,B\) 相等），當且即當 \(A\subseteq B\) 且 \(B\subseteq A\)。

• 命題 3.1.4（集合的相等關係的基本性質）：設 \(A,B,C\) 為集合，那麼：

  • 自反性：\(A=A\)。證明：根據命題 3.1.2 可知 \(A\subseteq A\)。

  • 對稱性：若 \(A=B\)，則 \(B=A\)。證明：根據定義可知。

  • 傳遞性：若 \(A=B,B=C\)，則 \(A=C\)。證明：根據命題 3.1.2 可知 \(A\subseteq C\) 且 \(C\subseteq A\)。

可以證明 「若 \(A=B\)，則 \(x\in A\iff x\in B\)」，即集合關於命題 「某個對象 \(x\) 是否屬於該集合 」 遵從代入公理。

• 引理 3.1.5（集合構造的唯一性）：若存在集合 \(S\)，滿足 \(x\in S\iff P(x)\)，其中 \(P(x)\) 是某個關於任意對象 \(x\) 的命題，那麼 \(S\) 唯一。

  證明：若存在兩個集合 \(S,S’\) 都滿足條件，那麼 \(x\in S\iff P(x)\iff x\in S’\)，於是 \(S=S’\)。

接下來運用公理構建集合時，我們都使用該引理來說明構建的集合的唯一性。

類似自然數，我們將從空集開始，然後藉助幾個運算公理化更多的集合。

• 公理 3.1.6（空集）：存在一個集合 \(\varnothing\)（空集），對於任意的 \(x\)，\(x\not\in \varnothing\)。

• 公理 3.1.7（單元素集）：對於任意一個對象 \(a\)，存在一個集合 \(\{a\}\)，它唯一的元素是 \(a\)。稱這樣的集合為單元素集。

• 公理 3.1.8（雙並）：對於兩個集合 \(A,B\)，存在一個集合 \(A\cup B\)，稱為 \(A\) 和 \(B\) 的並，其元素由屬於 \(A\) 或屬於 \(B\) 的一切元素組成。即，對於任意對象 \(x\)，

  \[x\in A\cup B\iff (x\in A \lor x\in B)
  \]

容易證明並運算滿足交換律和結合律。容易證明 \(A\cup \varnothing=A\)。

根據雙並公理，我們可以定義雙元素集：

• 定義 3.1.9（雙元素集）：若 \(a\) 和 \(b\) 是兩個對象，根據雙並公理，存在一個集合 \(\{a,b\}=\{a\}\cup\{b\}\)，其僅有的元素是 \(a\) 和 \(b\)。即，對於每個對象 \(y\)，有 \(y\in\{a,b\}\iff (y\in a\lor y\in b)\)。

類似地，我們可以定義三元素集、四元素集，依此類推。

但另一方面，我們還不能對於任意給定的自然數 \(n\) 定義由 \(n\) 個對象組成的集合。這將要求重複使用雙並公理 \(n\) 次，然而 \(n\) 次重複的概念尚不曾被嚴格地定義（沒有關於集合的歸納方法）。根據類似的理由，我們也還不能定義由無限多個對象組成的集合。

• 公理 3.1.10（分類公理）：設 \(A\) 是一個集合，並對於每個 \(x\in A\)，設 \(P(x)\) 是一個關於 \(x\) 的命題。那麼存在一個集合 \(\{x\in A:P(x)\}\)（或 \(\{x\in A|P(x)\}\)），它的元素恰恰是 \(A\) 中使 \(P(x)\) 成立的 \(x\)。即，對於任意對象 \(y\)，

  \[y\in\{x\in A:P(x)\}\iff (y\in A\land P(y))
  \]

分類可以看成關於集合 \(A\) 和命題 \(P\) 的運算。可以證明 「若 \(A=B\)，則 \(\{x\in A:P(x)\}=\{x\in B:P(x)\}\)」，即集合關於分類運算遵從代入公理。

利用分類運算和分類公理，我們可以定義集合的其他一些運算。

• 定義 3.1.11（交）：兩個集合 \(A\) 和 \(B\) 的交 \(A\cap B\) 定義為集合 \(\{x\in A:x\in B\}\)。根據分類公理，\(A\cap B\) 存在。

  定義兩個集合是不交的，當且僅當 \(A\cap B=\varnothing\)。

• 定義 3.1.12（差集）：兩個集合 \(A\) 和 \(B\) 的差 \(A\setminus B\) 定義為集合 \(\{x\in A:x\not\in B\}\)。根據分類公理，\(A\setminus B\) 存在。

• 命題 3.1.13（集合構成一個布爾代數）：

  設 \(A,B,C,X\) 均為集合，且滿足 \(A,B,C\subseteq X\)。

  1. 最小元：\(A\cup\varnothing=A\) 以及 \(A\cap\varnothing=\varnothing\)。
  2. 最大元：\(A\cup X=X\) 以及 \(A\cap X=A\)。
  3. 恆等式：\(A\cup A=A\) 以及 \(A\cap A=A\)。
  4. 交換律：\(A\cup B=B\cup A\) 以及 \(A\cap B=B\cap A\)。
  5. 結合律：\(A\cup(B\cup C)=(A\cup B)\cup C\) 以及 \(A\cap(B\cap C)=(A\cap B)\cap C\)。
  6. 分配律：\(A\cap(B\cup C)=(A\cap B)\cup(A\cap C)\) 以及 \(A\cup(B\cap C)=(A\cup B)\cap(A\cup C)\)。
  7. 分差法則：\(A\cup(X\setminus A)=X\) 以及 \(A\cap(X\setminus A)=\varnothing\)。
  8. 摩根定律：\(X\setminus(A\cup B)=(X\setminus A)\cap(X\setminus B)\)。

這些公理還不能滿足我們的要求，例如把集合中的元素每個都加上 \(1\)，把 \(\left\{1,6, 15\right\}\) 變為 \(\left\{2,7,16\right\}\)，這是我們現在有的公理無法辦到的。我們需要更加強大的數學工具，因此讓我們再添加一個公理：

• 公理 3.1.14（替換公理）：設 \(A\) 是一個集合，\(P(x,y)\) 是關於任意對象 \(x\in A\) 和任意對象 \(y\) 的命題，且滿足對於每個 \(x\in A\) 存在至多一個 \(y\) 使得 \(P(x,y)\) 成立。那麼存在一個集合 \(\{y:\exists_{x\in A},P(x,y)\}\)，使得對於任何對象 \(z\)

  \[z\in\{y:\exists_{x\in A},P(x,y)\}\iff \exists_{x\in A},P(x,z)
  \]

  我們常把形如 \(\{y:\exists_{x\in A},y=f(x)\}\) 的集合簡寫成 \(\{f(x):x\in A\}\)。

注意到，替換公理蘊含分類公理，我們只需令 \(P(x,y)\iff x=y\land Q(x)\) 即可構造出集合 \(\{x\in A:Q(x)\}\)。

接下來，我們將引入無限集合：

• 公理 3.1.15（無窮大）：存在一個集合 \(\mathbb{N}\)，其元素叫作自然數，滿足 \(0\) 是 \(\mathbb{N}\) 中的一個對象，並且對於任意 \(n\in\mathbb{N}\)，由 \(n\) 所指定的滿足皮亞諾公理的後繼對象 \(n^+\) 也在 \(\mathbb{N}\) 中。

這是假設 2.1.6 的更正式的形式。自然數集引入了無限集合的一個最基本的例子。

3.2 萬有分類公理

從分類公理更進一步，我們考慮拓展出一個新的公理並將其加入集合論公理之中：

• 公理 3.2.1（萬有分類公理）：設 \(P(x)\) 是關於任意對象 \(x\) 的命題，那麼存在一個集合 \(\{x:P(x)\}\)，使得對於任何對象 \(y\)，

  \[y\in\{x:P(x)\}\iff P(y)
  \]

該公理斷言每個性質對應一個集合，這也就是樸素的集合思想。這個公理蘊含了我們已經討論過的公理，但這個公理不能被引入集合論，因為它引出了一個邏輯上的矛盾：

羅素悖論：

根據萬有分類公理，有集合：

\[\Omega:=\{x:\text{$x$是集合且$x\not\in x$}\}
\]

即一切不以自己為元素的集合的集合。那麼現在問 \(\Omega\) 是否屬於 \(\Omega\)，發現不管 \(\Omega\) 是否屬於 \(\Omega\)，都會引出矛盾。

為了解決這個悖論，我們考慮把對象按照一定的層次結構排列。在層級結構最底層的是原始對象（不是集合的對象），在下一層次中則存在一些集合，但是這些集合的元素只能是原始對象。以此類推，一層次中存在的集合只能包含之前層次中的對象。這種想法引導出了正則公理。

• 公理 3.2.2 （正則公理） ：對於一個非空的集合 \(A\)，\(A\) 中至少存在一個元素 \(x\) 滿足 \(x\) 不是集合或 \(A\cap x=\varnothing\)。

正則公理的一個重要推論是一個集合不能包含其本身，但是可以包含其他（更低層次的）集合。這使得我們排除了羅素悖論中定義的集合 \(\Omega\)。

• 命題 3.2.3（集合不能包含其本身）：設 \(A\) 為一個集合，那麼 \(A\not\in A\)。

  證明：（反證法）假設存在一個集合 \(A\)，滿足 \(A\in A\)。根據單元素公理，存在一個集合 \(B=\left\{A\right\}\)。\(B\) 是一個非空的集合，因此根據正則公理，應該存在 \(x\in B\)，滿足 \(x\) 不是集合或 \(A\cap x=\varnothing\)，但是集合 \(B\) 作為單元素集，只有 \(A\in B\)，而 \(A\) 是一個集合，且 \(A\cap B=A\)，故 \(B\) 集合違反正則公理，矛盾，假設不成立。原命題得證。

3.3 函數

• 定義 3.3.1（函數/映射/變換）：設 \(X,Y\) 是集合，\(P(x,y)\) 是關於任意對象 \(x\in X\) 和任意對象 \(y\in Y\) 的命題，使得對於每個對象 \(x\in X\) 存在恰好一個 \(y\in Y\) 使得 \(P(x,y)\) 成立。那麼我們定義由 \(P\) 在 \(X\) 和 \(Y\) 上確定的函數 \(f:X\to Y\) 是這樣的對象，它對於任意的輸入 \(x\in X\)，將指定一個輸出 \(f(x)\in Y\)，滿足

  \[y=f(x)\iff P(x,y)
  \]

  根據 \(P(x,y)\) 的定義，對於任意 \(x\in X\)，\(f(x)\) 存在且唯一。

  定義函數 \(f\) 的定義域為 \(X\)，對應域為 \(Y\)，值域為 \(f(X):=\{f(x):x\in X\}\)，那麼值域為對應域的子集。

有時我們在定義函數時，為了方便，在確定完其定義域 \(X\) 後，直接指定從輸入 \(x\) 得到輸出 \(f(x)\) 的過程（procedure）（即如何從 \(x\) 得到 \(f(x)\)）來定義 \(f\)。其真正的過程如下：在確定完定義域 \(X\) 之後，先定義 \(P(x,y)\) 表示命題 「\(y\) 是 \(x\) 經過 procedure 過程得到的結果」，若未給出對應域，再令對應域為 \(Y:=\{y:\exists_{x\in X},P(x,y)\}\)（可以發現此時對應域和值域相等），然後再定義 \(f\) 為由 \(P\) 在 \(X\) 和 \(Y\) 上確定的函數。

易證對象關於函數遵從代入公理：如果 \(x=x’\)，那麼 \(f(x)=f(x’)\)。當然前提是 \(x\) 關於 \(P(x,y)\) 遵從代入公理。

有時函數的變元用下標來表示以取代括號，如，一個自然數序列 \(a_0,a_1,\cdots\) 嚴格地說是一個從 \(\mathbb N\) 到 \(\mathbb N\) 的函數，而 \(a_n\) 其實就是 \(a(n)\)。

• 定義 3.3.2（函數相等）：對於兩個函數 \(f\) 和 \(g\)，稱它們是相等的（記為 \(f=g\)），當且僅當它們含有相同的定義域 \(X\) 和對應域 \(Y\)，且對於任意 \(x\in X\)，\(f(x)=g(x)\)。

容易驗證函數相等是自反、傳遞、對稱的。

對於函數，一個基礎性的可執行的運算是複合。

• 定義 3.3.3（複合）：設 \(f:X\to Y\) 和 \(g:Y\to Z\) 是兩個函數，其中 \(f\) 的對應域等於 \(g\) 的定義域。那麼可以定義兩個函數 \(g\) 與 \(f\) 的複合：

  \[(g\circ f)(x):=g(f(x))
  \]

  容易證明，對於任意 \(x\in X\)，\(g(f(x))\) 存在且唯一。

易證函數關於複合遵從代入公理：如果 \(f=f’\)，那麼 \(g\circ f=g\circ f’\)；如果 \(g=g’\)，那麼 \(g\circ f=g’\circ f\)。

• 引理 3.3.4（複合是結合的）：\(f\circ \left(g\circ h\right)=(f\circ g)\circ h\)。證明：根據定義可知。

我們再來描述其他一些有關函數的概念。

• 定義 3.3.5（單射）：一個定義域為 \(X\) 的函數 \(f\) 是單射當且僅當對於任意的 \(x\in X\) 和任意的 \(x’\in X\)，若 \(x\neq x’\)，則 \(f(x)\neq f(x’)\)。

• 定義 3.3.6（滿射）：一個定義域為 \(X\) 對應域為 \(Y\) 的函數 \(f\) 是滿射當且僅當 \(Y=f(X)\)。

• 定義 3.3.7（雙射/一一對應）：一個函數是雙射的當且僅當它既是單射的，又是滿射的。

  該定義也等價於，對於每個 \(y\in Y\)，恰有一個 \(x\in X\) 使得 \(f(x)=y\)（至多一個意味着單射，至少一個意味着滿射），記為 \(f^{-1}(y)\)，那麼 \(f^{-1}\) 就是一個從 \(Y\) 到 \(X\) 的函數。此時稱 \(f^{-1}\) 為 \(f\) 的逆。

3.4 象和逆象

• 定義 3.4.1（集合的象）：設函數 \(f:X\to Y\)，設 \(S\) 是 \(X\) 的一個子集，定義 \(S\) 在映射 \(f\) 下的象為

  \[f(S):=\{f(x):x\in S\}
  \]

• 定義 3.4.2（逆象）：設 \(T\) 是 \(Y\) 的一個子集，定義 \(T\) 在映射 \(f\) 的逆象為

  \[f^{-1}(T):=\{x\in S:f(x)\in T\}
  \]

注意函數也是對象，特別地我們可以考慮函數的集合，這裡我們向考慮從一個集合 \(X\) 到一個集合 \(Y\) 的一切函數組成的集合。為此，我們引入公理：

• 公理 3.4.3（冪集公理）：設 \(X\) 和 \(Y\) 是集合，那麼存在一個集合 \(Y^X\)，滿足 \(f\in Y^X\) 當且僅當 \(f\) 是一個以 \(X\) 為定義域以 \(Y\) 為對應域的函數。

此公理的一個結果是：

• 引理 3.4.9（冪集存在性）：設 \(X\) 是一個集合，那麼存在集合 \(\{Y:Y\subseteq X\}\)（也記作 \(2^X\)，稱為 \(X\) 的冪集），使得對於任意對象 \(Z\)

  \[Z\in\{Y:Y\subseteq X\}\iff Z\subseteq X
  \]

  證明：設集合 \(Y=\{0,1\}\)。

  設 \(P(f,S)\) 是關於映射 \(f\in Y^X\) 和任意對象 \(S\) 的命題，滿足 \(P(f,S)\) 為真當且僅當 \(S\) 是 \(X\) 的子集且 \(\forall_{x\in X},f(x)=1\iff x\in S\)。

  根據引理 3.1.5，容易證明，對於每個 \(f\in Y^X\)，都恰好存在唯一的 \(S:=\{x\in X:f(x)=1\}\) 使得 \(P(f,S)\) 為真。

  根據替換公理，存在集合 \(A:=\{S:\exists_{f\in Y^X},P(f,S)\}\)。那麼 \(Z\in A\implies Z\subseteq X\)。

  為證 \(Z\subseteq X\implies(Z\in A\iff \exists_{f\in Y^X},P(f,Z))\)，我們構造函數 \(f(x):=[x\in Z]\) 即可。

  於是 \(Z\in A\iff Z\subseteq X\)，得證。

為了完整起見，我們現在再往集合論中添加一條公理，它擴充了雙並公理而允許做出更大的並集。

• 公理 3.4.10（並）：設 \(A\) 是集類（即它的每個元素都是一個集合），那麼存在一個集合 \(\bigcup A\)，使得對於任意對象 \(x\)

  \[x\in \bigcup A\iff \exists_{S\in A},x\in S
  \]

該公理的一個重要的結果是：

• 定義 3.4.11（集族的並）：設 \(I\) 為一集合，且對於任意 \(\alpha\in I\)，都映射到一個集合 \(A_{\alpha}\)。

  此時我們稱 \(I\) 為指標集，稱 \(I\) 的元素 \(\alpha\) 為標籤，稱 \(\{A_{\alpha}:\alpha\in I\}\) 為一個集族，其中的元素是貼有標籤 \(\alpha\in I\) 的。

  定義集族 \(\{A_{\alpha}:\alpha\in I\}\) 的並為集合 \(\bigcup_{\alpha\in I}A_{\alpha}:=\bigcup\{A_{\alpha}:\alpha\in I\}\)。那麼對於任意對象 \(y\)

  \[y\in\bigcup_{\alpha\in I}A_{\alpha}\iff \exists_{\alpha\in I},y\in A_{\alpha}
  \]

  注意到，當 \(I\) 為空集時，集族的並也為空集。

對稱地，儘管不需要用到並公理，我們定義：

• 定義 3.4.12（集族的交）：設 \(I\) 為一非空集合，且對於任意 \(\alpha\in I\)，都映射到一個集合 \(A_{\alpha}\)。

  由於 \(I\) 非空，那麼存在某個對象 \(\beta\in I\)。然後定義集族 \(\{A_{\alpha}:\alpha\in I\}\) 的交為集合 \(\bigcap_{\alpha\in I}A_{\alpha}:=\{x\in A_{\beta}:\forall_{\alpha\in I},x\in A_{\alpha}\}\)。那麼對於任意對象 \(y\)

  \[y\in \bigcap_{\alpha\in I}A_{\alpha}\iff \forall_{\alpha\in I},x\in A_{\alpha}
  \]

  注意，該定義不依賴於 \(\beta\) 的選擇。

集合論的這些我們已經引入的公理統稱為ZF公理集合論（Zermelo-Fraenkel Set Theory，策梅洛-弗蘭克爾集合論）。後面我們將還需要一個更進一步的公理，即著名的選擇公理，它們統稱為集合論的ZFC公理集合論（Zermelo-Fraenkel-Choise Set Theory，策梅洛-弗蘭克爾-選擇集合論）。

3.5 笛卡爾積

• 定義 3.5.1（序偶/有序對）：設 \(x\) 和 \(y\) 是兩個對象（可以相等），定義序偶 \((x,y):=\{\{x\},\{x,y\}\}\)，定義 \(x\) 為它的第一個分量而 \(y\) 為它的第二個分量。

  可以證明，兩個序偶 \((x,y)\) 和 \((x’,y’)\) 相等，當且僅當 \(x=x’\land y=y’\)。

• 定義 3.5.2（笛卡爾積）：設 \(X\) 和 \(Y\) 是集合，定義它們的笛卡爾積為集合 \(X\times Y\)（或記作 \(\{(x,y):x\in X,y\in Y\}\)），使得對於任意的對象 \(a\)

  \[a\in X\times Y\iff \exists_{x\in X,y \in Y},a=(x,y)
  \]

  證明：首先，對於每個 \(x\in X\)，存在一個集合 \(A_x:=\{(x,y):y\in Y\}\)。

  再構造集合 \(B=\bigcup_{x\in X}A_x\)。發現對於任意對象 \(a\)，\(a\in B\iff \exists_{x\in X,y \in Y},a=(x,y)\)，得證。

設 \(f:X\times Y\to Z\) 是一個函數。我們認為，\(f\) 即是以 \(X\times Y\) 為定義域的單變元函數，也是以 \(X\) 和 \(Y\) 同為定義域的兩個變元的函數。

現在我們擴展序偶的概念。

• 定義 3.5.3（有序 \(n\) 元組/\(n\) 元序列）：設 \(n\) 是自然數，定義一個有序 \(n\) 元組為一個函數 \(x:\{i\in\mathbb{N}:1\leqslant i\leqslant n\}\to X\)，其中 \(X\) 是任意的某個集合，滿足 \(x\) 是滿射。我們把 \(x(i)\) 寫成 \(x_i\)，稱為第 \(i\) 個分量，並把 \(x\) 寫成 \((x_i)_{1\leqslant i\leqslant n}\)。

  那麼可以證明，兩個有序 \(n\) 元組 \((x_i)_{1\leqslant i\leqslant n}\) 和 \((y_i)_{1\leqslant i\leqslant n}\) 是相等的，當且僅當對於任意自然數 \(1\leqslant i\leqslant n\)，\(x_i=y_i\)。

• 定義 3.5.4（\(n\) 重笛卡爾積）：設 \((X_i)_{1\leqslant i\leqslant n}\) 是一個集合的有序 \(n\) 元組，我們定義此組的諸分量的笛卡爾積為集合 \(\prod_{1\leqslant i\leqslant n}X_i\)（或記作 \(\prod_{i=1}^n X_i\) 或 \(X_1\times\cdots\times X_n\) 或 \(\{(x_i)_{1\leqslant i\leqslant n}:\forall_{1\leqslant i\leqslant n},x_i\in X_i\}\)），使得對於任意的對象 \(a\)

  \[a\in \prod_{1\leqslant i\leqslant n}X_i\iff \bigg(a=(x_i)_{1\leqslant i\leqslant n}\land (\forall_{1\leqslant i\leqslant n},x_i\in X_i)\bigg)
  \]

  證明：考慮集合 \(A:=\left(\bigcup_{1\leqslant i\leqslant n}X_i\right)^{\{i\in\mathbb N:1\leqslant i\leqslant n\}}\)，\(B:=\{x\in A:\forall_{1\leqslant i\leqslant n},x_i\in X_i\}\)，容易發現集合 \(B\) 即為所求。

設 \(f:X_1\times X_2\times X_3\to Y\) 是一個函數。我們認為，\(f\) 可以被看做是一個變元 \((x_1,x_2,x_3)\in X_1\times X_2\times X_3\) 的函數，或三個變元 \(x_1\in X_1,x_2\in X_2,x_3\in X_3\) 的函數，或兩個變元 \(x_1\in X_1,(x_2,x_3)\in X_2\times X_3\) 的函數，諸如此類。我們將不在乎這些不同的看法，而假裝它們實際上是相同的。

• 引理 3.5.5（有限選擇）：設 \((X_i)_{1\leqslant i\leqslant n}\) 是一個非空集合的 \(n\) 元序列，那麼 \(\prod_{1\leqslant i\leqslant n}X_i\) 也非空，即存在一個 \(n\) 元序列 \((x_i)_{1\leqslant i\leqslant n}\) 使得對於任意自然數 \(1\leqslant i\leqslant n\)，\(x_i\in X_i\)。

  證明：對 \(n\) 歸納。每次選擇一個 \(a\in X_{n^+}\) 並令 \(x_{n^+}=a\)。

3.6 集合的基數

• 定義 3.6.1（相同的基數）：稱兩個集合 \(X\) 和 \(Y\) 具有相同基數當且僅當存在一個 \(X\) 與 \(Y\) 間的雙射 \(f:X\rightarrow Y\)。

容易證明，「有相同的基數」這一概念是一個等價關係，滿足自反性、對稱性、傳遞性。對於一個有限集，我們可以用一個自然數來表示其集合的大小，即其所含元素的個數。

• 定義 3.6.2（基數）：設 \(n\) 是自然數。稱一個集合 \(X\) 具有基數 \(n\)（或稱 \(X\) 有 \(n\) 個元素，記作 \(\operatorname{card}X\)），當且僅當它與集合 \(\{i\in\mathbb N:1\leqslant i\leqslant n\}\) 具有相同的基數。

• 引理 3.6.3（基數的非退化性）：\(X=\varnothing\iff\operatorname{card}X=0\)，即一個集合 \(X\) 具有基數 \(0\) 當且僅當 \(X\) 為空集，且若 \(X\) 為空集，則 \(X\) 僅具有基數 \(0\)。

  證明：證明不存在空集與非空集間的雙射即可。

• 引理 3.6.4（基數的可減性）：設集合 \(X\) 具有基數 \(n^+\)（則 \(X\) 非空），若 \(x\in X\)，那麼 \(X\setminus \{x\}\) 有基數 \(n\)。

  證明：根據假設，存在一個 \(X\) 到 \(\{i\in\mathbb N:1\leqslant i\leqslant n^+\}\) 的雙射 \(f\)。現在定義一個 \(X\setminus\{x\}\) 到 \(\{i\in \mathbb N:1\leqslant i\leqslant n\}\) 的函數 \(g\)。分兩種情況討論：

  • 若 \(f(x)=n^+\)，那麼對於任意 \(y\in X\setminus\{x\}\)，定義 \(g(y):=f(y)\)。

  • 若 \(f(x)\neq n^+\)，那麼對於任意 \(y\in X\setminus\{x\}\)，若 \(f(y)\neq n^+\)，則定義 \(g(y):=f(y)\)；若 \(f(y)=n^+\)，則定義 \(g(y):=f(x)\)。

  可以證明，按上述定義的函數 \(g\) 存在且唯一，且 \(g\) 是雙射。

• 命題 3.6.5（基數的唯一性）：設集合 \(X\) 具有基數 \(n\)，那麼對於任意 \(m\neq n\)，\(X\) 不具有基數 \(m\)。

  證明：對 \(n\) 進行歸納。當 \(n=0\) 時，根據引理 3.6.3 可知命題成立。

  歸納地假設命題對 \(n\) 成立。設集合 \(X\) 具有基數 \(n^+\)（則 \(X\) 非空），反證地設其又具有基數 \(m^+\neq n^+\)，\(X\) 非空意味着存在 \(x\in X\)，那麼對於集合 \(X\setminus\{x\}\)，它既具有基數 \(n\)，有具有基數 \(m\neq n\)，矛盾，故命題對 \(n^+\) 成立。故命題對任意自然數 \(n\) 成立，得證。

• 定義 3.6.6（有限集）：稱一個集合是有限的，當且僅當它具有基數 \(n\)（那麼 \(n\) 唯一）；否則稱該集合為無限的。

注意到，兩個集合具有相同的基數，必要條件是它們同為有限集或同為無限集，而對於有限集，我們往後也不會用其他的方式來定義它另外具有的基數，所以對於有限集 \(X\)，設它具有基數 \(n\)，那麼我們不妨直接稱 \(X\) 的基數為 \(\operatorname{card}X=n\)。

• 定理 3.6.7：\(\mathbb N\) 是無限集。

  證明：反證法。若 \(\mathbb N\) 存在基數 \(n\)，那麼存在一個 \(\{i\in\mathbb N:1\leqslant i\leqslant n\}\) 到 \(\mathbb N\) 的雙射 \(f\)。

  通過對 \(n\) 歸納，可以證明序列 \(f(1),\cdots,f(n)\) 是有界的：存在一個自然數 \(M\)，使得 \(\forall_{1\leqslant i\leqslant n},f(i)\leqslant M\)。

  那麼自然數 \(M+1\) 就不等於任何 \(f(i)\)，這與 \(f\) 是雙射矛盾。

應用到集合論公理和定義上，我們給出關於有限集的基數的一些基本性質：

• 命題 3.6.8（基數算術）：基數滿足如下性質：

  1. 設 \(X\) 是有限集，並設 \(x\) 是一個不屬於 \(X\) 的對象。那麼 \(X\cup\{x\}\) 為有限集且 \(\operatorname{card}X\cup\{x\}=\operatorname{card}X+1\)。

     證明：在原來映射的基礎上，再將 \(x\) 映射到 \(\operatorname{card}(X)+1\) 即可。

  2. 設 \(X\) 是有限集，並設 \(Y\) 是 \(X\) 的子集。那麼 \(Y\) 是有限集且 \(\operatorname{card}Y\leqslant \operatorname{card}X\)，當且僅當 \(X=Y\) 時取等號。

     證明：設 \(P(n)\) 表示對於任意有限集 \(X\) 滿足 \(\operatorname{card}X=n\)，上述命題成立。我們只需證明對於任意自然數 \(n\) 有 \(P(n)\) 成立即可。對 \(n\) 進行歸納。當 \(n=0\) 時，\(X\) 為空集，命題顯然成立。

     歸納地假設 \(P(n)\) 成立。對於任意有限集 \(X\) 滿足 \(\operatorname{card}X=n^+\) 及任意 \(Y\subseteq X\)，

     1. 若 \(Y=X\)，則 \(Y\) 是有限集且 \(\operatorname{card}Y=\operatorname{card}X\)。

     2. 若 \(Y\neq X\) 即 \(X\not\subseteq Y\)，則存在 \(x\in X\) 滿足 \(x\not\in Y\)，考慮集合 \(X\setminus\{x\}\)，根據引理 3.6.4，該集合是有限集且其基數為 \(n\)。容易證明 \(Y\subseteq X\setminus\{x\}\)，那麼根據歸納，\(Y\) 是有限集且 \(\operatorname{card}Y\leqslant \operatorname{card}(X\setminus\{x\})<\operatorname{card}X\)。

     於是 \(P(n^+)\) 成立。於是對於任意自然數 \(n\) 有 \(P(n)\) 成立。

  3. 設 \(X\) 和 \(Y\) 是有限集，那麼 \(X\cup Y\) 是有限集且 \(\operatorname{card}(X\cup Y)\leqslant \operatorname{card}X+\operatorname{card}Y\)，當且僅當 \(X,Y\) 不交時等號成立。

     證明：設 \(\operatorname{card}X=n\) 且 \(\operatorname{card}Y=m\)，根據定義，存在雙射 \(f:X\to \{i\in\mathbb N:1\leqslant i\leqslant n\}\) 和 \(g:Y\to \{i\in\mathbb N:1\leqslant i\leqslant m\}\)。

     考慮構建雙射 \(h\)，其定義域為 \(X\cup Y\)，滿足對於任意 \(x\in X\cup Y\)：若 \(x\in X\)，則 \(h(x):=f(x)\)；若 \(x\not\in X\)，則 \(h(x):=n+g(x)\)。容易證明滿足該定義的雙射 \(h:X\cup Y\to (Z=h(X\cup Y))\) 存在，且 \(Z\subseteq \{i\in\mathbb N:1\leqslant i\leqslant n+m\}\)。

     根據 3.6.8.2，可知 \(Z\) 為有限集且 \(\operatorname{card}Z\leqslant n+m\)，當且僅當 \(Z=\{i\in\mathbb N:1\leqslant i\leqslant n+m\}\) 時取等。那麼 \(X\cup Y\) 也為有限集且 \(\operatorname{card}(X\cup Y)\leqslant n+m\)，當且僅當 \(h(X\cup Y)=\{i\in\mathbb{N}:1\leqslant i\leqslant n+m\}\)，即 \(X\cap Y=\varnothing\) 時等號成立。

  4. 設 \(X\) 是有限集，且 \(f:X\to Y\) 是一個函數，那麼 \(f(X)\) 是有限集且 \(\operatorname{card}f(X)\leqslant \operatorname{card}X\)，當且僅當 \(f\) 為單射時取等。

     證明：仍用與 3.6.8.2 類似的證明方法。設 \(P(n)\) 表示對於任意有限集 \(X\) 滿足 \(\operatorname{card}X=n\)，上述命題成立。當 \(n=0\) 時，\(X,f(X)\) 為空集，命題顯然成立。

     歸納地假設 \(P(n)\) 成立。欲對於有限集 \(X\) 滿足 \(\operatorname{card}X=n^+\) 和函數 \(f:X\to Y\) 證明命題。

     一定存在一個元素 \(x\in X\)，設 \(X’=X\setminus \{x\}\)。設函數 \(f’:X’\to Y\)，使得 \(\forall_{x\in X’},f'(x):=f(x)\)。根據歸納，\(f'(X’)\) 為有限集且 \(\operatorname{card}f'(X’)\leqslant \operatorname{card}(X’)=n\)，當且僅當 \(f'(X’)\) 為單射時取等。

     • 若 \(f(x)\in f'(X’)\)，則 \(f'(X’)=f(X)\)，那麼 \(f(X)\) 是有限集且 \(\operatorname{card}f(X)<n^+\)。

     • 若 \(f(x)\not\in f'(X’)\)，則 \(f(X)=f'(X’)\cup \{f(x)\}\) 為有限集，且 \(\operatorname{card}f(X)=\operatorname{card}f'(X’)+\operatorname{card}\{f(x)\}\leqslant n+1\)，當且僅當 \(f'(X’)\) 為單射時取等，結合 \(f(x)\not\in f'(X’)\)，可知等價於 \(f(X)\) 為單射。

     於是 \(P(n^+)\) 成立。於是對於任意自然數 \(n\) 有 \(P(n)\) 成立。

  5. 設 \(X\) 和 \(Y\) 是有限集，那麼笛卡爾積 \(X\times Y\) 是有限的，且 \(\operatorname{card}(X\times Y)=\operatorname{card}X\times \operatorname{card}Y\)。

     證明：設 \(\operatorname{card}X=n\) 且 \(\operatorname{card}Y=m\)，根據定義，存在雙射 \(f:X\to \{i\in\mathbb N:1\leqslant i\leqslant n\}\) 和 \(g:Y\to \{i\in\mathbb N:1\leqslant i\leqslant m\}\)。

     構造映射 \(h:X\times Y\to \{i\in\mathbb N:1\leqslant i\leqslant nm\}\)，滿足對於任意 \((x,y)\in X\times Y\)， \(h(x,y):=(f(x)-1)m+g(y)\)。

     容易證明 \(h\) 是個雙射，證畢。

  6. 設 \(X\) 和 \(Y\) 是有限集，那麼集合 \(Y^X\) 是有限的，且 \(\operatorname{card}(Y^X)=(\operatorname{card}Y)^{\operatorname{card}X}\)。

     證明：設 \(\operatorname{card}X=n\) 且 \(\operatorname{card}Y=m\)，根據定義，存在雙射 \(f:X\to \{i\in\mathbb N:1\leqslant i\leqslant n\}\) 和 \(g:Y\to \{i\in\mathbb N:1\leqslant i\leqslant m\}\)。

     構造映射 \(h:Y^X\to \{i\in\mathbb N:1\leqslant i\leqslant m^n\}\)，滿足對於任意 \(p\in Y^X\)，\(h(f):=\sum_{i=1}^n(g\circ p\circ f^{-1})(i)\cdot Y^{i-1}\)。

     此處需先對 \(n\) 歸納證明形如 \(\sum_{i=1}^na(i)\) 的求和式存在且唯一，其中 \(a:\{i\in \mathbb{N}:1\leqslant i\leqslant n\}\to \mathbb N\)。

     容易證明 \(h\) 是個雙射，證畢。

經過上述性質的證明，我們看到，通過基數和單個選取引理，我們已經能對有限集使用類似歸納的方法了。

至此，我們對於集合的討論告一段落。