集合论（一）：集合及其运算

集合及其运算

在本篇里，首先非形式地讨论集合论的基本概念：集合及其元素，以及元素与集合间的属于关系，集合的表示方法。然后，利用这些基本概念定义集合的子集、幂集、集合相等。接着定义集合间的运算:并、交、差、对称差、集的余集、Cartesian乘积，并讨论每种运算所满足的运算规律以及它们之间的联系。最后，介绍有穷集合的基数与基本的计数法则。

集合的概念

“集合”是集合论中的一个原始概念，原始概念是不能被精确定义的，因为我们没有比它更原始的概念。因此，我们只给出集合这个概念的一种非形式的描述，说明这个概念的含义。这正如同欧几里德几何中的“点”不加定义，而作为原始概念之一一样。

集合

通常把一些互不相同的东西放在一起所形成的整体就叫做一个集合，简称集。构成集合的每一个东西，称为这个集合的一个成员。构成集合的这些成员可以是具体的东西，也可以是抽象东西。例如，某教室里的所有学生形成的整体就是一个集合。全体自然数构成的整体也是一个集合。程序设计语言C的基本字符的全体也形成一个集合。集合的概念是如此的普遍和原始，以致于有许多同义语，如“全体”“汇集”等等。

元素

当抽象讨论集合时，任何一个东西称为元素，元素是可区分的。构成集合的那些成员就是集的元素。于是，任一元素，对给定的集合,要么这个元素是该集合的一个（成员）元素，要么就不是该集合的一个成员，两者必有一个成立，但不能都成立。通常我们用大写的英文字母或大写的希腊字母代替该集合。如果给定一个集合 $A$ 和一个元素 $a$ ，$a$ 是 $A$ 的一个成员（元素），即 $a$ 属于 $A$ ，就记 $a \in A$ 。否则，若 $a$ 不属 $A$ ，就记为 $a \notin A$ 。$a \in A$ 读成 “ $a$ 属于 $A$ ”，而 $a \notin A$ 读成“ $a$ 不属于 $A$ ”。
例1：设 $N$ 为全体自然数（正整数）之集，则

$$\begin{aligned} 7 \in N,2^7\in N,1024 \in N \tag{1}\end{aligned}$$

而

$$\begin{aligned} 0 \notin N,\frac{1}{2} \notin N,\sqrt{2} \notin N,-3\notin N \tag{2}\end{aligned}$$

于是，是，集合是由一些东西（或事物、对象，统称为元素）构成的，构成集合的每个东西叫做集合的成员。集合的成员与集合间有属于关系“ $\in$ ”。这样，集合、元素、属于关系就是集合论中三个原始概念,它们不能精确地形式定义。集合论中的其他概念均可用这三个原始概念加以定义。

集合的表示

有两种方法表示一个集合。最自然的方法是把构成集合的那些元素全列出来，元素之间用逗号”，”隔开，并用花括号“ $\{$ ”与“ $\}$ ”在两边括起来以表示这些元素构成整体。例如，由 $1,2,3$ 三个自然数构成的集合就记成 $\set{1,2,3}$ 。花括号把 $1,2,3$ 括在里面使它们组成一个整体。不过，在集合的概念里我们只要求构成集合的那些元素是互不相同的，而与它们在集合中出现的次序无关。因此，集合中的每个元素只能出现一次，至于先写出哪一个无关紧要。于是，$\set{1,2,3}$ 与 $\set{3,1,2}$ 表示了同一个集合。
一般说来，仅由少数元素构成的集合才能用列出它的全部元素的方法表示该集合。对于有穷（也说有限）多个元素，原则上这个方法也是可行的，但元素的个数很大时，列出这些元素在实际上是不可行的。不过在具体问题中借助于其他知识，只列出其几个元素后就可知道组成集合的那些元素。例如，由26个小写英文字母 $a,b,c,\cdots,x,y,z$ 构成的集合就可记为

$$\begin{aligned} \set{a,b,c,\cdots,x,y,z} \tag{3}\end{aligned}$$

其中的“ $\cdots$ ”就表示了那些未列出的字母，而不是说"…”也是一个元素。在这里，我们利用小写字母在英文字母表中的顺序的知识，就知道了未列出的那些字母是什么。利用此方法有时甚至可以表示某些由无穷多个元素组成的集合。例如，全体自然数构成的集合 $N$ 就可以写成

$$\begin{aligned} \set{1,2,3} \tag{4}\end{aligned}$$

这里借用了人们的已有知识——自然数的顺序，只列出了前三个自然数，其后的自然数用“…”代替。
用上述方法表示集合很直观，哪些元素是集合的成员一望可知,但集合的这种表示方法的表达能力是有局限的。有些集合很难或不能用这种方法表示，例如，区间 $(0,1)$ 中的所有实数组成的集合就不能用这种方法表示。实际上，这个集合是“大于或等于零且小于或等于1”的一切实数构成的。而在实际应用中，往往把具有某种性质的一些对象集合在一起形成一个集合，为此引入集合的另一表示法，这种方法是用概括集合中各元素的属性来表示集合。设x为某类对象的一般表示，$P(x)$ 为关于 $x$ 的一命题，则我们用

$$\begin{aligned} \set{x|P(x)} \tag{5}\end{aligned}$$

表示“使 $P(x)$ 成立的对象 $x$ 所组成的集合”。其中竖线“|”前写的是对象的一般表示，右边写出它应满足（具有）的属性。

例2：所有偶自然数之集合 $E$ 可记为

$$\begin{aligned} \set{m|2|m且m \in N} \tag{6}\end{aligned}$$

其中 $2|m$ 表示 $2$ 能整除 $m$ 。

例3： $[0,1]$ 上的所有连续函数之集 $C_{[0,1]}$ 可记成

$$\begin{aligned} \set{f(x)|f(x)在(0,1)上连续} \tag{7}\end{aligned}$$

易见，集合的第二种表示法较方便，它给出了组成集合的各元素所具有性质，因此它能告诉我们更多的信息。

有穷集合和无穷集合

由有限个元素构成的集合叫做有限集合，或有穷集。由无穷多个元素组成的集合叫做无穷集合。有穷集的一个特例是仅由一个元素形成的集合,称为单元素集。例如，方程

$$\begin{aligned} x^3-x^2+x-1=0 \tag{8}\end{aligned}$$

的实根构成的集合就是单元素集。注意，不要把单元素集 $\set{x}$ 与它的唯一元素 $x$ 混为一谈，否则会引出矛盾。例如，$x \in {x}$ 有意义，但 $x \in x$ 是无意义的。

空集

在实际的具体问题中，常涉及具有某种性质的对象全体形成的集合，这样的集合也参加运算。但事先不知道是否存在这种性质的元素，如果后来发现这种元素不存在，那么具有这种性质的元素之集合中就不包含任何元素。于是，有必要引入一个不含任何元素的集合。不含任何元素的集合叫做空集，记为 $\varnothing$ 。我们假定空集是存在的，例如，方程

$$\begin{aligned} x^2+1=0 \tag{9}\end{aligned}$$

的实根之集是空集。空集的引入可以使许多问题的叙述得以简化。

子集、集合的相等

“集合”、“元素”、元素与集合间的“属于”关系是三个没有精确定义的原始概念，对它们仅给出了直观的描述，以说明它们的各自含义。本节利用这三个概念定义集合的子集、集合间的包含关系、集合的相等、幕集、集族等概念。

集合的包含

定义1：设 $A$ 和 $B$ 是两个集合，如果集合 $A$ 中的每个元素都是 $B$ 的元素，则称 $A$ 是 $B$ 的子集合。简称子集。这是我们说 $A$ 包含在 $B$ 里，或 $B$ 包含着 $A$ 。$A$ 是 $B$ 的子集记为 $A \sube B$ 或 $B \supe A$ 。

由定义可知，$A \sube B$ 当且仅当对 $A$ 的每个元素 $x$ 均有 $x \in B$ 。以后常用记号 $\Harr$ 表示“当且仅当”；用“ $\forall x \cdots$ ”表示“对所有的 $x$ ···”；“ $\exist x \cdots$ ”表示“存在一个 $x$ ···”。于是 $\forall x \in A$ 就读做对 $A$ 的所有元素 $x$ 。于是

$$\begin{aligned} A \sube B \Harr \forall x \in A,x \in B \tag{10}\end{aligned}$$

或等价地

$$\begin{aligned} A \sube B \Harr 不在B的元素必不在A中 \tag{11}\end{aligned}$$

例4：设 $N$ 为所有自然数构成的集合，$Q$ 为一切有理数组成的集合，$R$ 为全体实数之集，$C$ 为全体复数之集，则

$$\begin{aligned} N \sube Q \sube R \sube C \tag{12}\end{aligned}$$ $$\begin{aligned} \set{1} \sube N,\set{1,1.2,9,9}\sube Q,\set{\sqrt{2},\pi}\sube R \tag{13}\end{aligned}$$

如果 $A$ 不是 $B$ 的子集，则记为 $A \nsubseteq B$ （读 $A$ 不包含在 $B$ 里），由定义得

$$\begin{aligned} A \nsubseteq B \Harr \exist x \in A 使得 x \notin B \tag{14}\end{aligned}$$

若 $A,B,C$ 都是集合，则由定义有 $$\begin{aligned} A \sube A \tag{15}\end{aligned}$$ $$\begin{aligned} 若 A \sube B 且 B \sube C ，则 A \sube C \tag{16}\end{aligned}$$

真子集

定义2：设 $A,B$ 为集合。如果 $A \sube B$ 且 $\exist x \in B$ 使得 $x \notin A$ ，则称 $A$ 是 $B$ 的真子集，记为 $A \sub B$ 。
例如，$\set{a,b}$ 的真子集。$N$ 是 $Q$ 的真子集，$Q$ 是 $R$ 的真子集，$R$ 是 $C$ 的真子集。
注意符号“ $\in$ ”与“ $\sube$ ”在概念上的区别。$\in$ 为元素与集合间的属于关系，而 $\sube$ 为集合间的包含关系。

集合的相等

定义3：设 $A,B$ 是集合，如果 $A \sube B$ 且 $B \sube A$ ，则称 $B$ 与 $A$ 相等,并记成 $A=B$ 。
这就是说，如果 $A$ 和 $B$ 由完全相同的元素组成时，那么 $A$ 与 $B$ 就是相等的两个集合。两个相等的集合并不意味着它们是用同样的方法定义的。如果 $A$ 与 $B$ 是两个不相等的集合，那么就记为 $A \ne B$ 。显然，

$$\begin{aligned} A\ne B \Harr A \nsubseteq B 或 B \nsubseteq A \tag{17}\end{aligned}$$ $$\begin{aligned} A \sub B \Harr A \sube B 且 A \ne B \tag{18}\end{aligned}$$

例5：设 $A=\set{2,3}$ ，$B$ 为方程

$$\begin{aligned} x^2-5x+6=0 \tag{19}\end{aligned}$$

的根形成的集合，则 $A=B$ 。

定义3指出了一个重要原则：要证明两个集合相等，唯一的方法是证明每一个集中的任一元素均是另一个集的元素。这种证明应是靠逻辑推理，而不是依靠直观。证明两个集合相等的方法是本文中必须掌握的方法，它贯穿在本部分的各篇中。

空集是任一集的子集且唯一

定理1：空集是任一集的子集且空集是唯一的。

〔证明(定理1)〕设 $A$ 是任一集。由于空集 $\varnothing$ 没有任何元素，所以断言“ $\varnothing$ 中每个元素均是 $A$ 的元素。”成立。因此，按子集的定义有 $\varnothing \sube A$ ，即 $\varnothing$ 是 $A$ 的子集。
设 $\varnothing$ 和 $\varnothing'$ 都是空集，则由上可知，$\varnothing \in \varnothing'$ 且 $\varnothing' \in \varnothing$ 。由定义3得到 $\varnothing=\varnothing'$ ，从而空集是唯一的。

证毕

由定理1，空集是唯一的，所以用 $\varnothing$ 表示空集是合理的。

由定义1可知，判断 $A$ 是否是集合 $B$ 的子集等价于判断断言“对每个 $x$ 若 $x \in A$ 则 $x \in B$ ”是否成立。如果这个断言成立，则 $A \sube B$ ；否则 $A \nsubseteq B$ 。而断言“对每个 $x$ 若 $x \in A$ 则 $x \in B$ ”是一个复合语句（命题） $x \in A$ 是前题，$x \in B$ 是结论。前题和结论都是断言，它们之间用联接词“如果…，则…”联接成一个复合命题。在数学中，特别是在数理逻辑中，我们规定一个复合命题是假的，当且仅当前提是真的，结论是假的。利用此规定进行推理是安全的，不会推出假的复含命题。定理1的前半部分的证明就利用了这个规定。

集族

在集合的概念中曾说过，集合是一些事物的总体,而这些东西可以是现实存在的，也可以是抽象的，并没有什么限制。于是，集合也是事物，也可以把一些集合构成一个整体形成一个新的集合。这种以集合为其元素的集合叫做集族。集族并不是一个新概念，只是提醒读者，这个集合的成员也是某些集合。于是，就有了层次。为了思考的清晰起见，我们有

