抽象代数

抽象代数 - Abstract Algebra

抽象代数是研究在一组上有一个或多个运算符的集合。就我们而言，我们只关注运算符为二元运算符的集合。

给定一个具有二元运算符的集合，我们可以根据这个二元运算符的行为及该集合中允许（或期望）存在的元素对这些集合进行分类。

数学家为二元运算符在集合上的所有可能行为都有自己的术语。作为应用程序开发者，我们主要关注的是群（来自群论），但让我们逐步了解。群只是在这个大型动物园中的一种类型。因此，与其孤立地研究群，不如在相关代数结构（即具有二元运算符的集合）的更大背景下研究群。

抽象代数是一个庞大的领域，但我们在这里的目标是明确理解什么是 群，因为这在零知识证明中到处使用。我们可以现在就给出一个定义：

群是一个具有封闭、结合、具有单位元素的二元运算符的集合，并且每个元素都有一个逆元素。

但这个简短的定义并不太具有启发性。理解群在更大的抽象代数领域中的关系更为有益。

Magma

Magma(溪流)是一个具有封闭二元运算符的集合。仅此而已。

Magma绝对是作为程序员你直观理解的东西。现在你有了一个词语来描述它。

例如，考虑所有正整数的集合，二元运算符为 xy。请注意，我们不允许负数，因为如果 y 为负数，我们得到的是一个分数。

显然，输出将位于整数的空间中。我们的函数是 (Z×Z) 和 Z 的笛卡尔积（关系）的一个子集。具体来说，xy 是一个从 (Z×Z) 到 Z 的函数。

有趣的是，这个例子既不是交换律的也不是结合律的。你可以通过选择下面 Python 代码中的 a、b 和 c 的值来验证这一点。

assert a ** (b ** c) != (a ** b) ** c
assert a ** b != b ** a

但我们不在意。Magma是最不受限制的 代数结构 之一。重要的是二元运算符是封闭的。其他的一切都是自由的。

代数结构 是一个集合，其中有一些操作可以作用于这个集合。就我们而言，我们关心的只有一种操作，即二元运算符。

半群 - Semigroup

半群是一个具有结合二元运算符的Magma。

所有的半群都是Magma，但并非所有Magma都是半群。

换句话说，半群是一个具有封闭和结合性质的二元运算符的集合。

设我们的（无穷）集合为来自传统字母表 a、b、c,…、x、y、z 的所有可能非空字符串的集合。例如，“az”、“programmer”、“zero”、“asdfghjk”、“foo”和“bar”都在这个集合中。

设我们的二元运算符为字符串的连接。这个运算是封闭的，因为它产生的结果仍然是集合中的另一个字符串。

请注意，如果我们交换“foo”和“bar”，输出字符串将不同，即“foobar”和“barfoo”。然而，这无关紧要。“foobar”和“barfoo”都是该集合的成员，因此二元运算符“连接”是封闭的。因为我们有一个带有封闭且结合的二元运算符的集合，在连接下所有字符串的集合就是一个半群。

练习： 自行推导出以该顺序连接“foo”、“bar”、“baz”是结合的。请记住，结合意味着 (A◻B)◻C=A◻(B◻C)，其中 ◻ 是半群的二元运算符。

练习： 给出一个Magma和一个半群的例子。Magma必须不是半群。不要使用上述例子。这意味着你必须思考一个封闭但不结合的二元运算符用于Magma，而对于半群，二元运算符必须是封闭的且结合的。

Monoid ( Monoid )

Monoid是一个具有单位元素的半群。

哦，没错，这就是“monad 在自函子的类别中是Monoid”的那个Monoid。

如果我们查看 Cats 库 中的Monoid文档，可以清楚地看到这些定义：

trait Semigroup[A] {
    def combine(x: A, y: A): A
}

