數學證明/集合論導論

在數學中，我們經常使用被稱為**集合**的物件，並且存在研究它們的**集合論**。雖然集合論可以被正式討論，但我們在這本書中不需要進行如此正式的討論，而且在這個階段我們可能對正式討論不感興趣也不理解。

即使我們不正式討論集合論，瞭解一些關於集合的基本概念也很重要，這些概念將在本章中介紹。

什麼是集合？

**集合**可以被看作是定義明確、不同物件的集合（這些物件也可以是集合）。由於“定義明確”一詞的模糊性，我們不認為這是集合的定義。相反，我們將集合視為一個原始概念（即，沒有用先前定義的概念來定義的概念）。數學中其他原始概念的例子包括**點**和**線**。

我們已經提到，集合是定義明確、不同物件的集合。集合中的物件被稱為集合的**元素**。我們寫$a\in A$表示元素$a$屬於集合$A$。如果$a$不屬於$A$，我們寫$a\notin A$.

例子。

• 考慮所有偶數的集合$E$。E 的元素包括（但不限於） -2、0 和 4，即 $-2,0,4\in E$.
• 英語字母的元素（一個集合）是英語字母。

描述集合的方式

有多種方式可以精確地描述一個集合（在屬於集合的元素被精確地知道的情況下）。

如果一個集合包含少量元素，那麼列舉法可能非常有效。在列舉法中，集合的元素被列在一個花括號（{}）內。特別是，僅僅改變元素的順序並不會改變所表示的集合。例如，$\{1,2\}$ 和 $\{2,1\}$ 都表示相同的集合，其元素為 1 和 2。如果花括號中列出的元素相同，則使用列舉法在不同列舉順序下建立的符號表示相同的集合。此外，在集合中重複列舉特定元素不會改變所表示的集合。例如，$\{1,1,2,2,2\}$ 和 $\{1,2\}$ 都表示相同的集合，其元素為 1 和 2。特別是，如果一個集合不包含任何元素，它可以用$\{\}$ 來表示，基於列舉法，或者可以用$\varnothing$來表示。這種集合被稱為空集。

另一種描述集合的方法是使用文字。例如，考慮集合$S$，它包含小於 10 的所有素數。如果我們使用列舉法，集合$S$ 可以表示為$\{2,3,5,7\}$。

第三種描述集合的方法在集合包含許多元素時很有優勢。這種方法被稱為集合構建器符號。在這種符號中，花括號內有三個部分。它們在下面用描述說明：$$\underbrace {\{} _{\text{The set of}}\underbrace {x} _{{\text{all elements }}x}\underbrace {:} _{\text{such that}}\underbrace {P(x)} _{{\text{the property }}P(x){\text{ is satisfied}}}\}$$

正如預期的那樣，兩個集合相等當且僅當它們包含相同的元素。等價地，兩個集合$A$和$B$相等當且僅當$A$的每個元素也是$B$的元素，$B$的每個元素也是$A$的元素。這可以被看作一個公理或一個定義。如果兩個集合$A$和$B$相等，我們寫$A=B$。如果不是，我們寫$A\neq B$.

在這本書中，當我們求解一個方程時，我們只考慮它的實數解，除非另有說明。

例子。

• $\{x:3x+2=0\}=\{-2/3\}$.
• $\{y:y{\text{ is a positive odd number}}\}=\{1,3,5,\ldots \}$.
• $\{z:z{\text{ is an English letter}}\}=\{a,b,c,\ldots ,z,A,B,\ldots ,Z\}$.

練習。 假設$a$和$b$是不同的元素。以下每個陳述是真還是假？

1 集合${\big \{}\{\}{\big \}}$不包含任何元素。

	正確。
	錯誤。

2 $\{\}=\varnothing .$

	正確。
	錯誤。

3 $\{1,1,2,3\}$是一個集合。

	正確。
	錯誤。