定义4：以集合为元素的集合称为集族。

在数学、计算机科学中，甚至在日常生活中常常会遇到集族。例如，在学校中，每个班级的学生形成一个集合,而全校的各个班就形成了一个集族。

设 $A_1,A_2,A_3$ 为集合，则 $\set{A_1,A_2,A_3}$ 为一个集族。若令 $I=\set{1,2,3}$ ，则 $\forall i \in I$ ，$i$ 确定了一个唯一的集合 $A_i$ 。于是，集族 $A_1,A_2,A_3$ 又常写成 $\set{A_i}_{i \in I}$ ，即 $I$ 中元素 $i$ 确定的那些集形成的集族。
一般地，若 $J$ 为任一集，对 $J$ 中每个 $j$ 有一个唯一的集与之对应, 这个集记为 $A_j$ ，那么所有这些 $A_j$ 形成的集族就用 $\set{A_j}_{j \in J}$ 表示，其 $J$ 称为标号集。

定义5：集合 $S$ 中的所有子集（包括空集 $\varnothing$ 及 $S$ 本身）形成的集族称为 $S$ 的幂集，并记为 $2^S$ ，或 $\mathscr{P}(s)$ 。
于是有 $$\begin{aligned} 2^S=\set{A|A \sube S} \tag{20}\end{aligned}$$

例6：设 $S={1,2,3}$ ，则

$$\begin{aligned} 2^S=\set{\varnothing,\set{1},\set{2},\set{3},\set{1,2},\set{1,3},\set{2,3},\set{1,2,3}} \tag{21}\end{aligned}$$

$S$ 有八个子集。

一般说来，若 $S$ 正好有 $n$ 个元素，则 $S$ 有 $2^n$ 个子集，这就是我们为什么采用记号 $2^S$ 的原因。

注意，$2^{\varnothing}=\set{\varnothing}$ 。在这里要区分 $\varnothing$ 和 $\set{\varnothing}$ ，$\varnothing$ 为空集，而 $\set{\varnothing}$ 是个集族，这个集族仅有一个元素，就是空集。因此，$\varnothing\ne\set{\varnothing}$ 。但 $\varnothing\in\set{\varnothing}$ 且 $\varnothing\sube\set{\varnothing}$ ，又集 $\set{\varnothing,\set{\varnothing}}$ 含有两个元素。

集合的基本运算

在任一数学系统中，总要引入若干种运算。引入运算的目的不仅在于由已知集合通过运算可以得新的集合，而且由于引入的运算往往服从某些熟知的规则，从而又能简化所得到的公式,而且在很多场合下，往往能简化科学结论的逻辑结构。本节介绍集合的并、交、差、对称差、补运算，并证明它们满足某些运算规律。

并运算

并集的定义

定义6（并集）：设 $A,B$ 是两个集合,至少属于集合 $A$ 与集合 $B$ 之一的那些元素构成的集合称为 $A$ 与 $B$ 的并集，并记为 $A \cup B$ 。符号 $\cup$ 称为并运算符。于是

$$\begin{aligned} A \cup B = \set{x|x \in A 或 x \in B} \tag{22}\end{aligned}$$

例7：设 $A=\set{a,b,c,d},B=\set{b,d,e,f}$，则 $A \cup B=\set{a,b,c,d,e,f}$ 。注意在本例中，$b$ 和 $d$ 既是 $A$ 的元素又是 $B$ 的元素，在 $A \cup B$ 中，$b$ 和 $d$ 各写一次，不能重写，因为 $A \cup B$ 是由互不相同的元素组成的。

例8：设 $A=\set{1,3,5,\cdots},B=\set{2,4,6,\cdots}$ ，则 $A \cup B = \set{1,2,3,4,5,6,\cdots}=N$ 。

对于 $x \in A \cup B$ ，我们可以根据定义写成

$$\begin{aligned} x \in A 或 x \in B \tag{23}\end{aligned}$$

但是对于 $x \notin A \cup B$ ，实际上我们得到的是

$$\begin{aligned} x \notin A 且 x \notin B \tag{24}\end{aligned}$$

的结论。

并运算的性质

并运算有下面的一些性质。

定理2：设 $A,B,C$ 为任意的三个集合，则

(1) 交换律成立。即

$$\begin{aligned} A \cup B = B \cup A \tag{25}\end{aligned}$$

(2) 结合律成立。即

$$\begin{aligned} (A \cup B ) \cup C = A \cup (B \cup C) \tag{26}\end{aligned}$$

(3) 幂等律成立。即

$$\begin{aligned} A \cup A = A \tag{27}\end{aligned}$$

(4)

$$\begin{aligned} \varnothing \cup A = A \tag{28}\end{aligned}$$

(5)

$$\begin{aligned} A \cup B = B \Harr A \sube B \tag{29}\end{aligned}$$

(6)

$$\begin{aligned} A \sube A \cup B,\quad B \sube A \cup B \tag{30}\end{aligned}$$

(7)

$$\begin{aligned} 若 A \cup B \sube C，则 A \sube C,B \sube C \tag{31}\end{aligned}$$

(8)

$$\begin{aligned} 若A \sube C,B \sube C，则A \cup B \sube C \tag{32}\end{aligned}$$

〔证明(定理2)〕
(1) 由(22)可得 $A \cup B = \set{x|x \in A 或 x \in B}$，而$B \cup A = \set{x|x \in B 或 x \in A} = \set{x|x \in A 或 x \in B}$ ，故 $A \cup B = B \cup A$ 。
(2) 设 $x \in (A \cup B) \cup C$ ，则有 $x \in A \cup B$ 或 $x \in C$ 。若 $x \in A \cup B$ ，则又有 $x \in A$ 或 $x \in B$ ，由定义知 $B \sube B \cup C$ ，因此对 $x$ 有 $x \in A$ 或 $x \in B \cup C$ ，即 $x \in A \cup (B \cup C)$ 。若 $x \in C$ ，由定义知 $C \sube B \cup C$ ，则 $x \in B \cup C$ ，又由定义知 $B \cup C \sube A \cup (B \cup C)$ ，因此 $x \in A \cup (B \cup C)$ 。于是不论怎样，$x \in A \cup (B \cup C)$ ，因此 $(A \cup B) \cup C \sube A \cup (B \cup C)$ 。
反之，设 $x \in A \cup (B \cup C)$ ，则由定义知 $x \in A$ 或 $x \in B \cup C$ 。若 $x \in A$ ，由定义知 $A \sube A \cup B \sube (A \cup B) \cup C$ ，故 $x \in (A \cup B) \cup C$ 。若 $x \in B \cup C$ ，则 $x \in B$ 或 $x \in C$ ，又由定义知 $B \sube A \cup B$ ，故 $x \in A \cup B$ 或 $x \in C$ ，即 $x \in (A \cup B) \cup C$ 。于是不论怎样，$x \in (A \cup B) \cup C$ ，因此 $A \cup (B \cup C) \sube (A \cup B) \cup C$ 。
综上所述，由定义3可知，$A \cup (B \cup C) = (A \cup B) \cup C$ 。
(3) 由(15)知 $A \sube A$ ，因此由(5)可知 $A \cup A = A$ 。
(4) 由定理1可知 $\varnothing \sube A$ 。因此由(5)可知 $\varnothing \cup A = A$ 。
(5) 设 $A \cup B = B$ ，任取 $x \in A$ ，由(1)可知 $A \sube A \cup B$ ，则 $x \in A \cup B = B$ ，即 $x \in B$ ，故 $A \sube B$ 。反过来，设 $A \sube B$ 。对任意 $x \in A \cup B$ ，即 $x \in A$ 或 $x \in B$ 。如果 $x \in A$ ，则由 $A \sube B$ 可得 $x \in B$ 。所以不管怎样都有 $x \in B$ ，所以 $A \cup B \sube B$ 。而由(1)可得 $B \sube A \cup B$ 。由定义3可知 $A \cup B = B$ 。
(6) 可直接由并集的定义得出。
(7) 若 $A \cup B \sube C$ ，则对任意 $x \in A \cup B$ ，$x \in C$ 。而由 $x \in A \cup B$ 和并集的定义可得 $x \in A$ 或 $x \in B$ ，故对任意 $x \in A, x \in B$ 都有 $x \in C$ ，即 $A \sube C,B \sube C$ 。
(8) 设 $A \sube C,B \sube C$ 。对任意 $x \in A \cup B$ ，有 $x \in A$ 或 $x \in B$ 。若 $x \in A$ ，由 $A \sube C$ 可知 $x \in C$ 。若 $x \in B$ ，由 $B \sube C$ 可知 $x \in C$ 。总之 $x \in C$ 。所以 $A \cup B \sube C$ 。

证毕

接下来是一些常用结论。

命题1：对集合 $A,B,C,D$ ，若 $A \sube C, B \sube D$ ，则有 $A \cup B \sube C \cup D$ 。

〔证明(命题1)〕对任意 $x \in A \cup B$ ，有 $x \in A$ 或 $x \in B$ 。由 $A \sube C$ 有 $x \in C$ ；由 $B \sube D$ 有 $x \in D$ 。故 $x \in C$ 或 $x \in D$ ，即 $x \in C \cup D$ 。因此，$A \cup B \sube C \cup D$ 。

证毕

无穷并集

由(26)，$(A \cup B) \cup C = A \cup (B \cup C)$ ，因此 $A \cup B \cup C$ 有意义。类似地，我们可以定义多个集合 $A_1,A_2,\cdots,A_n$ 的并集 $A_1 \cup A_2 \cup \cdots \cup A_n$ 为至少属于 $A_1,A_2,\cdots,A_n$ 中之一的那些元素构成的集合。$A_1 \cup A_2 \cup \cdots \cup A_n$ 常缩写成 $\displaystyle\bigcup_{i=1}^{n}A_i$ 。
若 $A_1,A_2,\cdots,A_n,\cdots$ 是一个无穷集合的无穷序列，则它们的并集记为 $A_1 \cup A_2 \cup \cdots \cup A_n \cup \cdots$ ，常缩写为 $\displaystyle\bigcup_{i=1}^{\infin}A_n$ ，其定义为

$$\begin{aligned} A_1 \cup A_2 \cup \cdots \cup A_n \cup \cdots = \bigcup_{i=1}^{\infin}A_n = \set{x | \exist\space n \in N 使得 x \in A_n} \tag{33}\end{aligned}$$

其中 $N$ 是自然数之集。
一般地，若 $\set{A_l}_{l \in I}$ 是任一集族，则集族中那些集之并集记为 $\displaystyle\bigcup_{l \in I}A_l$ ，并且

$$\begin{aligned} \bigcup_{l \in I}A_l=\set{x | \exist \space l \in I 使得 x \in A_l} \tag{34}\end{aligned}$$

交运算

集合的并运算，就是把给定集的那些元素放到一起合并成一个集合，在这个合并中，相同的元素只要一个。集合的另一个运算是交运算，它是由给定的集合的公共元素构成的集合。形式上，我们有如下的定义。

交集的定义

定义7（交集）：设 $A$ 和 $B$ 是任意的两个集合，由既属于 $A$ 又属于 $B$ 的一切元素构成的集合称为 $A$ 与 $B$ 的交集，并记为 $A \cap B$ 。
于是

$$\begin{aligned} A \cap B = \set{x|x \in A 且 x \in B} \tag{35}\end{aligned}$$

例9：设 $A=\set{a,b,c,d,e},B=\set{a,c,e,f}$ ，则 $A \cap B = \set{a,c,e}$ 。

例10： $A$ 为所有蓝眼睛的男人之集，$B$ 为所有棕色头发男人之集，则 $A \cap B$ 就是一切蓝眼睛棕色头发男人之集。

对于 $x \in A \cap B$ ，我们可以根据定义写成

$$\begin{aligned} x \in A 且 x \in B \tag{36}\end{aligned}$$

但是对于 $x \notin A \cap B$ ，实际上我们得到的是

$$\begin{aligned} x \notin A 或 x \notin B \tag{37}\end{aligned}$$

的结论。

交运算的性质

交运算有以下性质。

定理3：设 $A,B,C$ 是任意三个集合，则

(1) 交换律成立。即

$$\begin{aligned} A \cap B = B \cap A \tag{38}\end{aligned}$$

(2) 结合律成立。即

$$\begin{aligned} (A \cap B) \cap C = A \cap (B \cap C) \tag{39}\end{aligned}$$

(3) 幂等律成立，即

$$\begin{aligned} A \cap A = A \tag{40}\end{aligned}$$

(4)

$$\begin{aligned} \varnothing \cap A = \varnothing \tag{41}\end{aligned}$$

(5)

$$\begin{aligned} A \cap B = A \Harr A \sube B \tag{42}\end{aligned}$$

(6)

$$\begin{aligned} A \cap B \sube A,\quad A \cap B \sube B \tag{43}\end{aligned}$$

(7)

$$\begin{aligned} 若 C \sube A \cap B，则 C \sube A,C \sube B \tag{44}\end{aligned}$$

(8)

$$\begin{aligned} 若A \sube C,B \sube C，则A \cap B \sube C \tag{45}\end{aligned}$$

