为程序员准备的基础集合论

原文链接：https://www.rareskills.io/post/set-theory

为什么要写这篇集合论教程？

这篇文章的读者群体是那些除非有实际应用场景，否则对抽象数学没兴趣的人。他们只想掌握必要的知识，然后快速进入正题。这篇文章就是为这类读者量身定做的。

具体来说，抽象代数里有很多确实“有用”的概念，但抽象代数高度依赖于集合论。我们的目标是通过集合论找到最快捷的路径进入抽象代数，确保我们能理解其中的术语和概念。

工程师通常不喜欢纯粹收集抽象概念或证明定理，他们更关心如何高效完成项目，同时对相关的知识有足够的理解，避免无意间引入错误或低效。对于他们来说，任何不能直接帮助实现这个目标的知识，都是在浪费时间。

为此，我有意跳过了集合论中那些对理解抽象代数不太直接有用的部分，所以这篇文章并不全面。不过请记住，这是一个系列教程中的一部分，不是对集合论的完整讲解。

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

本教程的重点是让你清楚了解在集合论中什么是二元运算。二元运算的概念是群论的核心，而群论在零知识证明中随处可见。

我们的处理方式并不严谨

有些数学家可能会对我没有讨论集合论的公理感到震惊。但这不是缺点，这是特点。如果你想要某个东西的证明，去问 Google 或 ChatGPT（或者更好的是，自己推导出来）。这里讨论的概念在过去一个多世纪里已经被证明无数次了。

集合论并不难（至少如果你跳过写证明的话，第一次做集合论证明时可能会让人感到极其困难）。你可能已经直观地理解了集合论，并且几乎可以肯定在代码中使用过集合，可能是为了快速消除数组中的重复项。不过，我们需要为这种直觉配上语言，并让我们的直观理解变得明确。

学习抽象数学就像学习一门人类语言。你可以学到词汇（单词指的是什么），也可以学到语法（它们如何以有效的方式组合在一起）。这里我们更注重词汇而不是语法，使用这个类比的话是这样解释的。这是有充分理由的。

如果你在一个外国的商店里，用蹩脚的语法问“面包买给我在哪里？”，店员还是能帮你，尽管你的语法很糟糕。但如果你语法无懈可击却不懂词汇，你的知识是没用的。你可以构造一个完美的句子，但如果你不能准确表达“面包”和“买”的意思，你的购物之行就不会成功（这个类比不是我发明的，但遗憾的是我不记得最初在哪儿看到的了）。

因此，我们几乎不会涉及语法（证明和定理），而是重点强调抽象数学的词汇（这在你游历这个“外国”时非常有用）。

有些知识只能通过经验获得，而不能靠解释。 因此，你应该做这篇文章中的练习题。别担心，你不需要写证明，只是确保你真正内化了你刚刚读到的内容。

不要被这篇文章的相对简短迷惑。如果你真的去做练习题，至少需要一个下午（或者两个，也许三个）来完成。如果某一部分没理解，去网上查找该子主题的其他解释。

集合的定义

集合是一个明确定义的对象集合。它的抽象性在于，这些对象可以是任何东西，而我们从集合论中学习到的规则都适用于它们。整数、有理数、实数、复数、矩阵、多项式、多边形以及许多其他东西的共同点在于，它们都是集合。对于一个集合来说，存在一个明确的规则来决定某个对象是否属于该集合。虽然我们不会深入讨论，但很明显，多边形不是多项式，多项式也不是矩阵，等等。

集合可以是空的，我们称之为空集合。根据定义，集合中不允许有重复项，${a, a, b}$ 实际上是 ${a, b}$。

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

译者注：

数学上，可以表达为两个整数比的数 $(\frac{a}{b}, b \neq 0)$ 被定义为有理数。例如：$\frac{3}{8}$，0.75（可被表达为$\frac{3}{4}$）。即有理数包括整数、有限小数和无限循环小数。

有理数集合的定义可以写为：

$\mathbb{Q} = \left{ \frac{m}{n} \, | \, m \in \mathbb{Z}, \, n \in \mathbb{Z}, \, n \neq 0 \right}$

这里，$\mathbb{Q}$ 表示有理数集合，$\mathbb{Z}$ 表示整数集合。

超集和子集

当我们观察整数和有理数时，似乎可以看到它们之间的某种关系。具体来说，所有的整数都是有理数，但不是所有的有理数都是整数。这两者之间的关系是：整数是有理数的一个子集。反过来，有理数是整数的超集。