4 $\{x:0<x<2{\text{ and }}x^{2}=4\}=\{2\}$.

	正確。
	錯誤。

5 $\{a,b,b\}\in \{\{a,b\},a,b,b\}$.

	正確。
	錯誤。

6 $\{\{a\},\{a\}\}\in \{\varnothing ,\{a\},\{b\},\{a,b\}\}$.

	正確。
	錯誤。

集合基數

如果一個集合包含 有限 個元素，則稱為 有限 集合，否則稱為 無限 集合。 如果一個集合是有限的，那麼它的基數就是它的元素個數。 對於無限集，定義它們的基數比較困難和複雜，所以我們將在後面的關於集合基數的章節中進行討論。 對於每個集合 $S$，它的基數用 $|S|$ 表示。

例子。

• 令 $A=\{{\text{red}},{\text{yellow}},{\text{blue}}\}$。 那麼，$|A|=3$.
• 令 $B=\{\varnothing ,\{\varnothing \},\varnothing \}$。 那麼，$|B|=2$（不是 3，因為元素 $\varnothing$ 重複列出了）。
• 令 $C=\{x:x^{2}<0\}$。 那麼，$|C|=0$，因為 $x^{2}<0$ 沒有解（對於實數 $x$），因此 $C$ 是一個空集。
• 令 $D=\{y:y^{2}-4y+4=0\}$。求解 $y^{2}-4y+4=0\Leftrightarrow (y-2)^{2}=0$，得到 $y=2$。因此，$D=\{2\}$，因此 $|D|=1$ .

有一些特殊的無限集，它們的記號如下所示

• $\mathbb {N}$ 是所有自然數的集合（在本教材中，不 將 0 視為自然數）。
• $\mathbb {Z}$ 是所有整數的集合。
• $\mathbb {Q}$ 是所有有理數的集合。
• （非標準記號）$\mathbb {I}$ 是所有無理數的集合。
• $\mathbb {R}$ 是所有實數的集合。
• $\mathbb {C}$ 是所有複數的集合。

特別地，我們可以使用集合生成式來表示 $\mathbb {Q}$，如下所示：$\mathbb {Q} =\{p/q:p,q\in \mathbb {Z} {\text{ and }}q\neq 0\}$.

例子。

• ${\sqrt {2}},{\sqrt {3}}\notin \mathbb {Q}$
• ${\sqrt {5}},\pi ,e\in \mathbb {I}$

練習。 使用集合生成式來表示 $\mathbb {C}$，不使用 "$\mathbb {C}$" 在表示式中。

解答

我們可以這樣表示：$\mathbb {C} =\{x:x=a+bi{\text{ and }}a,b\in \mathbb {R} \}$ ($i={\sqrt {-1}}$).

子集

定義. (子集) 集合 $A$ 是集合 $B$ 的 子集 (記為 $A\subseteq B$)，如果 $A$ 中的每個元素也是 $B$ 的一個元素。

備註。

• 如果 $A$ 不是 $B$ 的子集，我們將其記為 $A\not \subseteq B$。
• 回想一下，兩個集合 $A$ 和 $B$ 相等，當且僅當 $A$ 中的每個元素都屬於 $B$，並且 $B$ 中的每個元素都屬於 $A$。利用子集的概念，我們可以寫出 $A=B$，當且僅當 $A\subseteq B$ 並且 $B\subseteq A$。

例子。

• $\mathbb {N} \subseteq \mathbb {Z} \subseteq \mathbb {Q} \subseteq \mathbb {R} \subseteq \mathbb {C}$.
• $\mathbb {Z} \not \subseteq \mathbb {I}$ (例如，$1\in \mathbb {Z}$ 但 $1\notin \mathbb {I}$)
• $\mathbb {C} \not \subseteq \mathbb {R}$ (例如，$i\in \mathbb {C}$ 但 $i\notin \mathbb {R}$)
• 對於每個集合 $S$，$S\subseteq S$，即每個集合都是它自身的子集。

