为什么又来一篇集合论教程？

本文的目标读者是那种除非看到直接的用例，否则不关心抽象数学的人。他们想要获取所需的精华部分，然后继续前进。本文正是迎合这部分读者的需求。

我们的最终目标是理解抽象代数，因为抽象代数中有很多完全称得上“有用”的概念，但抽象代数严重依赖于集合论。

我们在这里的目标是走一条从集合论到抽象代数的最直接路径，以便我们能理解将要处理的所有术语和概念。

工程师通常对收集抽象概念或证明定理不感兴趣，他们想要交付产品，同时对主题有足够深入的理解，以免在无意中制造 bug 或导致效率低下。获取那些对这一追求没有直接帮助的知识被视为浪费时间。

为了针对这一目标进行优化，我刻意省略了集合论中对理解抽象代数相关方面没有直接用处的任何内容。因此，这份关于集合论的资料在设计上就不是大而全的。

零知识证明中学习集合论的动机

本教程的目的是让你牢牢掌握在集合论语境下什么是二元运算符（binary operator）。

二元运算符的概念是 Group Theory 的核心，而群论在零知识证明中无处不在。

我们的处理方式并不严谨

些许数学家可能会对我在这里不讨论集合论的公理感到震惊。这是特性（feature），不是缺陷（bug）。如果你想要某样东西的证明，去问 Google 或聊天机器人（或者更好的是，你自己推导出来）。这里讨论的概念在一个多世纪以来已经被严谨地证明得彻头彻尾了。

集合论并不困难（至少如果你跳过编写证明的话，初次进行集合论证明可能会异常困难）。你可能已经在直觉上理解了集合论，并且几乎肯定在代码中使用过集合，也许是为了快速消除数组中的重复项。然而，我们需要用语言来表达这种直觉，并将我们直观的理解明确化。

学习抽象数学就像学习人类语言。你可以学习词汇（单词指代什么）和语法（它们如何以有效的方式组合在一起）。用这个比喻来说，我们将重点放在词汇而不是语法上。这有充分的理由。

如果你走进外国的一家商店，问出类似于“面包要给我买在哪里？”这样的话，即使你的语法错得离谱，店员也能帮助你。但是如果你精通语法却不懂词汇，你的知识就会变得毫无用处。你可以组织一个完美的句子，但如果你不能简明扼要地说出“面包”和“买”，你的商店之旅就不会成功（我并没有发明这个比喻，可惜我不记得第一次是在哪里看到的了）。

因此，我们几乎不会触及语法（证明和定理），而是强调抽象数学的词汇（这对于在这个异国他乡游刃有余非常有用）。

某些类型的知识只能通过经验获取，而不能通过解释来获得。

因此，你应该完成本文中的练习。别担心，你不需要写证明，只是为了确保你真正内化了刚刚阅读的内容。

不要被本文相对简短的篇幅所欺骗。如果你真的去做了那些练习，至少需要花一个下午（或者两三个下午）才能学完。如果某个部分让你感到困惑，请查阅互联网或询问聊天机器人，寻找该子主题的替代解释。

集合的定义

集合（set）是被明确定义的对象的聚集。这些对象可以是任何东西，而我们从集合论中学到的规则都适用于它们。

整数、有理数、实数、复数、矩阵、多项式、多边形以及许多其他事物都有一个共同点：它们都是集合。

有一条明确定义的规则决定了某物是否为该集合的成员。我们不会深入探讨，但很明显，多边形不是多项式，多项式不是矩阵，等等。

集合允许为空。我们称之为空集（empty set）。

根据定义，集合不包含重复的项。例如，$\set{a, a, b}$ 实际上就是 $\set{a, b}$。

练习： 假设你对整数有正确的定义。请创建一个定义明确的有理数集合。

超集与子集

当我们审视整数和有理数时，它们之间似乎存在某种联系。具体来说，所有整数都是有理数，但并非所有有理数都是整数。它们之间的关系是，整数是有理数的子集（subset）。反过来看，有理数是整数的超集（superset）。

子集不需要严格小于它所属的集合。例如，说整数集是其自身的子集是完全合理的。