子集不一定比它所属的集合严格“更小”。我们完全可以说整数是整数的子集，这并没有问题。

对于整数和有理数之间关系的精确定义是：真子集，也就是说，存在一些有理数不是整数。

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

译者注：

$\mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R} \subset \mathbb{C}$

这表示：整数集合 $\mathbb{Z}$ 是有理数集合 $\mathbb{Q}$ 的子集，有理数集合 $\mathbb{Q}$ 是实数集合 $\mathbb{R}$ 的子集，而实数集合 $\mathbb{R}$ 是复数集合 $\mathbb{C}$ 的子集。

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

译者注：

数学家们将可以表示为代数方程根的数称为代数数，而不能表示为代数方程根的数称为超越数。超越数集合 $\mathbb{T}$ 是复数集合 $\mathbb{C}$ 的一个子集，且是一个真子集，因为并非所有复数都是超越数。复数中既包含代数数，也包含超越数。

因此，这个子集关系可以表示为：

$\mathbb{T} \subsetneq \mathbb{C}$

集合相等

集合被定义为相等，当且仅当它们包含相同的元素，不论顺序。例如，${4, 2, 5}$ 与 ${2, 5, 4}$ 是相同的集合。

在对集合进行形式化证明时，我们说如果集合 $A$ 是 $B$ 的子集，且集合 $B$ 也是 $A$ 的子集，那么 $A = B$。用更加数学的符号表示为：

$A = B \iff A \subseteq B \ \text{and} \ B \subseteq A$

这意味着，如果 $A$ 是 $B$ 的子集，且 $B$ 是 $A$ 的子集，那么 $A$ 和 $B$ 是相等的。

基数（Cardinality）

在我们前面的例子中，整数、有理数等的数量是无限的。然而，我们也可以用有限的方式定义集合，例如数字 ${0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}$。这个集合的基数是11。如果 $A = {5, 9, 10}$，则 $|A| = 3$，其中围绕 $A$ 的两个竖线表示集合的基数。

集合论中有不同层次的“无限”。例如，实数的数量远远多于整数的数量。具体来说，我们说整数是可数无限的，因为你可以一个一个地数出来。但对于实数，没有办法开始数，因为它们是不可数无限的。

练习： 使用集合相等的正式定义，证明如果两个有限集合的基数不同，它们不能相等。（对于无限集合的证明更复杂，所以这里我们略过。）

译者注：

集合相等的定义表明，两个集合 $A$ 和 $B$ 相等，当且仅当它们包含完全相同的元素。形式上，如果 $A = B$，则 $A \subseteq B$ 且 $B \subseteq A$。

基数是集合中元素的数量，记为 $|A|$ 表示集合 $A$ 的基数。如果两个有限集合的基数不同，意味着它们的元素数量不同。因此：

假设 $|A| \neq |B|$，即集合 $A$ 和 $B$ 的元素数量不同。根据集合相等的定义，若 $A = B$，则 $A$ 和 $B$ 必须包含相同的元素，且它们的基数也必须相同。然而，我们已知 $|A| \neq |B|$，所以 $A \neq B$。

因此，通过集合相等的定义可以证明：如果两个有限集合的基数不同，它们不能相等。

Fancy blackboard letters （数学中的特殊字体符号）

由于“整数集”和“实数集”在数学中经常使用，所以有一种看起来吓人的数学速记符号来表示它们：

• 符号 $\mathbb{N}$ 表示自然数集 ${1, 2, 3, ...}$。它肯定不包括负数，但是否包括 $0$ 取决于你和谁交谈。
• 符号 $\mathbb{Z}$ 表示所有整数集（因为“zahlen”在德语中表示整数）。
• 符号 $\mathbb{Q}$ 表示所有有理数集（我记住它是分子和分母的商(quotient)）。
• 符号 $\mathbb{R}$ 表示所有实数集，因为 R 代表 real（实数）。
• 符号 $\mathbb{C}$ 表示所有复数集，原因同样显而易见（C 是 complex 首字母）。

有时人们会写 $\mathbb{R}^2$ 来表示两个实数的向量，因此 $a \in \mathbb{R}^2$ 表示“a”是一个二维向量。我推荐用$a \in \mathbb{R}^2$书写，因为它更简洁，也让你显得更聪明。

有序对

