集合代數

<image>

集合代數發展並描述了集合的基本性質和規律，集合論運算，如併集、交集、補集，以及集合的關係，如等於、包含。這門學科系統研究如何來表達和進行上述的運算和關係的操作。

## 導言

集合代數是研究集合運算和集合關係的基本性質的學科。研究這些性質可以深入探究集合的本質，也有助於實際應用。

像普通算術的表達和計算一樣，集合的表達和計算可能相當複雜。通過系統研究將有助於熟練使用和理解這些表達方式並進行計算。

在算術研究方面，是通過初等代數來研究算術的運算和關係的。

例如：加法和乘法運算遵循人們看時候帶吃熟知的交換律、結合律和分配律；而"小於等於"關係滿足自反性、反對稱性和傳遞性。

這些規律提供了簡化計算的工具，並描述了算術的本質、運算和關係。

集合代數相當於集合論中的算術代數。它是關於集合論運算如交集、併集、補集，和集合論關係如等於、包含等的代數：本文主要介紹這些內容。對集合的基本介紹請參見集合，更詳盡的內容請參見樸素集合論。

## 集合上的基本結構

集合上通常自然定義的結構包括：

二元關係

- 包含（$\subseteq$）：$A\subseteq B$ 若且唯若 $\forall e (e\in A \implies e\in B)$。
- 真包含（$\subset$）：$A\subset B$ 若且唯若 $A\subseteq B$ 且 $A\neq B$。

二元運算

- 交（$\cap$）：$A\cap B$定義為 $\{e \mid e\in A$ 且 $e\in B\}$。
- 並（$\cup$）：$A\cup B$ 定義為 $\{e \mid e\in A$ 或 $e\in B\}$。
- 差（$-$）：$A-B$ 定義為 $\{e \mid e\in A$ 且 $\neg(e\in B)\}$（亦稱相對補）。
- 對稱差（$\triangle$）：$A\triangle B$ 定義為 $(A-B)\cup (B-A)$。
- 補：補運算的前提是存在一個由上下文確定的全集$X$，其某個子集$A$對於$X$的補$A^c$ 定義為 $X-A$。

其它運算

- 冪集：$\mathcal{P}(A)$ 定義為 $\{E \mid E\subseteq A\}$（A 的冪集是 A 所有子集構成的集合）。
- 笛卡爾積：$X \times Y$ 定義為 $\left\{ \left( x,y \right) \mid x \in X \land y \in Y \right\}$（即所有可能的有序對組成的集合）。

特殊的集合

- 空集（$\varnothing$）：沒有任何元素的集合。
- 全集：這是一個由上下文確定的集合，通常上下文中其它的集合都是它的子集。

這些二元關係和二元運算構成了集合上的基本結構，包括序結構和代數結構。

### 代數結構

代數結構是關於運算的結構。以下是集合間運算的基本性質：

交換律

- $$A \cap B = B \cap A$$
- $$A \cup B = B \cup A$$
- $$A \triangle B = B \triangle A$$

結合律

- $$(A \cap B) \cap C = A \cap (B \cap C)$$
- $$(A \cup B) \cup C = A \cup (B \cup C)$$
- $$(A \triangle B) \triangle C = A \triangle (B \triangle C)$$

分配律

- $$(A \cap B) \cup C = (A \cup C) \cap (B \cup C)$$
- $$(A \cup B) \cap C = (A \cap C) \cup (B \cap C)$$
- $$(A -B) \cap C = (A \cap C) -(B \cap C)$$
- $$(A \triangle B) \cap C = (A \cap C) \triangle (B \cap C)$$

冪等律

- $$A \cup A = A$$
- $$A \cap A = A$$

么元

- $A \cup \varnothing = \varnothing \cup A = A$（$\varnothing$ 是 $\cup$ 運算的么元）
- $A \triangle \varnothing = \varnothing \triangle A = A$（$\varnothing$ 是 $\triangle$ 運算的么元）
- $A - \varnothing = A$（$\varnothing$ 是 $-$運算的右么元）

零元

- $A \cap \varnothing = \varnothing \cap A = \varnothing$ （$\varnothing$ 是 $\cap$ 運算的零元）
- $\varnothing -A = \varnothing$ （$\varnothing$ 是 $-$運算的左零元）

冪么律

- $$A \triangle A = \varnothing$$

德·摩根律

- $C -(A \cup B) = (C -A) \cap (C -B)$。
- $C -(A \cap B) = (C -A) \cup (C -B)$。
- $(A \cup B)^c = A^c \cap B^c$（這條是第一條的補集形式）
- $(A \cap B)^c = A^c \cup B^c$（這條是第二條的補集形式）

吸收律

- $$A \cup (A \cap B) = A$$
- $$A \cap (A \cup B) = A$$

### 序結構

包含關係「$\subseteq$」有如下性質：

- 自反性：$A \subseteq A$；（任何集合都是其本身的子集）
- 反對稱性：$A \subseteq B$且$B \subseteq A \iff A=B$；（這是證明兩集合相等的常用手段之一）
- 傳遞性：$A \subseteq B$且$B \subseteq C \implies A \subseteq C$。