整数和有理数之间关系的精确定义是真子集（proper subset），也就是说，存在不是整数的有理数。

练习： 定义整数、有理数、实数和复数之间的子集关系。

练习： 用子集的概念定义超越数集合与复数集合之间的关系。它是一个真子集吗？

集合相等

如果集合包含相同的元素，则定义它们是相等的，无论这些元素出现的顺序如何。例如，$\{4, 2, 5\}$ 与 $\{2, 5, 4\}$ 是同一个集合。在对集合进行形式化证明时，我们会说如果 $A$ 是 $B$ 的子集，并且 $B$ 是 $A$ 的子集，那么 $A = B$。或者用更数学化的符号表示：$A = B \iff A \subseteq B$ 且 $B \subseteq A$。它的读法是 $A = B$ 当且仅当 $A$ 是 $B$ 的子集，且 $B$ 是 $A$ 的子集。

基数 (Cardinality)

在我们上面的一些例子中，整数、有理数和其他类似集合包含了无限数量的元素。但是，我们也可以以有限的方式定义集合，例如数字 $\set{0,1,2,3,4,5,6,7,8,9,10}$。上面这个集合的基数为 $11$。如果 $A = \set{5,9,10}$，那么 $|A| = 3$，其中 A 两边的垂直双竖线表示基数。

集合论中存在不同层级的无限。例如，实数比整数有无穷多个更多。具体来说，我们说整数是可数无限的，因为你真的可以将它们数出来。但实数是不可数无限的，根本无法开始数。

练习： 使用上面相等的正式定义，论证如果两个有限集合具有不同的基数，它们就不可能相等。（对无限集合论证这一点稍微棘手一些，所以我们跳过它）。

花哨的黑板粗体字母

因为“作为集合的整数”和“作为集合的实数”被频繁使用，所以为此存在看起来很吓人的数学速记符号。

• 符号 $\mathbb{N}$ 表示自然数集合 $(1,2,3,…)$。它肯定不包含负数，但它是否包含零取决于你和谁讨论。
• 符号 $\mathbb{Z}$ 表示所有整数的集合（因为“zahlen”在德语中是整数的意思）
• 符号 $\mathbb{Q}$ 表示所有有理数的集合。有理数是可以表示为两个整数（分子 $p$ 和非零分母 $q$）的商或分数的数字，即 $\frac{p}{q}$。从这个定义中，很容易看出符号 $\mathbb{Q}$ 的来源。
• 符号 $\mathbb{R}$ 表示所有实数的集合，因为 R 代表 real（实数）。显然。
• 符号 $\mathbb{C}$ 表示所有复数的集合，原因同样显而易见。

有时人们把 $\mathbb{R}^2$ 写成包含两个实数的向量，所以 $a \in \mathbb{R}^2$ 意味着 $a$ 是一个二维向量。我建议用第二种方式写，因为它更简洁，并且也会让你看起来更聪明。

有序对

虽然集合没有固有的顺序，但从集合的集合中可以衍生出一种叫做有序对（ordered pair）的新数据结构。例如，$(a, b)$ 是一个有序对，而 $\{a, b\}$ 是一个集合。

我们程序员通常把有序对看作是元组。我们说两个有序对相等，就和我们说两个元组相等是同一个意思。

我们如何从本质上无序的东西中创造出顺序呢？

关键的实现细节是我们以集合形式将 $(a, b)$ 表示为 $\set{a, \set{b}}$。我们可以这样做，因为我们可以将集合定义为包含字母或者包含一个字母的基数为一的集合。这就是为什么我们可以说 $(a, b) \neq (b, a)$，因为 $\set{a, \set{b}} \neq \set{b, \set{a}}$。我们将不再纠结于这个实现细节。

就像在其他编程语言中一样，我们的有序对可以是任意长度的；例如，$(a,b,c,d)$ 是有效的。我们还可以将包含有序对的有序对编码为 $((a, b), c)$，这在稍后会很有用。

笛卡尔积

