集合论基础

集合论是现代数学的基础，也是离散数学的核心内容之一。它为其他数学分支提供了统一的语言和框架。本章介绍集合的基本概念、运算和重要性质。

什么是集合？

集合（Set） 是一些确定的、互不相同的对象的全体。这些对象称为集合的元素（Element） 或成员。

集合的特征

一个集合具有以下特征：

1. 确定性：给定一个集合和一个对象，可以明确判断该对象是否属于该集合
2. 互异性：集合中的元素互不相同，每个元素只出现一次
3. 无序性：集合中的元素没有顺序之分

集合的表示方法

列举法：将集合的所有元素一一列举出来，用花括号括起。

$A = \{1, 2, 3, 4, 5\}$

$B = \{\text{红}, \text{黄}, \text{蓝}\}$

描述法：用元素的特征性质来描述集合。

$C = \{x \mid x \text{ 是正偶数}\} = \{2, 4, 6, 8, \ldots\}$

$D = \{x \in \mathbb{R} \mid x^2 < 4\} = (-2, 2)$

区间表示：对于实数集合，常用区间表示。

• 开区间：$(a, b) = \{x \mid a < x < b\}$
• 闭区间：$[a, b] = \{x \mid a \leq x \leq b\}$
• 半开区间：$(a, b] = \{x \mid a < x \leq b\}$

常用数集

符号	名称	描述
$\mathbb{N}$	自然数集	$\{0, 1, 2, 3, \ldots\}$ 或 $\{1, 2, 3, \ldots\}$
$\mathbb{Z}$	整数集	$\{\ldots, -2, -1, 0, 1, 2, \ldots\}$
$\mathbb{Q}$	有理数集	所有可表示为分数的数
$\mathbb{R}$	实数集	所有的实数
$\mathbb{C}$	复数集	所有的复数

注意：自然数集的定义有两种，有些教材从 0 开始，有些从 1 开始。本教程采用 $\mathbb{N} = \{0, 1, 2, \ldots\}$。

元素与集合的关系

属于与不属于

如果 $a$ 是集合 $A$ 的元素，记作 $a \in A$，读作"$a$ 属于 $A$"。

如果 $a$ 不是集合 $A$ 的元素，记作 $a \notin A$，读作"$a$ 不属于 $A$"。

例子：

• $3 \in \{1, 2, 3, 4, 5\}$
• $6 \notin \{1, 2, 3, 4, 5\}$
• $\sqrt{2} \in \mathbb{R}$，但 $\sqrt{2} \notin \mathbb{Q}$

空集

不含任何元素的集合称为空集，记作 $\emptyset$ 或 $\{\}$。

注意：空集是唯一的。$\emptyset \neq \{\emptyset\}$，后者是以空集为唯一元素的集合。

子集与真子集

子集

如果集合 $A$ 的每一个元素都是集合 $B$ 的元素，则称 $A$ 是 $B$ 的子集，记作 $A \subseteq B$。

形式化定义：

$A \subseteq B \iff \forall x (x \in A \rightarrow x \in B)$

例子：

• $\{1, 2\} \subseteq \{1, 2, 3\}$
• $\mathbb{N} \subseteq \mathbb{Z} \subseteq \mathbb{Q} \subseteq \mathbb{R}$
• $\emptyset \subseteq A$（空集是任何集合的子集）

真子集

如果 $A \subseteq B$ 且 $A \neq B$，则称 $A$ 是 $B$ 的真子集，记作 $A \subset B$ 或 $A \subsetneq B$。

例子：

• $\{1, 2\} \subset \{1, 2, 3\}$
• $\{1, 2, 3\} \not\subset \{1, 2, 3\}$（不是真子集，是相等）

集合相等

两个集合相等，当且仅当它们互为子集。

$A = B \iff A \subseteq B \land B \subseteq A$

这个定义是证明两个集合相等的基本方法。

集合的运算

并集

集合 $A$ 和 $B$ 的并集，记作 $A \cup B$，包含属于 $A$ 或属于 $B$ 的所有元素。

$A \cup B = \{x \mid x \in A \lor x \in B\}$

例子：

• $\{1, 2, 3\} \cup \{2, 3, 4\} = \{1, 2, 3, 4\}$
• $\{a, b\} \cup \{c, d\} = \{a, b, c, d\}$

交集

集合 $A$ 和 $B$ 的交集，记作 $A \cap B$，包含同时属于 $A$ 和 $B$ 的所有元素。

$A \cap B = \{x \mid x \in A \land x \in B\}$

例子：

• $\{1, 2, 3\} \cap \{2, 3, 4\} = \{2, 3\}$
• $\{a, b\} \cap \{c, d\} = \emptyset$

如果 $A \cap B = \emptyset$，则称 $A$ 和 $B$ 不相交。

