WTF zk教程第0讲：集合

抽象代数（Abstract algebra），又名近世代数，是现代数学的重要基础之一，它研究群、环、域这三种基本的代数结构的结构理论。zk理论中大量使用到了抽象代数的概念，因此学习者应该熟悉抽象代数的基础知识。

在这一讲，我们主要学习抽象代数的基础：集合论。

1. 集合的定义

集合是由不同对象组成的整体（collections of objects）的数学模型，这些对象被称为集合的元素（elements）。整数（Integers）、有理数（Rational numbers）、实数（Real numbers）、复数（Complex numbers）、矩阵（Matrices）、多项式（Polynomials）、多边形（Polygons）以及其他的很多概念实质上都是集合。

常用集合缩写： $\mathbb{N}$ 表示全体自然数集合（Natural numbers）， $\mathbb{Z}$ 表示全体整数集合（"Zahl" is Integer in German）， $\mathbb{Q}$ 表示全体有理数集合（Rational numbers）， $\mathbb{R}$ 表示全体实数集合（Real numbers）， $\mathbb{C}$ 表示全体复数集合（Complex numbers）

我们将集合中元素数目定义为集合的基数（cardinality）。当基数为有限大，则称之为有限集合，否则为无限集合。有一类特殊的集合，它不包含任何元素，称之为空集 $\emptyset$ ，其特点是：

• 空集是任何非空集合的真子集；
• 空集是任何集合的子集。

2. 集合的特点

确定性：给定一个集合 $S$ ，任给一个元素 $a$ ，该元素属于该集合 $a\in S$ 或者不属于该集合 $a\notin S$ ，二者必居其一，不允许有模棱两可的情况出现。

互异性：一个集合中，任何两个元素都认为是不相同的，即每个元素只能出现一次。有时需要对同一元素出现多次的情形进行刻画，可以使用多重集，其中的元素允许出现多次。

S = {1, 1, 2}
for elem in S:
    print(elem)
# 1
# 2

无序性：一个集合中，每个元素的地位都是相同的，元素之间是无序的。集合上可以定义序关系，定义了序关系后，元素之间就可以按照序关系排序。但就集合本身的特性而言，元素之间没有必然的序。

S = {'0xaa', 123, 'a', 0.123}

# 无序性
for elem in S:
    print(elem)
# 0xaa
# 0.123
# 123
# a

3. 集合间的基本关系

子集与超集

考虑整数集和有理数集这两个集合，二者之间似乎存在某种关系：所有的整数都是有理数，但并非所有的有理数都是整数。我们定义：整数集是有理数集的子集（subset），相反地，有理数集是整数集的超集（superset）。

注意： $A$ 是 $B$ 的子集并非要求 $A$ 严格小于 $B$ 。因此可以说整数集是整数集的子集。当 $A$ 是 $B$ 的子集且 $A$ 严格小于 $B$ ，那么可以进一步的说： $A$ 是 $B$ 的真子集（proper subset）。

交并集

• 交集：由属于 $A$ 且属于 $B$ 的相同元素组成的集合，记作 $A\bigcap B$ （或 $B \bigcap A$ ）。
• 并集：由所有属于集合 $A$ 或属于集合 $B$ 的元素所组成的集合，记作 $A\bigcup B$ （或 $B\bigcup A$ ）

二者遵循交换律、结合律和分配律。

相等/等价

如果两个集合中包含的元素完全一致（无需考虑顺序），那么则称二者等价。用严格的数学语言表示为： 如果 $A \subseteq B \wedge B \subseteq A$ ，则 $A=B$ 。

基数

如前面所述，我们把集合中元素的数目定义为基数。一般而言，有限集合的基数才是有意义的，我们记作： $|A|$ 。对于无限集合，如果是整数集合这种，我们可以文字上把元素表达出来，称之为可数无限；而如果是复数这种，我们无法对其计数，因此称之为不可数无限。

4. 有序对

集合的元素是无序的，有序对（order pairs）是从集合中产生的一种新的数据结构。在编程世界中，程序员更愿意称其为元组（tuple）。

那么如何在无序的集合中生成有序对呢？具体实现方式是将元组 $(a, b)$ 表示为集合形式 $\{a, \{b\}\}$ 。注意到，这样的集合的元素要么是字母，要么是基数为1的集合。于是，我们说 $(a, b)\neq(b,a)$ ，因为 $\{a, \{b\}\}\neq\{b,\{a\}\}$ 。

注意有序对（元组）的元素数目可以是任意个。

5. 笛卡尔积

定义两个集合 $A$ 和 $B$，我们可以定义另一个集合 $C$ ，其中 $C$ 的元素是第一个元素来自于 $A$ ，第二个元素来自于 $B$ 的有序对。这样的集合我们称之为笛卡尔积（Cartesian product）。

笛卡尔积不遵循交换律。

6. 函数

借助笛卡尔积这个运算，我们就可以从数学角度上定义函数（function）。比如我们需要定义函数 f，满足 $f(1)=x,f(2)=y, f(3)=z$ ，那么只需要定义两个集合 $\{1, 2, 3\}, \{x, y, z\}$ ，二者进行笛卡尔积，并取结果的子集即可得到目标映射关系 $(1, x), (2, y), (3, z)$。

因此，在集合论中，函数就是域集（domain set）和共域集（codomain set）的笛卡尔积的子集。换句话说，只要我们有定义域集合和值域集合，二者的笛卡尔积能够得到从定义域到值域的所有可能的映射（mapping）关系，函数定义为这些映射关系的一个子集。

数学家很少关心可计算性。即数学家定义了两个集合之间的一个函数，但是这个函数是怎样计算的（具体的数学公式），数学家是不关心的。

程序员反之，他们认为：所有的函数都是可计算的，有具体数学公式的。

在大多数情况，函数这个说法和映射是等价的。当然，如何定义映射（函数）决定了其可用性。比如我们把所有东西映射为 0 ，这当然是合理的，但这种映射基本没有可用性可言。

选择公理（Axiom of Choice）：一组非空集合的笛卡尔积是非空的。

7. 单射、满射、双射

我们定义函数为两个集合笛卡尔积的一个子集，但是这个子集并不是任意的，需要对其进行限制：给定一个输入，函数的输出是唯一的。

有三种映射方式满足函数的要求：

• 单射（injective function）：值域的元素最多对应到一个定义域的元素（也称之为原像，preimage）。值域的元素可以不对应任何定义域中的原像。但是如果定义域中原像对应了同一个值域元素，那这个函数就不满足单射。
• 满射（surjective function）：值域的元素至少对应一个定义域的元素。如果存在值域的某个元素没有对应的原像，那么函数就不满足满射。
• 双射（bijective function）：当且仅当函数既满足单射、又满足满射的情况下，称函数是双射的。

对于上述映射，最重要的是如何定义定义域（domain）和值域（codomain），不同的定义域和值域会产生不一样的映射。

双射和满射在讨论同构和同态概念时也十分重要，请务必记住这些基础概念定义。

8. 关系

关系（Relation）是一个非常微妙的概念，当阅读 ZKP 相关论文时你会经常看到这一概念。其实在上述描述中我们已经接触到了关系，比如交并集、子超集、相等等都是集合之间的关系。

但从数学上讲，关系被定义为：“两个集合的笛卡尔积取子集”。不难发现这个定义和函数（或者映射）的定义别无二致。

由于涉及到两个集合之间确定的关系，我们也称之为二元关系，这在之后群、环、域的理论学习中会继续提及。