〔证明(定理3)〕
(1) 由(35)可得 $A \cap B = \set{x|x \in A 且 x \in B}$，而$B \cap A = \set{x|x \in B 且 x \in A} = \set{x|x \in A 且 x \in B}$ ，故 $A \cap B = B \cap A$ 。
(2) 设 $x \in (A \cap B) \cap C$ ，则有 $x \in A \cap B$ 且 $x \in C$ 。而由 $x \in A \cap B$ ，又有 $x \in A$ 且 $x \in B$ ，即 $x \in A$ 且 $x \in B$ 且 $x \in C$ ，即 $x \in A$ 且 $x \in B \cap C$ ，即 $x \in A \cap (B \cap C)$ 。由此可得 $(A \cap B) \cap C \sube A \cap (B \cap C)$ 。
反之，设 $x \in A \cap (B \cap C)$ ，则由定义知 $x \in A$ 且 $x \in B \cup C$ 。而由 $x \in B \cup C$ ,又有 $x \in B$ 且 $x \in C$ ，即 $x \in A$ 且 $x \in B$ 且 $x \in C$ ，即 $x \in A \cap B$ 且 $x \in C$ ，即 $x \in (A \cap B) \cap C$ 。由此可得 $A \cap (B \cap C) \sube (A \cap B) \cap C$ 。
综上所述，由定义3可知，$A \cup (B \cup C) = (A \cup B) \cup C$ 。
(3) 由(15)知 $A \sube A$ ，再由(5)得到 $A \cap A = A$ 。
(4) 由定理1知 $\varnothing \sube A$ 。再由(6)知 $\varnothing \cap A = \varnothing$ 。
(5) 若 $A \cap B = A$ ，任取 $x \in A$ ，由 $A \cap B = A$ 可知 $x \in A \cap B$ 。而由(1)可得 $A \cap B \sube B$ ，故 $x \in B$ ，因此 $A \sube B$ 。反过来，设 $A \sube B$ 。对任意 $x \in A$ ，因为 $A \sube B$ 有 $x \in B$ ，即 $x \in A$ 且 $x \in B$ ，由交集定义可得 $x \in A \cap B$ ，因此 $A \sube A \cap B$ 。又由(1)得 $A \cap B \sube A$ ，因此由定义3可知 $A \cap B = A$ 。
(6) 可直接由交集的定义得到。
(7) 若 $C \sube A \cap B$ ，对任意 $x \in C$ ，有 $x \in A \cap B$ ，即 $x \in A$ 且 $x \in B$ 。因此可得 $C \sube A$ 和 $C \sube B$ 。
(8) 设 $A \sube C,B \sube C$ 。由(6)可得 $A \cap B \sube A$ ，而 $A \sube C$ ，因此 $A \cap B \sube C$ 。

证毕

接下来是一些常用结论。

命题2：对集合 $A,B,C,D$ ，若 $A \sube C, B \sube D$ ，则有 $ A \cap B \sube C \cap D$ 。

〔证明(命题2)〕对任意 $x \in A \cap B$ ，有 $x \in A$ 且 $x \in B$ 。由 $A \sube C$ 有 $x \in C$ ；由 $B \sube D$ 有 $x \in D$ 。故 $x \in C$ 且 $x \in D$ ，即 $x \in C \cap D$ 。因此，$A \cap B \sube C \cap D$ 。

证毕

无穷交集

同样可定义 $n$ 个集合 $A_1,A_2,\cdots,A_n$ 的交集，也可定义集合序列 $A_1,A_2,\cdots,A_n,\cdots$ 的那些集的交集，并分别记为或定义为

$$\begin{aligned} A_1 \cap A_2 \cap \cdots \cap A_n = \bigcap_{i=1}^{n}A_n=\set{x|\forall i \in \set{1,2,\cdots,n},x\in A_i} \tag{46}\end{aligned}$$ $$\begin{aligned} A_1 \cap A_2 \cap \cdots \cap A_n \cap \cdots = \bigcap_{i=1}^{\infin}A_n=\set{x|\forall b \in N,x\in A_n} \tag{47}\end{aligned}$$

更一般地，集族 $\set{A_l}_{l \in I}$ 中各集的交记成 $\displaystyle\bigcap_{l \in I}A_l$ ，其定义为

$$\begin{aligned} \bigcap_{l \in I}A_l=\set{x|\forall \xi \in I, x \in A_\xi} \tag{48}\end{aligned}$$

并运算与交运算的联系

并运算与交运算的分配律

定理2和定理3各性质是并运算与交运算各自的性质。下面的定理表明了并运算与交运算之间的联系。

定理4：设 $A$ 为任一集合，$\set{B_l}_{l \in I}$ 为任一集族，则

$$\begin{aligned} A \cap \left(\bigcup_{l \in I}B_l\right)=\bigcup_{l \in I}\left(A \cap B_l \right) \tag{49}\end{aligned}$$ $$\begin{aligned} A \cup \left(\bigcap_{l \in I}B_l\right)=\bigcap_{l \in I}\left(A \cup B_l \right) \tag{50}\end{aligned}$$

其中 $I \ne \varnothing$ 。

〔证明(定理4)〕先证(49)。令 $\displaystyle S = A \cap \left(\bigcup_{l \in I}B_l\right),T=\bigcup_{l \in I}\left(A \cap B_l \right)$ 。
首先证明 $S \sube T$ 。取任意 $x \in S = \displaystyle A \cap \left(\bigcup_{l \in I}B_l\right)$ ，由交集的定义有 $x \in A$ 且 $x \in \displaystyle\bigcup_{l \in I}B_l$ ，由(34)知存在一个 $\xi_0 \in I$ 使得 $x \in B_{\xi_0}$ 。于是 $x \in A$ 且 $x \in B_{\xi_0}$ 。由交集的定义有 $x \in A \cap B_{\xi_0}$ 。由(30)可得 $x \in \displaystyle\bigcup_{\xi \in I}(A \cap B_\xi)$ ，即 $x \in T$ 。因此，$S \sube T$ 。
其次，我们来证明 $T \sube S$ 。取任意 $x \in T = \displaystyle\bigcup_{l \in I}\left(A \cap B_l \right)$ ，由(34)知必有 $\xi_0 \in I$ 使得 $x \in A \cap B_{\xi_0}$ 。因此由交集的定义有 $x \in A$ 且 $x \in B_{\xi_0}$ 。由(30)可得 $x \in A$ 且 $x \in \left(\displaystyle\bigcup_{\xi \in I}B_\xi\right)$ ，因此由交集的定义有 $x \in A \cap \left(\displaystyle\bigcup_{\xi \in I}B_\xi\right)$ ，即 $T \sube S$ 。
因此由定义3可知 $S=T$ ，即 $\displaystyle A \cap \left(\bigcup_{l \in I}B_l\right)=\bigcup_{l \in I}\left(A \cap B_l \right)$ 。
再证(50)。令 $S=\displaystyle A \cup \left(\bigcap_{l \in I}B_l\right),T=\bigcap_{l \in I}\left(A \cup B_l \right)$ 。
首先证明 $S \sube T$ 。设 $x \in S=\displaystyle A \cup \left(\bigcap_{l \in I}B_l\right)$ ，由并集的定义可得 $x \in A$ 或 $x \in \displaystyle\bigcap_{l \in I}B_l$ 。如果 $x \in A$ ，则由(30)可知对任意 $l$ 都有 $x \in A \cup B_l$ ，即 $x \in \displaystyle\bigcap_{l \in I}\left(A \cup B_l \right)$ 。如果 $x \in \displaystyle\bigcap_{l \in I}B_l$ ，则由(48)可得 $\forall \xi \in I,x \in B_\xi$ ，再由(30)可知 $\forall \xi \in I,x \in A \cup B_\xi$ ，由(48)得 $x \in \displaystyle\bigcap_{l \in I}\left(A \cup B_l \right)$ 。总之不论如何都有 $x \in \displaystyle\bigcap_{l \in I}\left(A \cup B_l \right)$ ，即 $x \in T$ ，因此 $S \sube T$ 。
再证明 $T \sube S$ 。设 $x \in T$ ，由(48)可得 $\forall \xi \in I,x \in A \cup B_\xi$ ，则由并集的定义可得 $\forall \xi \in I$，$x \in A$ 或 $x \in B_\xi$ 。假设 $x \in A$ ，则由(30)可知 $x \in \displaystyle A \cup \left(\bigcap_{l \in I}B_l\right) $ 。假设 $x \in B_\xi$ ，则 $\forall \in I,x \in B_\xi$ ，即 $x \in \displaystyle\bigcap_{l \in I}B_l$ ，由(30)可知 $x \in A \cup \displaystyle\bigcap_{l \in I}B_l$ 。总之，不论如何都有 $x \in A \cup \displaystyle\bigcap_{l \in I}B_l$ ，即 $x \in S$ 。所以 $T \sube S$ 。
综上所述，由定义3可知 $S=T$ ，即 $\displaystyle A \cup \left(\bigcap_{l \in I}B_l\right)=\bigcap_{l \in I}\left(A \cup B_l \right)$ 。

证毕

分配律的简单形式

定理5：设 $A,B,C$ 为任意三个集合，则
(1) 交运算对并运算满足分配律，即

$$\begin{aligned} A \cap (B \cup C) = (A \cap B) \cup (A \cap C) \tag{51}\end{aligned}$$

(2) 并运算对交运算满足分配律，即

$$\begin{aligned} A \cup (B \cap C) = (A \cup B) \cap (A \cup C) \tag{52}\end{aligned}$$

〔证明(定理5)〕这个定理是定理4的一个特例，因此无须证明。

证毕

但是，我们可以证明该定理的结论(1)和结论(2)是可以互推的。我们先从(1)开始证(2)。利用并运算和交运算的交换、结合性质和(51)、(55)和(56)可得

$$\begin{aligned} (A \cup B) \cap (A \cup C)=&(A \cup C) \cap (A \cup B) \\[5pt] =&((A \cup C) \cap A) \cup ((A \cup C) \cap B)\text{（(51)）}\\[5pt] =&(A \cap (A \cup C)) \cup (B \cap (A \cup C))\text{（交换律）}\\[5pt] =& A \cup (B \cap (A \cup C))\text{（(55)）}\\[5pt] =& A \cup ((B \cap A) \cup (B \cap C))\text{（(51)）}\\[5pt] =& (A \cup (B \cap A)) \cup (B \cap C)\text{（结合律）}\\[5pt] =& (A \cup (A \cap B)) \cup (B \cap C)\text{（交换律）}\\[5pt] =& A \cup (B \cap C)\text{（(56)）} \tag{53}\end{aligned}$$

我们再来从(2)推导(1)。利用并运算和交运算的交换、结合性质和(52)、(55)和(56)可得

$$\begin{aligned} (A \cap B) \cup (A \cap C)=&(A \cap C) \cup (A \cap B)\\[5pt] =&((A \cap C) \cup A)\cap((A \cap C) \cup B)\text{（(52)）}\\[5pt] =&(A \cup (A \cap C)) \cap (B \cup (A \cap C)) \text{（交换律）}\\[5pt] =&A \cap (B \cup (A \cap C))\text{（(56)）}\\[5pt] =&A \cap ((B \cup A) \cap (B \cup C))\text{（(52)）}\\[5pt] =&(A \cap (B \cup A))\cap(B \cup C) \text{（结合律）}\\[5pt] =&A \cap (B \cup C)\text{（(55)）} \tag{54}\end{aligned}$$

吸收律

定理6：对任何集 $A,B$ ，吸收律成立：
(1)

$$\begin{aligned} A \cap (A \cup B) = A \tag{55}\end{aligned}$$

(2)

$$\begin{aligned} A \cup (A \cap B) = A \tag{56}\end{aligned}$$

〔证明(定理6)〕由(30)可得 $A \sube A \cup B$ ，又由(42)可得 $A \cap (A \cup B) = A$ 。同理，由(43)可得 $A \cap B \sube A$ ，又由(29)可得 $(A \cap B) \cup A = A \cup (A \cap B) = A$ 。

证毕

两两不相交的集序列

定义8：设 $A,B$ 为任意集合，如果 $A \cap B = \varnothing$ ，则称 $A$ 与 $B$ 不相交。若集序列 $A_1,A_2,\cdots,A_n,\cdots$ 的任两集 $A_i$ 和 $A_j$ （ $i \ne j$ ）不相交，则称 $A_1,A_2,\cdots,A_n,\cdots$ 是两两不相交的集序列。

差运算

差集的定义

定义9（差集）：设 $A$ 与 $B$ 为任意集合，由属于 $A$ 但不属于 $B$ 的一切元素构成的集合称为 $A$ 与 $B$ 的差集，并记为 $A\backslash B$ 。于是

$$\begin{aligned} A \backslash B = \set{x | x \in A 且 x \notin B} \tag{57}\end{aligned}$$

例11：设 $A=\set{1,2,3,4,5},B=\set{3,4,5,6}$ ，则 $A \backslash B = \set{1,2}$ 。

对任意 $x \in A \backslash B$ ，可以写成