是集合間的一個非嚴格偏序關係。

真包含關係「$\subset$」有如下性質：

- 反自反性：$A \subset A$不成立。
- 非對稱性：$A \subset B \implies B \subset A$不成立；反之亦然。
- 傳遞性：$A \subset B$且$B \subset C \implies A \subset C$。

是集合間的一個嚴格偏序關係。

包含和真包含關係定義了集合間的一個偏序關係。在該偏序關係的意義下兩者等價，通常不失一般性地將該偏序關係指為 $\subseteq$。該偏序關係還有如下的結構：

上確界運算： $\cup$

- $$A \subseteq C,B \subseteq C \implies A \cup B \subseteq C$$
- $$A \subseteq A \cup B$$

下確界運算： $\cap$

- $$C \subseteq A,C \subseteq B \implies C \subseteq A \cap B$$
- $$A \cap B \subseteq A$$

最小元（底）： $\varnothing$

- $\varnothing \subseteq A$（$\varnothing$ 是任何集合的子集）

## 集合上結構的最小定義

顯然，上面的所有結果並不是獨立的，大部分結果都可以從一個很小的結構推導出來。

比如很容易知道：

- 對稱差可以用並和差來定義。
- 補可以用差來定義。
- 真包含關係可以用包含關係來定義。
- 包含關係可以用並，交，差之一來定義，這是因為 $A\subseteq B$等價於以下任一命題：
- $$A\cup B = B$$
- $$A\cap B = A$$
- $$A - B = \varnothing$$

因此我們完全可以用並，交，差三個運算以及它們的相關性質推導出上面所有二元運算和二元關係的性質。

當然這個「最小結構」的選擇並不唯一，可以根據需要選擇適當的方式。

下一個命題包含三種特殊集合：空集、全集、集合的補集，給出關於它們的兩組規律。

命題 2：對全集 $\mathcal{U}$ 的任意子集 $A$，下列恆等式成立：

同一性：

- $$A \cup \varnothing = A$$
- $$A \cap \mathcal{U} = A$$

補集律：

- $$A \cup A^c = \mathcal{U}$$
- $$A \cap A^c = \varnothing$$

同一性（結合交換律）說明，就像 0 和 1 分別是加法和乘法的單位元，$\varnothing$ 和 $\mathcal{U}$ 也分別是併集和交集的單位元。

跟加法和乘法不同，併集和交集沒有逆元。然而，補集律給出了類似逆運算的一元運算，集合的補集的基本性質。

上述五組性質：交換律、結合律、分配律、同一性和補集律，可以說包含了集合代數的所有內容，可以認為集合代數中所有正確的命題都是從它們得到的。

## 對偶性原理

上述命題有一個有趣的形式，就是每一組恆等式都是成對出現的。將 ∪ 和 ∩，或者 Ø 和 U 相互交換，一個恆等式就變成了相應的另一個。

這是集合代數的一個非常重要的性質，稱作集合的對偶性原理。它對集合的所有真命題都有效。真命題通過相互交換 ∪ 和 ∩，Ø 和 U，改變包含符號的方向得到的對偶命題也是真的。若一個命題和其對偶命題相同，則稱其為自對偶的。

## 更多關於併集和交集的定律

下列命題給出六條關於併集和交集的重要定律。

命題 3：對任意全集 $\mathcal{U}$ 的子集 $A$ 和 $B$，下列恆等式成立：

支配律：

- $$A \cup \mathcal{U} = \mathcal{U}$$
- $$A \cap \varnothing = \varnothing$$

如前所述，命題 3 里的每條定律都可以從命題 1 和命題 2 的五組基本定律推導出來。作為說明，下面給出併集的冪等律的證明。

證明：

$A \cup A$｜$= ( A \cup A) \cap \mathcal{U}$｜交集的同一律

$= ( A \cup A) \cap ( A \cup A^c)$｜併集的補集律

$= A \cup ( A \cap A^c)$｜併集對交集的分配律

$= A \cup \varnothing$｜交集的補集律

$= A$｜併集的同一律

下列證明說明，上述證明的對偶是對併集的冪等律的對偶，即交集的冪等律的證明。

證明：

$A \cap A$｜$= ( A \cap A) \cup \varnothing$｜併集的同一律

$= ( A\cap A) \cup ( A \cap A^c)$｜交集的補集律

$= A \cap ( A \cup A^c)$｜交集對併集的分配律

$= A \cap \mathcal{U}$｜併集的補集律

$= A$｜交集的同一律

## 更多關於補集的定律

下列命題給出五條關於補集的重要定律。

命題 4：設 $A$ 和 $B$ 為全集 $\mathcal{U}$ 的子集，則：

德·摩根律：

- $$(A \cup B)^c = A^c \cap B^c$$
- $$(A \cap B)^c = A^c \cup B^c$$

重補集或對合律：

- $$(A^c)^c = A$$

全集和空集的補集律：

- $$\varnothing ^c = \mathcal{U}$$
- $$\mathcal{U} ^c = \varnothing$$

注意，重補集律是自對偶的。

下一個命題也是自對偶的，說明集合的補集是唯一滿足補集律的集合。也就是說，互補的特徵通過補集律體現。