• 這是因為集合 $S$ 的每個元素都是 $S$ 的元素。

• 對於每個集合 $S$，$\varnothing \subseteq S$。

• 如果我們想直接證明這一點，會遇到一些困難，因為 $\varnothing$ 不包含任何元素。那麼，“$\varnothing$ 的每個元素”是什麼意思？
• 在這種情況下，最好用 反證法（一種在後面關於證明方法的章節中介紹的證明技巧）來證明。首先，我們假設相反，即 $\varnothing \not \subseteq S$。根據定義的否定，存在 至少一個 $\varnothing$ 的元素，它 不是 $S$ 的元素，這是錯誤的。這產生了矛盾，因此假設是錯誤的（稍後會解釋），即 $\varnothing \not \subseteq S$ 是錯誤的。

定義. (真子集) 如果集合 $A$ 是集合 $B$ 的 真子集 (記作 $A\subsetneq B$)，則 $A$ 是 $B$ 的子集，並且 $A\neq B$.

備註。

• 類似地，如果 $A$ 不是 $B$ 的真子集，我們寫成 $A\not \subsetneq B$.

例子。

• 對於每個 非空 集合 $S$，$\varnothing \subsetneq S$，因為 $\varnothing \subseteq S$ (前面已經證明) 並且 $\varnothing \neq S$ 如果 $S$ 是一個 非空 集合。
• $\mathbb {N} \subsetneq \mathbb {Z} \subsetneq \mathbb {Q} \subsetneq \mathbb {R} \subsetneq \mathbb {C}$.
• $\{1,2\}\subsetneq \{1,2,3\}$.
• $\{1,2\}\not \subsetneq \{\{1,2\},2,3\}$ 並且 $\{1,2\}\not \subseteq \{\{1,2\},2,3\}$.

練習。 令 $A=\{1\}$.

1 以下哪些集合是 $A$ 的子集？

	$\{1\}$
	$\{\}$
	$\{\{1\}\}$
	$\{1,\{1\}\}$

2 選擇哪些集合是 $A$ 的超集？

	$\{1\}$
	$\{\}$
	$\{\{1\}\}$
	$\{1,\{1\}\}$

3 選擇哪些集合是 $A$ 的元素？

	$\{1\}$
	$\{\}$
	$\{\{1\}\}$
	$\{1,\{1\}\}$

我們把一些常見的 $\mathbb {R}$ 的子集稱為 區間。對於每個實數 $a,b$，滿足 $a<b$，

• $(a,b){\overset {\text{ def }}{=}}\{x\in \mathbb {R} :a<x<b\}$ （開區間）
• $(a,b]{\overset {\text{ def }}{=}}\{x\in \mathbb {R} :a<x\leq b\}$ （半開（或半閉）區間）
• $[a,b){\overset {\text{ def }}{=}}\{x\in \mathbb {R} :a\leq x<b\}$ （半開（或半閉）區間）
• $[a,b]{\overset {\text{ def }}{=}}\{x\in \mathbb {R} :a\leq x\leq b\}$ （閉區間）

也有一些 無限 區間

• $(-\infty ,a){\overset {\text{ def }}{=}}\{x\in \mathbb {R} :x<a\}$
• $(-\infty ,a]{\overset {\text{ def }}{=}}\{x\in \mathbb {R} :x\leq a\}$
• $(a,\infty ){\overset {\text{ def }}{=}}\{x\in \mathbb {R} :a<x\}$
• $[a,\infty ){\overset {\text{ def }}{=}}\{x\in \mathbb {R} :a\leq x\}$
• $(-\infty ,\infty ){\overset {\text{ def }}{=}}\mathbb {R}$

注意：$\{x\in S:P(x)\}$ 是 $\{x:x\in S{\text{ and }}P(x)\}$ 的簡寫形式 ($S$ 是一個集合)。

例子。