$$\begin{aligned} x \in A 且 x \notin B \tag{58}\end{aligned}$$

对于 $x \notin A \backslash B$ ，则写成

$$\begin{aligned} x \notin A 或 x \in B \tag{59}\end{aligned}$$

差运算的性质

差运算有以下性质。

定理7：设 $A,B,C$ 是任意三个集合，则

(1)

$$\begin{aligned} A \backslash A = \varnothing \tag{60}\end{aligned}$$

(2)

$$\begin{aligned} A \backslash \varnothing = A \tag{61}\end{aligned}$$

(3)

$$\begin{aligned} \varnothing \backslash A = \varnothing \tag{62}\end{aligned}$$

(4)

$$\begin{aligned} A \backslash B \sube A \tag{63}\end{aligned}$$

(5)

$$\begin{aligned} 若A \sube B，则 A \backslash C \sube B \backslash C \tag{64}\end{aligned}$$

(5)

$$\begin{aligned} 若 B \sube C，则 A \backslash B \supe A \backslash C \tag{65}\end{aligned}$$

〔证明(定理7)〕
(1) 如果 $A \backslash A$ 不为空，假设 $x \in A \backslash A$ ，则 $x \in A$ 且 $x \notin A$ ，这种元素是不存在的，因此 $A \backslash A$ 中不能有元素，即为空集。
(2) 由空集的定义，$A \backslash \varnothing = \set{x | x \in A 且 x \notin \varnothing}= \set{x | x \in A} = A$ 。
(3) 不存在 $x$ 满足 $x \in \varnothing$ ，因此 $\varnothing \backslash A = \set{x | x \in \varnothing 且 x \in A}$ 没有元素，即为空集。
(4) 由定义知对任意 $x \in A \backslash B$ 都有 $x \in A$ 且 $x \in B$ ，即都有 $x \in A$ ，所以 $A \backslash B \sube A$ 。
(5)设 $x \in A \backslash C$ ，则 $x \in A$ 且 $x \notin C$ 。由于 $A \sube B$ ，则有 $x \in B$ 且 $x \notin C$ ，即 $x \in B \backslash C$ 。因此，$A \backslash B \sube A \backslash C$ 。
(6)设 $x \in A \backslash C$ ，则 $x \in A$ 且 $x \notin C$ 。由于 $B \sube C$ ，则 $x \notin B$ 。因此，$x \in A$ 且 $x \notin B$ ，即 $x \in A \backslash B$ 。因此，$A \backslash B \supe A \backslash C$ 。

证毕

差运算与并运算

定理8：设 $A,B$ 是任意两个集合，则

(1)

$$\begin{aligned} (A \backslash B) \cup B = A \cup B \tag{66}\end{aligned}$$

(2)

$$\begin{aligned} (A \backslash B) \cup B = A \Harr B \sube A \tag{67}\end{aligned}$$

(3)

$$\begin{aligned} A \backslash (B \cup C) = (A \backslash B) \cap (A \backslash C) \tag{68}\end{aligned}$$

(4)

$$\begin{aligned} (A \cup B) \backslash C = (A \backslash C) \cup (B \backslash C) \tag{69}\end{aligned}$$

〔证明(定理8)〕
(1) 设 $x \in (A \backslash B) \cup B$ ，则 $x \in A \backslash B$ 或 $x \in B$ 。如果 $x \in A \backslash B$ ，则由(63)可知 $x \in A$ ，由(30)可知 $A \sube A \cup B$ ，即 $x \in A \cup B$ 。如果 $x \in B$ ，则由(30)可知 $B \sube A \cup B$ ，即 $x \in A \cup B$ 。综上所述，$(A \backslash B) \cup B \sube A \cup B$ 。
另外，假设 $x \in A \cup B$ ，则 $x \in A$ 或 $x \in B$ 。假设 $x \in A$ ，此时又分为两种情况： $x \in B$ 或 $x \notin B$ 。如果 $x \in A$ 且 $x \in B$ ，由(30)可知 $B \sube (A \backslash B) \cup B$ ，即 $x \in (A \backslash B) \cup B$ 。如果 $x \in A$ 且 $x \notin B$ ，由差集的定义得 $x \in A \backslash B$ ，又由(30)得 $A \backslash B \sube (A \backslash B) \cup B$ ，即 $x \in (A \backslash B) \cup B$ 。所以当 $x \in A$ 时总有 $x \in (A \backslash B) \cup B$ 。当 $x \in B$ 时，由(30)可知 $B \sube (A \backslash B) \cup B$ ，即 $x \in (A \backslash B) \cup B$ 。总之，$x \in A \cup B$ 时 $x \in (A \backslash B) \cup B$ ，即 $A \cup B \sube (A \backslash B) \cup B$ 。
因此由定义3可知 $(A \backslash B) \cup B = A \cup B$ 。
(2) 先假设 $(A \backslash B) \cup B = A$ 。由(31)可直接得 $B \sube A$ 。再假设 $B \sube A$ 。由(63)可得 $A \backslash B \sube A$ 。和 $B \sube A$ 一起由(32)可得 $(A \backslash B) \cup B \sube A$ 。由(66)可得 $(A \backslash B) \cup B = A \cup B$ ，而由 $A \sube A \cup B$ 可得 $A \sube (A \backslash B) \cup B$ 。因此 $(A \backslash B) \cup B = A$ 。因此结论成立。
(3)设 $x \in A \backslash (B \cup C)$ ，则有 $x \in A$ 且 $x \notin B \cup C$ ，由(24)可知此时 $x \in A$ 且 $x \notin B$ 且 $x \notin C$ 。也可以写成 $x \in A$ 且 $x \notin B$ ，并且 $x \in A$ 且 $x \notin C$ ，即 $x \in A \backslash B$ 且 $x \in A \backslash C$ ，即 $x \in (A \backslash B) \cap (A \backslash C)$ 。因此，$A \backslash (B \cup C) \sube (A \backslash B) \cap (A \backslash C)$ 。
反之，设 $x \in (A \backslash B) \cap (A \backslash C)$ ，有 $x \in A \backslash B$ 且 $x \in A \backslash C$ ，即 $x \in A $ 且 $x \notin B$ ，并且 $x \in A$ 且 $x \notin C$ ，即 $x \in A$ ，并且 $x \notin B$ 且 $x \notin C$ 。由(24)可知此时 $x \in A$ 且 $x \notin (B \cup C)$ ，即 $x \in A \backslash (B \cup C)$ ，因此 $(A \backslash B) \cap (A \backslash C) \sube A \backslash (B \cup C)$ 。
综上所述，$A \backslash (B \cup C) = (A \backslash B) \cap (A \backslash C)$ 。
(4)设 $x \in (A \cup B) \backslash C$ ，则 $x \in A \cup B$ 且 $x \notin C$ ，即 $x \in A,x \notin C$ 或 $x \in B, x \notin C$ 。即 $x \in A \backslash C$ 或 $x \in B \backslash C$ ，即 $x \in (A \backslash C) \cup (B \backslash C)$ 。因此，$(A \cup B) \backslash C \sube (A \backslash C) \cup (B \backslash C)$ 。同理，设 $x \in (A \backslash C) \cup (B \backslash C)$ ，则 $x \in A \backslash C$ 或 $x \in B \backslash C$ ，也就是 $x \in A$ 且 $x \notin C$ ，或 $x \in B$ 且 $x \notin C$ ，相当于 $x \in A$ 或者 $x \in B$ 的同时 $x \notin C$ 。即 $x \in A \cup B$ 且 $x \notin C$ ，即 $x \in (A \cup B) \backslash C$ 。因此，$(A \backslash C) \cup (B \backslash C) \sube (A \cup B) \backslash C$ 。综上所述，$(A \cup B) \backslash C = (A \backslash C) \cup (B \backslash C)$ 。

证毕

差运算与交运算

定理9：设 $A,B,C$ 为任意三个集合，则

(1)

$$\begin{aligned} A \cap (B \backslash C)=(A \cap B) \backslash (A \cap C) \tag{70}\end{aligned}$$

该式称为交运算对差运算满足分配律。

(2)

$$\begin{aligned} (A \cap B) \backslash C = (A \backslash C) \cap (B \backslash C) \tag{71}\end{aligned}$$

(3)

$$\begin{aligned} A \backslash (B \cap C) = (A \backslash B) \cup (A \backslash C) \tag{72}\end{aligned}$$

〔证明(定理9)〕
(1)设 $x \in A \cap (B \backslash C)$ ，则 $x \in A$ 且 $x \in B \backslash C$ ，即 $x \in B$ 且 $x \notin C$ ，考虑 $x \in A$ 重复两次（在全是并运算的表达式中，由并运算的交换律和结合律可知可以这么做）即可得到 $x \in A$ 且 $x \in B$ 且 $x \in A$ 且 $x \notin C$ ，即 $x \in A \cap B$ 且 $x \notin A \cap C$ 。所以由差运算的定义，$x \in (A \cap B) \backslash (A \cap C)$ ，从而 $A \cap (B \backslash C) \sube (A \cap B) \backslash (A \cap C)$ 。
反之，设 $x \in (A \cap B) \backslash (A \cap C)$ 。则 $x \in A \cap B $ 且 $x \notin A \cap C$ 。因此，$x \in A$ 且 $x \in B$ 且 $x \notin A \cap C$ 。而 $x \notin A \cap C$ 等价于 $x \notin A$ 或 $x \notin C$ （见(24)），但是注意有条件 $x \in A$ ，因此 $x \notin A \cap C$ 等价于 $x \notin C$ 。即 $x \in A$ 且 $x \in B$ 且 $x \notin C$ 。即 $x \in A$ 且 $x \in B \backslash C$ 。$x \in A \cap (B \backslash C)$ 。于是有 $(A \cap B) \backslash (A \cap C) \sube A \cap (B \backslash C)$ 。
综上，由定义3，$A \cap (B \backslash C) = (A \cap B) \backslash (A \cap C)$ 。
(2)设 $x \in (A \cap B) \backslash C$ ，即 $x \in A \cap B$ 且 $x \notin C$ ，即 $x \in A$ 且 $x \in B$ 且 $x \notin C$ 。也可以写成 $x \in A$ 且 $x \notin C$ ，并且 $x \in B$ 且 $x \notin C$ ，即 $x \in A \backslash C$ 且 $x \in B \backslash C$ ，即 $x \in (A \backslash C) \cap (B \backslash C)$ 。因此，$(A \cap B) \backslash C \sube (A \backslash C) \cap (B \backslash C)$ 。
再设 $x \in (A \backslash C) \cap (B \backslash C)$ ，则有 $x \in A \backslash C$ 并且 $x \in B \backslash C$ 。即 $x \in A$ 且 $x \notin C$ ，并且 $x \in B$ 且 $x \notin C$ 。也可以写成 $x \in A$ 且 $x \in B$ ，并且 $x \notin C$ 。即 $x \in A \cap B$ 且 $x \notin C$ ，即 $x \in (A \cap B) \backslash C$ 。因此，$(A \backslash C) \cap (B \backslash C) \sube (A \cap B) \backslash C$ 。
综上所述，$(A \cap B) \backslash C = (A \backslash C) \cap (B \backslash C)$ 。
(3) 设 $x \in A \backslash (B \cap C)$ ，有 $x \in A$ 且 $x \notin B \cap C$ ，由(24)可知此时有 $x \in A$ 且 $x \notin B$ 或者 $x \in A$ 且 $x \notin C$ ，即 $x \in A \backslash B$ 或 $x \in A \backslash C$ ，即 $x \in (A \backslash B) \cup (A \backslash C)$ 。因此有 $A \backslash (B \cap C) \sube (A \backslash B) \cup (A \backslash C)$ 。反之，设 $x \in (A \backslash B) \cup (A \backslash C)$ ，有 $x \in A \backslash B$ 或者 $x \in A \backslash C$ ，即 $x \in A$ 且 $x \notin B$ 或者 $x \in A$ 且 $x \notin C$ 。总的来说，$x \in A$ ，并且 $x \notin B$ 或者 $x \notin C$ 。即 $x \in A$ 且 $x \notin B \cap C$ ，即 $x \in A \backslash (B \cap C)$ 。即 $(A \backslash B) \cup (A \backslash C) \sube A \backslash (B \cap C)$ 。综上 $A \backslash B) \cup (A \backslash C) = A \backslash (B \cap C)$ 。

证毕

例12： $A,B$ 为例11中的 $A,B$ ，则

$$\begin{aligned} B \backslash A = \set{6} \ne A \backslash B \tag{73}\end{aligned}$$

这表明差运算不满足交换律。若令 $C=\set{3,4}$ ，则 $(A \backslash B) \backslash C = \set{1,2} \backslash C = \set{1,2}$ ，而 $A \backslash (B \backslash C) = A \backslash \set{5,6} = \set{1,2,3,4}$ 。于是 $(A \backslash B) \backslash C \ne A \backslash (B \backslash C)$ 。这表明差运算也不满足结合律。

对称差

对称差的定义

定义10：设 $A$ 与 $B$ 为任两个集合，$A \backslash B$ 与 $B \backslash A$ 的并集称为 $A$ 与 $B$ 的对称差，记为 $A \triangle B$ 。于是