尽管集合本身是无序的，但通过集合可以产生一种叫做有序对的新数据结构。例如，$(a, b)$ 是一个有序对，而 ${a, b}$ 是一个集合。程序员通常将其称为元组（tuple）。我们说两个有序对相等的方式与说两个元组相等的方式相同。如何在无序的集合中创建顺序呢？有序对的实现细节是，我们可以将 $(a, b)$ 表示为集合 ${{a}, {a, b}}$。这样我们可以确保 $(a, b) \neq (b, a)$，因为集合 ${{a}, {a, b}} \neq {{b}, {b, 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), \ldots, (3, z)}$ 或者用表格表示如下：

$A \times B = \begin{array}{c|ccc} & x & y & z \ \hline 1 & (1,x) & (1,y) & (1,z) \ 2 & (2,x) & (2,y) & (2,z) \ 3 & (3,x) & (3,y) & (3,z) \end{array}$

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

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

译者注：

笛卡尔积（Cartesian Product）是从两个集合中创建所有可能的有序对的集合。给定两个集合 $A$ 和 $B$，它们的笛卡尔积 $A \times B$ 定义为：

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

也就是说，笛卡尔积是所有可能的组合 $(a, b)$，其中 $a$ 是来自集合 $A$ 的元素，$b$ 是来自集合 $B$ 的元素。

对于练习题，我们知道 $B = {x, y, z}$ 且 $A = {1, 2, 3}$。根据笛卡尔积的定义，我们需要将 $B$ 中的每个元素与 $A$ 中的每个元素配对，形成有序对：

$B \times A = {(x, 1), (x, 2), (x, 3), (y, 1), (y, 2), (y, 3), (z, 1), (z, 2), (z, 3)}$

可以用类似的表格展示这些有序对：

$B \times A = \begin{array}{c|ccc} & 1 & 2 & 3 \ \hline x & (x,1) & (x,2) & (x,3) \ y & (y,1) & (y,2) & (y,3) \ z & (z,1) & (z,2) & (z,3) \end{array}$

$A \times B$ 和 $B \times A$ 的有序对中的元素顺序不同，因此我们可以得出 $A \times B \neq B \times A$，笛卡尔积不满足交换律。

笛卡尔积的子集形成函数

假如我们想表示我们有一个函数：

$1 \to y$

$2 \to z$

$3 \to x$

（我选择了这个无序的例子来使它更有趣一些）。我们可以定义一个集合来描述这个映射。我们只需从上面的笛卡尔积中取一个子集，包括 $(1,y)$、$(2,z)$ 和 $(3,x)$。从集合论的角度来看，函数是定义域和值域集合的笛卡尔积的一个子集。对于我们的例子，1映射到y，2映射到z，3映射到x，笛卡尔积的子集在下面以粗体显示：

${1,2,3} \times {x,y,z} = \begin{array}{c|ccc} & x & y & z \ \hline 1 & (1,x) & \mathbf{(1,y)} & (1,z) \ 2 & (2,x) & (2,y) & \mathbf{(2,z)} \ 3 & \mathbf{(3,x)} & (3,y) & (3,z) \end{array}$

因此，我们的函数由集合 ${(1,y), (2,z), (3,x)}$ 定义。要定义这个集合，我们需要起始集合和目标集合。我们取这两个集合的笛卡尔积，得到输入集合到输出集合的所有可能的对应关系。然后，我们从笛卡尔积中取一个子集，根据我们的需求定义函数。当处理像整数这样的无限集合时，尽管我们无法明确列举出所有的有序对，但这并不会影响我们的操作。

函数并不一定是可计算的

一个非常重要的说明是，数学家很少关注函数是否可计算。函数是集合之间的映射。函数是如何计算的，或者是否可以通过合理的计算机来计算，大多数数学家并不关心。这也是程序员有时会困惑的地方。他们通常只把函数看作可以通过代码高效计算的东西。虽然这种看法有用，但它限制了我们对函数一般性质的理解。

我强调这一点的原因是，在零知识证明中，我们将处理的函数远远超出了将参数传入函数并得到返回值的范畴。我们需要能够理解函数的“大局观”。函数是从一个集合到另一个集合的映射。而集合之间的映射是通过取它们的笛卡尔积的一个子集来实现的。

不同定义域和值域的函数

具体来说，我们将会在整数、多项式、矩阵、一维椭圆曲线和另一维度的椭圆曲线之间跳跃。如果你不从基础层面理解，在集合论中我们可以自由地定义这些跳跃，概念化这些操作会让你感到头晕。当然，我们如何映射这些跳跃对它的实用性有很大影响。如果我们把所有内容都映射到零，这虽然是一个有效的映射，但显然不太有用。

