[free_objects]

    Free algebra（1）

    我们在上一篇中提到了代数效应的工程应用，从这一篇开始我们开始聚焦数学视角上的代数效应。代数效应中的代数二字来自于 free algebra，这是一个来自泛代数（universal algebra）的词语，代数效应这一概念的提出者 Plotkin 和 Power 使用了来自 Lawvere 理论的工具。不过，如果只是出于理解代数效应，而非研究其上的命题和证明的角度出发，传统的泛代数理论就已经足够了。虽然如此，代数效应在传统的泛代数理论下的解释依然需要一定的数学知识作为前提，其中之一就是自由对象的构造，在 Andrej Bauer 的文章中，对 free algebra 的构造是完全范畴的，也就是他给出的构造完全基于自由对象的 universal property，为了能够使得接下来的文章更方便理解，我们在这篇文章里简单描述一下代数中自由对象的特征，以起到承前启后的作用。

    群

    在对自由对象的描述中，自由群是最典型的例子之一，本文的目的并不是群论，但是通过自由群来理解自由对象可以大大降低理解门槛，如果读者对群不太熟悉，我们在这里给出群的定义和几个简单的例子

    Definition. 群 [#]

      一个群 包含一个集合 以及 上的二元运算 （当上下文明确时，我们通常直接写作群 并将 直接写作 ），满足如下几条公理

      1. 结合律：
      2. 幺元：存在一个 使得对所有 ，有
      3. 逆元：对所有 ，存在 ，使得

      数学不同领域的大量数学对象都是群的例子，如下列出了几个常见的群，读者不妨自行验证其是否符合群的定义：

      1. 整数对加法构成群 ，特别的，这个群满足交换律。
      2. 整数模 同余类对加法构成交换群 。
      3. 等边三角形的旋转和沿其中一个角翻转的动作构成了一个群，称为6阶二面体群 或者三阶对称群 。
      4. 所有与 互素的整数模 同余类对乘法构成交换群 。
      5. 取一个拓扑空间并固定一个点，令 是从该点出发并且回到该点的所有道路，如果道路 可以通过连续变换称为道路 ，我们称 ，则集合 对道路的“拼接”构成一个群，称为该空间的第一同伦群或者基本群，关系 称为同伦关系，道路 和 称为同伦的。
      6. 所有的线性空间都是群。

      群的生成元

      对于熟悉线性代数的读者，应该知道线性空间存在一组基，表现在二维平面上就是平面上的任意一个点都可以由其 坐标表示，我们说整个平面被这两个基底 轴和 轴所生成。研究基底的好处在于，在诸如二维平面这样的有限维空间中，我们可以将对空间中任意点（无穷多个）的研究，转化为对基底（有限多个）的研究，对于空间之间的映射，我们只需要研究基底被映射到什么元素，就可以了解整个空间是如何变换的。

      由于所有的线性空间都是群，因此一部分群也享有同样的性质，与线性空间不同的是，在群上我们可以要求一些额外的等价关系，例如，我们可以指定一个元素 使得 ，在 群中，如果我们将 视为“沿一个角平分线翻转”，则 代表一个等边三角形沿着一个角翻转两次后将会回到没有翻转的状态。

      在群论的术语中，我们将类似线性空间“基”的概念命名为生成元。给定一个群 ，如果他的一组生成元是 ，那么根据生成元的定义， 中的任何元素都可以由 的组合得到。例如， 群中的所有元素都对应了将等边三角形沿着一个角平分线翻转或者逆时针旋转60°的操作，因此 群的两个生成元就是代表“翻转”操作的 和代表“逆时针旋转 ” 的操作 ，该群中的所有元素都可以由这两个元素的组合得到，例如， 意味着两次翻转+逆时针旋转60°，注意，由于群的运算是结合的，是先翻转还是先旋转并不影响最终结果。同时，注意到在等边三角形中

      1. 连续逆时针60°旋转三次会回到初始状态。
      2. 连续沿着同一个角平分线翻转两次会回到初始状态。
      3. 翻转 → 逆时针旋转 → 翻转 → 逆时针旋转也会回到初始状态。

      因此，在这个群上我们需要额外的三个等式

      因而，我们可以说，六阶二面体群 是由两个元素 ，在上述三个方程的约束下生成的，写作

      我们该怎么想象这样的一个构造呢？我们可以把从生成元生成整个自由群的过程想象成如下的几个步骤

      1. 随意的拼接 和 两个元素，这会让我们生成在形式语言上称为 的 Kleene 闭包的一组无穷集合，这组集合里是 和 所有可能的组合 （注意 可以被看做“不进行任何拼接”的空元素，类比形式语言中的空字符串）
      2. 我们对这个集合中的每一个元素，按照上述三个等式进行简化，例如， 会在 等式的条件下变成 ，同理， 会在 等式的条件下变成 ，等到集合中所有的元素都已经无法再化简之后，我们就得到了最终的群，不难注意到，整个 群一共就只有六个元素：

      自由群

      上面洋洋洒洒的讲了半天生成元，目的就是引出对自由群的讨论：所谓自由群，就是由一组生成元，在没有任何等式约束下，所生成的一个群。

      上文中提到的 不是自由群，因为他的生成元收到三个等式约束，反过来考虑 ，它的生成元显然是 ，而且很容易注意到该群上没有任何等式约束，因此，我们可以讲 表示为

      这就是一个自由群。

      接下来，让我们思考一下该怎么从这个直觉里走出来，我们可以先给出自由群的定义。

      Definition. 自由群 [#]

        给定一组生成元构成的集合 和一个群 ，我们称 是 上的一个自由群，当且仅当 在 下的范畴 是 initial 的，这意味着如下交换图表成立

        或者说，一个自由群是由一个集合和一个映射 构成的，使得对所有的 ，都存在一个唯一的群同态 使得

        我们来解释一下为什么自由群是这样要求的，在上面的交换图表中， 可以视为是恒等映射，将 “映入” 中，以 为例，其生成元是集合 ，则 就可以定义为恒等映射 。自由群的核心在于，由于所有元素都可以被写成生成元的组合，因此，自由群上的任何同态都应该可以由其在生成元上的表现所决定。我们可以用下面的例子来解释这一点。考虑群 ，以及一个 上的同态

        并且我们只知道 ，虽然我们只知道 在一个元素上的表现，但由于 是 的生成元，由群同态的性质，有

        因此我们可以推导出 即为该群同态的确切定义。

        从上面的例子，我们可以知道，生成元的性质允许我们从任何群同态在生成元上的表现，推断出群同态在整个群上的表现，但是这一点并不是普遍成立的，一个不成立的例子就是当群具有额外等式约束的时候，我们首先要明确一点，对一个群来说，任何等式约束都可以被写作 的形式，其中 是一个群元素，例如， 的等式约束 ，只需要左右同时在右边乘上 ，就可以变成 ，我们称这是一个等式约束的标准形式，接下来让我们考虑在拥有等式约束的群上，群同态会有什么样的表现？考虑 上的一个群同态 ，其中 是另一个群，则 ，同时，由于 ，所以 ，联立两个等式，我们有 ，或者说 ，这就对 有了额外要求（必须满足 这个等式）。

        从上面的例子中我们可以看到，如果一个群具有额外的等式约束，那么这个约束表现在其上的群同态会呈现出一些特殊的性质，从而使得群同态不能完全由生成元上的表现决定（比如上文中 不仅由生成元决定，还由等式 决定），那么，我们自然可以尝试从这一点出发来定义自由群。现在，回过头来看上方的交换图表

        其中 是任意的，而 是唯一的，且 。我们来翻译一下这到底表达了什么含义。因为 是一个群同态，因此

        1. 在生成元上，
        2. 在其他元素上，每个元素都是由生成元生成的，假设该元素 （ 为生成元），则 ，由第一条，可以得到

        以上两点意味着，群同态 在所有元素（生成元和非生成元）上的行为，都是完全由 在生成元上的行为决定的。回想起上文中我们提到，如果一个群具有额外的等式约束，则 会具有一些额外的性质。因此，我们只需要在此处要求 是“任意的”，就可以要求 上不具备任何额外约束，以上面的 上的群同态作为例子，其要求 ，然而，并不是所有的 都满足这个性质，因此 违反了上述交换图表中对 任意性的要求，从而 不是一个自由群。

        可以看出，我们现在已经证明了群同态 的两个性质：

        1. 的任何表现都由 在生成元上的表现决定，因此对于每个 ， 都一定是唯一的。
        2. 由于 是任意的，而 的表现又由 决定，因此 上不会有任何额外的要求。（思考一下这句话：如果 不是任意的，那么“符合要求”的 一定会满足一些非平凡的特殊性质，又因为 由 唯一决定，因此这些特殊性质就会反映在 上。相反，如果要求 是任意的，则说明 上不存在任何特殊性质，因此 上也不会有任何额外的等式约束要求）

        如果读者将满足以上这两点的 与上文中 上的例子做对比，就会发现我们已经严格的、形式化的反应了上面所说的“可以通过群同态在生成元上的性质唯一推断出群同态的整体表现”这一直觉意义上的描述。不仅如此，自由群是自由对象的最简单的例子，在接下来的文章中，我们会了解到 free -algebra 就是在 -algebra 所构成的范畴上的一个自由对象，其定义与自由群的定义几乎完全一致。我们在本文中着重介绍自由群，是因为 free -algebra 并不具备自由群这种可以类比用生成元当做形式语言中的字母，用群运算当做形式语言中的拼接的容易想象、容易理解的良好直觉：在自由群的定义中，你只需要想象生成元集合中的所有元素任意拼接，就能得到一个自由群中的元素，而free -algebra 的具体构造看上去则相当的抽象拗口。通过对自由群的描述，我们希望读者能够对自由对象同时建立起直觉和形式化描述，这样，在接下来介绍 free algebra 的时候，就不要再去尝试用直觉直接思考了。下一篇，我们会介绍泛代数中的基础概念。