差集

集合 $A$ 和 $B$ 的差集，记作 $A \setminus B$ 或 $A - B$，包含属于 $A$ 但不属于 $B$ 的所有元素。

$A \setminus B = \{x \mid x \in A \land x \notin B\}$

例子：

• $\{1, 2, 3\} \setminus \{2, 3, 4\} = \{1\}$
• $\{a, b, c\} \setminus \{b\} = \{a, c\}$

补集

设 $U$ 是全集，集合 $A$ 的补集，记作 $\overline{A}$ 或 $A^c$，是 $U$ 中不属于 $A$ 的所有元素。

$\overline{A} = U \setminus A = \{x \in U \mid x \notin A\}$

例子：

• 设 $U = \{1, 2, 3, 4, 5\}$，$A = \{1, 2, 3\}$
• 则 $\overline{A} = \{4, 5\}$

对称差

集合 $A$ 和 $B$ 的对称差，记作 $A \triangle B$ 或 $A \oplus B$，包含恰好属于 $A$ 和 $B$ 之一的元素。

$A \triangle B = (A \setminus B) \cup (B \setminus A) = (A \cup B) \setminus (A \cap B)$

例子：

• $\{1, 2, 3\} \triangle \{2, 3, 4\} = \{1, 4\}$

幂集

集合 $A$ 的幂集，记作 $\mathcal{P}(A)$ 或 $2^A$，是 $A$ 的所有子集构成的集合。

例子：

• $A = \{a, b\}$
• $\mathcal{P}(A) = \{\emptyset, \{a\}, \{b\}, \{a, b\}\}$

重要性质：如果 $|A| = n$，则 $|\mathcal{P}(A)| = 2^n$。

笛卡尔积

两个集合 $A$ 和 $B$ 的笛卡尔积，记作 $A \times B$，是所有有序对 $(a, b)$ 的集合，其中 $a \in A$，$b \in B$。

$A \times B = \{(a, b) \mid a \in A \land b \in B\}$

例子：

• $A = \{1, 2\}$，$B = \{a, b\}$
• $A \times B = \{(1, a), (1, b), (2, a), (2, b)\}$

注意：$(a, b)$ 和 $(b, a)$ 是不同的有序对，除非 $a = b$。

推广：$n$ 个集合的笛卡尔积

$A_1 \times A_2 \times \cdots \times A_n = \{(a_1, a_2, \ldots, a_n) \mid a_i \in A_i\}$

当 $A_1 = A_2 = \cdots = A_n = A$ 时，记作 $A^n$。

集合运算的性质

交换律

$A \cup B = B \cup A$

$A \cap B = B \cap A$

结合律

$(A \cup B) \cup C = A \cup (B \cup C)$

$(A \cap B) \cap C = A \cap (B \cap C)$

分配律

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

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

德摩根律

$\overline{A \cup B} = \overline{A} \cap \overline{B}$

$\overline{A \cap B} = \overline{A} \cup \overline{B}$

理解：

• "不属于 A 或 B" 等价于 "不属于 A 且不属于 B"
• "不属于 A 且 B" 等价于 "不属于 A 或不属于 B"

推广：对于任意集合族 $\{A_i\}_{i \in I}$

$\overline{\bigcup_{i \in I} A_i} = \bigcap_{i \in I} \overline{A_i}$

$\overline{\bigcap_{i \in I} A_i} = \bigcup_{i \in I} \overline{A_i}$

吸收律

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

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

恒等律

$A \cup \emptyset = A$

$A \cap U = A$

支配律

$A \cup U = U$

$A \cap \emptyset = \emptyset$

补元律

$A \cup \overline{A} = U$

$A \cap \overline{A} = \emptyset$

$\overline{\overline{A}} = A$

集合恒等式的证明

证明方法

证明两个集合相等，通常有两种方法：

方法一：双向包含

证明 $A \subseteq B$ 且 $B \subseteq A$。

方法二：逻辑等价

利用集合的定义和逻辑等价式，直接推导。

例子：证明 $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$

方法一（双向包含）：

证明 $\subseteq$：设 $x \in A \cap (B \cup C)$，则 $x \in A$ 且 $x \in B \cup C$。如果 $x \in B$，则 $x \in A \cap B$；如果 $x \in C$，则 $x \in A \cap C$。无论哪种情况，$x \in (A \cap B) \cup (A \cap C)$。

证明 $\supseteq$：设 $x \in (A \cap B) \cup (A \cap C)$，则 $x \in A \cap B$ 或 $x \in A \cap C$。无论哪种情况，$x \in A$ 且 $x \in B \cup C$，即 $x \in A \cap (B \cup C)$。

方法二（逻辑等价）：

