组合学 [1]

本篇内容

• 集合的概念
• 有限集合和无限集合
• 函数（映射）
• 单射， 满射，双射

---

集合

1. 概念

集合是一组无序^[1]的元素，可以用花括号表示。$a \in A$ 表示元素 $a$ 属于集合 $A$，而 $a \notin A$ 表示元素 $a$ 不属于集合 $A$。空集 $\emptyset$ 是一个没有任何元素的集合，而全集则包含所有可能的元素。

两个集合相等（$A=B$）当且仅当它们包含相同的元素。

如果一个集合 $A$ 中的所有元素都属于另一个集合 $B$，则称 $A$ 是 $B$ 的子集（$A \subseteq B$）。

如果 $A$ 是 $B$ 的子集且 $A \neq B$, 则称 $A$ 是 $B$ 的真子集（𝐴⊂𝐵）。

两个或多个集合可以进行并运算（𝐴∪𝐵），结果为一个新的包含所有原始集合中元素的新结婚。也可以进行交运算（𝐴∩𝐵），结果为一个新的只包含同时属于所有原始结婚中元素的新结婚。

补运算（$\overline{A}$）表示由不属于 𝐴 但属于全局域中其他元素组成的新集合。

2. 有限和无限

• 如果集合 $A$ 中的元素个数是有限的，则称其为 有限集合 。

• 相反地，如果集合 $A$ 中的元素个数是无限的，则称其为 无限集合 。

3. 分割

一个集合的分割（partition）是指把该集合分成若干个非空的子集，使得这些子集的并集就是原集合本身，而且这些子集两两之间没有交集。也就是说，每个子集都是原集合的一个独立部分，所有子集之间互相独立，且它们的并集就是原集合。

例如，假设集合𝐴包含元素 $\{1,\ 2,\ 3,\ 4,\ 5,\ 6\}$ 。一个可能的分割就是$\{\ \{1,\ 4\},\ \{2,\ 5\},\ \{3,\ 6\}\ \}$ 。这个分割把集合 $A$ 划分成了三个非空子集，每个子集都没有交集，且它们的并集就是原集合 $A$ 。

注意，一个集合可能有多个不同的分割方式。

---

函数（映射）

1. 概念

函数（或映射）将一个集合中的元素映射到另一个集合中的元素。函数的定义通常由三个部分组成：定义域 $A$、值域 $B$ 和映射规则 $f$ 。其中中，集合 $A$ 表示函数的定义域；集合 $B$ 表示函数的值域；而映射规则就是将 $A$ 中的每个元素唯一地映射到 $B$ 中的元素，确保函数的一致性和确定性，因为对于每个输入，函数只能产生唯一的输出。

例如，考虑一个函数 $f$，它将实数集合 $\mathbb{R}$ 中的每个元素 $x$ 映射到实数集合 $\mathbb{R}$ 中的 $x$ 的平方。在这种情况下，$\mathbb{R}$ 是函数 $f$ 的定义域，而映射规则是 $f(x) = x^2$。

2. 分类

函数的有三类，它们分别是单射（injective）、满射（surjective）和双射（bijective）。

• 单射（injective）

  对于定义域中的任意两个不同元素 $a$ 和 $b$，如果它们在函数中映射到了相同的值，即 $f(a) = f(b)$，则 $a$ 和 $b$ 必须相等，即 $a = b$。换句话说，函数的不同元素映射到不同的值。这意味着，函数没有重复的值。

• 满射（surjective）

  对于值域中的任意一个元素 $b$，都可以在定义域中找到至少一个元素 $a$，使得 $f(a) = b$。换句话说，函数的所有可能的值都被映射到了值域中。这意味着，函数覆盖了整个值域。

• 双射（bijective）

  简单来说就是一一对应的映射同时具有单射和满射性质的函数，也就是说，对于定义域中的任意两个不同元素 $a$ 和 $b$，如果它们在函数中映射到了相同的值，即 $f(a) = f(b)$，则 $a$ 和 $b$ 必须相等，同时对于值域中的任意一个元素 $b$，都可以在定义域中找到唯一的元素 $a$，使得 $f(a) = b$。这意味着函数的每个元素都有唯一的对应元素，且函数的所有可能的值都被映射到了值域中，因此双射函数具有一一对应的关系。

---

1. 1.虽然在表示的时候一般会按某种顺序表示 ↩