4. 常见的数学数据类型

集合

集合是由一系列对象组成的整体。集合中的对象称作 元素。集合中的元素可以是任意的，集合内的元素没有顺序之分，一个元素不能重复出现在集合中。

对于有限集，我们可以考虑列出它的所有元素；对于无限集，我们可以通过集合中的元素具有某个共同的性质 $P(x)$ 来描述，记作 $\{x\in A\mid P(x)\}$。

如果一个集合 $A$ 内的所有元素都在另一个集合 $B$ 中出现过，称 $A$ 是 $B$ 的 子集，记作 $A\subseteq B$。显然对任何集合 $S$ 都有 $\mathrm{\varnothing },S\subseteq S$。两个集合相等当且仅当其含有完全相同的元素；等价的表述是 $A\subseteq B$ 且 $B\subseteq A$。如果 $A\subseteq B$ 但 $A\ne B$，称 $A$ 是 $B$ 的 真子集，记作 $A\subset B$。显然对任何集合 $S$ 都有 $S\not\subset S$。

我们定义一些由多个集合得到新集合的运算：

• 并集 $\cap$
• 交集 $\cup$
• 差集 $-$：$A-B=\{x\in A\mid x\notin B\}=A\cap \overline{B}$
• 补集：设 $D$ 为全域，则 $\overline{A}=D-A$
• 幂集：由 $A$ 的所有子集构成的集合 $\text{pow}(A)=\{B\mid B\subseteq A\}$。若 $A$ 有 $n$ 个元素，则 $\text{pow}(A)$ 有 $2^N$ 个元素。该性质的证明见下面。

集合的运算之间也存在一些关系，此处不再赘述。

序列

序列，即对象的列表，是另一种将一系列对象组合在一起形成一个整体的结构。序列内的对象也称元素。我们常以 $\lambda$ 代指空序列。

集合与序列都具有聚合性，但有如下几点不同：

• 集合中的元素不可重复，序列中的元素可以重复。
• 集合是无序的，序列是有序的。

我们称长度为 $2$ 的序列为 对。

定义集合的 笛卡尔积 是一个由序列构成的新集合，其中序列的第一个元素来自第一个集合，第二个元素来自第二个集合，以此类推......形式化表示为：

$n$ 个集合 $S$ 的笛卡尔积简记为 $S^n$。

二元关系与函数

二元关系 定义了一个集合 $A$ 的元素到另一个集合 $B$ 的元素之间的关系。一个二元关系由三个部分组成：集合 $A$，称作 域；集合 $B$，称作 陪域；集合 $A\times B$ 的一个子集，称作 图，指示集合 $A$ 与 $B$ 中的哪些元素具有该二元关系。如果域和陪域为同一集合，称其为 齐次二元关系 或 内关系，后续描述一个内关系时，会简单将其描述为定义在某集合上的关系。

我们称关系 $R$ 下 $A$ 的某个子集 $Y$ 的 像 为陪域 $B$ 中所有与 $Y$ 中元素具有二元关系的元素集合。从关系图上， $Y$ 的像即为 $Y$ 中元素所指向的所有陪域 $ B$ 中元素的集合。形式化的来说，

二元关系 $R$ 的 逆关系 $R^{-1}$ 被定义为 $B\to A$ 的关系，使得

在关系图上来看，就是将关系 $R$ 的箭头反过来得到逆关系 $R^{-1}$。对应地，在关系 $R^{-1}$ 下某个集合的像就被称作 逆像。

整个域的像 $R(A)$ 被称作关系 $R$ 的 值域。显然 $R(A)\subseteq B$。

二元关系可以进行复合。设二元关系 $P:A\to B$，$Q:B\to C$，则复合二元关系 $P\circ Q$ 是一个定义在 $A\to C$ 上的二元关系，且

我们接下来介绍一些特殊的二元关系：

• 如果对于域内的每个元素，其像最多只有一个元素，体现在关系图上就是该元素最多有一个出箭头，则这样的关系被称作 函数。
• 如果对于域内的每个元素，其像至少有一个元素，体现在关系图上就是该元素至少有一个出箭头，则这样的关系被称作 全映射。全映射满足 $A=R^{-1}(B)$。
• 如果一个二元关系既是函数又是全映射，即域内的每个元素，其像有且仅有一个元素，体现在关系图上就是每个域内的元素都必定指向且仅指向一个陪域内的元素，则其被称作 全函数。
• 如果对于陪域内的每个元素，其逆像最多只有一个元素，体现在关系图上就是该元素最多有一个入箭头，则这样的关系是 单射 的。
• 如果对于陪域内的每个元素，其逆像最少只有一个元素，体现在关系图上就是该元素最少有一个入箭头，则这样的关系是 满射 的。满射满足 $R(A)=B$。
• 如果对于域内的每个元素，其像有且仅有一个元素；且陪域内的每个元素，其逆像也有且仅有只有一个元素，其体现在关系图上就是每个域内的元素都必定指向且仅指向一个陪域内的元素，陪域内所有元素都被一个域内的元素所指向，则这样的关系是 双射 的，这种关系又称作 一一对应关系。双射对于计数十分有用，因为两个存在双射关系的集合一定具有相同的元素数量，下面将详细解释这点。

关于二元关系的其它关于性质与特殊的二元关系的讨论，请见 10. 有向图与偏序。

有限集的基数

我们称集合 $A$ 含有的元素数量为 基数，记作 $|A|$。

一些特殊的二元关系揭示了域与陪域的元素个数所满足的关系。具体而言，设 $A$ 与 $B$ 为有限集，则有如下定理成立：

• 若存在一个从 $A$ 到 $B$ 的 双射，记作 $A\text{bij}B$，则 $|A|=|B|$。

• 若存在一个从 $A$ 到 $B$ 的 满射函数，记作 $A\text{surj}B$，则 $|A|\ge |B|$。

• 若存在一个从 $A$ 到 $B$ 的 单射、全映射 关系，记作 $A\text{inj}B$，则 $|A|\le |B|$。

对于多个集合，由上述结论可得到以下关于多个集合基数关系的推论：设 $A$，$B$，$C$ 为集合，

• 若 $A\text{bij}B$ 且 $B\text{bij}C$，则 $A\text{bij}C$，即 $|A|=|C|$。
• 若 $A\text{surj}B$ 且 $B\text{surj}C$，则 $A\text{surj}C$，即 $|A|\ge |C|$。
• 若 $A\text{surj}B$ 且 $B\text{surj}A$，则 $A\text{bij}B$，即 $|A|=|B|$。

这三条推论不仅对有限集成立，对无限集同样成立。关于无限集的相关内容见 8. 无限集。

利用这些关系，就可以尝试通过建立集合之间的双射关系，从而将计算一个集合的基数化为计算一个更易计数的集合的基数的问题。