trait Monoid[A] extends Semigroup[A] {
    def empty: A

Cats 库简单地将“单位”称为empty，将二元运算符称为combine。Monoid扩展自半群的事实表明，Monoid是一个具有“empty”（单位）的半群。

上面的片段没有显示出这一点，但确实要求 combine 是结合的。

半群只是有一个二元运算符，除了输出与输入（x 和 y）相同的类型（A）外，没有其他限制。

例如，正整数的加法（不包括零）是一个半群，但如果包括零，它就变成了Monoid。

单位元素(identity element) 的含义是：当你用单位元素和另一个元素 a 应用二元运算符时，你得到 a。在加法的例子中，8+0=8，其中 0 是单位元素。如果你的二元运算符是乘法，那么单位元素就是 1，因为乘以 1 还是得到同样的数。

如果我们的集合是所有 2×2 矩阵的集合，而我们的二元运算符是矩阵乘法，那么单位元素将是单位矩阵

$$ \begin{bmatrix} 1&0\ 0&1\ \end{bmatrix} $$

集合的并与交

在我们早先的集合讨论中，有一个非常奇怪的缺失，即对集合的并与交的提及。这些都是二元运算符，现在是引入它们的好时机。

如果你取两个集合 {1,2,3,4} 和 {3,4,5,6} 的并集，你会得到 {1,2,3,4,5,6}。如果取 {1,2,3,4} 和 {3,4,5,6} 的交集，你会得到 {3,4}。

显然，这两个运算都是结合的。

如果我们将领域定义为所有有限整数集的集合，那么二元运算符的并与交都是封闭的，因为它们的结果是整数的集合。

在这个领域中，集合的并具有单位元素：空集合 {}。将一个集合与空集合的并会得到原始集合，即 A∪{}=A。

因此，所有 有限 整数集合在并集下是一个Monoid。

然而，在所有可能的有限整数集合的交集（∩）中，它是一个半群——没有有限集合可以作为单位元素。但如果我们将这个集合扩展到包括 Z 本身——即我们的集合是 {所有有限整数集合}∪{Z} 在交集下，那么它变成了一个Monoid，因为 Z 是单位元素。

如果你的感觉是我们“hacked”了单位元素，我们确实这样做了。

稍后我们将看到，椭圆曲线使用类似的技巧，并包括一个称为“无穷远点”的特殊点，以保持与代数法则的一致性。问题在于，如果我们说一个集合是一个Monoid，我们需要非常明确我们单位元素是什么。

作为另一个例子，我们可以说我们的集合是所有正整数在加法下，加上额外的元素 mug。我们定义 mug+x=x 和 x+mug=x。作为系统的设计者，我们可以让我们的集合由我们喜欢的任何东西组成，二元运算符的行为也可以按照我们的意愿。然而，二元运算符必须是封闭的、结合的，且该集合必须具有单位元素，方才能够成为一个Monoid。

如果我们将领域限制为 {0,1,2,3,4,5} 的所有子集，则交集显然变成一个Monoid，因为单位元素将是 {0,1,2,3,4,5}，因为你与任何集合交集都将产生其他集合，即 A∩{0,1,2,3,4,5}=A。例如，{1,3,4}∩{0,1,2,3,4,5}={1,3,4}。

此时，代数结构的类别对于给定的二元运算符对集合的领域非常敏感。

练习： 让我们的二元运算符为整数上的函数 min(a,b)。这是一个Magma、半群还是Monoid？如果我们将领域限制为正整数（零或更大）呢？对于这两个领域上的二元运算符 max(a,b) 又是什么呢？

练习： 设我们的集合是所有 3 位二进制数（基数为 8 的集合）。去确定二元运算符为按位与、按位或、按位异或、按位非、按位等同和按位与非的可行性。显然这是封闭的，因为输出是一个 3 位的二进制数。对于每个二元运算符，确定在那个二元运算符下该集合是一个Magma、半群还是Monoid。

群( Group) – 主角

群是一个Monoid，其中每个元素都有一个逆元素。

或者明确地说，它是一个具有四个属性的集合：

1. 二元运算符是封闭的（Magma）
2. 二元运算符是结合的（半群）
3. 该集合具有一个单位元素（Monoid）
4. 每个元素都有一个 逆元素

也就是说，对于集合 A 中的任何元素 a，存在一个 a′ 使得 a◻a′=i，其中 i 是单位元素，◻ 是二元运算符。更数学化的说法是：

∀a∈A∃a′∈A:a◻a′=i

这里，◻ 是集合的二元运算符。

说“集合具有逆元素”是不正确的。确切地说，每个元素在集合中都有另一个元素作为该元素的逆元素。

使用带有加法的整数，单位元素为零（因为你加零会得到同样的数），而整数的逆元素是将该整数的符号翻转（例如，5 的逆元素是 -5，-7 的逆元素是 7）。

回到领域的敏感性，正整数的加法不是一个群，因为没有逆元素。

这里是一个清晰的表格以强化这一点：

请注意，“逆元素”在集合没有单位元素的情况下是没有意义的。根据定义，将二元运算符应用于一个元素和该元素的逆元素会得到单位元素。

练习： 为什么字符串在连接下不能构成群？

练习： 多项式在加法下满足群的性质。通过显示它满足定义群的所有属性来证明这一点。

不幸的是，我们的教程在这里必须结束，因为初等群论是另一章的主题。

但现在即使我们在这里几乎没有讨论，你也有了很多背景来理解什么是群！

关于交换性的说明

上述所有代数数据结构都不要求是交换的。如果它们是，我们就说它们在其二元运算符下是阿贝尔的。在这个背景下，“阿贝尔”意味着二元运算符是可交换的，这意味着操作数的顺序不会影响结果。

阿贝尔意味着二元运算符是可交换的。

但是说“阿贝尔”，你会听起来更聪明。

技术上讲，我们通常不说“加法是阿贝尔的”，而是说“这个群在加法下是阿贝尔的”。

子集再探

让我们将这一切重新联系到我们开始时所学到的。Magma、半群、Monoid和群都是具有封闭二元运算符的集合。二元运算符仅仅是从集合的笛卡尔积的所有有序对映射回集合本身。

群是Monoid的一个子集，Monoid是半群的一个子集，半群是Magma的一个子集，而Magma通常是集合的一个子集。每个群也是一个Magma或一个集合，但是Magma不一定是一个群。

“集合”易于理解，但当我们开始讨论群和其他代数结构时，很容易迷失方向。群在我们研究密码学时非常重要。请记住：

群是具有遵循四条规则的二元运算符的集合。

此外，是时候让你的思维摆脱“加法”和“乘法”是组合事物的主要方式这个观念。

我们可以将一个集合（可以是任何东西）与它自身的笛卡尔积进行运算，然后将那组有序对映射回原来的集合。这是一个二元运算符。如果它遵循上述构造，那么它是封闭的。

数学词汇不会让我们感到害怕

在你开始这个教程之前，句子

“在二元运算符的字符串连接下的字符串集合是一个半群或Monoid，具体取决于集合中空字符串的存在或缺失”

可能没有任何意义。

你可能还得像许多外语学习者一样在脑中翻译，但你意识到它实际上在一个小空间中包含了许多信息。

我能否在没有数学术语的情况下表述那句话？当然可以，但我至少需要500个词才能清晰地表达。这实际上值得理解那些术语的含义。这将为我们今后的学习节省很多麻烦。

有趣的是，有大量关于群的定理，让我们在不理解群的二元运算符在底层工作方式的情况下就能对该群做出某些声明。这在某种程度上类似于面向对象编程中的多态性或函数语言中的特征。它们隐藏了实现细节，让你专注于高层次的概念。这是非常强大的。

在下一章中，你将学习如何通过同态将群“相互关联”。

深入学习

请查看我们的 零知识课程， 包含系列中的其余零知识教程。

最初发布于 2023年7月25日

• 原文链接： rareskills.io/post/abstr...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～