命題 5：設 $A$ 和 $B$ 為全集 $\mathcal{U}$ 的子集，則：

補集的唯一性：

- 若 $A \cup B = \mathcal{U}$ 且 $A \cap B = \varnothing$ 則 $B = A^c$。

## 包含的代數

下列命題說明包含是種偏序關係。

命題 6：若 $A, B, C$ 為集合，則下述成立：

自反性：

- $$A \subseteq A$$

反對稱性:

- $A \subseteq B$ 且 $B \subseteq A$，若且唯若 $A = B$

傳遞性:

- 若 $A \subseteq B$ 且 $B \subseteq C$，則 $A \subseteq C$

下列命題說明對任意集合 $S$，$S$ 的冪集按照包含來排列是個有界格；因此，結合上述的分配律和補集律，它是一個布爾代數。

命題 7：若 $A, B, C$ 是集合 $S$ 的子集，則下述成立：

存在最小元和最大元：

- $$\varnothing \subseteq A \subseteq S$$

存在並運算:

- $$A \subseteq A \cup B$$
- 若 $A \subseteq C$ 且 $B \subseteq C$ 則 $A \cup B \subseteq C$

存在交運算:

- $$A \cap B \subseteq A$$
- 若 $C \subseteq A$ 且 $C \subseteq B$ 則 $C \subseteq A \cap B$

下列命題說明，" $A \subseteq B$ " 與各種採用併集、交集、補集的表示方法等價。

命題 8：對任意兩個集合 $A$ 和 $B$，下述等價：

- $$A \subseteq B$$
- $$A \cap B = A$$
- $$A \cup B = B$$
- $$A - B = \varnothing$$
- $$B^c \subseteq A^c$$

上述命題說明，集合的包含關係可以採用併集運算或交集運算來表示，即包含關係在公理體系中是多餘的。

## 相對補集的代數

下列命題給出一些關於相對補集或集合論差的恆等式。

命題 9：對任意全集 $\mathcal{U}$ 和 $\mathcal{U}$ 的子集 $A$，$B$，$C$，下列恆等式成立：

- $$C - (A \cap B) = (C - A) \cup (C - B)$$
- $$C - (A \cup B) = (C - A) \cap (C - B)$$
- $$C - (B - A) = (A \cap C) \cup (C - B)$$
- $$(B - A) \cap C = (B \cap C) - A = B \cap (C - A)$$
- $$(B - A) \cup C = (B \cup C) - (A - C)$$
- $$A - A = \varnothing$$
- $$\varnothing - A = \varnothing$$
- $$A - \varnothing = A$$
- $$B - A = A^c \cap B$$
- $$(B - A)^c = A \cup B^c$$
- $$\mathcal{U} - A = A^c$$
- $$A - \mathcal{U} = \varnothing$$

## 常用代數結構

### 半環

若集類$S$滿足：

- 對交運算封閉：$\forall E,F\in S$，則 $E\cap F\in S$。
- $\forall E,F\in S$，若$E\subseteq F$，則存在$C^{0},C^{1}, \ldots ,C^{n}\in S$，使得$E\subseteq C^{0}\subseteq C^{1}\subseteq \ldots \subseteq C^{n}\subseteq F$，且$\forall 0\leq i\leq n,C^{i}-C^{i-1}\in S$；（即$E$可以通過和$S$中一些集合的無交並得到$F$）。

則$S$構成一個半環。

### 格

若集類$S$滿足：

- 空集屬於$S$。
- 對交運算封閉：$\forall E,F\in S$，則$E\cap F\in S$。
- 對並運算封閉：$\forall E,F\in S$，則$E\cup F\in S$。

則$S$構成一個格。

### 環，代數

非空集類S，若：

- S對集合的並和差運算封閉，即：$\forall E,F\in S \implies E\cup F\in S,E-F\in S$。
- S對集合的交和對稱差運算封閉，即：$\forall E,F\in S \implies E\cap F\in S,E\triangle F\in S$。
- S對集合的交，差以及無交並運算封閉。

若且唯若$S$滿足以上幾個條件中任何一個時，$S$構成一個環，此時$S$被稱為一個集環。

若集環$S$還滿足：

- $\exists X\in S$，使得$\forall E\in S$，有$E\subseteq X$。（即$S$中的所有集合的全集$X$也在$S$中）

則$S$是$X$上的代數，稱為X上的集代數。

- 從代數角度來看，集環（集代數）$S$以$\cap$ 為乘法，$\triangle$ 為加法；以空集為零元，並且由於乘法滿足冪等律，$\forall E\in S,E\cap E=E\cdot E=E$，因此$S$還是布爾環（布爾代數）。
- 設$S$為一非空集類，可以知道，必存在唯一的集環R，使得$S\subseteq R$，且$\forall$ 集環$R'$使得$S\subseteq R'$有$R\subseteq R'$，則$R$稱為包含$S$的最小集環或由$S$生成的集環。

### $\sigma$ 環，$\sigma$ 代數

設$S$是集環（集代數），若$S$對可列並運算封閉，則稱$S$為一個σ環（σ代數）。