我希望你早些明白，当我们在这种方式中“穿越不同宇宙”时，我们并没有做什么奇怪的事情。归根结底，我们可以取任意两个集合，通过取它们的笛卡尔积生成一个新集合，再从这个有序对的集合中取子集，最终得到了一个映射。

选择公理

如果你在想：“等等，我可以随意挑选一个子集并任意定义函数吗？” 你并不孤单。如果你想深入探讨这个问题，我们其实一直在讨论选择公理，虽然它的定义看似不具争议性，但它一直是争议的焦点：一组非空集合的笛卡尔积是非空的。

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

让我们定义一个非负实数（零或更大）和非负整数（零或更大）之间的映射，使用向下取整函数。向下取整函数简单地移除数字的小数部分。我们无法显示所有的实数（或整数），但我们可以创建一个示意图。当我们进行 $\mathbb{R} \times \mathbb{Z}$ 并取一个子集时，我们只选择对应于从实数中取整的有序对。我们在表格中未显示的有序对是不在定义映射的子集中的有序对。例如，2不是500.3的向下取整，所以有序对(500.3, 2)不包括在内。

$$ \begin{array}{c|ccccc} & 1 & 2 & \cdots & 499 & 500 \ \hline 1.5 & \color{red}{(1.5, 1)} & (1.5, 2) & \cdots & (1.5, 499) & (1.5, 500) \ 2.7772 & (2.7772, 1) & \color{red}{(2.7772, 2)} & \cdots & (2.7772, 499) & (2.7772, 500) \ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \ 500.3 & (500.3, 1) & (500.3, 2) & \cdots & (500.3, 499) & \color{red}{(500.3, 500)} \end{array} $$

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

译者注：

$f: {1, 2, 3, 4, 5, 6} \rightarrow {even, odd}$

映射可以表示为以下有序对的集合： ${(1, odd), (2, even), (3, odd), (4, even), (5, odd), (6, even)}$

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

译者注：

$g: {triangle, square, pentagon, hexagon, heptagon, octagon} \rightarrow {0, 1, 2, ..., 8}$

映射可以表示为以下有序对的集合： ${(triangle, 3), (square, 4), (pentagon, 5), (hexagon, 6), (heptagon, 7), (octagon, 8)}$

练习 3： 定义正整数和正有理数之间的映射（显然不是整个映射）。可以完美地将整数映射到有理数。提示：画一个表格来构造有理数，其中列是分子，行是分母。

译者注：

定义正整数到正有理数的映射。我们可以使用 Cantor 配对函数来构造这个映射。首先，我们可以把正有理数排列成一个无限的二维表格：

1/1  2/1  3/1  4/1  ...
1/2  2/2  3/2  4/2  ...
1/3  2/3  3/3  4/3  ...
1/4  2/4  3/4  4/4  ...
...  ...  ...  ...  ...

然后，我们可以按对角线方式遍历这个表格，跳过已经出现过的简化分数：

1. 1/1
2. 2/1
3. 1/2
4. 3/1
5. 1/3
6. 2/3
7. 4/1
8. 3/2
9. 2/5
10. 1/4 ...

这样，我们就建立了一个从正整数到正有理数的双射。例如，映射 $h: \mathbb{Z}^+ \rightarrow \mathbb{Q}^+$ 可以部分表示为：

${(1, 1/1), (2, 2/1), (3, 1/2), (4, 3/1), (5, 1/3), (6, 2/3), (7, 4/1), (8, 3/2), (9, 2/5), (10, 1/4), ...}$

笛卡尔积的有效和无效子集

在选择子集时存在一个重要的限制。例如，笛卡尔积 ${1, 2, 3} \times {p, q, r}$ 的以下子集是无效的，因为 1 映射到 $p$ 又映射到 $q$。在使用笛卡尔积定义函数时，同一个定义域元素不能映射到两个不同的陪域元素。

$$ \begin{array}{c|ccc} & p & q & r \ \hline 1 & (1,p) & (1,q) & \ 2 & & (2,q) & \ 3 & & & (3,4) \end{array} $$

集合与自身的笛卡尔积

不足为奇的是，除了进行 $A$ 和 $B$ 之间的笛卡尔积，你还可以进行 $A$ 和 $A$ 之间的笛卡尔积。这实际上就是将一个集合映射到自身。这是我们传统上认为的整数函数的更抽象形式的第一步。例如，$y = x^2$（对正整数而言）可以在集合论中可视化为 $\mathbb{Z} \times \mathbb{Z}$ 的子集：