$$\begin{aligned} A \triangle B = (A \backslash B) \cup (B \backslash A) = \set{x | (x \in A 且x \notin B)或(x \in B且x \notin A)} \tag{74}\end{aligned}$$

对 $x \in A \triangle B$ ，可以写成

$$\begin{aligned} 若 x \in A \triangle B，则x \in A,x \notin B或x \in B, x \notin A \tag{75}\end{aligned}$$

对 $x \notin A \triangle B$ ，则要么 $x \in A, x \in B$ ，要么 $x \notin A,x \notin B$ 。因为一共就四种情况： $x \in A, x \in B$ ； $x \in A, x \notin B$ ； $x \notin A, x \in B$ ； $x \notin A, x \notin B$ 。因此可以写成

$$\begin{aligned} 若 x \notin A \triangle B，则x \in A, x \in B 或 x \notin A, x \notin B \tag{76}\end{aligned}$$

对称差的性质

对称差运算有如下性质。

定理10：设 $A,B,C$ 为任意三个集合，则

(1)

$$\begin{aligned} A \triangle B = B \triangle A \tag{77}\end{aligned}$$

(2)

$$\begin{aligned} (A \triangle B) \triangle C = A \triangle (B \triangle C) \tag{78}\end{aligned}$$

(3)

$$\begin{aligned} A \triangle A = \varnothing \tag{79}\end{aligned}$$

(4)

$$\begin{aligned} A \triangle \varnothing = A \tag{80}\end{aligned}$$

〔证明(定理10)〕
(1) $A \triangle B = (A \backslash B) \cup (B \backslash A)$ ，由并运算的交换律(25)可得 $B \triangle A = (B \backslash A) \cup (A \backslash B)=(A \backslash B) \cup (B \backslash A)=A \triangle B$ 。
(2) 对任意 $x \in (A \triangle B) \triangle C$ ，由(75)知 $x \in A \triangle B, x \notin C$ 或 $x \notin A \triangle B, x \in C$ 。先看第一种可能 $x \in A \triangle B, x \notin C$ ，由(75)知此时又可分为 $x \in A, x \notin B, x \notin C$ 和 $x \notin A, x \in B, x \notin C$ 两种情况。再看第二种可能 $x \notin A \triangle B, x \in C$ ，由(76)知此时还有两种情况 $x \notin A,x \notin B, x \in C$ 和 $x \in A,x \in B,x \in C$ 。综上所述，$x \in (A \triangle B) \triangle C$ 一共有四种情况，分别是

$$\begin{aligned} x \in A, x \notin B, x \notin C \\[5pt] x \notin A, x \in B, x \notin C \\[5pt] x \notin A, x \notin B, x \in C \\[5pt] x \in A,x \in B,x \in C \tag{81}\end{aligned}$$

再来看 $A \triangle (B \triangle C)$ 。对任意 $ x \in A \triangle (B \triangle C)$ ，由(75)知 $x \in A, x \notin B \triangle C$ 或 $x \notin A, x \in B \triangle C$ 。先看第一种可能 $x \in A, x \notin B \triangle C$ ，由(76)知此时又可分为 $x \in A, x \in B, x \in C$ 和 $x \in A, x \notin B, x \notin C$ 两种情况。再看第二种可能 $x \notin A, x \in B \triangle C$ ，由(75)知此时还有两种情况 $x \notin A, x \in B, x \notin C$ 和 $x \notin A, x \notin B, x \in C$ 。综上所述，$A \triangle (B \triangle C)$ 一共有四种情况，分别是

$$\begin{aligned} x \in A, x \in B, x \in C \\[5pt] x \in A, x \notin B, x \notin C \\[5pt] x \notin A, x \in B, x \notin C \\[5pt] x \notin A, x \notin B, x \in C \tag{82}\end{aligned}$$

我们发现(81)和 (82)是完全一样的，因此证明了 $(A \triangle B) \triangle C = A \triangle (B \triangle C)$ 。
(3) 由(60)可知 $A \backslash A = \varnothing$ 。因此，$A \triangle A = (A \backslash A) \cup (A \backslash A) = \varnothing \cup \varnothing =\varnothing$ 。
(4) 由(61)、(62)和(28)可推导出 $A \triangle \varnothing = (A \backslash \varnothing) \cup ( \varnothing \backslash A) = A \cup \varnothing \ = A$ 。

证毕

对称差与交运算

定理11：交运算关于对称差满足分配律，即

$$\begin{aligned} A \cap (B \triangle C) = (A \cap B) \triangle (A \cap C) \tag{83}\end{aligned}$$

〔证明(定理11)〕由(51)、(70)和(74)得

$$\begin{aligned} A \cap (B \triangle C) =& A \cap ((B \backslash C) \cup (C \backslash B))\quad\text{（(74)）}\\[5pt] =& (A \cap (B \backslash C)) \cup (A \cap (C \backslash B))\quad\text{（(51)）}\\[5pt] =&((A \cap B) \backslash (A \cap C)) \cup ((A \cap C) \backslash (A \cap B))\quad\text{（(70)）}\\[5pt] =&(A \cap B) \triangle (A \cap C)\quad\text{（(74)）} \tag{84}\end{aligned}$$

证毕

Venn图

在许多实际问题中，常以某个集合 $S$ 为出发点，而所涉及的集合都是 $S$ 的子集。这个包含所考虑的所有集的集合 $S$ ，称为该问题的全集。这时，常用图示法的方法表示全集的各子集间的包含关系，以及并集、交集、差集和对称差集。在这种图示法中，用矩形中各点表示全集 $S$ 的各个元素，矩形中的圆里的各点表示 $S$ 的子集的各元素。于是，若 $A,B \sube S$ ，则 $A \cup B,A\cap B, A \backslash B, A \triangle B, A \sube B$ 可用下图表示，称为Venn图表示。

图1 Venn图

余集、De Morgan公式

余集

余集的定义

定义11：设 $S$ 是一个集合，$A \sube S$ ，差集 $S \backslash A$ 称为集 $A$ 对集 $S$ 的余集，记为 $A^c$ ，即 $A^c=S \backslash A$ 。

在数学的文献中，余集也称为补集，并且记号也未统一。有的作者用 $\complement_SA$ 表示 $A$ 对 $S$ 的余集，其优点是明确地指出是相对于 $S$ 求 $A$ 的余集，但不简洁。还有些作者使用 $\bar{A}$ 、 $A'$ 表示 $A$ 的余集。记号 $A^c,\bar{A},A'$ 的优点在于其简洁性，便于在公式中书写。但由于余集的概念是相对于某个集合而言，记号 $A^c,\bar{A},A'$ 没有指明对哪个集求余集。然而，在具体问题中所考虑的集合 $A$ 都是某个集 $S$ 的子集，根据上下文，$A$ 对哪个集求余集是清楚的。于是，记号 $A^c,\bar{A},A'$ 的简洁性优点便突出来。因此，本文使用记号 $A^c$ 表示 $A$ 的余集，其中的 $c$ 为 $\text{complement}$ 的第一个字母。在易发生误会时就用 $\complement_SA$ 注明。
集 $A$ 对 $S$ 的余集用Venn图表示时如图所示。

图2 $A$ 的余集的Venn图表示

例13：设 $S=\set{1,2,3,4}$ ，$A = \set{2,4}$ ，则 $A^c = \set{1,3}$ 。可是 $A$ 对自然数集 $N$ 求余集时 $\complement_NA=\set{1,3,5,6,7,\cdots}$ 。

余集的性质

余集具有以下性质。

定理12：设 $S$ 是任一集合，$A$ 是 $S$ 的子集，则有

(1) $S$ 对 $S$ 的余集为空集，即

$$\begin{aligned} \complement_SS=S^c=\varnothing \tag{85}\end{aligned}$$

(2)

$$\begin{aligned} \varnothing^c=S(\complement_\varnothing=S) \tag{86}\end{aligned}$$

(3)

$$\begin{aligned} A \cap A^c = \varnothing，即\complement_SA\cap A = \varnothing \tag{87}\end{aligned}$$

(4)

$$\begin{aligned} A \cup A^c = S，即 A \cup \complement_SA=S \tag{88}\end{aligned}$$

(5)

$$\begin{aligned} (A^c)^c=A \tag{89}\end{aligned}$$

〔证明(定理12)〕
(1) 由(60)可得 $S^c=S \backslash S = \varnothing$ 。
(2) 由(61)可得 $\varnothing^c=S \backslash \varnothing = S$ 。
(3) 由(70)、 $A \sube S$ 、 (42)和(40)可得 $A \cap A^c = A \cap ( S \backslash A)=(A \cap S) \backslash (A \cap A) = A \backslash A = \varnothing$ 。
(4) 由(66)、 $A \sube S$ 、(29)可得 $A \cup A^c = A \cup (S \backslash A) = (S \backslash A) \cup A = S \cup A = S$ 。
(5) 设 $x \in (A^c)^c$ ，由定义有 $x \in S \backslash A^c$ ，即 $x \in S$ 且 $x \notin A^c$ 。而对 $x \in A^c$ 有 $A^c = S \backslash A$ ,因此 $x \notin S \backslash A$ ，由(59)可得 $x \notin S 或 x \in A$ 。注意前面已经有了 $x \in S$ 的条件，因此只能有 $x \in A$ ，因此 $x \in S \cup A$ 。又 $A \sube S$ ，因此由(29)可得 $x \in A$ 。

证毕

De Morgan公式

定理13（De Morgan公式）：设 $S$ 为任一集合，$I$ 为标号集，$\forall\xi\in I$ 有 $A_\xi \sube S$ ，则有

(1) 并集的余集等于各余集的交集，即

$$\begin{aligned} \left(\bigcup_{\xi \in I}A_\xi\right)^c=\bigcap_{\xi \in I}A_\xi^c \tag{90}\end{aligned}$$

(2) 交集的余集等于各余集的并集，即

$$\begin{aligned} \left(\bigcap_{\xi \in I}A_\xi\right)^c=\bigcup_{\xi in I}A_\xi^c \tag{91}\end{aligned}$$

〔证明(De Morgan公式)〕
(1) 设 $x \in \displaystyle\left(\bigcup_{\xi \in I}A_\xi\right)^c$ ，则 $x \in S$ 且 $x \notin \displaystyle\bigcup_{\xi \in I}A_\xi$ ，从而 $\forall\xi\in I,x \notin A_\xi$ 。于是，$\forall\xi\in I,x \in A_\xi^c$ 。因此，$x \in \displaystyle\bigcap_{\xi \in I}A_\xi^c$ ，故 $\displaystyle\left(\bigcup_{\xi \in I}A_\xi\right)^c \sube \bigcap_{\xi \in I}A_\xi^c$ 。
其次，设 $x \in \displaystyle\bigcap_{\xi \in I}A_\xi^c$ ，则 $\forall \xi \in I$ 都有 $x \in A_\xi^c$ 。因此，$\forall \xi \in I$ 都有 $x \notin A_\xi$ ，且 $x \in S$ ，故 $x \notin \displaystyle\bigcup_{\xi \in I}A_\xi$ 。于是，$x \in \displaystyle\left(\bigcup_{\xi \in I}A_\xi\right)^c$ 。所以，$\displaystyle\bigcap_{\xi \in I}A_\xi^c \sube \left(\bigcup_{\xi \in I}A_\xi\right)^c$ 。
由定义3可得 $\displaystyle\left(\bigcup_{\xi \in I}A_\xi\right)^c=\bigcap_{\xi \in I}A_\xi^c$ 。
(2) 设 $x \in \displaystyle\left(\bigcap_{\xi \in I}A_\xi\right)^c$ ，则 $x \in S$ 且 $x \notin \displaystyle\bigcap_{\xi \in I}A_\xi$ ，从而 $\exist\xi\in I,x \notin A_\xi$ 。于是，$\exist\xi\in I,x \in A_\xi^c$ 。因此，$x \in \displaystyle\bigcup_{\xi \in I}A_\xi^c$ ，故 $\displaystyle\left(\bigcap_{\xi \in I}A_\xi\right)^c \sube \bigcup_{\xi \in I}A_\xi^c$ 。
其次，设 $x \in \displaystyle\bigcup_{\xi \in I}A_\xi^c$ ，则 $\exist \xi \in I$ 都有 $x \in A_\xi^c$ 。因此，$\exist \xi \in I$ 都有 $x \notin A_\xi$ ，且 $x \in S$ ，故 $x \notin \displaystyle\bigcap_{\xi \in I}A_\xi$ 。于是，$x \in \displaystyle\left(\bigcap_{\xi \in I}A_\xi\right)^c$ 。所以，$\displaystyle\bigcup_{\xi \in I}A_\xi^c \sube \left(\bigcap_{\xi \in I}A_\xi\right)^c$ 。
由定义3可得 $\displaystyle\left(\bigcap_{\xi \in I}A_\xi\right)^c=\bigcup_{\xi \in I}A_\xi^c$ 。

证毕

命题3：De Morgan公式在有限形式下，可以写成