$x \in A \cap (B \cup C)$ $\iff x \in A \land (x \in B \lor x \in C)$ $\iff (x \in A \land x \in B) \lor (x \in A \land x \in C)$ （分配律） $\iff x \in A \cap B \lor x \in A \cap C$ $\iff x \in (A \cap B) \cup (A \cap C)$

集合的基数

有限集的基数

有限集 $A$ 的基数（或称为集合的大小），记作 $|A|$ 或 $\#A$，是 $A$ 中元素的个数。

例子：

• $|\{1, 2, 3\}| = 3$
• $|\emptyset| = 0$
• $|\mathcal{P}(\{1, 2\})| = |\{\emptyset, \{1\}, \{2\}, \{1, 2\}\}| = 4$

容斥原理

对于有限集 $A$ 和 $B$：

$|A \cup B| = |A| + |B| - |A \cap B|$

理解：直接相加会把交集部分算两次，所以需要减去一次。

推广：对于三个集合：

$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$

例子：某班有 30 人学英语，25 人学法语，15 人同时学两种语言，问至少学一门语言的有多少人？

设 $E$ 为学英语的集合，$F$ 为学法语的集合。

$|E \cup F| = |E| + |F| - |E \cap F| = 30 + 25 - 15 = 40$

无限集的基数

无限集的基数比较复杂，需要用到一一对应的概念。

两个集合 $A$ 和 $B$ 具有相同的基数，记作 $|A| = |B|$，当且仅当存在从 $A$ 到 $B$ 的双射（一一对应）。

可数集：与自然数集 $\mathbb{N}$ 具有相同基数的集合，称为可数无限集，其基数记作 $\aleph_0$（阿列夫零）。

例子：

• 正偶数集 $\{2, 4, 6, \ldots\}$ 是可数的，因为可以建立一一对应 $n \leftrightarrow 2n$
• 有理数集 $\mathbb{Q}$ 是可数的
• 实数集 $\mathbb{R}$ 是不可数的，其基数记作 $\mathfrak{c}$ 或 $2^{\aleph_0}$

集合的分划

分划：设 $A$ 是一个非空集合，$A$ 的一个分划是将 $A$ 分成若干非空子集，使得每个元素恰好属于一个子集。

形式化定义：集合族 $\{A_i\}_{i \in I}$ 是 $A$ 的分划，当且仅当：

1. 每个 $A_i \neq \emptyset$
2. $\bigcup_{i \in I} A_i = A$
3. 当 $i \neq j$ 时，$A_i \cap A_j = \emptyset$

例子：

• $A = \{1, 2, 3, 4\}$ 的一个分划：$\{\{1, 2\}, \{3, 4\}\}$
• 整数集可以分划为偶数集和奇数集：$\{E, O\}$

分划与等价关系有密切联系，每个等价关系诱导一个分划，每个分划也确定一个等价关系。

应用实例

数据库的关系模型

关系数据库基于集合论。一个关系（表）就是一个元组的集合，关系代数的运算（并、交、差、笛卡尔积、选择、投影）都是集合运算的推广。

例子：

• 学生表 $S$ 和选课表 $E$ 的连接操作本质上是笛卡尔积的选择

集合在编程中的应用

大多数编程语言都提供集合数据结构，支持基本的集合运算。

Python 示例：

A = {1, 2, 3, 4}
B = {3, 4, 5, 6}

print(A | B)  # 并集: {1, 2, 3, 4, 5, 6}
print(A & B)  # 交集: {3, 4}
print(A - B)  # 差集: {1, 2}
print(A ^ B)  # 对称差: {1, 2, 5, 6}

位向量表示

对于有限全集 $U = \{0, 1, \ldots, n-1\}$，可以用长度为 $n$ 的位向量表示子集：

• 第 $i$ 位为 1 表示 $i$ 在集合中
• 第 $i$ 位为 0 表示 $i$ 不在集合中

例子：$U = \{0, 1, 2, 3, 4\}$，$A = \{1, 3, 4\}$

位向量表示：$01011$

集合运算对应位运算：

• 并集 → 按位或（OR）
• 交集 → 按位与（AND）
• 补集 → 按位取反（NOT）

小结

本章介绍了集合论的基础知识：

• 集合是一些确定、互异、无序的对象的全体
• 子集关系是集合之间最基本的包含关系
• 集合运算包括并、交、差、补、对称差等
• 笛卡尔积产生有序对集合，是关系定义的基础
• 幂集是所有子集的集合，其大小为 $2^n$
• 德摩根律是集合运算的重要性质
• 容斥原理用于计算多个集合并集的大小
• 分划将集合分成互不相交的子集

集合论为后续的关系、函数、图论等内容提供了基础语言和工具。下一章将学习谓词逻辑，引入量词的概念。