$$ \begin{array}{c|cccccccccc} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \ \hline 1 & \color{red}{(1,1)} & (1,2) & (1,3) & (1,4) & (1,5) & (1,6) & (1,7) & (1,8) & (1,9) & (1,10) \ 2 & (2,1) & (2,2) & (2,3) & \color{red}{(2,4)} & (2,5) & (2,6) & (2,7) & (2,8) & (2,9) & (2,10) \ 3 & (3,1) & (3,2) & (3,3) & (3,4) & (3,5) & (3,6) & (3,7) & (3,8) & \color{red}{(3,9)} & (3,10) \ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{array} $$

集合关系

短语“取笛卡尔积的子集”非常常见，因此我们有一个词来表示它。这就是关系（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$ 中的一个元素。让我们用集合 ${0, 1, 2}$ 的二元运算符加法模 3 为例。首先，我们取集合与其自身的笛卡尔积（即 $A \times A$）：

$$ \begin{array}{c|ccc} A \times A & 0 & 1 & 2 \ \hline 0 & (0,0) & (0,1) & (0,2) \ 1 & (1,0) & (1,1) & (1,2) \ 2 & (2,0) & (2,1) & (2,2) \ \end{array} $$

然后，我们将这个新对集合与原集合的笛卡尔积：

$$ \begin{array}{c|ccc} (A \times A) \times A & 0 & 1 & 2 \ \hline (0,0) & ((0,0),0) & ((0,0),1) & ((0,0),2) \ (0,1) & ((0,1),0) & ((0,1),1) & ((0,1),2) \ (0,2) & ((0,2),0) & ((0,2),1) & ((0,2),2) \ (1,0) & ((1,0),0) & ((1,0),1) & ((1,0),2) \ (1,1) & ((1,1),0) & ((1,1),1) & ((1,1),2) \ (1,2) & ((1,2),0) & ((1,2),1) & ((1,2),2) \ (2,0) & ((2,0),0) & ((2,0),1) & ((2,0),2) \ (2,1) & ((2,1),0) & ((2,1),1) & ((2,1),2) \ (2,2) & ((2,2),0) & ((2,2),1) & ((2,2),2) \ \end{array} $$

然后，从中取定义二元运算符“模 3 加法”的子集：

$$ \begin{array}{c|ccc} & 0 & 1 & 2 \ \hline (0,0) & \textcolor{red}{((0,0),0)} & ((0,0),1) & ((0,0),2) \ (0,1) & ((0,1),0) & \textcolor{red}{((0,1),1)} & ((0,1),2) \ (0,2) & ((0,2),0) & ((0,2),1) & \textcolor{red}{((0,2),2)} \ (1,0) & \textcolor{red}{((1,0),0)} & ((1,0),1) & ((1,0),2) \ (1,1) & ((1,1),0) & \textcolor{red}{((1,1),1)} & ((1,1),2) \ (1,2) & ((1,2),0) & ((1,2),1) & \textcolor{red}{((1,2),2)} \ (2,0) & \textcolor{red}{((2,0),0)} & ((2,0),1) & ((2,0),2) \ (2,1) & ((2,1),0) & \textcolor{red}{((2,1),1)} & ((2,1),2) \ (2,2) & ((2,2),0) & ((2,2),1) & \textcolor{red}{((2,2),2)} \ \end{array} $$

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

将函数视为笛卡尔积的子集，刚开始可能有点奇怪——尤其是这种定义并不能直接转换成代码。然而，零知识证明深受数学家定义的影响，因此掌握这些概念性词汇会很有帮助。将函数概念化为从一个集合中取出一个元素并返回另一个集合中的元素，这也是非常有帮助的。

一个封闭的二元运算接受集合中的任意两个元素，并输出来自同一集合的另一个元素。“封闭”部分很重要，因为它限制了输出必须在同一集合中。具体来说，从一个集合 $A$ 开始，构造一个二元运算如下：

1. 对集合自身取笛卡尔积，即 $A \times A$，称这个有序对集合为 $P$。
2. 再对 $P$ 和 $A$ 取笛卡尔积，并从中取一个子集，使得 $P \times A$ 是良好定义的。

整数上的除法不是二元运算，因为真正发生的情况是我们先做 $P = (\mathbb{Z} \times \mathbb{Z})$，然后取 $P \times \mathbb{Q}$ 的一个子集以得到我们的关系。整数上的除法并不封闭，因为它可能产生有理数。