$$\begin{aligned} (A \cup B)^c = A^c \cap B^c \tag{92}\end{aligned}$$ $$\begin{aligned} (A \cap B)^c = A^c \cup B^c \tag{93}\end{aligned}$$

余集、差集与对称差

定理14：设 $A,B$ 都是 $S$ 的子集，则

(1) $$\begin{aligned} A \backslash B = A \cap B^c \tag{94}\end{aligned}$$

(2) $$\begin{aligned} A \triangle B = (A \cap B^c) \cup (B \cap A^c) \tag{95}\end{aligned}$$

(3) $$\begin{aligned} A^c = S \triangle A \tag{96}\end{aligned}$$

〔证明(定理14)〕
(1) $\forall x \in A \backslash B$ ，则 $x \in A$ 且 $x \notin B$ 。由于 $A \sube S$ ，则 $x \in S$ ，因此 $x \in A$ 且 $x \in B^c$ 。即 $x \in A \cap B^c$ 。反过来，$\forall x \in A \cap B^c$ ，有 $x \in A$ 且 $x \in B^c$ 。由于 $A \sube S$ ，则 $x \in S$ 。故有 $x \in A$ 且 $x \notin B$ ，即 $x \in A \backslash B$ 。因此，$A \backslash B = A \cap B^c$ 。
(2) 由(74)和(94)可知

$$\begin{aligned} A \triangle B = (A \backslash B) \cup (B \backslash A) = (A \cap B^c) \cup (B \cap A^c) \tag{97}\end{aligned}$$

(3) 由(95)可得

$$\begin{aligned} S \triangle A = (S \cap A^c) \cup (A \cap S^c) \tag{98}\end{aligned}$$

由(85)可知 $A \cap S^c=A \cap \varnothing = \varnothing$ 。又因为 $A^c \sube S$ ，由(42)可知 $S \cap A^c = A^c$ 。故

$$\begin{aligned} S \triangle A = A^c \cup \varnothing = A^c \tag{99}\end{aligned}$$

证毕

对偶原理

利用De Morgan公式可以证明如下对偶原理。

原理1（对偶原理）：若有关集的并、交及余集运算的某一关系式成立，如果将式中的记号

\[\cup,\cap,\sube,\supe\]

分别换成

\[\cap,\cup,\supe,\sube\]

等号保持不变，并将式中每个集换成它的余集，由此得到的关系式一定成立。

〔证明(对偶原理)〕假设关系式 $P \sube Q$ 成立，$P$ 和 $Q$ 是由并、交及余集运算构成的表达式。$\forall x \in Q^c$ ，有 $x \notin Q$ ，又因为 $P \sube Q$ ，因此 $x \notin P$ ，因此 $x \in P^c$ 。故 $Q^c \sube P^c$ ，即 $P^c \supe Q^c$ 。对 $P^c$ 反复使用De Morgan公式可得 $P^c$ 实际上就是将 $P$ 中的 $\cup$ 换成 $\cap$ ，并将 $\cap$ 换成 $\cup$ ，对 $Q$ 也如此。因此对于 $P \sube Q$ ，对偶原理成立。对于 $P \supe Q$ ，用类似的方法可以证明对偶原理也成立。对于 $P=Q$ ，直接得到 $P^c=Q^c$ ，故对偶原理成立。因此对任意有关集的并、交及余集运算的关系式，对偶原理都成立。

Cartesian乘积

二元组

前面已经讨论了集合的并、交、差、对称差和求余集的运算。这五种运算的共同特点是：如果参加运算的各个集是同一个集的子集，则运算后的结果集仍是这个集的子集。在这里，并、交、差、对称差是二元运算，即参加运算的对象为两个集合，而求余集只要求有一个运算对象，它是一元运算。我们还可把求集 $S$ 的幕集视为一个一元运算，其结果集不再是 $S$ 的子集，而是 $S$ 的所有子集构成的集。本节下面讨论的集合的Cartesian乘积也是一种二元运算，其结果集不再与运算对象集的类型一样。
为了定义Cartesian乘积的概念，需要引入序对或二元组的概念。两个对象 $a$ 和 $b$ （允许 $a=b$ ）按一定的次序排列的整体就叫做一个二元组或序对。如果 $a$ 排在 $b$ 的前面，则这个序对就记为 $(a,b)$ ，$a$ 称为序对 $(a,b)$ 的第一个元素，$b$ 称为第二个元素。注意，序对是由有次序的两个对象组成的，因此序对与含两对象的集合是有区别的。集合 $\set{a,b}$ 的元素间没有次序（先后）关系，$\set{a,b}$ 与 $\set{b,a}$ 是同一个集合。但 $(a,b)$ 与 $(b,a)$ 在 $a \ne b$ 就应视为不相同。因此，我们规定 $(a,b)=(c,d)$ 当且仅当 $a=b$ 且 $c=d$ 这个规定刻划了序对的特征。
上面描述的序对概念是一个直观概念，借助了“次序”这个直观的描述。对我们的今后讨论和应用，这已足够了。不过倒也真是可以应用集论的原始概念把序对定义的集合。

定义12（有序对）：集合 $\set{a,\set{a,b}}$ 称为序对，记为 $(a,b)$ 。于是我们就能证明 $\set{a,\set{a,b}}=\set{c,\set{c,d}}$ 当且仅当 $a=c$ 且 $b=d$ 。于是，这个定义与上面描述的有序对的直观概念有相同的基本性质。

Cartesian乘积的定义

定义13：设 $A$ 与 $B$ 为任意两个集合，则称集合

$$\begin{aligned} \set{(a,b)|a \in A 且 b \in B} \tag{100}\end{aligned}$$

为 $A$ 与 $B$ 的Cartesian乘积，记为 $A \times B$ 。
于是，$A \times B = \set{(a,b)|a \in A 且 b \in B}$ 。

由此定义可知，$A \times B$ 是由一切这样的序对组成的集合：每个序对的第1分量是 $A$ 中的元素，第二分量是 $B$ 中的元素。于是，$A \times B$ 与 $A,B$ 的次序有关。因此，一般地有 $A \times B \ne B \times A$ ，即交换律不成立。其次，若 $A \sube S,B \sube S$ ，则 $A \cup B、A \cap B、A \backslash B、A \triangle B$ 都是 $S$ 的子集，但 $A \times B \nsubseteq S$ 。

由定义13知，对任一集 $A$ ，有

$$\begin{aligned} A \times \varnothing = \varnothing \times A = \varnothing \tag{101}\end{aligned}$$

其次，Cartesian乘积也不满足结合律，即

$$\begin{aligned} (A \times B) \times C \ne A \times (B \times C) \tag{102}\end{aligned}$$

因为当 $A \ne \varnothing,B \ne \varnothing, C \ne \varnothing$ 时，$(A \times B) \times C$ 的一般元素形如

$$\begin{aligned} ((x,y),z),x \in A,y \in B,z \in C \tag{103}\end{aligned}$$

而 $A \times (B \times C)$ 中元素的一般形式为

$$\begin{aligned} (x,(y,z)),x \in A,y \in B,z \in C \tag{104}\end{aligned}$$

按有序对相等的定义便知结合律不成立。

Cartesian乘积与并、交、差运算之间的联系

下面的定理说明Cartesian乘积与并、交、差运算之间的联系。

定理15：设 $A,B,C$ 为任意三个集合，则Cartesian乘积运算对并、交、差运算分别满足分配律，即

$$\begin{aligned} A \times (B \cup C) = (A \times B) \cup (A \times C) \tag{105}\end{aligned}$$ $$\begin{aligned} A \times (B \cap C) = (A \times B) \cap (A \times C) \tag{106}\end{aligned}$$ $$\begin{aligned} A \times (B \backslash C) = (A \times B) \backslash (A \times C) \tag{107}\end{aligned}$$

〔证明(定理15)〕首先证明(105)。
设 $(x,y) \in A \times (B \cup C)$ ，则 $x \in A$ 且 $y \in B \cup C$ 。因此，$x \in A$ 且 $y \in B$ ，或者 $x \in A$ 且 $y \in C$ 。所以，$(x,y) \in A \times B$ 或 $(x,y) \in A \times C$ ，故 $(x,y) \in (A \times B) \cup (A \times C)$ 。于是 $A \times (B \cup C) \sube (A \times B) \cup (A \times C)$ 。
反之，设 $(x,y) \in (A \times B) \cup (A \times C)$ ，则 $(x,y) \in A \times B$ 或 $(x,y) \in A \times C$ ，从而 $x \in A$ 且 $y \in B$ ，或者 $x \in A$ 且 $y \in C$ 。总之，$x \in A$ 且 $y \in B \cup C$ 。所以，$(x,y) \in A \times (B \cup C)$ 。于是 $(A \times B) \cup (A \times C) \sube A \times (B \cup C)$ 。
综上所述，$A \times (B \cup C) = (A \times B) \cup (A \times C)$ 。
再证明(106)。
设 $(x,y) \in A \times (B \cap C)$ ，则 $x \in A$ 且 $y \in B \cap C$ 。因此，$x \in A$ 且 $y \in B$ ，并且 $x \in A$ 且 $y \in C$ 。所以，$(x,y) \in A \times B$ 且 $(x,y) \in A \times C$ ，故 $(x,y) \in (A \times B) \cap (A \times C)$ 。于是 $A \times (B \cap C) \sube (A \times B) \cap (A \times C)$ 。
反之，设 $(x,y) \in (A \times B) \cap (A \times C)$ ，则 $(x,y) \in A \times B$ 且 $(x,y) \in A \times C$ ，从而 $x \in A$ 且 $y \in B$ ，并且 $x \in A$ 且 $y \in C$ 。总之，$x \in A$ 且 $y \in B \cap C$ 。所以，$(x,y) \in A \times (B \cap C)$ 。于是 $(A \times B) \cap (A \times C) \sube A \times (B \cap C)$ 。
综上所述，$A \times (B \cap C) = (A \times B) \cap (A \times C)$ 。
最后证明(107)。
设 $(x,y) \in A \times (B \backslash C)$ ，则 $x \in A$ 且 $y \in B \backslash C$ 。因此，$x \in A$ 且 $y \in B$ 且 $y \notin C$ 。所以，$(x,y) \in A \times B$ 且 $(x,y) \notin A \times C$ ，故 $(x,y) \in (A \times B) \backslash (A \times C)$ 。于是 $A \times (B \backslash C) \sube (A \times B) \backslash (A \times C)$ 。
反之，设 $(x,y) \in (A \times B) \backslash (A \times C)$ ，则 $(x,y) \in A \times B$ 且 $(x,y) \notin A \times C$ 。从第一项 $(x,y) \in A \times B$ 可得出 $x \in A$ 且 $y \in B$ ，$x$ 一定是 $A$ 的元素，所以对于第二项 $(x,y) \notin A \times C$ 就等价于 $y \notin C$ 。从而 $x \in A$ 且 $y \in B$ 且 $y \notin C$ 。总之，$x \in A$ 且 $y \in B \backslash C$ 。所以，$(x,y) \in A \times (B \backslash C)$ 。于是 $(A \times B) \backslash (A \times C) \sube A \times (B \backslash C)$ 。
综上所述，$A \times (B \backslash C) = (A \times B) \backslash (A \times C)$ 。

n元组

有序对也称二元组。我们可把二元组的概念推广，而有三元组、四元组，乃至n元组。例如，三元组就是三个对象按一定次序组成的整体，其第一个元为 $x$ ，第二个为 $y$ ，第三个为 $z$ ，则这个三元组就记为 $(x,y,z)$ 。一般地，一个n元组是几个元素按一定顺序的一个排列组成的整体，若第一个为 $x_1$ ，第二个为 $x_2$ ，···，第 $n$ 个为 $x_n$ ，则这个n元组就记为 $(x_1,x_2,\cdots,x_n)$ 。
称两个n元组 $(x_1,x_2,\cdots,x_n)$ 与 $(y_1,y_2,\cdots,y_n)$ 是相等的，并记为 $(x_1,x_2,\cdots,x_n)=(y_1,y_2,\cdots,y_n)$ ，当且仅当 $x_1=y_1,x_2=y_2,\cdots,x_n=y_n$ 同时成立。

定义14：设 $A_1,A_2,\cdots,A_n(n \ge 2)$ 为 $n$ 个集合，集合

$$\begin{aligned} \set{(a_1,a_2,\cdots,a_n) | a_i \in A_i,i=1,2,\cdots,n} \tag{108}\end{aligned}$$

称为 $A_1,A_2,\cdots,A_n$ 的Cartesian乘积，并记为 $A_1 \times A_2 \times \cdots \times A_n$ ，或简记为 $\displaystyle\prod_{i=1}^{n}A_i$ 。
于是

$$\begin{aligned} A_1 \times A_2 \times \cdots \times A_n = \prod_{i=1}^{n}A_i = \set{(a_1,a_2,\cdots,a_n) | a_i \in A_i,i=1,2,\cdots,n} \tag{109}\end{aligned}$$

当 $A_1 = A_2 = \cdots = A_n = A$ 时，$A_1 \times A_2 \times \cdots \times A_n$ 就简记为 $A^n$ 。即