因为集合是明确定义的，我们可以定义这样一个集合：将一个集合中的每个元素与另一个集合中的元素组合成一个有序对。例如，如果 $A = {1,2,3}$ 且 $B = {x, y, z}$，那么笛卡尔积 $A \times B$ 就是集合 $\{(1, x), (1, y), (1, z), (2, x), …, (3, z)\}$。这也可以用表格表示：

笛卡尔积不满足交换律，接下来的练习将证明这一点。交换律意味着在一般情况下 $B \times A = A \times B$。

练习： 使用上面的定义计算 $B \times A$ 的笛卡尔积。

笛卡尔积的子集构成函数

如果我们想说我们有一个函数

（我挑了这个不按顺序排列的例子，让它更有趣一点）。

我们可以定义一个描述这种映射的集合。我们只需要从上面的笛卡尔积中取出一个子集，使其包含 $(1, y)$、$(2, z)$ 和 $(3, x)$。

用集合论的术语来说，函数 是定义域集合与陪域集合笛卡尔积的子集。

对于我们将 $1$ 映射到 $y$、$2$ 映射到 $z$、$3$ 映射到 $x$ 的示例，笛卡尔积的子集在下方以粗体显示：

因此，我们的函数由集合 $\{(1, y), (2, z), (3, x)\}$ 定义。

为了定义一个函数，我们需要起始的集合和结束的集合。我们将这两个集合进行笛卡尔积操作，这就得出了从输入集合到输出集合的所有可能赋值。然后我们取笛卡尔积的子集，按照我们想要的方式定义函数。当处理像整数这样的无限集合时，我们并不会因为无法显式枚举所有有序点而感到困扰。

函数不一定是可计算的

需要特别注意的一点是，数学家很少关心可计算性（computability）。函数是集合之间的映射。这个函数是如何被计算的，或者说用一台合理的计算机是否有可能计算出它，并不是大多数数学家所关心的问题。

这正是程序员有时会被绊倒的地方。他们往往只把函数看作是可以用几行代码高效计算的东西。虽然这很有用，但这限制了我们对函数一般性质的理解。

我强调这一点的原因为，在零知识证明中，我们将要处理的函数，比单纯地向函数传入一个参数并获取返回值的层次要“高”得多。我们需要能够理解函数的“宏大图景”。它们是从一个集合到另一个集合的映射。 而集合之间的映射是通过选取它们笛卡尔积的子集来实现的。

具有不同定义域和陪域的函数

具体来说，我们将要在整数、多项式、矩阵、一维椭圆曲线，然后是另一维椭圆曲线等等之间跳跃。

试图概念化这些过程会让你非常头晕，除非你在基础层面上理解了：根据集合论，我们被允许随心所欲地定义这些跳跃！

当然，我们如何映射这种跳跃将对其有用性产生巨大的影响。如果我们把所有东西都映射到零，那是一个有效的映射，但并不是很有用。

我希望你尽早明白，当我们在这些宇宙间这样穿梭时，我们并没有在做任何奇怪的事情。

归根结底，我们被允许选取任何两个我们喜欢的集合，通过它们的笛卡尔积创建一个新集合，从这个有序对集合中取出一个子集，然后瞧，我们就拥有了一个映射。

选择公理

如果你在想“嘿等一下，我可以只挑一个子集然后随意定义这个函数吗？”有这种疑问的不只你一个。如果你想深究这个兔子洞，我们一直以来真正讨论的其实是 axiom of choice，尽管它的定义看起来毫无争议，但它一直都是争议的焦点：

一族非空集合的笛卡尔积是非空的。

笛卡尔积的子集构成函数：示例

让我们使用向下取整函数（floor function）定义一个非负实数（大于或等于零）和非负整数（大于或等于零）之间的映射。向下取整函数简单地去除了一个数字的小数部分。我们无法展示所有的实数（或整数），但我们可以画一个草图。

当我们求 $\mathbb{R}\times\mathbb{Z}$ 并取一个子集时，我们只需挑选那些与从实数中提取向下取整元素相对应的有序对。在表格中没有显示的有序对，即是不在定义该映射的子集中的有序对。例如，$2$ 不是 $500.3$ 向下取整的结果，因此不包含有序对 $(500.3, 2)$。