我们会经常处理二元运算，例如在椭圆曲线、整数、多项式、矩阵等上。当我们可以确信二元运算具有某些性质时，就能抽象掉很多实现细节。

例如，椭圆曲线上的“加法”运算并不是一件简单的事，数学过程从一开始也并不显而易见。然而，如果你知道这个二元运算是封闭的，并且遵循某些特定的规则，那么“加法”的具体实现方式就不再重要了！它只是一个遵循特定规则的映射而已！

再看一个更常见的例子：如果你将两个行列式为 1 的矩阵相乘，乘积的行列式依然是 1。虽然证明这个性质并不是一眼能看出来的，但如果你知道“行列式为 1 的 3×3 矩阵”这个集合的乘法运算是封闭的，你就不需要关心矩阵乘法的具体过程，而能直接得出结论：乘积的矩阵也一定行列式为 1。

使用描述封闭二元运算的语言，可以帮助我们站在更高的抽象层次上去理解整个数学结构，而不必过多纠结于细节实现。当涉及非常复杂的数学问题，如椭圆曲线双线性配对时，这种能力非常有用。

练习 1： 选取一个定义 $a * b \mod 3$ 的有序对子集。

译者注：

首先，我们考虑集合 $A = {0, 1, 2}$，它的笛卡尔积 $A \times A$ 是所有可能的有序对：

$$ A \times A = {(0,0), (0,1), (0,2), (1,0), (1,1), (1,2), (2,0), (2,1), (2,2)} $$

接下来，我们根据运算 $a * b \mod 3$ 计算每一对的结果，并构造出相应的有序对子集：

• $0 * 0 \mod 3 = 0$
• $0 * 1 \mod 3 = 0$
• $0 * 2 \mod 3 = 0$
• $1 * 0 \mod 3 = 0$
• $1 * 1 \mod 3 = 1$
• $1 * 2 \mod 3 = 2$
• $2 * 0 \mod 3 = 0$
• $2 * 1 \mod 3 = 2$
• $2 * 2 \mod 3 = 1$

因此，定义 $a * b \mod 3$ 的有序对子集可以写为：

$$ {((0,0),0), ((0,1),0), ((0,2),0), ((1,0),0), ((1,1),1), ((1,2),2), ((2,0),0), ((2,1),2), ((2,2),1)} $$

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

译者注：

定义集合 $A = {0, 1, 2, 3, 4}$，并定义二元运算为模 5 的减法。首先，我们将 $A \times A$ 的所有有序对列在表格中，并将这些有序对通过模 5 的减法运算映射到集合 $A$。

模 5 的减法规则是：
对于两个数 $a, b \in A$，运算结果为 $(a - b) \mod 5$。

第一步：构造 $A \times A$

$$ \begin{array}{c|ccccc} A \times A & 0 & 1 & 2 & 3 & 4 \ \hline 0 & (0,0) & (0,1) & (0,2) & (0,3) & (0,4) \ 1 & (1,0) & (1,1) & (1,2) & (1,3) & (1,4) \ 2 & (2,0) & (2,1) & (2,2) & (2,3) & (2,4) \ 3 & (3,0) & (3,1) & (3,2) & (3,3) & (3,4) \ 4 & (4,0) & (4,1) & (4,2) & (4,3) & (4,4) \ \end{array} $$

第二步：将每个有序对映射到集合 $A$

使用模 5 的减法，将每个有序对映射到 $A$：

$$ \begin{array}{c|ccccc} A - A & 0 & 1 & 2 & 3 & 4 \ \hline 0 & 0 & 4 & 3 & 2 & 1 \ 1 & 1 & 0 & 4 & 3 & 2 \ 2 & 2 & 1 & 0 & 4 & 3 \ 3 & 3 & 2 & 1 & 0 & 4 \ 4 & 4 & 3 & 2 & 1 & 0 \ \end{array} $$

在这个表格中，每个元素表示 $(a - b) \mod 5$，例如：

• $(1 - 3) \mod 5 = -2 \mod 5 = 3$
• $(4 - 2) \mod 5 = 2$

构造有效的二元运算

在处理二元运算时，我们不能在将其映射到集合 $A$ 之前，先从 $A \times A$ 中取出一个子集。二元运算必须接受集合 $A$ 中的所有元素作为输入。当然，我们必须从 $A \times A$ 和 $A$ 之间的有序对中取出一个子集，因为每一个来自 $A \times A$ 的有序对都必须映射到集合 $A$ 中的某个唯一元素。