$$\begin{aligned} A^n = \underbrace{A \times A \times \cdots \times A}_{n个A} \tag{110}\end{aligned}$$

由给定的集合 $A$ ，用Cartesian成绩运算得到集合 $A^1=A,A^2,A^3,A^4,\cdots,A^n,\cdots$ 。再用并运算得到集合

$$\begin{aligned} A^+=\bigcup_{n=1}^{\infin}A^n \tag{111}\end{aligned}$$

及

$$\begin{aligned} A^* = \bigcup_{n=0}^{\infin}A^n = \set{\varepsilon} \cup A^+ \tag{112}\end{aligned}$$

其中 $A^0=\set{\varepsilon}$ ，$\varepsilon$ 就是0元组 $()$ 。

如果把 $A$ 定义为26个英文字母、标点符号及空格所组成的有穷集合——称为字母表，并把 $A^n$ 中的n元组 $(a_1,a_2,\cdots,a_n)$ 简写成 $a_1a_2 \cdots a_n$ （称为 $A$ 中的符号串或符号行），则 $A^+$ 就是所有有意义、无意义的英语“单词”、“句子”的集合。而英语语言就是那些正确的句子的集合，从而是 $A^+$ （或 $A^*$ ）的一个子集。Chomsky在研究自然语言时，把语言抽象为一个数学模型：它是一个由一个有穷字母表 $ \varSigma $ ，及一个子集 $L \sube \varSigma^*$ ，组成的数学系统。直到今天，几乎所有的语言理论研究都是在这个模型下进行的。这个模型已充分广泛，它包括了各种自然语言、程序设计语言等等。

有穷集合的基数

一一对应

当抽象地研究集合时，集合中的元素的属性是不研究的，或说被抽象掉了。只假定集合是彼此互不相同的一些元素构成的整体，至于这些元素究竟是什么以及元素之间有些什么关系是根本不管的。于是，一个集合中的元素只是一些彼此可区分的抽象符号。因此，一个集合中所包含的元素的“个数”就成为这个抽象集合的重要属性了。它是抽去了元素的属性和元素间的次序关系后所保留下来的属性。如果一个集合中只含有穷多个元素，谈论该集合的元素的个数，自然是有意义的。但当集合中含有无穷多个元素时，怎么能谈论它的元素的个数呢？因为按通常的理解，元素的个数应指一个有限数。而什么是“无穷”、“无限数”？确实我们还不甚清楚。Cantor的伟大功绩就在于什么是无限数、什么是无穷集合，从而建立无穷集合的理论。在第四篇中，我们将介绍这一理论。本节先讨论有限集合的元素的个数概念及有关结果。
集合中元素的个数概念对每个人都熟悉，这是我们在数学里最早遇到的概念之一，即计数的概念。有人可能认为，计数是数学里最基本概念，我们每个人从幼儿园开始就学过了。实际上，计数是一个复杂的概念，它是建立在更基本概念——一对一配对上，在数学上称为一一对应。例如，要知道集合 $\set{a,c,b}$ 从有几个元素，我们是用数数的方法得到的。我们指着 $a$ 说 $1$ ，指 $c$ 说 $2$ ，指 $b$ 说 $3$ ，这样就数完了这个集合的元素，得到个数 $3$ 。这过程就把集合 $\set{a,c,b}$ 与 $\set{1,2,3}$ 的元素一对一配对无余，即 $〔a,1〕$、$〔b,2〕$、$〔c,3〕$ 三对, 亦即 $a$ 对应于 $1$ ，$c$ 对应于 $2$ ，$b$ 对应于 $3$ 。

定义15：设 $A$ 和 $B$ 是两个集合，如果有一个法则 $\varphi$ 使 $\forall x \in A$ ，根据法则 $\varphi$ 在 $B$ 中有唯一的一个 $y$ 与 $x$ 对应，这个 $y$ 常记为 $\varphi(x)$ ，而且 $\forall y \in B$ 在 $A$ 中也有唯一的 $x$ 使 $x$ 在 $\varphi$ 下对应于 $y$ 。这个法则 $\varphi$ 称为从 $A$ 到 $B$ 的一个一一对应（一对一配对无余的方法）。

这是在分析中大家熟知的概念。现在我们并不满意这个定义，因为其中包含了尚未定义的概念：“法则”、“对应”。而现在，我们已有条件把这个概念弄得更清楚了。实际上，从 $\set{a,c,b}$ 与 $\set{1,2,3}$ 的元素间配对得到启发，给出如下的定义。