练习： 定义一个从整数 $\{1,2,3,4,5,6\}$ 到集合 $\{\text{even}, \text{odd}\}$ 的映射（函数）。

练习： 求多边形集合 $\{\text{triangle}, \text{square}, \text{pentagon}, \text{hexagon}, \text{heptagon}, \text{octagon}\}$ 与整数集合 $\{0,1,2,…,8\}$ 的笛卡尔积。定义一个映射，使多边形映射到表示其边数的整数。例如，有序对 $(\Box, 4)$ 应该在子集中，但 $(\bigtriangleup, 7)$ 不应在笛卡尔积的子集中。

练习： 定义正整数和正有理数之间的映射（显然不需要全部映射）。这是可能将整数完美映射到有理数上的。提示：画一个表格来构造有理数，其中列为分子，行为分母。在查看答案之前，请在这个问题上苦思冥想至少 15 分钟。

笛卡尔积的有效子集与无效子集。

我们如何选择子集有一个重要的限制。例如，下面选取自笛卡尔积 $\{1,2,3\}$, $\{p,q,r\}$ 的子集是无效的，因为 $1$ 映射到了 $p$，且 $1$ 也映射到了 $q$。当用笛卡尔积定义一个函数时，同一个定义域元素不能映射到两个不同的陪域元素上。

一个集合与其自身的笛卡尔积

可以毫无意外地发现，你不仅可以在 $A$ 和 $B$ 之间做笛卡尔积，也可以在 $A$ 和 $A$ 之间做笛卡尔积。这仅仅是将一个集合映射到其自身。

这是更抽象形式的第一步，即我们在传统上所认为的关于整数的函数。

例如，$y=x^2$（正整数上的）可以在集合论语境中可视化为 $\mathbb{Z}\times\mathbb{Z}$ 的子集：

集合关系

“取笛卡尔积的子集”这个短语非常普遍，以至于我们专门有一个词汇来描述它。那就是关系（relation）。

关系可以是出自一个集合与其自身的笛卡尔积，或者是出自一个集合与另一个集合的笛卡尔积。如果我们有两个集合 $A$ 和 $B$（不失一般性，$B$ 可能等于也可能不等于 $A$），并且我们取 $A \times B$ 的一个子集，如果在该 $A \times B$ 的子集中存在一个有序对 $(a, b)$，我们就可以说 $A$ 中的元素 $a$ 关联到 $B$ 中的元素 $b$。

在 $y=x^2$ 这个例子中，$X$ 中的 $2$ 关联到 $Y$ 中的 $4$，但 $X$ 中的 $3$ 并不关联到 $Y$ 中的 $6$。

集合论术语中的“二元运算符”

二元运算符是从 $A \times A \rightarrow A$ 的一个函数。基本上，我们从 $A \times A$（$A$ 与其自身的笛卡尔积）中取出所有可能的配对，并将它映射到 $A$ 中的一个元素。换句话说，它是 $A \times A$ 与 $A$ 之间的一个集合关系。

下面是一些二元运算符的基础示例：

• 整数加法：从整数集合中任意取出两个元素并将它们加在一起，你得到了整数集合中的另一个元素。在这里，我们将一对整数映射到了另一个整数。例如，$(1, 3)$ 映射到 $4$。
• 有理数乘法：取任意两个有理数并将它们相乘，你得到了另一个有理数。例如，$(3.5, 2.0)$ 映射到 $7.0$。
• 字符串拼接：从字符串集合中取任意一对字符串并将它们拼接起来，结果是另一个字符串。例如，$(\text{Rare},\text{Skills})$ 映射到 $\text{RareSkills}$。与上述两个例子不同的是，配对中字符串的顺序会改变这对字符串最终所映射到的字符串。例如，$(\text{Rare},\text{Skills})$ 映射到字符串 $\text{RareSkills}$，但 $(\text{Skills},\text{Rare})$ 则映射到字符串 $\text{SkillsRare}$。

构造一个集合论中的二元运算符

