跳转至

前言：关于代数、数学和计算科学

约 3466 个字 预计阅读时间 12 分钟

在本文中，我们将首先讨论一些所谓“世界观和方法论”上的问题，即：代数研究的对象是什么？或者更广泛的意义上说，怎样探讨数学？另外，因为这个系列是“写给计算机系学生”的，笔者也不妨在此稍微谈谈对计算科学1的理解。

对系列标题的批判

关于系列的标题，自然有不少可供澄清，或者说批判的内容。一方面，所谓的“计算机系学生”指的是哪些？当然，我们指的并不仅仅是本科生。在这里，学生代指任何对计算机（或者计算，见下文）感兴趣、并且希望接触前沿研究的人，本书的编排之首要目的就是让不同程度的人都能学到东西。但是，由于面向对象的背景如上设定，我们也会默认读者对很多“计算机”的东西有所了解。例如，对于算法、图灵机之类的概念有一个直观的认识，可能要有一点基本的代码素养，了解一点数据结构、一点图论，并且理解复杂度分析的基本内容。这些前置知识将在用到时做粗略的回顾或者深化。

当然，或许有读者会问，面向计算机系学生的讨论为什么不增加一些代码内容？这事实上是笔者想要努力的一个方向，我们希望将自动证明系统和符号计算系统的实际应用引入到里面来，但是因为时间关系，笔者本人也能力有限，可能要到后面再更新这些相关的东西。另外，也有一些讨论自然涉及一些代码工作，例如计算群论，计算代数数论等等，这些内容将会放在习题当中，但是 starter code 显然是还没弄的（对，我就是鸽子）。

下一个问题是“代数”。为什么要学代数将在下文新开一节讨论，在这里毕竟是批判，那还是得指出这个标题事实上多少有点挂羊头卖狗肉的嫌疑。首先，一般所谓的“代数”教材涵盖的内容多半会远小于这里涉及的内容，很多代数拓扑、代数几何的内容又会在本系列中加以介绍；此外，我们还会讲到比较多的拓扑内容，以及大量关于“元数学”（metamathematics）的讨论。这使得标题说的“代数”多少有点寒酸了，但若说是“写给计算机系学生的现代数学”却又太过了。

若是按照“现代数学”的标准，不妨说一下“这里没有什么”。首先，传统的分析学研究的内容在这里大概是没有的，因此也没有关于优化的内容；关于测度的讨论可能会出现但应该会集中在代数结构上的测度，但是非标准分析会被较大量地涉及，也可能被用于处理一些传统分析的问题。其次，一般拓扑的内容会涉及但是不多，拓扑学的各种分支中应当只会涉及代数拓扑，毕竟它与图论有强关联。再次，几何学的内容应当仅限于必要的部分，例如讨论一些有几何背景的概念时被引入。最后，概率论和统计学的内容基本上不会涉及，除了在一些难以绕开的习题里会用到概率的基本概念，原因一方面是和主旨关系不大，且涉及很多麻烦的处理，另一方面是笔者学不明白。集合论的深入讨论也在计划之外，但是也或许有可能会在必要时提及，其它大部分相对偏门的领域也是被排除在外的。

好，一段废话。总而言之，代数之外的内容基本不会被主线包含，可以跳过。

代数在研究什么，以及为什么要学习代数

代数在研究什么？恐怕代数学家们也很难统一作出回答。在本系列中，我们将以集合上的结构作为切入口，讨论由此诞生的问题。与历史上从方程解的问题引出代数不同，我们的叙述手段更类似于被称为“结构主义”的布尔巴基学派。为了理解笔者为什么要作此处理，或许稍微提一提分析（analytic）和综合（synthetic）的差异比较好2。

分析的数学和综合的数学最大的区别在于公理系统的不同。一般地，我们会用“公理化的”（axiomatic）一词来描述综合的方法，它的公理直接联系讨论对象，而且“如其所是地”反映对象3。最经典的例子是公理化集合论，它的讨论对象是集合，它的公理就事关集合，公理直接限定讨论对象的方式就被称作综合的。其它的一些例子还有欧几里得或者希尔伯特的几何学，等等，以及后面可能会放在附录里的综合可计算性理论（synthetic computability theory）4。分析的方法的典型例子之一就是分析学，我们预置的公理系统其实是集合论公理系统，通过在其上定义拓扑、定义测度等等的方式，我们能够找到许多有用的性质。