• $(0,1)\subseteq [0,1)\subseteq [0,1]$.
• ${\sqrt {2}},e,\pi \in (1,4)$.
• $(0,1]\not \subseteq [0,1)$ 因為左側集合中的元素 "1" 不 屬於右側集合。
• $(0,1)\subseteq (0,\infty )$.

例子。

• $x^{2}-9\leq 0$ 的 (實數) 解集是 $[-3,3]$.
• $x^{2}\leq 0$ 的 (實數) 解集是 $\{0\}$。(注意：我們不能 用 $[0,0]$ 來表示這個集合，因為要求對於區間 $[a,b]$，$a<b$）。
• 方程 $x^{2}<0$ 的（實數）解集是 $\varnothing$.

練習。

以下哪些是有效的區間？

	$(0,0)$
	$(0,0.000001)$
	$(-2,-3)$
	$[-1,\infty ]$

全集和韋恩圖

定義。（全集）全集，用 $U$ 表示，是一個包含特定研究中所有元素的集合。

例子。

• 如果我們研究的是實數，那麼全集就是 $\mathbb {R}$.

定義。（補集）集合 $A$ （它是全集 $U$ 的子集）的 補集，用 $A^{c}$ 表示，是集合 $\{x\in U:x\notin A\}$.

例子。

• 令 $A=\{1\}$ 且 $U=\{0,1,1,2\}$。那麼，$A^{c}=\{0,2\}$。（注意：$U=\{0,1,2\}$ 也是。）
• 對於每個全集 $U$，$\varnothing ^{c}=U$（因為 $U$ 中的每個元素都不屬於 $\varnothing$）並且 $U^{c}=\varnothing$（因為 $U$ 中沒有元素不屬於 $U$）。
• 令 $B=\{1,3,5\}$ 並且 $U=\{2,4,6\}$。那麼，$B^{c}=\{2,4,6\}=U$，因為 $U$ 中的每個元素都不屬於 $B$。

練習。 令全集為 $\mathbb {R}$。

1 什麼是 $(-\infty ,1]^{c}$?

	$[1,\infty )$
	$(1,\infty )$
	$(-\infty ,1)$
	$(-\infty ,1]$

2 什麼是 $(-\infty ,1)^{c}$?

	$[1,\infty )$
	$(1,\infty )$
	$(-\infty ,1)$
	$(-\infty ,1]$

3 如果全集是 $U$，$(-\infty ,1)^{c}=(1,3)$。以下哪些可以是 $U$（可能不止一個答案）？

	$[1,3]$
	$(1,3)$
	$(1,\infty )$
	$(3,\infty )$
	$(-\infty ,3)$

一個 維恩圖 是一個圖，它顯示了有限個集合之間所有可能的邏輯關係。全集通常用矩形圍成的區域表示，而集合通常用圓形圍成的區域表示。以下是一個維恩圖。

在這個圖中，如果白色區域表示集合 $A$，矩形圍成的區域表示全集，那麼紅色區域就是集合 $A^{c}$。

然而，以下 不是 維恩圖。

這是因為沒有區域只有黃色和藍色區域相交，只有紅色和綠色區域相交。所以，不是 所有 集合之間的邏輯關係都顯示出來了。

為了顯示四個集合之間所有邏輯關係，可以使用以下維恩圖。

集合運算

類似於將兩個實數組合成一個的算術運算，集合運算將兩個集合組合成一個。

集合的並集

定義. (集合的並集)

兩個集合的並集的維恩圖。

集合 $A$ 和集合 $B$ 的 並集，記為 $A\cup B$，是集合 $\{x:x\in A{\text{ or }}x\in B\}$。

備註。

• 這裡的“或”是 包含的，即如果一個元素屬於 兩個 $A$ 和 $B$，它也屬於 $A\cup B$。

例子。

• $\{1,3,5\}\cup \{2,4,6\}=\{1,2,3,4,5,6\}$.
• $\{1,3,5\}\cup \{1,4,6\}=\{1,3,4,5,6\}$.
• $\{1,3,5\}\cup \{1,3,5\}=\{1,3,5\}$.
• $\mathbb {Q} \cup \mathbb {I} =\mathbb {R}$.

命題. 令 $A,B$ 和 $C$ 為集合. 那麼,

• $A\cup A=A$
• $A\cup B=B\cup A$ (交換律)
• $A\cup (B\cup C)=(A\cup B)\cup C$ (結合律)
• $A\subseteq A\cup B$ 以及 $B\subseteq A\cup B$
• $A\cup \varnothing =A$

證明. (形式)證明將在稍後討論. 現在, 你可以使用維恩圖來驗證這些結果.

$\Box$

備註。

• 由於結合律, 我們可以寫三個 (或更多) 集合的並集而不需要括號. 交集的集合將有類似的結果, 所以我們也可以寫三個 (或更多) 集合的交集而不需要括號.

集合的交集

定義. (集合的交集)

兩個集合交集的維恩圖.

集合 $A$ 和集合 $B$ 的 交集, 記為 $A\cap B$, 是集合 $\{x:x\in A{\text{ and }}x\in B\}$.

備註。

• 如果 $A\cap B=\varnothing$, 我們說 $A$ 和 $B$ 是 不相交 的.

命題. 令 $A,B$ 和 $C$ 為集合. 那麼,

• $A\cap A=A$
• $A\cap B=B\cap A$ (交換律)
• $A\cap (B\cap C)=(A\cap B)\cap C$ （結合律）
• $A\cap B\subseteq A$ 和 $A\cap B\subseteq B$
• $A\cap \varnothing =A$

證明. (形式)證明將在稍後討論. 現在, 你可以使用維恩圖來驗證這些結果.

$\Box$

命題。 （分配律）令 $A,B$ 和 $C$ 為集合。那麼，

• $A\cap (B\cup C)=(A\cap B)\cup (A\cap C)$ （“$A\cap$” 分佈到 $B$ 和 $C$ 分別）
• $A\cup (B\cap C)=(A\cup B)\cap (A\cup C)$

相對補集

定義。 （相對補集）

相對補集的文氏圖。如果左圓和右圓所包圍的區域分別代表 $A$ 和 $B$，那麼紅色區域代表 $B\setminus A$。

集合 $A$ 在集合 $B$ 中的 相對補集，記作 $B\setminus A$，是集合 $\{x:x\in B{\text{ and }}x\notin A\}$。

備註。

• $A^{c}=U\setminus A$ 如果 $U$ 是全集。因此，集合 $A$ 的補集也是 $A$ 在 $U$ 中的相對補集。
• 符號 $B\setminus A$ 讀作“去掉 A 後剩下的 B”。
• 從定義可以看出 $B\setminus A=B\cap A^{c}$

例子。

• $\{a,b,c\}\setminus \{b,c,d\}=\{a\}$.
• $\{a,b,c\}\setminus \{a,b,c,d\}=\varnothing$.
• $\{a,b,c\}\setminus \{1,2,3\}=\{a,b,c\}$.
• $\mathbb {R} \setminus \mathbb {Q} =\mathbb {I}$.
• $\mathbb {Z} \setminus \mathbb {N} =\{0,-1,-2,\ldots \}$.

練習。

1 什麼是 $\mathbb {R} \setminus \mathbb {C}$？

	$\{x:x=a+bi,a,b\in \mathbb {R} {\text{ and }}b\neq 0\}$
	$\{x:x=bi,b\in \mathbb {R} \}$
	$\varnothing$
	$\mathbb {C}$
	$\mathbb {R}$

2 什麼是 $[1,10]\setminus (3,5)$?

	$[1,3]\cup [5,10]$
	$[1,3)\cup (5,10]$
	$(1,3)\cup (5,10)$
	$(1,3]\cup [5,10)$

3 什麼是 $\mathbb {R} \setminus \{0\}$?

	$(-\infty ,0)\cup (0,\infty )$
	$(-\infty ,0]\cup [0,\infty )$
	$(-\infty ,0)\cap (0,\infty )$
	$(-\infty ,0]\cap [0,\infty )$

4 以下哪個/哪些集合表示所有正數的集合？

	$\mathbb {R} \setminus (-\infty ,0)$
	$\mathbb {R} \setminus (-\infty ,0]$
	$(0,\infty )$
	$[0,\infty )$
	$\mathbb {R} \cup (0,\infty )$
	$\mathbb {R} \cap (0,\infty )$

5 什麼是 $\varnothing \setminus \varnothing$?

	$\varnothing$
	全集。
	$\{\varnothing \}$

命題。 令 $A$ 和 $B$ 為集合。那麼，

• $A\setminus A=\varnothing$.
• $A\setminus \varnothing =A$.
• $\varnothing \setminus A=\varnothing$.
• $A\setminus B=\varnothing$ 當且僅當 $A\subseteq B$.
• $(A\setminus B)\cap (B\setminus A)=\varnothing$.
• $A\cap (B\setminus A)=\varnothing$.

證明. (形式)證明將在稍後討論. 現在, 你可以使用維恩圖來驗證這些結果.

$\Box$

定理。 (德摩根定律) 令 $A$ 和 $B$ 為集合。那麼，$$(A\cup B)^{c}=A^{c}\cap B^{c}{\text{ and }}(A\cap B)^{c}=A^{c}\cup B^{c}.$$

證明. (形式)證明將在稍後討論. 現在, 你可以使用維恩圖來驗證這些結果.

$\Box$

示例。 假設全集是 $\{1,2,3,4,5,6,7\}$，$A=\{1,2,3\}$ 並且 $B=\{1,3,5\}$。由於 $A\cup B=\{1,2,3,5\}$，$(A\cup B)^{c}=\{4,6,7\}$。另一方面，由於 $A^{c}=\{4,5,6,7\}$ 並且 $B^{c}=\{2,4,6,7\}$，$A^{c}\cap B^{c}=\{4,6,7\}=(A\cup B)^{c}$.

練習。

什麼是 $(A\cap B)^{c}$？

	$\{4,6,7\}$
	$\{4,5,6,7\}$
	$\{2,4,6,7\}$
	$\{2,4,5,6,7\}$

對稱差

定義。 （對稱差）

一個用於說明對稱差的韋恩圖。

集合 $A$ 和 $B$ 的 對稱差，記作 $A\triangle B$，是集合 $(A\setminus B)\cup (B\setminus A)$.

例子。

• $\{0,1,2\}\triangle \{1,2,3\}=\{0\}\cup \{3\}=\{0,3\}$.
• $\{x,y\}\triangle \{y\}=\{x\}\cup \varnothing =\{x\}$
• $\{x\}\triangle \{y\}=\{x\}\cup \{y\}=\{x,y\}$

命題. 令 $A,B$ 和 $C$ 為集合. 那麼,

• $A\triangle A=\varnothing$
• $A\triangle \varnothing =A$
• $A\triangle B=(A\cup B)\setminus (A\cap B)$
• $A\triangle (B\triangle C)=(A\triangle B)\triangle C$ (結合律)
• $A\triangle B=B\triangle A$ (交換律)

練習。

1 $\varnothing \triangle \varnothing$ 等於什麼？

	$\varnothing$
	$\{\varnothing \}$
	$\{\varnothing ,\{\varnothing \}\}$
	$\{\{\varnothing \}\}$

2 $A\triangle (B\setminus A)$ 等於什麼？

	$A\cup B$
	$A\cap B$
	$A\setminus B$
	$A\triangle B$
	$B\setminus A$
	$A$
	$B$

3 $A\triangle B\triangle C=(A\cup B\cup C)\setminus (A\cap B\cap C)$ (試著利用韋恩圖來確定，目前不需要數學證明。)

	是。
	否。

冪集

定義。 （冪集）集合 $A$ 的冪集，記作 ${\mathcal {P}}(A)$，是 $A$ 的所有子集的集合。用集合生成式表示，${\mathcal {P}}(A)=\{S:S\subseteq A\}$。

備註。

• 因為 $\varnothing \subseteq A$ 對於每個集合 $A$ 成立，$\varnothing$ 是每個冪集的元素。
• 同樣，因為 $A\subseteq A$ 對於每個集合 $A$ 成立，$A$ 是冪集 ${\mathcal {P}}(A)$ 的元素。

例子。

• ${\mathcal {P}}(\varnothing )=\{\varnothing \}$。它的基數是 1。
• 如果 $A=\{1\}$，那麼 ${\mathcal {P}}(A)=\{\varnothing ,A\}=\{\varnothing ,\{1\}\}$。它的基數是 2。
• 如果 $B=\{1,\{1\}\}$，那麼 ${\mathcal {P}}(B)=\{\varnothing ,\{1\},\{\{1\}\},B\}$。它的基數是 4。
• ${\mathcal {P}}(\{1,2,3\})=\{\varnothing ,\{1\},\{2\},\{3\},\{1,2\},\{2,3\},\{1,3\},\{1,2,3\}\}$. 它的大小是 8。

定理。 (有限集冪集的大小) 設 $A$ 是一個大小為 $n$ 的有限集。那麼， $|{\mathcal {P}}(A)|=2^{n}$.

證明。 假設 $A$ 是一個大小為 $n$ 的有限集。由於冪集 ${\mathcal {P}}(A)$ 的每個元素都是 $A$ 的子集，所以只需要證明 $A$ 有 $2^{n}$ 個子集。下面，我們分別考慮 $A$ 中元素個數不同的子集，並使用組合學計算每種不同型別子集的個數。

• 對於元素個數為零的子集，它就是空集，所以只有一個這樣的子集。
• 對於元素個數為一的子集，有 $C_{1}^{n}$ 個子集。
• 對於元素個數為二的子集，有 $C_{2}^{n}$ 個子集。
• ...
• 對於元素個數為 $n-1$ 的子集，有 $C_{n-1}^{n}$ 個子集。
• 對於包含 $n$ 個元素的子集，它是集合 $A$，因此只有一個這樣的子集。

因此，集合 $A$ 的子集總數為 $1+C_{1}^{n}+C_{2}^{n}+\dotsb +C_{n-1}^{n}+1=(1+1)^{n}=2^{n}$，根據 二項式定理。

$\Box$

備註。

• 這裡採用的證明方法稱為 直接證明，這可能是最“自然”的方法，也是最常用的方法。我們將在 後面章節 中討論證明方法。
• 有其他方法可以證明這個定理。

練習。 在下列問題中，選擇給定集合的 冪集。

1 $\{\varnothing \}$

	${\big \{}\varnothing ,\{\{\varnothing \}\}{\big \}}$
	${\big \{}\{\varnothing \},\{\{\varnothing \}\}{\big \}}$
	${\big \{}\varnothing ,\{\varnothing \}{\big \}}$
	${\big \{}\varnothing ,\{\varnothing \},\{\{\varnothing \}\}{\big \}}$

2 ${\mathcal {P}}(\{\varnothing \})$

	${\big \{}\varnothing ,\{\varnothing \},\{\{\varnothing \}\},\{\varnothing ,\{\varnothing \}\}{\big \}}$
	${\big \{}\varnothing ,\{\varnothing ,\{\varnothing \}\},\{\{\varnothing \}\},\{\varnothing ,\{\varnothing \}\}{\big \}}$
	$\left\{\varnothing ,\{\{\varnothing \}\},\{\{\{\varnothing \}\}\},{\big \{}\{\varnothing \},\{\{\varnothing \}\}{\big \}}\right\}$
	$\left\{\varnothing ,\{\varnothing \},\{\{\varnothing \}\},{\big \{}\{\varnothing \},\{\{\varnothing \}\}{\big \}}\right\}$

3 $\{a,\{a\}\}$

	$\{\varnothing ,\{a\},\{\{a\}\},\{a,\{a\}\}\}$
	$\{\varnothing ,a,\{\{a\}\},\{a,\{a\}\}\}$
	$\{\varnothing ,a,\{a\},\{\{a\}\}\}$

4 $S=\{1,3\}\triangle \{3,5\}$

	$\{\varnothing ,\{1\},\{3\},\{5\},\{1,3\},\{3,5\},\{1,5\},S\}$
	$\{\varnothing ,\{1\},\{3\},\{5\},S\}$
	$\{\varnothing ,S\}$
	$\{\varnothing ,\{1\},\{5\},\{1,5\},S\}$

已知 $|A|=2$。在以下每個問題中，選擇題目中給定集合的 基數。

1 ${\mathcal {P}}({\mathcal {P}}(A))$

	4
	8
	16
	32

2 ${\mathcal {P}}({\mathcal {P}}(\varnothing ))$

	0
	1
	2
	4

3 $\{{\mathcal {P}}(A)\}$

	1
	2
	4
	8

4 ${\mathcal {P}}(\{A\})$

	1
	2
	4
	8

5 ${\mathcal {P}}(\varnothing \cap {\mathcal {P}}(A))$

	1
	2
	4
	8

笛卡爾積

定義。 (笛卡爾積) 集合 $A$ 和 $B$ 的 笛卡爾積，記作 $A\times B$，是 $A\times B=\{(a,b):a\in A{\text{ and }}b\in B\}$.

備註。

• $(a,b)$ 是一個 有序對（即順序 重要 的一對事物）。

• 有序對用於指定平面上的點，有序對稱為 座標。

• 特別地，我們有 $(a,b)\neq (b,a)$ 如果 $a\neq b$.
• (符號) 我們使用 $A^{2}$ 表示每個集合 $A$ 的 $A\times A$。
• 我們可以觀察到 $|A\times B|=|A|\times |B|$。

示例. 令 $A=\{0,1\}$ 且 $B=\{a,b,c\}$。那麼，

• $A\times B=\{(0,a),(0,b),(0,c),(1,a),(1,b),(1,c)\}$.
• $B\times A=\{(a,0),(b,0),(c,0),(a,1),(b,1),(c,1)\}$.

備註。

• 從上面的例子可以看出，笛卡爾積是 非交換的，即 $A\times B=B\times A$ 不一定成立。

練習. 令 $A=\{1,2,3\}$。

1 什麼是 $A\times \varnothing$（可能有多個答案）？

	$\{(1,0),(2,0),(3,0)\}$
	$\{(1,\varnothing ),(2,\varnothing ),(3,\varnothing )\}$
	$\varnothing$
	$\varnothing \times A$
	$\varnothing ^{2}$

2 什麼是 $A^{2}$？

	$\{(1,1),(2,2),(3,3)\}$
	$\{(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)\}$
	$A$
	$\{(1,A),(2,A),(3,A)\}$

類似地，我們可以定義三個或更多集合的笛卡爾積。

定義。 (三個或更多集合的笛卡爾積) 令 $n$ 是大於 2 的整數。 $n$ 個集合 $A_{1},A_{2},\dotsc ,A_{n}$ 的笛卡爾積是 $A_{1}\times A_{2}\times \dotsb \times A_{n}=\{(a_{1},a_{2},\dotsc ,a_{n}):a_{1}\in A_{1},a_{2}\in A_{2},\dotsc ,{\text{ and }}a_{n}\in A_{n}\}$.

備註。

• (符號) 我們使用 $A^{n}$ 來表示 $\underbrace {A\times A\times \dotsb \times A} _{n{\text{ times}}}$，其中 $n\in \mathbb {N}$.