定义16：一个从集合 $A$ 到集合 $B$ 的一一对应是 $A \times B$ 的子集 $\varphi$ 使之满足
① $\forall x \in A, \exist y \in B$ 使 $(x,y) \in \varphi$ ；如果 $(x,y)、(x,z) \in \varphi$ ，则 $y=z$ 。
② $\forall y \in B, \exist x \in A$ 使得 $(x,y) \in \varphi$ ，并且如果 $(x,y)、(x',y) \in \varphi$ ，则 $x=x'$ 。
如果 $(x,y) \in \varphi$ ，则把 $y$ 记为 $\varphi(x)$ ，即 $y=\varphi(x)$ 。

基数

基数的定义

定义17：集合 $A$ 称为有限集，如果 $A=\varnothing$ ，或 $A \ne \varnothing$ 且存在一个自然数 $n$ 使得 $A$ 与集合 $\set{1,2,\cdots,n}$ 间存在一个一一对应。数 $n$ 称为 $A$ 的基数，$A$ 的基数记成 $|A|$ 。空集的基数定义为数 $0$ 。如果 $A$ 不是有穷集，则称 $A$ 为无穷集。

基数的比较

利用一一对应的概念还可建立基数的比较。如果问教室里的学生多还是椅子多呢？我想不会有人去数一数教室里的学生数和椅子数才给出答案的。在假设每把椅子至多坐一个人时，他环顾一下教室，马上会说椅子多。因为他发现有空椅子，从而学生之集不能与椅子之集间有一一对应，学生之集只能与椅子之集的一个真子集间有一一对应关系。

定义18：如果 $A$ 与 $B$ 的一个真子集间有一个一一对应存在，但 $A$ 与 $B$ 之间不存在一一对应，则称 $|A|$ 小于 $|B|$ ，记为 $|A|<|B|$ 。

计数法则

计数的本质是一一对应，由定义17得到一些计数法则。

加法法则

定理16（加法法则）：设 $A,B$ 为两个不相交的有限集，则 $|A \cup B| = |A| + |B|$ 。

〔证明(加法法则)〕由定义17，若 $A=\varnothing$ 或 $B=\varnothing$ ，则 $|A \cup B|=|A|+|B|$ 成立。现设 $A \ne \varnothing,B \ne \varnothing$ ，那么由定义17，从 $A$ 到 $\set{1,2,\cdots,|A|}$ 有一个一一对应 $f$ ，从 $B$ 到 $\set{1,2,\cdots,|B|}$ 有一个一一对应 $g$ 。现构造从 $A \cup B$ 到 $\set{1,2,\cdots,|A|+|B|}$ 的一一对应 $h$ 如下： $\forall x \in A \cup B$ ，若 $x \in A$ ，则 $h(x)=f(x)$ ；若 $x \in B$ ，则 $h(x)=g(x)+|A|$ 。由于 $|A \cap B| = \varnothing$ ，可以验证 $h$ 为一一对应。由定义17便知 $|A \cup B|=|A|+|B|$ 。

应用数学归纳法可以证明

定理17：设 $A_1,A_2,\cdots,A_n$ 为 $n$ 个两两不相交的有限集，则

$$\begin{aligned} |\bigcup_{i=1}^{n}A_i|=\sum_{i=1}^{n}|A_i| \tag{113}\end{aligned}$$

〔证明(定理17)〕 $n=1$ 时，有 $|A_1|=|A_1|$ 成立。假设 $n = k$ 时成立，现证明 $n=k+1$ 时成立。由加法法则可得

$$\begin{aligned} |\bigcup_{i=1}^{k+1}A_i| =& |\bigcup_{i=1}^{k}A_i \cup A_{k+1}| \\[10pt] =& |\bigcup_{i=1}^{k}A_i| + |A_{k+1}| \quad \text{（加法法则）} \\[10pt] =& \sum_{i=1}^{k}|A_i| + |A_{k+1}| \\[10pt] =& \sum_{i=1}^{k+1}|A_i| \tag{114}\end{aligned}$$

由数学归纳法可得(113)成立。

乘积法则

定理18（乘积法则）：设 $A,B$ 为有穷集，则 $|A \times B| = |A| \cdot |B|$ 。

〔证明(乘积法则)〕令 $A = \set{a_1,a_2,\cdots,a_m}$ 。对 $i=1,2,\cdots,m$ ，令 $A_i=\set{a_i,b|b \in B}$ ，则 $A \times B = \displaystyle \bigcup_{i=1}^{m}A_i$ 且 $A_1,\cdots,A_m$ 两两不相交。由定理17便得到

$$\begin{aligned} |A \times B| = \sum_{i=1}^{m}|A_i|=m \cdot |B| = |A| \cdot |B| \tag{115}\end{aligned}$$

应用数学归纳法可以证明

定理19：设 $B_1,B_2,\cdots,B_n$ 为有限集，则

$$\begin{aligned} |B_1 \times B_2 \times \cdots \times B_n|=|B_1| \cdot |B_2| \cdots |B_n| \tag{116}\end{aligned}$$

〔证明(定理19)〕 $n=1$ 时，$|B_1|=|B_1|$ 成立。假设 $n=k$ 时成立，现证明 $n=k+1$ 时成立。由乘积法则可得

$$\begin{aligned} |B_1 \times B_2 \times \cdots \times B_{k+1}| =& |B_1 \times B_2 \times \cdots \times B_k| \cdot |B_{k+1}| \quad \text{（乘积法则）} \\[5pt] =& |B_1| \cdot |B_2| \cdots |B_n| \cdot |B_{n+1}| \tag{117}\end{aligned}$$

由数学归纳法可得(116)成立。

减法法则

定理20（减法法则）：设 $S$ 为有穷集，$A \sube S$ ，则 $|A^c|=|S \backslash A| = |S|-|A|$ 。

〔证明(减法法则)〕由于 $S = A \cup A^c$ 且 $A \cap A^c = \ \varnothing$ ，由加法法则得 $|S| = |A| + |A^c|$ ，故 $|A^c|=|S|-|A|$ 。由定义11得 $A^c = S \backslash A$ 故得 $|S \backslash A| = |S| - |A|$ 。

关于计数的其他定理

定理21：设 $A,B$ 为有限集，则

$$\begin{aligned} |A \cup B| = |A| + |B| - |A \cup B| \tag{118}\end{aligned}$$

要证明该定理，需先证明四个引理。

引理1： $$\begin{aligned} A \cup B = A \cup (B \backslash A) \tag{119}\end{aligned}$$

〔证明(引理1)〕将 (66)中的 $A,B$ 互换即得。

引理2： $$\begin{aligned} A \cap (B \backslash A) = \varnothing \tag{120}\end{aligned}$$

〔证明(引理2)〕设 $x \in A \cap (B \backslash A)$ ，有 $x \in A$ 且 $x \in B \backslash A$ ，即 $x \in A$ 且 $x \in B$ 且 $x \notin A$ ，这是不可能同时满足的，所以 $A \cap (B \backslash A) = \varnothing$ 。

引理3： $$\begin{aligned} B = (B \backslash A) \cup (B \cap A) \tag{121}\end{aligned}$$

〔证明(引理3)〕由(52)可得

$$\begin{aligned} (B \backslash A) \cup (B \cap A) = ((B \backslash A) \cup B) \cap ((B \backslash A) \cup A) \tag{122}\end{aligned}$$

由引理1可知 $(B \backslash A) \cup A = A \cup B$ 。而由(63)可知 $B \backslash A \sube B$ ，因此再由(67)可得 $(B \backslash A) \cup B = B$ 。因此上式变为

$$\begin{aligned} (B \backslash A) \cup (B \cap A) = B \cap (A \cup B) \tag{123}\end{aligned}$$

由(55)可得 $B \cap (A \cup B) = B$ 。因此

$$\begin{aligned} (B \backslash A) \cup (B \cap A) = B \tag{124}\end{aligned}$$ 引理4： $$\begin{aligned} (B \backslash A) \cap (B \cap A) = \varnothing \tag{125}\end{aligned}$$

〔证明(引理4)〕由结合律(39)可得

$$\begin{aligned} (B \backslash A) \cap (B \cap A) = ((B \backslash A) \cap A) \cap B \tag{126}\end{aligned}$$

而根据引理2可知

$$\begin{aligned} (B \backslash A) \cap A = \varnothing \tag{127}\end{aligned}$$

又因为(41)，可以得到

$$\begin{aligned} (B \backslash A) \cap (B \cap A) = \varnothing \cap B = \varnothing \tag{128}\end{aligned}$$

现在来证明定理21。

〔证明(定理21)〕由引理1、引理2和加法法则可得

$$\begin{aligned} |A \cup B| = |A| + |B \backslash A| \tag{129}\end{aligned}$$

由引理3、引理4和加法法则可得

$$\begin{aligned} |B| = |B \backslash A| + |B \cap A| \tag{130}\end{aligned}$$

将(129)两边同时减去(130)并化简可得

$$\begin{aligned} |A \cup B| = |A| + |B| - |A \cap B| \tag{131}\end{aligned}$$

证毕。

定理22：设 $A,B$ 为有限集，则

$$\begin{aligned} |A \triangle B| = |A| + |B| - 2|A \cap B| \tag{132}\end{aligned}$$

要证明该定理，需先证明一个引理。

引理5： $$\begin{aligned} A \triangle B = (A \cup B) \backslash (A \cap B) \tag{133}\end{aligned}$$

〔证明(引理5)〕由(72)、(69)、(60)、(28)和定义10可得

$$\begin{aligned} (A \cup B) \backslash (A \cap B) =& ((A \cup B) \backslash A) \cup ((A \cup B) \backslash B) \quad \text{（(72)）}\\[5pt] =& ((A \backslash A) \cup (B \backslash A)) \cup ((A \backslash B) \cup (B \backslash B)) \quad \text{（(69)）}\\[5pt] =& (\varnothing \cup (B \backslash A)) \cup ((A \backslash B) \cup \varnothing) \quad \text{（(60)）}\\[5pt] =& (A \backslash B) \cup (B \backslash A) \quad \text{（(28)）}\\[5pt] =& A \triangle B \quad \text{（定义10）} \tag{134}\end{aligned}$$

现在来证明定理22。

〔证明(定理22)〕首先由(43)和(30)易推导出 $A \cap B \sube A \sube A \cup B$ （或 $A \cap B \sube B \sube A \cup B$ ）。因此由减法法则可得

$$\begin{aligned} |A \triangle B| = |(A \cup B) \backslash (A \cap B)| = |A \cup B| - |A \cap B| \tag{135}\end{aligned}$$

再利用定理21可得

$$\begin{aligned} |A \triangle B| = |A| + |B| - |A \cap B| - |A \cap B| = |A| + |B| - 2|A \cap B| \tag{136}\end{aligned}$$

逐步淘汰原理

进一步推广加法法则，便得到

定理23（逐步淘汰原理形式一）：设 $A_1,A_2,\cdots,A_n$ 为 $n$ 个有穷集，则

$$\begin{aligned} |\bigcup_{i=1}^{n}A_i|=\sum_{i=1}^{n}|A_i|-\sum_{1 \le i < j \le n}|A_i \cap A_j| + \sum_{1 \le i < j < k \le n}|A_i \cap A_j \cap A_k|-\cdots + (-1)^{n-1}|A_1 \cap A_2 \cap \cdots \cap A_n| \tag{137}\end{aligned}$$

要证明该定理，先证明一个组合求和常用的引理。

引理6：假设有变量 $x_1,x_2,\cdots,x_n$ ，求和指标 $i_1,i_2,\cdots,i_m,m < n$ ，和函数 $f(x_{i_1},x_{i_2},\cdots,x_{i_m})$ ，那么这些变量和函数满足求和关系

$$\begin{aligned} \sum_{1 \le i_1 < i_2 < \cdots < i_m \le n-1}f(x_{i_1},x_{i_2},\cdots,x_{i_m}) + \sum_{1 \le i_1 < i_2 < \cdots < i_{m-1} \le n-1}f(x_{i_1},x_{i_2},\cdots,x_{i_{m-1}},x_n) \\[15pt] = \sum_{1 \le i_1 < i_2 < \cdots < i_m \le n}f(x_{i_1},x_{i_2},\cdots,x_{i_m}) \tag{138}\end{aligned}$$

〔证明(引理6)〕考虑右侧的和式 $\displaystyle \sum_{1 \le i_1 < i_2 < \cdots < i_m \le n}f(x_{i_1},x_{i_2},\cdots,x_{i_m}) $ ，所有满足 $1 \le i_1 < i_2 < \cdots < i_m \le n$ 的索引组合可以分为两类：第一类是不包含 $n$ 的索引组合，由于 $i_m$ 是最大的索引，所以 $i_m \le n-1$ ，此时所有索引满足 $1 \le i_1 < i_2 < \cdots < i_m \le n-1$ ，正好是左侧第一个求和式 $\displaystyle \sum_{1 \le i_1 < i_2 < \cdots < i_m \le n-1}f(x_{i_1},x_{i_2},\cdots,x_{i_m})$ ；第二类是包含 $n$ 的索引组合，由于 $i_m$ 是最大的索引，因此只有可能 $i_m=n$ ，因此此时所有索引满足 $1 \le i_1 < i_2 < \cdots < i_{m-1} \le n-1$ ，正好是左侧第二个求和式 $\displaystyle \sum_{1 \le i_1 < i_2 < \cdots < i_{m-1} \le n-1}f(x_{i_1},x_{i_2},\cdots,x_{i_{m-1}},x_n) $ 。即可得到(138)是正确的。

现在我们来证明逐步淘汰原理形式一。

〔证明(逐步淘汰原理形式一)〕应用数学归纳法，施归纳于 $n$ 。当 $n=2$ 时就是定理21，因此结论成立。假定定理的结论对 $n-1 \ge 2$ 个有限集合成立。往证对 $n$ 个有限集合定理的结论也成立。由定理21和定理4有

$$\begin{aligned} |\bigcup_{i=1}^{n}A_i|=&|(\bigcup_{i=1}^{n-1}A_i) \cup A_n| \\[10pt] =& |\bigcup_{i=1}^{n-1}A_i|+|A_n|-|\bigcup_{i=1}^{n-1}A_i \cap A_n| \text{（定理21）} \\[10pt] =& |\bigcup_{i=1}^{n-1}A_i|+|A_n|-|(A_1 \cap A_n) \cup (A_2 \cap A_n) \cup \cdots \cup (A_{n-1} \cap A_n)| \text{（定理4）} \tag{139}\end{aligned}$$

由归纳假设得

$$\begin{aligned} |\bigcup_{i=1}^{n-1}A_i| = \sum_{i=1}^{n-1}|A_i|-\sum_{1 \le i < j \le n-1}|A_i \cap A_j| + \sum_{1 \le i < j < k \le n-1}|A_i \cap A_j \cap A_k|-\cdots + (-1)^{n-2}|A_1 \cap A_2 \cap \cdots \cap A_{n-1}| \tag{140}\end{aligned}$$

并得

$$\begin{aligned} &|(A_1 \cap A_n) \cup (A_2 \cap A_n) \cup \cdots \cup (A_{n-1} \cap A_n)| \\[5pt] =& \sum_{i=1}^{n-1}|A_i \cap A_n| - \sum_{1 \le i < j \le n-1} |(A_i \cap A_n) \cap (A_j \cap A_n)| + \sum_{1 \le i < j < k \le n-1}|(A_i \cap A_n) \cap (A_j \cap A_n) \cap (A_k \cap A_n)| - \cdots \\[15pt] & + (-1)^{n-2}|(A_1 \cap A_n) \cap (A_2 \cap A_n) \cap \cdots \cap (A_{n-1} \cap A_n)| \\[5pt] =& \sum_{i=1}^{n-1}|A_i \cap A_n| - \sum_{1 \le i < j \le n-1} |A_i \cap A_j \cap A_n| + \sum_{1 \le i < j < k \le n-1}|A_i \cap A_j \cap A_k \cap A_n| - \cdots \\[15pt] & + (-1)^{n-2}|A_1 \cap A_2 \cap \cdots \cap A_{n-1} \cap A_n| \tag{141}\end{aligned}$$

将(140)、(141)代入(139)可得

$$\begin{aligned} |\bigcup_{i=1}^{n}A_i|=& \sum_{i=1}^{n-1}|A_i|-\sum_{1 \le i < j \le n-1}|A_i \cap A_j| + \sum_{1 \le i < j < k \le n-1}|A_i \cap A_j \cap A_k|-\cdots + (-1)^{n-2}|A_1 \cap A_2 \cap \cdots \cap A_{n-1}| \\[15pt] & + |A_n| - \bigg(\sum_{i=1}^{n-1}|A_i \cap A_n| - \sum_{1 \le i < j \le n-1} |A_i \cap A_j \cap A_n| + \sum_{1 \le i < j < k \le n-1}|A_i \cap A_j \cap A_k \cap A_n| - \cdots \\[15pt] & + (-1)^{n-2}|A_1 \cap A_2 \cap \cdots \cap A_{n-1} \cap A_n|\bigg) \\[15pt] =& \sum_{i=1}^{n-1}|A_i|-\sum_{1 \le i < j \le n-1}|A_i \cap A_j| + \sum_{1 \le i < j < k \le n-1}|A_i \cap A_j \cap A_k|-\cdots + (-1)^{n-2}|A_1 \cap A_2 \cap \cdots \cap A_{n-1}| \\[15pt] & + |A_n| - \sum_{i=1}^{n-1}|A_i \cap A_n| + \sum_{1 \le i < j \le n-1} |A_i \cap A_j \cap A_n| - \sum_{1 \le i < j < k \le n-1}|A_i \cap A_j \cap A_k \cap A_n| + \cdots \\[15pt] & + (-1)^{n-1}|A_1 \cap A_2 \cap \cdots \cap A_{n-1} \cap A_n| \\[15pt] =& \bigg(\sum_{i=1}^{n-1}|A_i| + |A_n|\bigg) - \bigg(\sum_{1 \le i < j \le n-1}|A_i \cap A_j| + \sum_{i=1}^{n-1}|A_i \cap A_n|\bigg) + \\[15pt] & \bigg(\sum_{1 \le i < j < k \le n-1}|A_i \cap A_j \cap A_k| + \sum_{1 \le i < j \le n-1} |A_i \cap A_j \cap A_n|\bigg) - \cdots + \\[15pt] & (-1)^{n-2}\bigg(|A_1 \cap A_2 \cap \cdots \cap A_{n-1}| + \sum_{1 \le i_1 < i_2 < \cdots < i_{n-2} \le n-1} |A_{i_1} \cap A_{i_2} \cap \cdots \cap A_{i_{n-2}} \cap A_n| \bigg) \\[15pt] & + (-1)^{n-1}|A_1 \cap A_2 \cap \cdots \cap A_{n-1} \cap A_n| \tag{142}\end{aligned}$$

易得$\displaystyle\sum_{i=1}^{n-1}|A_i| + |A_n| = \sum_{i=1}^{n}|A_i|$ 。由引理6可得 $\displaystyle\sum_{1 \le i < j \le n-1}|A_i \cap A_j| + \sum_{i=1}^{n-1}|A_i \cap A_n| = \sum_{1 \le i < j \le n}|A_i \cap A_j|$ 、 $\displaystyle\sum_{1 \le i < j < k \le n-1}|A_i \cap A_j \cap A_k| + \sum_{1 \le i < j \le n-1} |A_i \cap A_j \cap A_n| = \sum_{1 \le i < j < k \le n}|A_i \cap A_j \cap A_k|$ 、···。注意 $|A_1 \cap A_2 \cap \cdots \cap A_{n-1}|$ 可以写成 $\displaystyle\sum_{1 \le i_1 < i_2 < \cdots < i_{n-1} \le n-1} |A_{i_1} \cap A_{i_2} \cap \cdots \cap A_{i_{n-1}}|$ ，因此 $\displaystyle |A_1 \cap A_2 \cap \cdots \cap A_{n-1}| + \sum_{1 \le i_1 < i_2 < \cdots < i_{n-2} \le n-1} |A_{i_1} \cap A_{i_2} \cap \cdots \cap A_{i_{n-2}} \cap A_n| = \sum_{1 \le i_1 < i_2 < \cdots < i_{n-1} \le n} |A_{i_1} \cap A_{i_2} \cap \cdots \cap A_{i_{n-1}}| $ ，因此

证毕。

定理24（逐步淘汰原理形式二）：设 $A_1,A_2,\cdots,A_n$ 都是有限集 $S$ 的子集，则

$$\begin{aligned} |\bigcap_{i=1}^{n}A_i^c|=|S| - \sum_{i=1}^{n}|A_i| + \sum_{1 \le i < j \le n}|A_i \cap A_j| - \sum_{1 \le i < j < k \le n}|A_i \cap A_j \cap A_k| + \cdots + (-1)^n|A_1 \cap A_2 \cap \cdots \cap A_n| \tag{144}\end{aligned}$$

〔证明(逐步淘汰原理形式二)〕由De Morgan公式和定义11可得 $A_1^c \cap A_2^c \cap \cdots \cap A_n^c = (A_1 \cup A_2 \cup \cdots \cup A_n)^c = S \backslash (A_1 \cup A_2 \cup \cdots \cup A_n)$ ，由减法法则可得

$$\begin{aligned} |\bigcap_{i=1}^{n}A_i^c|=|S|-|\bigcup_{i=1}^{n}A_i| \tag{145}\end{aligned}$$

再利用逐步淘汰原理形式一即得所要证明之结果。

逐步淘汰原理也称容斥原理。

任何体验如果未达到极致并终归寂灭，都会重新出现，悲哀总会回归。

― Hermann Hesse, 《悉达多》