而事关代数，方法论上的问题就有点复杂。我们会将其分成两个部分来处理。第一部分（前一到四章）我们以纯粹分析的方式来处理问题，也就是说，我们给定集合论公理系统，在集合论上给出关于某个结构5的定义，然后应用这些定义去解决问题。而在后半部分，我们将集中于这样的构造在综合的方法论所构建的学科中的应用，例如综合同伦论以及一些综合的关于概型（scheme）的理论，并且更广泛地探讨综合数学这一整个学科。

因此，我们在本文中所述的代数学，事实上是以分析的方法起步，又被广泛应用到综合的数学上去的一个数学分支。很快读者就能从目录中发现，本系列讨论的问题相当多地可以被归为“元数学”。我们不应局限于一种方法、一种基础，而应当崇尚多种思路的结合，不妨读读 F. Klein 在 1908 年的叙述：

In mathematics, however, as everywhere else, men are inclined to form parties, so that there arose schools of pure synthesists and schools of pure analysts, who placed chief emphasis upon absolute “purity of method,” and who were thus more one-sided than the nature of the subject demanded.

然而，数学界与别的地方并无不同，人们终归要抱团取暖。因此也就形成了纯粹综合或者纯粹分析的学派，其核心观点是强调“方法的纯正”。与他们研究对象的本质所要求的不同，他们太过偏心了。

这是笔者通过此系列想要传达的第一点：不要局限于单一的方法论，或者单一的学科，对于计算科学而言尤其是如此。

第二个问题是，为什么要学习代数？一方面，有非常多的结果与代数相关，例如老生常谈的密码学，还有老生不谈的程序分析和验证；另一方面，关于代数结构的话题也充斥了相当多的期刊和文档，例如 Haskell 中的单子（monad），以及一些 AI 的论文，例如这个知识图谱的文章和这个 ICML 2023 的论文。前者无需再提，而后者则是不得不再讲讲。

上面讲到的三份工作在笔者看来都是不那么成功的。Haskell 的单子和数学上的单子事实上有所不同，这在后文中会提及，而后面两篇论文则可以被戏称为“大词 rap”，都是对基本概念的陈述和失败的抽象。笔者认为，每一个计算机科学的研究者，尤其是希望使用这类方法论的研究者都应当至少通读 J. Goguen 的老论文 A Categorical Manifesto，这篇文章在后面还会被提及，但其中这段文字在此值得被整段引用：

Category theory can also be abused, and in several different styles. One style of abuse is specious generality, in which some theory or example is generalized in a way that does not actually include any new examples of genuine interest. A related style of abuse is categorical overkill, in which the language of category theory is used to describe phenomena that do not actually require any such elaborate treatment or terminology. An example is to describe a Galois connection in the language of adjoint functors.

范畴论也可以被以各种形式滥用。一种是浮夸的泛化，这种理论和例子的泛化完全不能包含任何有意思的新实例。与之相类的，还有多此一举的情形，使用范畴论的语言来描述本不需要如此精致的处理或术语。一个例子是用伴随函子的方式描绘 Galois 连接6。

那么，既然这些东西被笔者认为是抽象废话（abstract nonsense），为什么我们还需要了解它们的前置知识？一方面是因为，还有很多好的抽象，不过笔者在此只引出了不好的，好的抽象会留在章节中做详细阐述；另一方面，只有了解了它们的那些大词在说些什么，我们才能对“好”和“不好”的抽象做出自己的评价。因此，本系列想传达的第二个观点是：理解并应用好的抽象，理解并远离坏的抽象。以上就是这个系列的初心，以及希望它能完成的使命。

计算科学：这是什么，这将是什么

这一节事实上主要是讨论笔者在后面的选材依据。因为写给计算机系学生的代数书自然要以计算科学为核心，大部分的实例和讨论都会与之相关。因此，为了明确选题，我们要讨论的第一个问题就是，什么是计算。

大概不少计算机专业的学生会给出的答案都是算法，或者有一些人会给出图灵机的描述。那么笔者不妨剑走偏锋，给出一个非常物理的定义7：

定义

考虑三维欧氏空间 \(E\)，区域（region）\(A\) 是 \(E\) 的一个子集，它可能的状态记为 \(\Sigma(A)\)，称 \(\Sigma(E)\) 为全局状态。将时刻 \(t\) 区域 \(A\) 的状态记作 \(\rho(A, t)\)，它是 \(\Sigma(A)\) 的一个元素。

