集合,关系,函数的概念

摘要: 集合、关系、函数

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

此前我们系统第学习了组合数学，详细内容见下面这些文章：

• 组合数学1-排列组合
• 组合数学2-母函数,递推关系
• 组合数学3-特殊计数序列,指数型母函数
• 组合数学4-容斥原理,鸽巢原理
• 组合数学5-群论
• 组合数学6-polya计数

本文我们整理一些此前没有提到但还比较有用的概念，包括集合、关系、函数。参考《组合数学》冯荣权 $1-1。

$1 集合

集合, 元素

集合和元素在组合数学中是不加严格定义的概念。

将某些确定的能够区分的对象汇合在一起形成一个整体，这个整体是集合，组成集合的这些对象，为元素。

多重集

元素可以重复出现的集合，$\{a_{1}^{n_{1}}, a_{2}^{n_{2}}, …, a_{k}^{n_{k}}\}$。

集合的基数，n-集合

集合 A 有 n 个元素，称 A 的基数为 n，记为 $|A| = n$。

若 $|A| = n$，则 A 为 n-集合。

幂集

A 为 n-集合，A 的所有子集构成的集合为 A 的幂集，记为 P(A)，$|P(A)| = 2^{n}$。

图

图是一个二元组，记为 $G=(V, E)$，其中 V 是集合，里面的元素称为顶点，E 为 V 的所有 2-子集组成的集合的一个子集，称为边集。

划分

若 A 的非空子集和的集合 $\mathit{P} = \{A_{1}, A_{2}, …, A_{k}\}$ 满足：

$$A = \bigcup\limits_{i=1}\limits^{k}A_{i} \quad\quad 且 \quad\quad A_{i} \cap A_{j} = \varnothing (i \neq j)$$

则 P 为集合 A 的一个划分。

Cartesion 积

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

当 $|A| = n, |B| = m$，有 $|A \times B| = |n \times m|$。

---

$2 关系

二元关系

A 到 B 的二元关系，记为 $R: A \rightarrow B$。定义为 $A \times B$ 的一个子集。

当 $|A| = n, |B| = m$，A 到 B 的二元关系有 $2^{mn}$ 个。

若 $a \in A, b \in B$ 且 $(a, b) \in R$，则 a, b 具有二元关系 R。

定义域，值域

对于二元关系 $R: A \rightarrow B$。

定义域为 $\{a \in A | \exists b \in B, (a, b) \in R\}$。

值域为 $\{b \in B | \exists a \in A, (a, b) \in R\}$。

像，原像

二元关系 $R: A \rightarrow B$。

对于 $a \in A$，a 的像为 $R(a) = \{b \in B|(a, b) \in R\}$。

对于 $b \in B$，b 的原像为 $R^{-1}(b) = \{a \in A|(a, b) \in R\}$。

反关系

$$R^{-1} = \{(b, a) | (a, b) \in R\}$$

自反，对称，传递

如果 $R: A \rightarrow A$，称 R 是自反的。

如果 $\forall a \in A, (a, a) \in R$，称 R 是对称的。

如果 $\forall (a, b) \in R, (b, a) \in R$，称 R 是反对称的。

如果 $(a, b) \in R, (b, c) \in R \Rightarrow (a, c) \in R$，称 R 是传递的。

等价关系

若 A 上的二元关系 R 满足自反，对称，传递，称 R 是 A 上的等价关系。

对于等价关系 R，若 $(a, y) \in R$，称 x 与 y 等价，记为 $x \sim y$。

等价类

R 为 A 上的等价关系。$\forall a \in A$， a 的像 $R(a) = \{b \in B|(a, b) \in R\}$ 称为包含元素 a 的等价类。

划分与等价关系

• A 上的等价关系 R 的等价类为集合 A 的一个划分。
• A 的一个划分 $\mathit{P}$ 也可得到 A 的一个等价关系 R $(a, b) \in R$ 当且仅当 a,b 在 $\mathit{P}$ 的某个元素中。

---

$3 函数

映射

f 是 A 到 B 的二元关系。若 $|f(a)| = 1, \forall a \in A$ 则称 f 是 A 到 B 的映射。

当 $|A| = n, |B| = m$，A 到 B 的二元关系有 $n^{m}$ 个。

单射，满射

对于映射 f：

• 若 $\forall a_{1} \neq a_{2} \in A$ 都有 $f(A_{1}) \neq f(a_{2})$，称f 为单射。
• 若 $\forall b \neq B$ 都有 $f^{-1}(b) \neq \varnothing$，称f 为满射。

双射

对于映射 f，如果 $f^{-1}$ 也是映射，则 f 为双射。

f 为双射当且仅当 f 即是单射又是满射。

如果 A, B 为基数相同的有限集。f 为 A 到 B 的映射，则 f 为单射当且仅当 f 为满射。

---