让我们以集合 $\set{0,1,2}$ 及对 $3$ 取模加法的二元运算符为例。首先，我们求该集合与其自身的笛卡尔积（即 $A \times A$）：

然后我们求这个新的配对集合与原始集合的笛卡尔积

接着从中提取子集以定义我们对 $3$ 取模加法的二元运算符：

观察发现，如果我们对“内部元组”中的值做模 $3$ 加法，我们就得到了元组中的第三个数字。例如，在最底下一行，我们可以看到 $2 + 2 = 1 \pmod 3$。

函数通常是“存在的”——但可计算性则是另一回事

把函数想象成笛卡尔积的一个子集一开始可能会觉得有些奇怪——特别是因为这种定义并不容易转化为代码。

但 ZK 深受数学家定义的影响，所以把这些词汇揣在兜里备用是大有裨益的。

将函数概念化为一种提取某个集合中元素并返回另一个集合中元素的映射是非常有帮助的。

练习： 挑选一个定义了 $a \times b \pmod 3$ 的有序对子集。

练习： 将我们的集合 $A$ 定义为数字 $\set{0,1,2,3,4}$，并且将我们的二元运算符定义为对 $5$ 取模减法。在表格中定义 $A \times A$ 的所有有序对，然后将该有序对集合映射到 $A$。

一个封闭的（closed）二元运算符接受一个集合中的任何两个元素，并输出同一个集合中的另一个元素。闭包属性很重要，因为它限制了输出必须在同一个集合中。

具体来说，从集合 $A$ 开始，按以下方式构造一个二元运算符：

求一个集合与其自身的笛卡尔积 $A \times A$，并将该有序对集合称为 $P$。

求 $P$ 与 $A$ 的笛卡尔积，并取出其子集，使得 $P\times A$ 被明确定义。

整数上的除法不是二元运算符，因为实际上发生的是，我们求出了 $P = (\mathbb{Z} \times \mathbb{Z})$，然后取 $P \times \mathbb{Q}$ 的一个子集来获得我们的关系。整数上的除法不是封闭的，因为它可以产生有理数。

我们将在椭圆曲线、整数、多项式、矩阵等方面大量处理二元运算符。

当我们确信二元运算符具备某些特定属性时，我们就可以抽象出大量的实现细节。

例如，“相加”椭圆曲线上的点绝不是件微不足道的事，而且其数学原理从一开始就不是很直观。

然而，如果你知道这个二元运算符是封闭的，并且遵循某些属性，那么“加法”是如何实现的就无关紧要了！它只是一种遵循特定规则的映射！

让我们用一个稍微容易引起共鸣的例子。如果你把两个行列式为 $1$ 的方阵相乘，乘积矩阵的行列式也将为 $1$。其证明并不是你脑海中能很快算出来的。但是如果你将其建模为“行列式为 $1$ 的 $3\times 3$ 矩阵集合与乘法二元运算符，并且乘法是封闭的”，那么你就会突然拥有了关于一个你不知道实现细节的系统的大量函数化知识。你知道无论你怎么做，你都会得到一个行列式为 $1$ 的矩阵，而不需要知道原因。

拥有将二元运算符描述为“封闭”的语言使你能够在更高的层面上进行操作，理解各种变换的宏观图景，而不至于陷入实现细节的泥潭。

甚至不需要理解它们是如何工作的，你就能推导运算！当涉及处理像 Elliptic curve bilinear pairings 这种非常深奥的数学时，这是非常有帮助的。

构造有效的二元运算

涉及二元运算符时，我们不允许在将其映射到 $A$ 之前取 $A \times A$ 的子集。二元运算符必须接受集合 $A$ 的所有成员作为其输入。当然，我们必须取 $A \times A$ 和 $A$ 之间有序对的一个子集，因为 $A \times A$ 中的每个配对必须精确映射到一个 $A$。二元运算的结果必须有一个明确的答案。

在 RareSkills 了解更多

抽象代数词汇的实用性正是我们的 zero knowledge course 不回避数学的原因。我们只是确保在开始使用它们之前掌握了基本的词汇。

原载于 2023 年 7 月 25 日