在经典物理学的假定下，从自然数 \(k\) 到 \(kT\) 时间系统的全局状态的映射被称为一个可计算的函数（computable function），将系统从时刻 \(0\) 到时刻 \(kT\) 的演变称为一个计算（computation）。

其中所谓的经典物理学的假定有以下五条：

  • 空间均一性（homogeneity of space），即一块区域和它平移之后的区域可能的状态集合相同；从 \(t\) 时刻系统的全局状态到 \(t+T\) 时刻系统的全局状态的映射与平移操作交换。
  • 时间均一性（homogeneity of time），从 \(t\) 时刻系统的全局状态到 \(t+T\) 时刻系统的全局状态的映射与时刻 \(t\) 无关。
  • 有限信息密度（bounded density of information），如果 \(A\) 是有界的，那么 \(\Sigma(A)\) 是有限的。
  • 有限信息传播速度（bounded velocity of propagation of information），存在常数 \(T\) 使得对于任意区域 \(A\) 和时刻 \(t\)，\(\rho(A, t+T)\) 仅仅和 \(\rho(A', t)\) 有关，其中 \(A'\) 为 \(A\) 半径为 \(1\) 的邻域。
  • 静止态（quiescence），对于每个区域 \(A\) 都有一个基本状态 \(q_A \in \Sigma(A)\) 称为静止态，如果 \(A\) 处于静止态，那么其任意子集也处于静止态。最开始除了一个有界区域以外的空间都处于静止态。

这个定义看起来很绕，不是吗？但是它确实在符合我们的大部分物理愿景的同时等价于图灵机给出的定义。而我们讨论的计算科学的问题就是：

  • 在可计算的框架下可以处理的问题有哪些？
  • 怎样在可计算的框架下处理问题？
  • 处理问题的速度有多快？
  • 怎样设计能够更好地达到这些限制带来的边界的物理系统？

前三个问题分别对应可计算性、算法设计和算法复杂度，而最后一个问题可以称作是计算机科学。再细分、融合下去，我们当然就有了经典的计算机系学生所学习的内容，本文的选材也都会着重于对这些问题的回答，主要的讨论有：

  • 状态机理论，对这些假定的一些深入研究；
  • 密码学，关于单向函数的问题；
  • 程序分析和形式化验证，事实上作为状态机的一些应用；
  • 图算法和一些代数问题的算法，关于算法设计；

其它细分方向涉及的问题也会在讨论之列。例如会为了计算机图形学等方向介绍四元数，算法复杂度中经典的代数复杂度理论，以及可计算性理论中的很多构造等等。

那么，让我们开始吧！

  1. 这是笔者一个同学的用词。他觉得本系列的目的不是给计算机科学（computer science）服务，而是为计算科学（computational science）服务的。当然，这个意见很好，所以我们在本系列中都会采纳这个术语。 ↩

  2. 可以参考 nLab 上面的叙述。对于哲学意义上的分析和综合的讨论更加复杂，在此我们只讨论数学。 ↩

  3. 原谅我使用了这样有点现象学的术语。事实上这里想要说的是例如欧氏几何（特指几何原本的几何）和解析几何的区分，欧氏几何直接反映点、线，而解析几何会将问题引申到公式上去，这就是综合的和分析的方法的差异。 ↩

  4. 关于综合的方法可以讨论的东西还非常多，例如它事实上和 DSL 有一点关系。它和可计算性理论的关联可以参考 A. Bauer 的系列课程。 ↩

  5. 关于结构，其实在讨论第六章的 Lawvere 理论和泛代数之前，我们都会泛泛而谈地使用这个词。粗略地说，我们提及的结构就是指这个集合具备某些性质（equipped with sth.）。 ↩

  6. 这个例子中所谓的 Galois 连接大概特指在程序的抽象解读（abstract interpretation）中的应用，与后面会提及的作为纯粹数学对象的 Galois 连接不同。 ↩

  7. 这个定义的正当性参见 Gandy 的论文，这里提供的版本转引自 Arrighi 等人的发展。在此展现这个定义的目的主要是说明前述观点中的第一点：不要局限于“计算机式的”或者“数学式的”方法论。 ↩