第十五章 泛代数与等式逻辑代数结构的公理化之巅引言从具体到抽象再从抽象到元抽象前四章我们逐一建构了群、环、向量空间与模的公理体系。尽管这些结构差异显著——群仅有一种运算环有两种模涉及外部标量——但任何仔细的读者都会注意到深刻的平行性。子结构与商结构的定义高度雷同同态与同构的概念几乎逐字逐句重复同态基本定理的陈述在群、环、模中如出一辙。这绝非巧合。数学家的天性驱使我们追问能否将这些共性本身公理化使得群论、环论、模论成为同一套元理论的个例答案是肯定的这套元理论便是泛代数或称作万有代数。泛代数的研究对象不再是某一具体的代数结构而是“代数结构”这个概念本身。它建立了一套统一的语言和定理使得所有由等式定义的代数类——群、环、模、格、布尔代数——都成为其特例。这种向更高抽象层次的跃迁是二十世纪数学最显著的特征之一。1898年怀特海Alfred North Whitehead在其专著《泛代数》A Treatise on Universal Algebra中首次系统尝试将多种代数理论统一起来而到了1935年加勒特·伯克霍夫Garrett Birkhoff通过簇定理HSP定理给出了这一纲领的核心定理彻底刻画了等式可定义的代数类的语义特征。从此“代数结构”不再是一盘散沙的个例而是一个由精确定理统治的完备体系。与泛代数紧密相伴的是等式逻辑。在卷一我们建立了命题逻辑和一阶谓词演算它们足以表达“对所有 (x, y) 有 (x \cdot y y \cdot x)”这样的等式公理。等式逻辑是谓词逻辑的片段它只允许全称量词和等式不允许存在量词、否定或蕴涵。这种限制反而赋予了等式逻辑极其优美的证明论性质——完备性、可判定性在某些情形下以及Birkhoff的簇定理。事实上等式逻辑恰好处在一个精妙的平衡点上它的表达能力足以刻画几乎所有经典的代数结构但又足够弱以至于语义和句法完美吻合且具备其他逻辑系统难得的良好行为。本章将沿着一条从具体到抽象的路径展开。我们首先定义签名、代数、项代数等泛代数的基本概念然后形式化等式逻辑的句法与语义证明 Birkhoff 簇定理——这是泛代数的巅峰成就它断言“等式可定义”与“对子代数、同态像、直积封闭”HSP完全等价。随后我们将展示如何用 HSP 定理统摄群、环、模、格、布尔代数的理论。自由代数的范性质与存在定理将作为等式逻辑完备性的桥接出现。最后我们简要触及泛代数与范畴论、模型论的交汇点以及等式逻辑在计算机科学代数规约、重写系统中的应用。整章将贯穿“公理化方法反身自照”的主旨数学不仅公理化对象也公理化自身。15.1 代数结构的统一描述签名、代数与子代数15.1.1 签名运算的蓝图在泛代数中首先需要一种语言来刻画“一个代数结构有哪些运算”。这通过签名实现。签名好比是建筑蓝图它告诉我们可以使用哪些运算每个运算接受多少个输入但不规定这些运算满足何种规律。定义 15.1.1签名一个签名signature或运算型是一个集合 (\Sigma)其中每个元素 (f \in \Sigma) 被赋予一个非负整数 (n_f \in \mathbb{N})称为 (f) 的元数arity。0 元运算称为常量。元数刻画了运算的“输入端口”数量。常量是无需输入即可产出的特殊元素。注意尽管数学中常见的签名总是有限的但泛代数允许 (\Sigma) 可以是任何集合甚至允许无限元运算只是实践中有限签名最为普遍。例子群的签名传统上我们取 (\Sigma_{\mathrm{Grp}} {\cdot, {}^{-1}, e})元数分别为 (2, 1, 0)。但群还有其他等价签名。例如我们可仅用单一的二元运算 (/)右除令 (x/y) 满足等式也能公理化群。甚至可用一个常量和一个二元运算或一个一元运算和一个二元运算。签名的选择影响等式理论的形态但不改变代数类的本质——这正是泛代数优美之处。环的签名(\Sigma_{\mathrm{Ring}} {, -, \cdot, 0, 1})元数为 (2, 1, 2, 0, 0)。注意减号作为一元运算纳入使我们可以纯粹用等式刻画环(x (-x) \approx 0)。格的签名(\Sigma_{\mathrm{Lat}} {\vee, \wedge})元数均为 (2)。布尔代数的签名(\Sigma_{\mathrm{BA}} {\vee, \wedge, \neg, 0, 1})。模在固定环 (R) 上的左模的签名除了加法群结构外对每个标量 (r \in R) 都有一个一元运算 (r\cdot(-))称为标量乘法。此时签名可能是无限的但仍是合法的签名。有了签名我们就可以谈论基于该签名的代数结构。15.1.2 (\Sigma)-代数与同态定义 15.1.2(\Sigma)-代数设 (\Sigma) 是一签名。一个 (\Sigma)-代数 (\mathbf{A}) 是一个非空集合 (A)承载集以及对每个 (f \in \Sigma)有一个解释 (f^{\mathbf{A}}: A^{n_f} \to A)。特别地若 (n_f 0)则 (f^{\mathbf{A}}) 是 (A) 中的一个元素。我们用粗体字母表示整个代数用斜体表示其承载集。例如一个群 (\mathbf{G} (G, \cdot^{\mathbf{G}}, {}{-1{\mathbf{G}}}, e^{\mathbf{G}}))。当上下文明确时我们省略上标直接写作 (G)。定义 15.1.3同态与同构设 (\mathbf{A}, \mathbf{B}) 是 (\Sigma)-代数。映射 (\varphi: A \to B) 称为 (\Sigma)-同态如果它保持所有运算对于每个 (f \in \Sigma)元数 (n)和任意 (a_1, \dots, a_n \in A)[\varphi(f^{\mathbf{A}}(a_1,\dots,a_n)) f^{\mathbf{B}}(\varphi(a_1),\dots,\varphi(a_n)).]对于常量 ((n0))即 (\varphi(c^{\mathbf{A}}) c^{\mathbf{B}})。若 (\varphi) 是双射则称为同构记作 (\mathbf{A} \cong \mathbf{B})。同态的概念在泛代数中是完全统一的它只是“保持所有运算”的映射。群同态、环同态、模同态、格同态无一不是这个模式的具体实例。公理化的威力在此展露无遗。定义 15.1.4子代数(\Sigma)-代数 (\mathbf{A}) 的子代数是一个子集 (B \subseteq A)对 (\Sigma) 中所有运算封闭。即对每个 (f \in \Sigma)元数为 (n)和任意 (b_1, \dots, b_n \in B)有 (f^{\mathbf{A}}(b_1, \dots, b_n) \in B)。封闭性自动使 (B) 承载一个 (\Sigma)-代数 (\mathbf{B})运算为 (\mathbf{A}) 运算的限制。记作 (\mathbf{B} \le \mathbf{A})。一个非空子集可能不包含常量如果常量的值不在其中此时它不是子代数。因此通常要求子代数非空或通过包含常量保证非空。在群论中子代数即子群在环论中子代数即子环若常量0,1均在子集中在模论中即子模。15.1.3 项与项代数语法的代数化泛代数将表达式形式化为项。项的定义是递归的它们纯粹是语法对象不携带任何语义内容——但巧妙的是它们自身就构成一个代数。定义 15.1.5项给定签名 (\Sigma) 和变元集合 (X)通常取可数集 (X {x_1, x_2, \dots})全体 (\Sigma)-项 (T(\Sigma, X)) 归纳定义如下每个变元 (x \in X) 是项。若 (f \in \Sigma) 有元数 (n)且 (t_1, \dots, t_n) 是项则 (f(t_1, \dots, t_n)) 是项。不含变元的项称为闭项或地项。例如在群签名下(x \cdot (y \cdot e)) 是项在环签名下((x y) \cdot z - 1) 是项。项可以任意复杂它的高度对应于运算的嵌套深度。项不仅是形式表达式它们自身也构成了一个 (\Sigma)-代数定义 15.1.6项代数项集合 (T(\Sigma, X)) 上自然定义 (\Sigma)-代数结构对 (f \in \Sigma)定义[f^{\mathbf{T}}(t_1, \dots, t_n) f(t_1, \dots, t_n).]即运算就是形式地构造更复杂的项。该代数称为(X) 上的项代数记作 (\mathbf{T}_{\Sigma}(X))。项代数是“绝对自由”的代数除了被运算的形式结构强制外任何项之间没有额外的等式。它满足泛代数的初始性对任意 (\Sigma)-代数 (\mathbf{A}) 和任意赋值映射 (h: X \to A)存在唯一的同态 (\bar{h}: \mathbf{T}_{\Sigma}(X) \to \mathbf{A}) 将每个变元 (x) 映为 (h(x))将项 (f(t_1,\dots,t_n)) 映为 (f^{\mathbf{A}}(\bar{h}(t_1),\dots,\bar{h}(t_n)))。这一性质是自由代数概念的滥觞。15.2 等式逻辑句法与语义15.2.1 等式与等式公理化定义 15.2.1等式给定签名 (\Sigma)一个等式或等式公式是一对项 ((s, t))常写作 (s \approx t)。一组等式集合 (E) 称为一个等式理论或代数理论。注意等式表面上是两个项的形式关系但它的逻辑含义是“对所有变元(s t)”。由于没有其他连接词等式理论极简而纯粹。定义 15.2.2等式理论的模型给定等式理论 ((\Sigma, E))。一个 (\Sigma)-代数 (\mathbf{A}) 称为该理论的模型或称 (E) 在 (\mathbf{A}) 中成立如果对所有赋值 (h: X \to A)以及 (E) 中每个等式 (s \approx t)将 (h) 扩展到项上的同态 (\bar{h}) 满足 (\bar{h}(s) \bar{h}(t))。记作 (\mathbf{A} \models E)。该理论的所有模型构成的类称为由 (E) 定义的簇variety或等式类。换句话说等式在代数中成立当且仅当在变元的任何取值下两边计算出的元素相等。这里全称量词是隐含的。例子群是签名 ({\cdot, {}^{-1}, e}) 上的代数满足等式[(x \cdot y) \cdot z \approx x \cdot (y \cdot z), \quad e \cdot x \approx x, \quad x \cdot e \approx x, \quad x^{-1} \cdot x \approx e, \quad x \cdot x^{-1} \approx e.]这就构成了等式理论 (E_{\mathrm{Grp}})。环、模、格、布尔代数均可类似地用等式公理化。域不能用等式公理化因为乘法逆元只在非零元上定义无法用无条件等式表达所有元素见15.5.2详述。等式逻辑的推理规则极其简单但足以推导出所有语义后承定义 15.2.3等式逻辑的证明系统从等式集 (E) 出发可推导出新等式的规则自反性(t \approx t)对所有项 (t)。对称性由 (s \approx t) 推出 (t \approx s)。传递性由 (s \approx t) 和 (t \approx u) 推出 (s \approx u)。替换性若 (s_1 \approx t_1, \dots, s_n \approx t_n)且 (f \in \Sigma)元数为 (n)则 (f(s_1, \dots, s_n) \approx f(t_1, \dots, t_n))。代入性若 (s \approx t) 是已推导出的等式(\sigma) 是将变元代换为项的代换则 (\sigma(s) \approx \sigma(t)) 也可推导。此外(E) 中所有等式视为公理。若存在从 (E) 出发使用以上规则推导出 (s \approx t)记作 (E \vdash s \approx t)。这五条规则完全捕捉了相等关系的自反、对称、传递以及与运算的兼容性。它实际上是一阶谓词演算带等词的一个片段但由于去掉了否定和存在量词它获得了更为简洁的元理论。15.2.2 等式逻辑的可靠性定理定理 15.2.4可靠性若 (E \vdash s \approx t)则在每个满足 (E) 的代数 (\mathbf{A}) 中(s \approx t) 成立。证明对推导长度归纳。公理 (E) 中的等式根据定义在所有模型中成立。自反性、对称性、传递性由等词的逻辑公理保证。替换性由函数符号的解释保持相等性。代入性由全称实例化保证等式隐含量词全称闭包。∎可靠性确保句法推导不会产生语义谬误这是任何逻辑系统必须满足的基本要求。15.2.3 等式逻辑的完备性定理——Birkhoff 之前在泛代数的早期完备性就已通过“林登鲍姆-塔尔斯基代数”的构造得以证明。其想法是若要证 (E \models s \approx t) 蕴含 (E \vdash s \approx t)我们可以构造一个“最一般”的模型——项代数模去等式等价关系——使其恰好满足 (E) 且仅满足必要的等式。定义 15.2.5林登鲍姆-塔尔斯基等价在项集合 (T(\Sigma, X)) 上定义等价关系[s \sim_E t \iff E \vdash s \approx t.]由等式逻辑的规则特别是自反、对称、传递和替换(\sim_E) 是一个合同关系即与所有运算兼容。商代数 (\mathbf{T}_{\Sigma}(X)/{\sim_E}) 称为林登鲍姆-塔尔斯基代数记作 (\mathbf{L}_E(X))。在该商代数中([s] [t]) 当且仅当 (E \vdash s \approx t)。因此若 (E \not\vdash s \approx t)则 (\mathbf{L}_E(X)) 中 (s) 与 (t) 的解释不同。又因为 (E) 中所有公理在该代数中显然成立它们正是生成 (\sim_E) 的根源所以 (\mathbf{L}_E(X) \models E)但它不满足 (s \approx t)。于是(E \not\models s \approx t)。完备性得证。这个构造不仅证明了完备性还意外地提供了一个簇上的“自由代数”。事实上(\mathbf{L}_E(X)) 正是由 (E) 定义的簇在生成元集 (X) 上的自由代数见§15.4。但在伯克霍夫定理中完备性将被提升到一个全新的高度。15.3 Birkhoff 簇定理HSP 等式可定义1935年加勒特·伯克霍夫发表了划时代的论文《论代数结构的构造》On the structure of abstract algebras证明了泛代数中最著名的定理彻底揭示了等式类的语义特征。这一定理将“公理化”的句法行为与封闭性这种纯粹语义条件等价起来堪称公理化方法自我指涉的巅峰。15.3.1 三个闭包算子H, S, P定义 15.3.1H, S, P 闭包设 (\mathcal{K}) 是一类 (\Sigma)-代数。S子代数封闭(\mathbf{A} \in S(\mathcal{K})) 当且仅当 (\mathbf{A}) 同构于 (\mathcal{K}) 中某代数的子代数。H同态像封闭(\mathbf{A} \in H(\mathcal{K})) 当且仅当 (\mathbf{A}) 是 (\mathcal{K}) 中某代数的同态像即存在满同态 (\mathbf{B} \to \mathbf{A})其中 (\mathbf{B} \in \mathcal{K})。P直积封闭(\mathbf{A} \in P(\mathcal{K})) 当且仅当 (\mathbf{A}) 同构于 (\mathcal{K}) 中一簇代数的直积。直积设 ({\mathbf{A}i}{i \in I}) 是一族 (\Sigma)-代数。它们的直积 (\prod_{i \in I} \mathbf{A}_i) 的承载集是笛卡尔积 (\prod A_i)运算逐分量定义[f^{\prod \mathbf{A}_i}(a_1, \dots, a_n)(i) f^{\mathbf{A}_i}(a_1(i), \dots, a_n(i)).]常量 (c) 的分量是各个代数中常量的值。H, S, P 可看作作用于代数类上的算子。它们可以复合例如 (H S P(\mathcal{K})) 表示先取直积再取子代数最后取同态像。如果 (\mathcal{K}) 是一类代数那么包含 (\mathcal{K}) 且对 H, S, P 封闭的最小类正是这些算子的各种复合。Birkhoff 定理断言当 (\mathcal{K}) 本身是等式可定义的即簇时它就已经对这三种操作封闭了。15.3.2 Birkhoff 定理的陈述与详细证明定理 15.3.2Birkhoff 簇定理一类 (\Sigma)-代数 (\mathcal{V}) 是簇即可被一组等式公理化当且仅当它对 H, S, P 封闭即 (H(\mathcal{V}) \subseteq \mathcal{V}, S(\mathcal{V}) \subseteq \mathcal{V}, P(\mathcal{V}) \subseteq \mathcal{V})。证明分为两个方向。(⇒) 等式类对 H, S, P 封闭。设 (\mathcal{V}) 由等式集 (E) 定义。我们需要证若某个代数属于 (H(\mathcal{V})) 或 (S(\mathcal{V})) 或 (P(\mathcal{V}))则它也满足 (E)。子代数封闭S设 (\mathbf{A} \in \mathcal{V})(\mathbf{B} \le \mathbf{A})。对任意赋值 (h: X \to B)因为 (B \subseteq A)也可视为到 (A) 的赋值。因 (\mathbf{A} \models E)得 (\bar{h}(s) \bar{h}(t)) 在 (A) 中成立故在 (B) 中也成立。所以 (\mathbf{B} \models E)。同态像封闭H设 (\varphi: \mathbf{A} \to \mathbf{B}) 是满同态(\mathbf{A} \in \mathcal{V})。对任意赋值 (h: X \to B)因 (\varphi) 满可取提升 (\tilde{h}: X \to A) 使 (\varphi \circ \tilde{h} h)。由于 (\mathbf{A} \models E)有 (\overline{\tilde{h}}(s) \overline{\tilde{h}}(t))。应用 (\varphi)利用同态保持运算得到 (\bar{h}(s) \bar{h}(t))。故 (\mathbf{B} \models E)。直积封闭P设 (\mathbf{A} \prod_{i \in I} \mathbf{A}_i)每个 (\mathbf{A}_i \models E)。对任意赋值 (h: X \to A)考虑投影 (\pi_i \circ h: X \to A_i)。由于 (\mathbf{A}_i \models E)有 (\overline{\pi_i \circ h}(s) \overline{\pi_i \circ h}(t)) 对所有 (i) 成立。因此对每个分量 (i)(\bar{h}(s)(i) \bar{h}(t)(i))所以 (\bar{h}(s) \bar{h}(t))得 (\mathbf{A} \models E)。这一方向直接且机械它证实了等式定义的稳固性。(⇐) HSP 封闭类必是簇。设 (\mathcal{V}) 对 H, S, P 封闭。我们要找出一组等式 (E) 恰好定义 (\mathcal{V})。令[E { s \approx t \mid \text{对所有 } \mathbf{A} \in \mathcal{V}, \mathbf{A} \models s \approx t }.]即(E) 是 (\mathcal{V}) 的理论包含 (\mathcal{V}) 中所有成立的等式。显然 (\mathcal{V} \subseteq \operatorname{Mod}(E))(E) 的模型类。我们需要反包含若 (\mathbf{B} \models E)则 (\mathbf{B} \in \mathcal{V})。为此我们引入一个“通用”代数。选择一个充分大的变元集合 (X)其基数 (\kappa) 大于或等于 (\operatorname{Mod}(E)) 中所有代数的基数可通过取 (\kappa) 为某个足够大的正则基数实现或者更直接地对每个具体的 (\mathbf{B}) 我们只需存在性而不必一次性统一处理但统一处理更为优雅。经典证明如下构造项代数 (\mathbf{T}{\Sigma}(X)) 上的合同关系 (\theta)[s \mathrel{\theta} t \iff \text{对于所有 } \mathbf{A} \in \mathcal{V} \text{ 及所有赋值 } h: X \to A,\ \bar{h}(s) \bar{h}(t).]等价地(\theta) 是在所有 (\mathcal{V}) 中代数上都成立的等式决定的等价关系。由定义(\theta) 是合同关系。考虑商代数 (\mathbf{F} \mathbf{T}{\Sigma}(X)/\theta)。我们断言 (\mathbf{F} \in \mathcal{V})。为证明这一点考虑所有对 ((\mathbf{A}, h))其中 (\mathbf{A} \in \mathcal{V}) 且 (h: X \to A) 是任意赋值。它们构成一个集合因为 (X) 固定(\mathcal{V}) 是类但对每个固定的 (X)本质上赋值映射的个数有界。考察直积[\mathbf{P} \prod_{(\mathbf{A}, h)} \mathbf{A},]即对每一个 (\mathcal{V}) 中的代数和每一个赋值放入一个分量。定义映射 (\Phi: \mathbf{T}{\Sigma}(X) \to \mathbf{P}) 为[\Phi(t)(\mathbf{A}, h) \bar{h}(t) \in A.]换言之我们将项 (t) 送往它在每个可能语义解释下的值的“向量”。易验证 (\Phi) 是同态。其像 (\operatorname{Im}(\Phi)) 是直积 (\mathbf{P}) 的一个子代数。而 (\Phi) 的核恰好是 (\theta)因为 (s) 和 (t) 被 (\Phi) 映到相同向量当且仅当在所有 (\mathbf{A} \in \mathcal{V}) 及所有 (h) 下取值相等这正是 (\theta) 的定义。由同态分解定理[\mathbf{F} \mathbf{T}{\Sigma}(X)/\theta \cong \operatorname{Im}(\Phi) \le \mathbf{P}.]由于每个 (\mathbf{A} \in \mathcal{V})(\mathbf{P} \in P(\mathcal{V}))。又子代数封闭给出 (\operatorname{Im}(\Phi) \in S P(\mathcal{V}))。而 (\mathcal{V}) 对 S 和 P 封闭故 (S P(\mathcal{V}) \subseteq \mathcal{V})。因此 (\mathbf{F} \in \mathcal{V})。现在注意到(\mathbf{F}) 恰好是 (\operatorname{Mod}(E)) 上的自由代数见§15.4。事实上对于任意 (\mathbf{B} \models E)任一映射 (f: X \to B) 可唯一地扩展为同态 (\tilde{f}: \mathbf{T}_{\Sigma}(X) \to \mathbf{B})。因为 (\mathbf{B} \models E)所以对 (E) 中所有等式都成立而 (\theta) 由在 (\mathcal{V}) 中成立的等式生成但 (\mathbf{B}) 可能满足更多等式关键之处在于若 (s \theta t)则对所有 (\mathbf{A} \in \mathcal{V})(s \approx t) 成立但 (\mathbf{B}) 不一定在 (\mathcal{V}) 中。然而由于 (E) 是 (\mathcal{V}) 的理论且 (\mathbf{B} \models E)我们只知道 (\mathbf{B}) 满足所有在 (\mathcal{V}) 中成立的等式。因此若 (s \theta t)即这一等式属于 (E)可能作为语义后承则 (\mathbf{B} \models s \approx t)。所以 (\ker \tilde{f} \supseteq \theta)。于是 (\tilde{f}) 通过商映射分解得到同态 (\mathbf{F} \to \mathbf{B})。选择 (f: X \to B) 为满射因 (|X| \ge |B|) 可做到则该同态为满射。故 (\mathbf{B} \in H({\mathbf{F}}) \subseteq H(\mathcal{V}) \subseteq \mathcal{V})。至此反包含得证。∎Birkhoff 簇定理是泛代数最耀眼的结果。它告诉我们“可由等式定义”这一句法性质精确地对应于“对子代数、同态像、直积封闭”这一语义性质。任何同时满足 HSP 的代数类无论其具体运算为何都必然拥有一套完备的等式公理系统。群、环、模、格、布尔代数因此被统一在簇的旗帜之下。15.4 自由代数及其范性质15.4.1 合同关系与商代数在泛代数中商结构由合同关系congruence定义对应于群的正规子群和环的理想。定义 15.4.1合同关系(\Sigma)-代数 (\mathbf{A}) 上的等价关系 (\theta) 称为合同若它与 (\Sigma) 中所有运算兼容对所有 (f \in \Sigma)元数 (n)若 (a_i \mathrel{\theta} b_i)(i1,\dots,n)则[f^{\mathbf{A}}(a_1, \dots, a_n) \mathrel{\theta} f^{\mathbf{A}}(b_1, \dots, b_n).]在此情形下商集 (A/\theta) 上可自然定义 (\Sigma)-代数结构[f^{\mathbf{A}/\theta}([a_1]\theta, \dots, [a_n]\theta) [f^{\mathbf{A}}(a_1, \dots, a_n)]_\theta.]良定义由合同条件保证。由此得到商代数(\mathbf{A}/\theta)。自然投影是满同态核为 (\theta)。合同关系在群中对应正规子群(a\theta b \iff ab^{-1} \in N)在环中对应理想。泛代数将这一对应统一为合同的概念并建立了相应的同态定理若 (\varphi: \mathbf{A} \to \mathbf{B}) 是同态则核 (\ker \varphi {(a,b) \mid \varphi(a)\varphi(b)}) 是合同且 (\mathbf{A}/\ker \varphi \cong \operatorname{Im}\varphi)。这使得商结构理论完全系统化。15.4.2 自由代数的构造与泛性质定义 15.4.2自由代数设 (\mathcal{V}) 是 (\Sigma)-代数簇(X) 是一集合。(\mathcal{V}) 上由 (X) 生成的自由代数(\mathbf{F}{\mathcal{V}}(X)) 是一个带包含映射 (\eta: X \to F{\mathcal{V}}(X)) 的 (\mathcal{V})-代数满足如下泛性质对任意 (\mathbf{A} \in \mathcal{V}) 和任意映射 (h: X \to A)存在唯一的同态 (\tilde{h}: \mathbf{F}_{\mathcal{V}}(X) \to \mathbf{A}) 使得 (\tilde{h} \circ \eta h)。换言之任意生成元的指派可唯一地扩充为同态。自由代数就像“没有约束除了等式理论强制的关系之外”的代数。定理 15.4.3自由代数的存在性对任意簇 (\mathcal{V}) 和集合 (X)自由代数 (\mathbf{F}_{\mathcal{V}}(X)) 存在且在同构意义下唯一。构造取项代数 (\mathbf{T}{\Sigma}(X))。定义 (\mathbf{T}{\Sigma}(X)) 上的关系 (\theta)[s \mathrel{\theta} t \iff \text{对于 } \mathcal{V} \text{ 中所有代数 } \mathbf{A} \text{ 及所有赋值 } h: X \to A,\ \bar{h}(s) \bar{h}(t).]换言之(\theta) 是 (\mathcal{V}) 中全体等式语义后承的合同。由合同生成定理(\theta) 是 (\mathbf{T}{\Sigma}(X)) 上的合同。商代数 (\mathbf{T}{\Sigma}(X)/\theta) 即所求的自由代数 (\mathbf{F}{\mathcal{V}}(X))。泛性质的验证直接来自商代数的定义任意映射 (h: X \to A) 诱导项代数的同态 (\bar{h}: \mathbf{T}{\Sigma}(X) \to \mathbf{A})且 (\theta \subseteq \ker \bar{h})因此可通过商代数分解唯一性显然。∎自由代数在簇中是“最一般”的代数所有关系均来自簇中等式。在 Birkhoff 定理的证明中我们正是通过证明自由代数属于 (SP(\mathcal{V})) 从而属于 (\mathcal{V})完成了关键一步。从范畴论观点看自由代数构造给出了遗忘函子 (U: \mathcal{V} \to \mathbf{Set}) 的左伴随 (F: \mathbf{Set} \to \mathcal{V})。这种伴随关系刻画了代数结构的“自由生成”本质。15.4.3 自由代数实例群簇中自由群 (\mathbf{F}_{\mathrm{Grp}}(X)) 是集合 (X) 上的自由群其元素是简化字。交换群簇中自由交换群是直和 (\bigoplus_X \mathbb{Z} \cong \mathbb{Z}^X)当 (X) 有限时为 (\mathbb{Z}^{|X|})。含幺交换环簇中自由环是多项式环 (\mathbb{Z}[X])(X) 为变元集。模簇中自由模是相应基的直和。格簇中自由格的结构非常复杂但其存在由泛代数保证。域不构成簇见下节故没有自由域。15.5 簇与等式理论的实例15.5.1 群、环、模、格、布尔代数所有这些均为簇因为它们都由等式公理化。以格为例其签名 ({\vee, \wedge})等式包括结合律、交换律、吸收律[x \vee (y \vee z) \approx (x \vee y) \vee z, \quad x \vee y \approx y \vee x, \quad x \vee (x \wedge y) \approx x,]以及 (\wedge) 的对称版本。这些等式定义了格簇。布尔代数在格的基础上增加 (\neg, 0, 1) 和补充律 (x \vee \neg x \approx 1, x \wedge \neg x \approx 0)以及分配律同样构成簇。值得注意的是许多常见的代数子类并不是簇。例如无零因子环整环虽然可以由等式加上非等式条件刻画但整环类对直积不封闭两个整环的直积有零因子因此不是簇。同样除环、域、主理想整环等都不构成簇。15.5.2 域为什么不是簇域的公理通常包含“每个非零元有乘法逆元”[\forall x (x \neq 0 \to \exists y (x \cdot y 1)).]这里包含了否定(x \neq 0)和存在量词。等式逻辑不允许否定除非有特殊的补运算或存在量词。因此这一语句不是等式。能否添加一元运算 ({}^{-1}) 并用等式刻画逆元若定义 (0^{-1} 0) 或类似处理会得到 (0 \cdot 0^{-1} 0 1) 除非放弃一些环的性质。事实上域类对直积不封闭两个域的直积通常不是域因为有零因子 ((1,0) \cdot (0,1) (0,0))。此外域同态的满像可能是平凡环其中 (01)而平凡环通常不被视为域于是域类对 H 也不封闭。根据 Birkhoff 定理域不是簇。域的公理化需要一阶谓词演算的全力量词与否定。这就解释了为何泛代数通常不包含域论而模型论必须处理域。这也是代数与逻辑分界的一个标志等式理论适合“处处可运算、无条件成立”的代数结构而一旦涉及例外情形如非零元就必须借助更丰富的逻辑。15.5.3 半群、幺半群、群这些均是簇半群等式 (x \cdot (y \cdot z) \approx (x \cdot y) \cdot z)幺半群再加法单位元等式群再加法逆元等式。它们构成子簇链 (\mathcal{V}{\text{Sgp}} \supseteq \mathcal{V}{\text{Mon}} \supseteq \mathcal{V}_{\text{Grp}})。值得指出的是群也可以由单一等式使用除号运算公理化希格曼和诺依曼的结果这并不矛盾因为签名的选择不同但簇作为代数类是不变的。这体现了签名的辅助性而代数的本质性。15.6 HSP 定理的应用与深层结构15.6.1 生成簇与等价刻画给定任意 (\Sigma)-代数类 (\mathcal{K})包含 (\mathcal{K}) 的最小簇记作 (V(\mathcal{K}))称为由 (\mathcal{K}) 生成的簇。Birkhoff 定理的另一个等价形式为[V(\mathcal{K}) H S P(\mathcal{K}).]即反复取子代数、同态像和直积就能从 (\mathcal{K}) 生成整个簇。这提供了构造簇的算法性语义从一组初始代数出发通过这三种操作产生的所有代数恰好构成等式公理化所能捕捉的范围。这也可以视为“等式推理的完备性”在语义层面的表现所有在 (\mathcal{K}) 中成立的等式所定义的类正是 HSP 闭包。15.6.2 子直积与 Birkhoff 子直积表示定理除了完全直积还有子直积的概念代数 (\mathbf{A}) 是一族 ({\mathbf{A}i}{i \in I}) 的子直积若 (\mathbf{A}) 嵌入 (\prod \mathbf{A}_i)且每个投影到 (\mathbf{A}_i) 是满射。子直积捕获了“协调一致”的成分。一个代数 (\mathbf{A}) 称为子直不可约的如果对任何子直积表示 (\mathbf{A} \hookrightarrow \prod \mathbf{A}_i)其中某一投影是同构。换言之它不能“拆分”为更简单的非平凡子直积。在合同格中子直不可约等价于存在唯一的最小非平凡合同独异合同。定理 15.6.1Birkhoff 子直积表示定理每个代数同构于一族子直不可约代数的子直积。该定理的证明巧妙地利用了合同格的性质对每个非零元素对 ((a,b))可选取一个极大合同分离它们商代数是子直不可约的且所有这样的商代数构成一个子直积表示。在群论中子直不可约群包含所有单群但也包括如 (\mathbb{Z}/p^n\mathbb{Z})(p) 素数这类循环 (p)-群。在交换群中子直不可约群恰是子直不可约 (\mathbb{Z})-模即对每个素数幂次循环群和拟循环群。该定理在泛代数中的地位类似主理想整环上的准素分解将任何代数拆解为“基本构件”的复杂组合。15.6.3 簇的格结构全体 (\Sigma)-簇按照包含关系构成完备格。交是交集即满足两个簇等式的代数类并是由并集生成的簇。研究这个格的代数性质分配性、模性是泛代数的一个分支。例如群簇的格极其复杂包含大量非有限基的簇交换群簇的格已完全分类对应于自然数的某些集合。此外有限基簇有有限个等式公理化和有限生成的簇等问题也是重要课题。15.7 等式逻辑的证明论与重写系统等式逻辑不仅定义代数类也提供计算模型。将等式视为从左到右的重写规则[s \to t.]若一组重写规则具有合流性Church-Rosser性质和终止性则它构成一个项重写系统。该系统可自动判定两个项是否在等式理论中等价——只需不断重写直到无法再重写得到唯一正规形式比较它们是否相同即可。这种思想催生了现代函数式编程语言如Haskell、ML和定理证明器如Coq、Isabelle中的代数规约机制。纽曼引理Newman’s lemma指出若重写系统是终止的且局部合流的则它是合流的。这为等式理论的机械化提供了理论基础。群、环、布尔代数的许多等式理论均可找到合流且终止的重写系统从而实现可判定性。例如自由群有经典的合流终止重写系统[x \cdot e \to x, \quad e \cdot x \to x, \quad x^{-1} \cdot x \to e, \quad x \cdot x^{-1} \to e, \quad (x{-1}){-1} \to x,]加上结合律的特殊处理通常用平面化或模结合律。Knuth-Bendix 完成算法试图从一组等式自动生成合流终止的重写系统这在代数计算和自动推理中意义重大。15.8 泛代数与范畴论、模型论的交汇15.8.1 代数范畴与 Lawvere 理论在范畴论语言中一个簇对应于一个代数范畴即具体范畴带有遗忘函子到 (\mathbf{Set})且该遗忘函子有左伴随并且具有某些精确性质如 Barr 正合性。更精确地Lawvere 理论刻画了等式理论的范畴语义一个等式理论等价于一个具有有限积的小范畴 (\mathcal{L})其对象为自然数 (0,1,2,\dots)表示元数态射为运算的复合和投影满足有限积的性质。该理论的模型恰好是保持有限积的函子 (\mathcal{L} \to \mathbf{Set})。自由模型则对应到可表函子。这种视角将泛代数和范畴逻辑深度融合统一了代数结构的语义。单子monad观点同样有力簇上的自由代数单子 (\mathbb{T} U \circ F) 在 (\mathbf{Set}) 上其代数范畴 (\mathbf{Set}^{\mathbb{T}}) 等价于原簇。Birkhoff 定理可提升为伴随函子之间的正规满态射闭包等概念给出了广义的 HSP 定理。15.8.2 模型论视角等式理论是全称理论的特例全称公式无存在量词。模型论中全称理论对子结构封闭而全称 Horn 理论对直积封闭。簇恰好对 HSP 全封闭更为严格。因此簇是一类性质极好的初等类尽管不一定初等但由全称等式集定义必是初等类。模型论进一步研究簇中模型的结构如量词消去、稳定性、单纯性等。例如代数闭域理论不是簇因为它用到存在量词多项式有根但在固定特征下它是一阶理论且具有量词消去域论因而成为模型论的经典课题。这揭示了泛代数与模型论的分工前者处理无条件等式后者处理全一阶逻辑。15.8.3 代数逻辑泛代数与逻辑的交汇催生了代数逻辑。布尔代数对应于经典命题逻辑的林登鲍姆代数Heyting代数对应于直觉主义逻辑MV-代数对应于 Łukasiewicz 多值逻辑。这些代数类都是簇因此 Birkhoff 定理统一了逻辑与代数揭示了逻辑后承的代数本质。在这个意义上泛代数不仅仅是代数结构的理论也是逻辑系统的理论。15.9 结语公理的自我指涉从第十五章的起点——群、环、模的具体公理——我们攀升至泛代数的元公理层面。Birkhoff 簇定理在此成为一座灯塔它告诉我们公理化的行为等式有其必然的语义表征HSP封闭性。任何用等式刻画的结构类无论其运算签名为何必将拥有对子代数、同态像和直积封闭的性质反之任何满足这三条封闭性的代数类必然存在一套完备的等式公理系统。这是公理化方法的自我指涉我们不仅公理化数学对象还公理化“公理化”本身。泛代数与等式逻辑构成了元数学的重要篇章与形式逻辑和集合论遥相呼应共同绘制出数学基础的完整画卷。从怀特海的宏愿到伯克霍夫的定理数学家们证明了在等式的世界里语义与句法完美和谐而这个和谐的本质正是 HSP 这三种朴素操作的封闭性。在下一卷我们将离开代数踏入几何公理体系的宏伟殿堂。希尔伯特的五组二十条公理将重新定义点、线、面并以其无懈可击的严密性延续欧几里得两千年前的梦想。从代数的等式到几何的顺序与合同公理化的语言再次扩展它的疆域。