cover.png#代数结构与数理逻辑学习笔记5

参考书：

格论导引（方捷）

Lattice Theory: Foundation（George Grätzer）

本篇所需的前置知识——偏序集、上下确界、哈斯图、格的初步定义——已在《集合与图论学习笔记》ls01–ls02 中处理过，这里只作简单回顾，重点放在格作为代数系统的视角、分配格、有补格以及布尔代数的结构

本篇的主线是两条语言的互译

第一条是偏序语言：上确界、下确界、最大元、最小元

第二条是代数语言：两个二元运算 \(\vee,\wedge\) 及其恒等律

前半篇先证明这两种语言等价，再讨论同态、子格、理想和完备性；后半篇逐步加入分配性、补元和布尔运算，最后把布尔代数与布尔环、幂集表示联系起来

定义 15.1 偏序集与格

先从偏序出发

格的关键是任意两个元素即使不可比，也仍然能找到最小公共上界和最大公共下界

这样就可以把序结构转写成两个运算。

非空集合 \(L\) 上的二元关系 \(\leq\) 若满足：

• 自反性：\(a \leq a\)
• 反对称性：\(a \leq b\) 且 \(b \leq a\) 蕴含 \(a = b\)
• 传递性：\(a \leq b\) 且 \(b \leq c\) 蕴含 \(a \leq c\)

则称 \((L,\leq)\) 为偏序集（poset）

对 \(a,b \in L\)，若 \(a \leq b\) 或 \(b \leq a\)，则称二者可比；否则称为不可比，记作 \(a \parallel b\)

任意两个元素都可比的偏序集称为链（chain），又称全序集；任意两个不同元素都不可比的偏序集称为反链（antichain）

非空集合 \(H \subseteq L\) 的上确界 \(\sup H\) 是其全体上界中的最小者；下确界 \(\inf H\) 类似定义。在偏序集中上下确界若存在则唯一

若对 \(L\) 中任意 \(a,b\)，\(\{a,b\}\) 的上确界和下确界都存在，则称 \((L,\leq)\) 为格（lattice）

记 \[ a \vee b = \sup\{a,b\},\qquad a \wedge b = \inf\{a,b\} \] 分别称为 \(a,b\) 的并（join）与交（meet）

定理 15.1.1 有限子集的上下确界

若 \(L\) 是格，则对任意非空有限子集 \(H \subseteq L\)，\(\sup H\) 与 \(\inf H\) 都存在

特别地，有限格必有最小元 \(0\) 与最大元 \(1\)，分别记为 \(0_L\) 与 \(1_L\)

证明： 点击查看证明

对 \(|H|\) 作归纳

若 \(|H|=1\)，结论显然

若 \(|H| = n > 1\)，取 \(a \in H\)，由归纳假设 \(\sup(H \setminus \{a\})\) 存在，记为 \(b\)；则 \[ \sup H = a \vee b \] 依两元上确界的存在性即可证明

下确界同理

把这一结论应用于 \(L\) 本身（有限格），即得最小元与最大元

定理 15.1.2 序与运算的关系

设 \((L,\leq)\) 是格，\(a,b \in L\)，则：

• \(a \leq b \iff a \vee b = b\)
• \(a \leq b \iff a \wedge b = a\)

证明： 点击查看证明

若 \(a \leq b\)，则 \(b\) 是 \(\{a,b\}\) 的上界；任意上界 \(c\) 都满足 \(b \leq c\)，故 \(b = \sup\{a,b\} = a \vee b\)

反之若 \(a \vee b = b\)，则 \(a \leq a \vee b = b\)

第二式由对偶得到

定义 15.2 格

现在反过来，不从 \(\leq\) 出发，而把 \(\vee,\wedge\) 当作原始运算。若这两个运算满足幂等、交换、结合、吸收四类恒等式，就能重新定义出偏序。下面的定理说明“偏序意义下的格”和“代数系统意义下的格”其实是同一个对象的两种写法

设 \(L\) 是非空集合，\(\vee\)、\(\wedge\) 是 \(L\) 上的二元运算，若对任意 \(a,b,c \in L\) 满足：

• 幂等律：\(a \vee a = a\)，\(a \wedge a = a\)
• 交换律：\(a \vee b = b \vee a\)，\(a \wedge b = b \wedge a\)
• 结合律：\((a \vee b)\vee c = a \vee (b \vee c)\)，\((a \wedge b)\wedge c = a \wedge (b \wedge c)\)
• 吸收律：\(a \vee (a \wedge b) = a\)，\(a \wedge (a \vee b) = a\)

则称代数系统 \((L,\vee,\wedge)\) 为格

定理 15.2.1

设 \((L,\leq)\) 为偏序意义下的格，定义 \(a \vee b = \sup\{a,b\}\)，\(a \wedge b = \inf\{a,b\}\)，则 \((L,\vee,\wedge)\) 是代数意义下的格

反之，设 \((L,\vee,\wedge)\) 是代数意义下的格，定义 \[ a \leq b \iff a \vee b = b \] 则 \((L,\leq)\) 是偏序意义下的格，且 \(a \vee b\)、\(a \wedge b\) 分别给出上、下确界

这两种构造互为逆操作

证明： 点击查看证明

由偏序到代数：

幂等律由 \(\sup\{a,a\}=a\) 直接得；

交换律因 \(\sup\) 与 \(\inf\) 对集合操作无关于排列；

结合律由“多元上下确界结合性”立得；

吸收律：因 \(a \wedge b \leq a \leq a \vee (a \wedge b) \leq a\)，故 \(a \vee (a \wedge b)=a\)，另一式同理

由代数到偏序：

自反性：\(a \vee a = a\)，故 \(a \leq a\)

反对称性：若 \(a \vee b = b\) 且 \(b \vee a = a\)，由交换律得 \(a = b\)

传递性：若 \(a \vee b = b\) 且 \(b \vee c = c\)，则 \[ a \vee c = a \vee (b \vee c) = (a \vee b) \vee c = b \vee c = c \]

下证 \(a \vee b\) 是 \(\{a,b\}\) 的上确界

由结合律和幂等律 \[ a \vee (a \vee b) = (a \vee a) \vee b = a \vee b \] 故 \(a \leq a \vee b\)；同理 \(b \leq a \vee b\)

任取上界 \(u\)（满足 \(a \vee u = u\)，\(b \vee u = u\)），则 \[ (a \vee b) \vee u = a \vee (b \vee u) = a \vee u = u \] 故 \(a \vee b \leq u\)

吸收律保证下界同理。从这两种构造互逆显而易见

此后，我们对“格”一词在两种意义间不加区分

定理 15.2.2 对偶原理

把格 \((L,\leq)\) 中的偏序反向得到的偏序集 \((L,\geq)\) 仍是格，称为 \(L\) 的对偶，记为 \(L^{\partial}\)

在对偶格中 \[ a \vee^{\partial} b = a \wedge b,\qquad a \wedge^{\partial} b = a \vee b \] 最小元与最大元也对换

对偶原理：若关于格的命题 \(\Phi\) 在所有格中成立，则把 \(\Phi\) 中所有 \(\vee,\wedge,\leq\) 同时替换为 \(\wedge,\vee,\geq\) 得到的命题 \(\Phi^{\partial}\) 也在所有格中成立

这是因为 \(\Phi\) 在 \(L\) 中成立等价于 \(\Phi^{\partial}\) 在 \(L^{\partial}\) 中成立，而 \(L^{\partial}\) 取遍全体格

定理 15.2.3

设 \(L\) 是格，\(a,b,c \in L\)，则：

• 若 \(b \leq c\)，则 \(a \vee b \leq a \vee c\)，\(a \wedge b \leq a \wedge c\)
• \(\vee,\wedge\) 都是两个变量上的同时单调的运算

证明： 点击查看证明

设 \(b \leq c\)，则 \(b \wedge c = b\)，故 \[ (a \wedge b) \wedge (a \wedge c)=a \wedge (b \wedge c) = a \wedge b \] 所以 \(a \wedge b \leq a \wedge c\)；并运算同理

定义 15.3 子格、格同态与格同构

格同态要保持的是两个运算，而不只是保持顺序

保序映射只说明大小关系不被颠倒，格同态还要求上确界和下确界的构造本身也被保留下来

设 \(L\) 是格，\(K \subseteq L\) 非空。若对 \(a,b \in K\) 都有 \(a \vee b \in K\) 与 \(a \wedge b \in K\)（这里的运算取自 \(L\)），则称 \(K\) 为 \(L\) 的子格（sublattice）

设 \(L_1,L_2\) 都是格，映射 \(\varphi:L_1 \to L_2\) 若对任意 \(a,b \in L_1\) 满足 \[ \varphi(a \vee b) = \varphi(a) \vee \varphi(b),\qquad \varphi(a \wedge b) = \varphi(a) \wedge \varphi(b) \] 则称为格同态

• 单的格同态称为嵌入
• 双射的格同态称为格同构，记 \(L_1 \cong L_2\)
• 若两个格都有 \(0,1\)，且同态保 \(0\) 与 \(1\)，则称为 \(\{0,1\}\)-同态

定理 15.3.1 格同态

若 \(\varphi:L_1 \to L_2\) 是格同态，则它保持 \(\leq\)，即 \(a \leq b\) 蕴含 \(\varphi(a) \leq \varphi(b)\)

证明： 点击查看证明

设 \(a \leq b\)，则 \(a \vee b = b\)，故 \[ \varphi(b) = \varphi(a \vee b) = \varphi(a) \vee \varphi(b) \] 即 \(\varphi(a) \leq \varphi(b)\)

反之未必：保序映射只是“弱同态”，未必保两种运算

这与群、环的同态情形不同——序的存在让“格同态”比“保序映射”要求更强

定理 15.3.2 子格与“偏序子格”

如果取格 \(L\) 的非空子集 \(K\)，要求 \((K,\leq)\) 作为子偏序集本身是格，则不一定是 \(L\) 的子格

只有 \(K\) 在 \(L\) 的 \(\vee,\wedge\) 之下封闭，并且这两种运算限制到 \(K\) 仍然给出 \(K\) 上的上下确界时，才能称 \(K\) 为 \(L\) 的子格

反例： 点击查看反例

设 \(S=\{1,2,3\}\)，\(S_3\) 是 \(\{1,2,3\}\) 上的 \(3\) 次对称群

\((\mathcal{P}(S);\cup,\cap)\) 是一个格

取 \(T=\{\{e\}, H_1, H_2, H_3, H_4, S_3\}\)，其中 \[ H_1=\{e,\sigma_1\},\ H_2=\{e,\sigma_2\},\ H_3=\{e,\sigma_3\},\ H_4=\{e,\sigma_4,\sigma_5\} \] 都是 \(S_3\) 的子群

\((T,\subseteq)\) 关于包含关系是格，但 \(H_1 \cup H_2\) 并不属于 \(T\)（它甚至不是 \(S_3\) 的子群），所以 \(T\) 不是 \(\mathcal{P}(S_3)\) 的子格

注记 15.3.3 格在前几章中的体现

前几章里被反复使用的“子结构集合”几乎都可以用格刻画：

来源	对象	偏序与运算
ls11	群 \(G\) 的全体子群 \(\operatorname{Sub}(G)\)	\(\subseteq\)，并取 \(\langle H \cup K\rangle\)，交取 \(H \cap K\)
ls11	群 \(G\) 的正规子群 \(\operatorname{Nor}(G)\)	同上，运算给出 \(HK=H \lor K\)
ls13	环 \(R\) 的理想 \(\operatorname{Id}(R)\)	\(\subseteq\)，并取 \(I+J\)，交取 \(I \cap J\)
ls14	域扩张 \(F/K\) 的中间域	\(\subseteq\)，并取复合域，交取交域
ls14	伽罗瓦扩张的中间域 ↔︎ 子群	反向 \(\subseteq\)，给出格反同构（见 15.11.2）

定义 15.4 理想与滤子

群和环里都有“子结构集合”的格；在一般格里，也可以直接定义理想和滤子

设 \(L\) 是格，\(I \subseteq L\) 非空。若：

• \(a,b \in I\) 蕴含 \(a \vee b \in I\)
• \(x \in I\) 且 \(a \leq x\) 蕴含 \(a \in I\)

则称 \(I\) 为 \(L\) 的理想（ideal）

直观上，理想就是 \(L\) 的“下闭子格”——既对并封闭，又对取更小元封闭

\(L\) 的所有理想的集合记为 \(\operatorname{Id} L\)，按集合包含构成偏序集

由 \(H \subseteq L\) 生成的理想（包含 \(H\) 的最小理想）记为 \(\operatorname{id}(H)\)；若 \(H=\{a\}\)，记 \(\operatorname{id}(a)\)，称为主理想

把上面两条的方向反过来，得到滤子的定义：

• \(a,b \in F\) 蕴含 \(a \wedge b \in F\)
• \(x \in F\) 且 \(a \geq x\) 蕴含 \(a \in F\)

由 \(H\) 生成的滤子记为 \(\operatorname{fil}(H)\)，主滤子记为 \(\operatorname{fil}(a)\)

定理 15.4.1 理想的表示

设 \(L\) 是格，\(H \subseteq L\) 非空，则 \[ \operatorname{id}(H)=\{x \in L \mid \exists\, n\geq 1,\ \exists\, h_1,\dots,h_n \in H,\ x \leq h_1 \vee \cdots \vee h_n\} \] 特别地 \[ \operatorname{id}(a)=\{x \in L \mid x \leq a\} \]

证明： 点击查看证明

记右边集合为 \(I_0\)

包含性：\(H \subseteq I_0\)（取 \(n=1\) 且 \(h_1 = h\)）；任取 \(x,y \in I_0\)，存在 \(h_i,h'_j \in H\) 使 \(x \leq h_1 \vee\cdots\vee h_n\)，\(y \leq h'_1\vee\cdots\vee h'_m\)，故 \[ x \vee y \leq h_1\vee\cdots\vee h_n\vee h'_1\vee\cdots\vee h'_m \] 仍属 \(I_0\)；且若 \(a \leq x \in I_0\)，显然 \(a \in I_0\)

最小性：若 \(J\) 是包含 \(H\) 的理想，\(x \in I_0\)，则 \(x \leq h_1\vee\cdots\vee h_n\)，而每个 \(h_i \in J\)，由 \(J\) 对并封闭得 \(h_1\vee\cdots\vee h_n \in J\)，再由 \(J\) 是下闭得 \(x \in J\)，故 \(I_0 \subseteq J\)

定理 15.4.2 理想格

\(\operatorname{Id} L\) 按集合包含构成一个格，其中 \[ I \wedge J = I \cap J,\qquad I \vee J = \operatorname{id}(I \cup J) \] 并且 \[ \operatorname{id}(a) \vee \operatorname{id}(b)=\operatorname{id}(a \vee b),\qquad \operatorname{id}(a) \wedge \operatorname{id}(b)=\operatorname{id}(a \wedge b) \] 所以映射 \(a \mapsto \operatorname{id}(a)\) 是 \(L\) 到 \(\operatorname{Id} L\) 的格嵌入

证明： 点击查看证明

理想的交仍是理想，因此 \(I \cap J\) 是 \(\{I,J\}\) 的下确界

由理想的定义，\(I \cup J\) 不一定是理想，所以并定义为 \(\operatorname{id}(I \cup J)\)，它是包含 \(I \cup J\) 的最小理想

对主理想：\(x \in \operatorname{id}(a)\vee \operatorname{id}(b)\) 当且仅当存在 \(u \in \operatorname{id}(a),v \in \operatorname{id}(b)\) 使 \(x \leq u \vee v\)，等价于 \(x \leq a \vee b\)，即 \(x \in \operatorname{id}(a \vee b)\)

主理想之交显然给出 \(\operatorname{id}(a \wedge b)\)

最后 \(a \neq b\) 蕴含 \(\operatorname{id}(a) \neq \operatorname{id}(b)\)，故映射是嵌入

定义 15.4.3 素理想

\(L\) 的真理想 \(I\)（即 \(I \neq L\)）若满足 \[ a \wedge b \in I \Longrightarrow a \in I\ \text{或}\ b \in I \] 则称 \(I\) 为素理想（prime ideal）

对偶地，真滤子 \(F\) 若满足 \(a \vee b \in F \Rightarrow a \in F\) 或 \(b \in F\)，则称为素滤子

定理 15.4.4 素理想与到二元链的同态

\(L\) 的真理想 \(I\) 是素理想，当且仅当存在格同态 \(\varphi:L \to \{0,1\}\)（这里 \(\{0,1\}\) 是两元链）使 \[ I=\varphi^{-1}(0) \]

证明： 点击查看证明

充分性：若有这样的 \(\varphi\)，则 \(a \wedge b \in I\) 即 \(\varphi(a)\wedge \varphi(b)=0\)，于是 \(\varphi(a)=0\) 或 \(\varphi(b)=0\)，即 \(a \in I\) 或 \(b \in I\)，且 \(I \neq L\) 显然

必要性：定义 \[ \varphi(x)=\begin{cases}0,& x \in I\\ 1,& x \notin I\end{cases} \] \(\varphi\) 保 \(\vee\)：若 \(a,b \in I\)，则 \(a \vee b \in I\)，两边为 \(0\)；若至少一个不属于 \(I\)，则 \(a \vee b \notin I\)（因为 \(I\) 下闭），两边都为 \(1\)

\(\varphi\) 保 \(\wedge\)：若都不属于 \(I\)，由素性 \(a \wedge b \notin I\)，两边为 \(1\)；若至少一个属于 \(I\)，则 \(a \wedge b\) 落入 \(I\)，两边为 \(0\)

定义 15.5 有界格与完备格

前面的格只要求任意两个元素有并和交，完备格把这个要求推广到任意子集

格 \(L\) 若有最小元 \(0\) 和最大元 \(1\)，则称为有界格。它们也称作零元与单位元。每个有限格显然有界

若 \(L\) 的每个非空子集 \(S\) 都有上确界 \(\bigvee S\) 与下确界 \(\bigwedge S\)，则称 \(L\) 为完备格

约定 \(\bigvee \varnothing=0\)，\(\bigwedge \varnothing=1\)，故完备格必有界

例子：

• 任意集合 \(X\) 的幂集 \((\mathcal{P}(X),\subseteq)\) 是完备格，运算分别是并与交
• 任一群 \(G\) 的全体子群关于包含构成完备格（注意运算不再是简单的并）
• \(\mathbb{R} \cup \{-\infty,+\infty\}\) 关于通常序是完备的
• \((\mathbb{Q},\leq)\) 是格但不完备：有界单调子集未必有上确界

对子群格可以把“不是简单的并”写成明确公式。若 \(\mathcal{A}\) 是 \(G\) 的一族子群，则 \[ \bigwedge_{H\in\mathcal{A}}H=\bigcap_{H\in\mathcal{A}}H,\qquad \bigvee_{H\in\mathcal{A}}H=\left\langle \bigcup_{H\in\mathcal{A}}H\right\rangle \] 也就是说，下确界仍是交；上确界则是由所有子群的并集生成的子群，而不是集合论意义下的并

定理 15.5.1 完备格判别

偏序集 \(L\) 是完备格，当且仅当每个子集 \(S \subseteq L\) 都有上确界

特别地，要验证完备性，只需检验“上确界存在”这一方向

证明： 点击查看证明

若每个子集都有上确界，则对任意 \(S \subseteq L\)，记 \[ S^\ell=\{a \in L \mid a \leq s,\forall s \in S\} \] 为 \(S\) 的下界全体。\(S^\ell\) 是 \(L\) 的一个子集，由假设它有上确界 \(b\)。下证 \(b=\inf S\)

每个 \(s \in S\) 都是 \(S^\ell\) 的上界，故 \(b \leq s\)，即 \(b\) 是 \(S\) 的下界

任取 \(S\) 的下界 \(a\)，则 \(a \in S^\ell\)，故 \(a \leq b\)。所以 \(b\) 是最大的下界

类似地“每个子集都有下确界 \(\Rightarrow\) 每个子集都有上确界”

故只需验证一个方向

定理 15.5.2 Knaster–Tarski 不动点定理

设 \(L\) 是完备格，\(f:L \to L\) 保序（即 \(a \leq b \Rightarrow f(a) \leq f(b)\)），则 \(f\) 的不动点集合 \[ \operatorname{Fix}(f)=\{x \in L \mid f(x)=x\} \] 在 \(L\) 的诱导序下是完备格

特别地，\(f\) 总有最小不动点 \[ \bigwedge\{x \in L \mid f(x)\leq x\} \] 和最大不动点 \[ \bigvee\{x \in L \mid x \leq f(x)\} \]

证明： 点击查看证明

记 \[ D=\{x \in L \mid f(x)\leq x\},\quad U=\{x \in L \mid x \leq f(x)\} \] 均非空（\(1 \in D\)，\(0 \in U\)）

令 \(m=\bigwedge D\)。对任意 \(x \in D\)，\(m \leq x\)，故 \(f(m)\leq f(x)\leq x\)，于是 \(f(m)\) 是 \(D\) 的下界，故 \(f(m)\leq m\)，即 \(m \in D\)

由 \(m \in D\) 且 \(f(m)\leq m\)，再用单调性 \(f(f(m))\leq f(m)\)，所以 \(f(m)\in D\)，故 \(m \leq f(m)\)，从而 \(f(m)=m\)

由 \(m\) 是 \(D\) 的最小元，且每个不动点都在 \(D\) 中，故 \(m\) 是最小不动点。最大不动点对偶可得

要看 \(\operatorname{Fix}(f)\) 本身是完备格，任取 \(S \subseteq \operatorname{Fix}(f)\)。令 \[ b=\bigvee S,\qquad I_b=\{x \in L \mid b \leq x,\ f(x)\leq x\} \] \(I_b\) 非空（\(1 \in I_b\)），按 \(L\) 的序构成完备子格（对交封闭且下界存在）

把 \(f\) 限制到 \(I_b\) 上仍保序，故由上面同样论证它在 \(I_b\) 中有最小不动点，这就是 \(S\) 在 \(\operatorname{Fix}(f)\) 中的上确界

下确界同理

这一定理是格论应用到逻辑学、程序语义、自动机理论的核心工具

定义 15.6 分配格

在任意格中，总有一些单调性和吸收律；分配格则要求 \(\wedge\) 与 \(\vee\) 的相互作用更像集合的交并。可以把它看成从“一般上下确界结构”向“集合代数结构”靠近的第一步。

格 \(L\) 若对任意 \(a,b,c \in L\) 满足 \[ a \wedge (b \vee c) = (a \wedge b)\vee (a \wedge c) \] 则称为分配格（distributive lattice）

定理 15.6.1 两条分配律等价

在任何格中，下列三条等价：

• \(a \wedge (b \vee c)=(a \wedge b)\vee (a \wedge c)\) 对所有 \(a,b,c\) 成立
• \(a \vee (b \wedge c)=(a \vee b)\wedge (a \vee c)\) 对所有 \(a,b,c\) 成立
• \((a \wedge b)\vee (b \wedge c)\vee (c \wedge a)=(a \vee b)\wedge (b \vee c)\wedge (c \vee a)\)

证明： 点击查看证明

设第一条成立，则 \[ \begin{aligned} (a \vee b)\wedge (a \vee c) &=\bigl((a \vee b)\wedge a\bigr)\vee \bigl((a \vee b)\wedge c\bigr)\\ &=a \vee \bigl((a \wedge c)\vee (b \wedge c)\bigr)\\ &=\bigl(a \vee (a \wedge c)\bigr)\vee (b \wedge c)\\ &=a \vee (b \wedge c) \end{aligned} \] 其中第一步用第一条分配律展开，第二步用了吸收律 \((a \vee b)\wedge a = a\)，第三步是结合律，第四步是吸收律

由对偶得到第二条蕴含第一条

设两条都成立，则 \[ \begin{aligned} (a \vee b)\wedge (b \vee c)\wedge (c \vee a) &=\bigl(b \vee (a \wedge c)\bigr)\wedge (c \vee a)\\ &=\bigl(b \wedge (c \vee a)\bigr)\vee \bigl((a \wedge c)\wedge (c \vee a)\bigr)\\ &=(b \wedge c)\vee (b \wedge a)\vee (a \wedge c) \end{aligned} \] 故第三条成立

反过来设第三条成立。展开 \[ (a \wedge b)\vee (a \wedge c)\leq a,\qquad (a \wedge b)\vee (a \wedge c)\leq b \vee c \] 故 \((a \wedge b)\vee (a \wedge c)\leq a \wedge (b \vee c)\)

另一方向：把第三条用到 \(a\)、\(b \vee c\)、\(a\) 等元素的组合上化简，最终可得相反不等式

也就是说，分配格的定义是“自对偶”的——把 \(\vee,\wedge\) 互换得到等价的等式

定理 15.6.2 N5 与 M3 的刻画

格 \(L\) 是分配格，当且仅当 \(L\) 不含同构于 \(N_5\) 或 \(M_3\) 的子格

这里 \(N_5\)（五边形）与 \(M_3\)（钻石）是下面这两个最小的非分配格——它们都恰好有五个元素：

\(N_5\)：五个元素 \(0,a,b,c,1\)，其中 \(0<a<b<1\) 构成一条三段链；另外 \(c\) 满足 \(0<c<1\)，且 \(c\) 与 \(a,b\) 都不可比，并满足 \[ a \vee c = b \vee c = 1,\qquad a \wedge c = b \wedge c = 0 \]

\(M_3\)：五个元素 \(0,a,b,c,1\)，其中 \(a,b,c\) 严格在 \(0\) 与 \(1\) 之间，两两不可比，且 \[ a \vee b = a \vee c = b \vee c = 1,\qquad a \wedge b = a \wedge c = b \wedge c = 0 \]

它们的哈斯图：

 N5                  M3

  1                   1
 / \                 /|\
b   \               a b c
|    c               \|/
a   /                 0
 \ /
  0

它们都只用五个元素就把分配律破坏掉

证明： 点击查看证明

必要性（含 \(N_5\) 或 \(M_3\) 子格 \(\Rightarrow\) 不分配）：

在 \(N_5\) 中取三元组 \((b,a,c)\)，由 \(a<b\) 有 \(b \wedge a = a\)，故 \[ b \wedge (a \vee c) = b \wedge 1 = b,\qquad (b \wedge a)\vee (b \wedge c) = a \vee 0 = a \] 而 \(a \neq b\)，分配律失败

在 \(M_3\) 中取三元组 \((a,b,c)\)： \[ a \wedge (b \vee c) = a \wedge 1 = a,\qquad (a \wedge b)\vee (a \wedge c) = 0 \vee 0 = 0 \] 而 \(a \neq 0\)，分配律失败

含有 \(N_5\) 或 \(M_3\) 子格的大格自然继承上面的反例，因此也不分配

充分性（不分配 \(\Rightarrow\) 含 \(N_5\) 或 \(M_3\) 子格）：

设 \(L\) 非分配。我们按下面这个辅助等式是否总成立来分两种情况： \[ r\leq t\quad\Longrightarrow\quad (t\wedge s)\vee r=t\wedge(s\vee r). \]

情形一：存在 \(r\leq t\) 使上面的辅助等式失败

也就是说，存在 \(r,s,t\in L\)，\(r\leq t\)，使 \[ (t\wedge s)\vee r\neq t\wedge(s\vee r) \] 而任意格中总有 \[ (t\wedge s)\vee r\leq t\wedge(s\vee r) \] 所以可记 \[ u=(t\wedge s)\vee r,\qquad v=t\wedge(s\vee r) \] 并且有 \(u<v\)。

再记 \[ p=t\wedge s,\qquad q=s\vee r \] 下面证明五个元素 \[ p,\quad u,\quad v,\quad s,\quad q \] 构成一个 \(N_5\)

先看长链。由 \[ p=t\wedge s\leq (t\wedge s)\vee r=u<v=t\wedge(s\vee r)\leq s\vee r=q \] 得到 \[ p\leq u<v\leq q \] 事实上 \(p<u\)，否则 \(u=p\) 会推出 \(r\leq p\leq s\)，于是 \(q=s\)，从而 \(v=t\wedge s=p=u\)，矛盾。也有 \(v<q\)，否则 \(q=v\leq t\)，于是 \(s\leq t\)，从而 \(p=s\)、\(u=s\vee r=s=q=v\)，也矛盾

因此 \[ p<u<v<q \]

再看旁支元素 \(s\) 与这条链的交、并

首先 \[ s\wedge v=s\wedge t\wedge(s\vee r)=t\wedge s=p \] 又因 \(u\leq v\)，有 \[ p=t\wedge s\leq s\wedge u\leq s\wedge v=p \] 故 \[ s\wedge u=s\wedge v=p \] 类似地， \[ s\vee u=s\vee\bigl((t\wedge s)\vee r\bigr)=s\vee r=q \] 又因 \(u\leq v\leq q\)，有 \[ q=s\vee u\leq s\vee v\leq s\vee q=q \] 故 \[ s\vee u=s\vee v=q \]

因此，在这五个元素里，\(p<u<v<q\) 是一条链，而 \(s\) 与 \(u,v\) 的交都是 \(p\)、并都是 \(q\)

这正是五边形 \(N_5\) 的运算表：\(p\) 是底，\(q\) 是顶，\(u<v\) 是长边中间两点，\(s\) 是旁支。所以它们构成同构于 \(N_5\) 的子格

情形二：对所有 \(r\leq t\)，辅助等式都成立

由于 \(L\) 非分配，存在 \(a,b,c\in L\) 使 \[ a\wedge(b\vee c)>(a\wedge b)\vee(a\wedge c) \] 因为反向不等式在任意格中恒成立

定义 \[ p=(a\wedge b)\vee(b\wedge c)\vee(c\wedge a) \] \[ q=(a\vee b)\wedge(b\vee c)\wedge(c\vee a) \] 并令 \[ x=(a\wedge q)\vee p,\qquad y=(b\wedge q)\vee p,\qquad z=(c\wedge q)\vee p. \] 因为 \(a\wedge b,b\wedge c,c\wedge a\) 都小于等于 \(a\vee b,b\vee c,c\vee a\) 中的每一项，所以 \(p\leq q\)

因此 \[ p\leq x,y,z\leq q. \] 下面证明 \(p,x,y,z,q\) 构成一个 \(M_3\)

先证 \(p<q\)

因为 \[ a\wedge q=a\wedge(b\vee c) \] 而由本情形的辅助等式 \[ \begin{aligned} a\wedge p &=a\wedge\bigl((b\wedge c)\vee(a\wedge b)\vee(a\wedge c)\bigr)\\ &=(a\wedge b)\vee(a\wedge c) \end{aligned} \] 第二个等号可这样看：令 \(r=(a\wedge b)\vee(a\wedge c)\)，则 \(r\leq a\)，于是 \[ a\wedge p=a\wedge\bigl(r\vee(b\wedge c)\bigr) =r\vee\bigl(a\wedge b\wedge c\bigr)=r \] 若 \(p=q\)，则 \(a\wedge p=a\wedge q\)，从而 \[ (a\wedge b)\vee(a\wedge c)=a\wedge(b\vee c) \] 这与分配律失败的选取矛盾。因此 \(p\neq q\)；又 \(p\leq q\)，故 \(p<q\)

接着证两两交为 \(p\)

只算 \(x\wedge y\)，其余两个由 \(a,b,c\) 的循环对称性完全相同。用辅助等式化简： \[ \begin{aligned} x\wedge y &=\bigl((a\wedge q)\vee p\bigr)\wedge\bigl((b\wedge q)\vee p\bigr)\\ &=\Bigl(\bigl((b\wedge q)\vee p\bigr)\wedge(a\wedge q)\Bigr)\vee p\\ &=\Bigl(\bigl(q\wedge(b\vee p)\bigr)\wedge(a\wedge q)\Bigr)\vee p\\ &=\bigl((b\vee p)\wedge(a\wedge q)\bigr)\vee p \end{aligned} \] 这里第三步用了 \(p\leq q\)，所以 \((b\wedge q)\vee p=q\wedge(b\vee p)\)

再代入 \(a\wedge q=a\wedge(b\vee c)\)，并注意 \[ b\vee p=b\vee(c\wedge a) \] 因为 \(a\wedge b\leq b\)、\(b\wedge c\leq b\) 都会被 \(b\) 吸收

于是 \[ \begin{aligned} x\wedge y &=\bigl((b\vee(c\wedge a))\wedge a\wedge(b\vee c)\bigr)\vee p\\ &=\bigl(a\wedge(b\vee(c\wedge a))\bigr)\vee p\\ &=\bigl((a\wedge b)\vee(c\wedge a)\bigr)\vee p\\ &=p \end{aligned} \] 所以 \[ x\wedge y=y\wedge z=z\wedge x=p \]

再证两两并为 \(q\)。把上一段计算中的上下符号对调，并把 \(p,q\) 的角色对调，可得完全相同的计算，因此 \[ x\vee y=y\vee z=z\vee x=q \] 这里能直接对调，是因为由 \(p\leq q\) 和辅助等式也有 \[ x=(a\wedge q)\vee p=(a\vee p)\wedge q, \] \(y,z\) 同理，所以 \(x,y,z\) 的定义本身关于区间 \([p,q]\) 上下对称。若不借助对调语言，也可以逐项重复同样的计算。

最后，由 \(p<q\)、两两交为 \(p\)、两两并为 \(q\) 可知 \(x,y,z\) 都严格夹在 \(p\) 与 \(q\) 之间，并且两两不可比。比如若 \(x=p\)，则由 \(x\vee y=q\)、\(x\vee z=q\) 得 \(y=z=q\)，这又使 \(y\wedge z=q\neq p\)，矛盾；若 \(x=q\) 也类似矛盾。若 \(x=y\)，则 \(x\wedge y=x\) 与 \(x\vee y=x\) 会同时给出 \(x=p\) 和 \(x=q\)，也矛盾。因此五个元素 \[ p,\quad x,\quad y,\quad z,\quad q \] 以 \(p\) 为底、\(q\) 为顶，三个中间元素两两交为底、两两并为顶，正构成 \(M_3\) 子格

综上，两种情形分别给出 \(N_5\) 或 \(M_3\) 子格

充分性得证

这是 Birkhoff 1934 年的经典刻画。它的实用价值在于：判断一个格是否分配，只要扫一遍哈斯图，看有无“五边形”或“钻石”作为子图——无需逐三元组验证分配律

课堂上这里通常只使用这个判别结论，而不展开完整证明。上面的证明把关键的五元子格直接构造出来，实际使用时通常只需要记住结论本身。

定理 15.6.3

设 \(L\) 是分配格，\(a,b \in L\)，\(a \leq b\)。若 \(x_1,x_2\) 都是 \(a\) 在区间 \([a,b]\) 中针对某固定元素 \(y\) 的相对补元——即 \[ y \vee x_i = b,\quad y \wedge x_i = a,\qquad i=1,2 \] 则 \(x_1 = x_2\)

更一般地，分配格中每个元素 \(y\) 在任意区间内至多有一个相对补元

证明： 点击查看证明

由分配律 \[ x_1=x_1 \wedge b = x_1 \wedge (y \vee x_2)=(x_1 \wedge y)\vee (x_1 \wedge x_2)=a \vee (x_1 \wedge x_2) \] 对 \(x_2\) 同理 \(x_2 = a \vee (x_1 \wedge x_2)\)，故 \(x_1 = x_2\)

定理 15.6.4

设 \(L\) 是分配格，\(I,J \in \operatorname{Id} L\)，则 \[ I \vee J=\{i \vee j \mid i \in I,\ j \in J\} \]

证明： 点击查看证明

包含 \(\supseteq\) 显然

反向：任取 \(t \in I \vee J\)，由定理 15.4.1，\(t \leq h_1 \vee \cdots \vee h_n\)，其中每个 \(h_k\) 属于 \(I\) 或 \(J\)。把属于 \(I\) 的并起来记为 \(i_0\)，把属于 \(J\) 的并起来记为 \(j_0\)，则 \(i_0 \in I\)，\(j_0 \in J\)，\(t \leq i_0 \vee j_0\)。由分配律 \[ t = t \wedge (i_0 \vee j_0)=(t \wedge i_0)\vee (t \wedge j_0) \] 而 \(t \wedge i_0 \in I\)，\(t \wedge j_0 \in J\)（理想下闭），故 \(t\) 形如 \(i \vee j\)

定理 15.6.5 有限分配格的不可约元素表示

设 \(L\) 是有限分配格。元素 \(a \in L\) 若 \(a \neq 0\) 且 \[ a = b \vee c \Longrightarrow a = b\ \text{或}\ a = c \] 则称为并不可约元

记 \(\operatorname{Ji}(L)\) 为 \(L\) 中全体非零并不可约元构成的偏序集

则映射 \[ \varphi:L \to \operatorname{Down}(\operatorname{Ji}(L)),\qquad \varphi(a)=\{x \in \operatorname{Ji}(L)\mid x \leq a\} \] 是格同构。这里 \(\operatorname{Down}(P)\) 表示偏序集 \(P\) 的所有下集按包含构成的格

特别地：

• 有限分配格的结构由其并不可约元的偏序集唯一决定
• 有限格是分配格，当且仅当它同构于某个有限集合的子集环（subset ring）

证明思路： 点击查看证明

下集格 \(\operatorname{Down}(P)\) 在并与交即集合并交下显然分配，故 \(\varphi\) 良定义且像在分配格中

\(\varphi(a \vee b)=\varphi(a)\cup \varphi(b)\)：\(x \in \operatorname{Ji}(L)\)，\(x \leq a \vee b\)，由分配律 \(x = (x \wedge a)\vee (x \wedge b)\)，由并不可约知 \(x = x \wedge a\) 或 \(x = x \wedge b\)，即 \(x \leq a\) 或 \(x \leq b\)

\(\varphi(a \wedge b)=\varphi(a)\cap \varphi(b)\) 显然

\(\varphi\) 是单射：由有限性，每个元素都能表为并不可约元的并 \(a=\bigvee \varphi(a)\)，故 \(\varphi(a)=\varphi(b) \Rightarrow a=b\)

\(\varphi\) 是满射：任取下集 \(A\)，令 \(a=\bigvee A\)，则 \(\varphi(a)=A\)

这条定理被称为有限分配格的表示定理，由 G. Birkhoff 于 1933 年给出

推论 15.6.6 分配格嵌入幂集

每个分配格 \(L\) 都可以嵌入某集合 \(X\) 的幂集 \(\mathcal{P}(X)\) 中

换言之，分配格恰好是”幂集的子格”

证明思路： 点击查看证明

有限情形已由定理 15.6.5 给出：\(L \cong \operatorname{Down}(\operatorname{Ji}(L))\)，而 \(\operatorname{Down}(P)\) 本身就是 \(\mathcal{P}(P)\) 的子格

一般情形，取 \(X\) 为 \(L\) 的全体素理想集合，定义 \[ \sigma:L \to \mathcal{P}(X),\qquad \sigma(a)=\{P \in X \mid a \notin P\} \] 即 \(\sigma(a)\) 是”\(a\) 不属于”的素理想集

\(\sigma(a \vee b)=\sigma(a)\cup \sigma(b)\)：\(a \vee b \notin P\) 当且仅当 \(a \notin P\) 或 \(b \notin P\)（因 \(P\) 是理想，闭并）

\(\sigma(a \wedge b)=\sigma(a)\cap \sigma(b)\)：\(a \wedge b \notin P\) 等价于 \(a \notin P\) 且 \(b \notin P\)（由素性）

单射：若 \(a \neq b\)，不妨 \(a \nleq b\)。由 Zorn 引理可构造一个不含 \(a\) 但包含 \(\operatorname{id}(b)\) 的极大理想（同 15.10.2 的证法），并验证其素性，从而它把 \(a\) 与 \(b\) 分开

这条结果等价于布尔代数 Stone 表示定理的“分配格版本”

它说明，把“布尔代数嵌入幂集”中的“补”性质拿掉，仍正确

定义 15.7 有补格与相对补格

分配性控制 \(\vee,\wedge\) 的相互作用，补元则引入类似集合补集的结构。注意这两个条件彼此独立：有补不保证分配，分配也不保证有补。布尔格正是把这两者同时加上

设 \(L\) 是有界格，\(a \in L\)。若存在 \(b \in L\) 使 \[ a \vee b = 1,\qquad a \wedge b = 0 \] 则称 \(b\) 为 \(a\) 的补元（complement），并称 \(a\) 为可补元

若 \(L\) 中每个元素都有补元，则称 \(L\) 为有补格（complemented lattice）

设 \(L\) 是格，\(a,b,c \in L\)，\(a \leq c\)。\(b\) 称为 \(a\) 在区间 \([a',c']\) 中的相对补元，若存在 \(a'\leq b\leq c'\) 与某个 \(a''\) 满足该区间内的补关系；这一定义在一般文献中通常表述为：

若对每个区间 \([a,c]\)（\(a \leq c\)）和每个 \(b \in [a,c]\)，\(b\) 在 \([a,c]\) 中存在相对补元，即存在 \(x \in [a,c]\) 使 \[ b \vee x = c,\qquad b \wedge x = a \] 则称 \(L\) 为相对补格（relatively complemented lattice）

注意：

• 有补格中元素的补元未必唯一（如 \(M_3\)）
• 相对补格未必是有界格；定义不依赖整体的 \(0,1\)

例子：

• \(M_3\) 是有补格也是相对补格，但不是分配格
• \(N_5\) 是有补格但不是相对补格（区间 \([0,b]\) 中的 \(a\) 没有相对补元）
• 链是分配格，但只有两元链才有补

定理 15.7.1

设 \(L\) 是有界分配格，\(a \in L\)。若 \(a\) 有补元，则补元唯一

证明： 点击查看证明

设 \(b_1,b_2\) 都是 \(a\) 的补元，则 \[ b_1 = b_1 \wedge 1 = b_1 \wedge (a \vee b_2)=(b_1 \wedge a)\vee (b_1 \wedge b_2)=0\vee (b_1 \wedge b_2)=b_1 \wedge b_2 \] 故 \(b_1 \leq b_2\)；同理 \(b_2 \leq b_1\)，所以 \(b_1=b_2\)

这就把“分配”与“补元唯一”紧紧绑在了一起。注意：补元唯一不蕴含分配（有反例，但需要更多元素），不过在合理的额外条件下，唯一补蕴含分配（如有限格、模格中）

定理 15.7.2 分配格 + 有补 = 相对补

有界分配格若是有补格，则也是相对补格

证明： 点击查看证明

设 \(L\) 有补，\(a \leq c\)，\(b \in [a,c]\)。设 \(b'\) 是 \(b\) 在 \(L\) 中的（唯一）补元。令 \[ x = (b'\vee a)\wedge c \] 则 \(a \leq x \leq c\)。计算 \[ b \vee x = b \vee \bigl((b' \vee a)\wedge c\bigr) \] 由分配律 \[ b \vee x =\bigl((b \vee b' \vee a)\wedge (b \vee c)\bigr)= 1 \wedge c = c \] \[ b \wedge x = b \wedge (b'\vee a)\wedge c=\bigl((b \wedge b')\vee (b \wedge a)\bigr)\wedge c=(0 \vee a)\wedge c = a \] 故 \(x\) 是 \(b\) 在 \([a,c]\) 中的相对补元

定理 15.7.3

有界格 \(L\) 是分配且有补，当且仅当 \(L\) 是分配相对补的——等价地，每个区间都是有补格

这一刻画把整体的“有补”与局部的“相对补”联系起来，将在下一节讨论布尔格时反复使用

定义 15.8 布尔格与布尔代数

到这里把条件合在一起：有界、分配、有补

作为偏序结构时称布尔格；把 \(\vee,\wedge,{}',0,1\) 都看作运算时称布尔代数。两者信息相同，但同态要求略有差别

兼具分配性和有补性的有界格称为布尔格（Boolean lattice）

在布尔格中，每个元素 \(a\) 的补元由定理 15.7.1 唯一，记为 \(a'\)（或 \(\bar a\)、\(\neg a\)）

若把 \(0,1,'\) 都视为运算，则代数系统 \[ (B;\vee,\wedge,{}',0,1) \] 是一个含两条二元运算、一条一元运算、两条零元运算的代数系统，称为布尔代数（Boolean algebra）

注意：布尔格与布尔代数所携带的信息完全等价，但作为代数系统它们的同态、子代数概念不同——布尔代数同态必须保 \(0,1,'\)，而布尔格同态只保 \(\vee,\wedge\)

注记：布尔代数的 H1-H4 判定

设 \(B\) 是至少含两个元素的集合，\(\vee,\wedge\) 是 \(B\) 上的二元运算，\({}'\) 是 \(B\) 上的一元运算，\(0,1\in B\)。若对任意 \(a,b,c\in B\) 满足：

• H1（交换律）：\(a\vee b=b\vee a,\quad a\wedge b=b\wedge a\)
• H2（分配律）：\(a\vee(b\wedge c)=(a\vee b)\wedge(a\vee c),\quad a\wedge(b\vee c)=(a\wedge b)\vee(a\wedge c)\)
• H3（界元）：\(a\vee 0=a,\quad a\wedge 0=0,\quad a\vee 1=1,\quad a\wedge 1=a\)
• H4（补元）：\(a\vee a'=1,\quad a\wedge a'=0\)

则 \((B;\vee,\wedge,{}',0,1)\) 是布尔代数

验证一个具体系统是否为布尔代数时，不必先列出格的幂等律、结合律、吸收律、有界性、有补性等所有性质；H1-H4 已经足以推出这些性质

证明思路： 点击查看证明

由 H1 直接得到两种运算的交换律。利用 H3 和 H4，再配合 H2，可推出吸收律与幂等律，例如 \[ a\vee(a\wedge b)=(a\wedge 1)\vee(a\wedge b)=a\wedge(1\vee b)=a \] 以及对偶的 \(a\wedge(a\vee b)=a\)

结合律也可由 H1-H4 代数化推出

于是 \(\vee,\wedge\) 满足格的四条基本恒等律，\(0,1\) 给出有界性，H2 给出分配性，H4 给出每个元素有补元，所以得到布尔代数

定理 15.8.1 布尔代数的基本恒等式

设 \(B\) 是布尔代数，对任意 \(a,b \in B\)：

• 双重补：\((a')'=a\)
• \(0' = 1\)，\(1' = 0\)
• De Morgan 律： \[ (a \vee b)'=a' \wedge b',\qquad (a \wedge b)'=a' \vee b' \]
• \(a \leq b \iff a \wedge b' = 0 \iff a' \vee b = 1\)

证明： 点击查看证明

双重补：\(a'\) 的补元是 \(a\)，由补元唯一立得 \((a')'=a\)

\(0' = 1\)：\(0 \vee 1 = 1\)，\(0 \wedge 1 = 0\)，故 \(1\) 是 \(0\) 的补元

De Morgan 律：验证 \((a \vee b)\vee (a'\wedge b')=1\) 和 \((a \vee b)\wedge (a'\wedge b')=0\)

由分配律 \[ (a \vee b)\vee (a'\wedge b')=\bigl((a \vee b)\vee a'\bigr)\wedge\bigl((a \vee b)\vee b'\bigr) \] 两项都因 \(a \vee a'=1\)、\(b \vee b' = 1\) 而等于 \(1\)，故并为 \(1\)

类似得交为 \(0\)。再用补元唯一性即知 \(a' \wedge b'=(a \vee b)'\)

\(a \leq b \iff a \wedge b' = 0\)：\(a \leq b\) 蕴含 \(a \wedge b'\leq b \wedge b' = 0\)；反之若 \(a \wedge b'=0\)，则 \[ a = a \wedge 1 = a \wedge (b \vee b')=(a \wedge b)\vee 0=a \wedge b \] 故 \(a \leq b\)。\(a' \vee b=1\) 同理

定义 15.8.2 子布尔代数和布尔代数同态

设 \(B\) 是布尔代数，非空 \(K \subseteq B\) 若对 \(\vee,\wedge,{}'\) 封闭，且 \(0,1 \in K\)，则称 \(K\) 为 \(B\) 的子布尔代数

设 \(\varphi:B_1 \to B_2\) 是格同态。若 \(\varphi\) 还满足 \(\varphi(0)=0\)，\(\varphi(1)=1\)，\(\varphi(a')=\varphi(a)'\)，则称为布尔代数同态

定理 15.8.3

设 \(B_1,B_2\) 都是布尔代数，\(\varphi:B_1 \to B_2\) 是 \(\{0,1\}\)-格同态，则 \(\varphi\) 自动保补——即它是布尔代数同态

证明： 点击查看证明

任取 \(a \in B_1\)，则 \[ \varphi(a)\vee \varphi(a')=\varphi(a \vee a')=\varphi(1)=1 \] \[ \varphi(a)\wedge \varphi(a')=\varphi(a \wedge a')=\varphi(0)=0 \] 故 \(\varphi(a')\) 是 \(\varphi(a)\) 在 \(B_2\) 中的补元。由 \(B_2\) 中补元唯一，\(\varphi(a')=\varphi(a)'\)

例 15.8.4 典型例子

• 任意集合 \(X\) 的幂集 \(\mathcal{P}(X)\) 关于 \(\cup,\cap\) 与“相对 \(X\) 取补”构成布尔代数
• \(X\) 有 \(n\) 元，则 \(\mathcal{P}(X)\) 有 \(2^n\) 个元素
• 二元链 \(\{0,1\}\) 是最小的非平凡布尔代数（除掉平凡的单元）
• 布尔代数的直积仍为布尔代数；特别地 \(\{0,1\}^n\) 是 \(n\) 个二元布尔代数的直积，与 \(\mathcal{P}(\{1,\dots,n\})\) 同构

把 \(\{0,1\}^n\) 写成 \(B^n\) 时，可以按坐标定义偏序： \[ (x_1,\dots,x_n)\leq(y_1,\dots,y_n)\iff x_i\leq y_i\quad(1\leq i\leq n) \] 并与交都是逐坐标取最大、最小： \[ x\vee y=(\max(x_i,y_i))_{i=1}^n,\qquad x\wedge y=(\min(x_i,y_i))_{i=1}^n \] 补元为逐坐标取反。显式同构 \[ \Phi:B^n\to\mathcal{P}(\{1,\dots,n\}),\qquad \Phi(x_1,\dots,x_n)=\{i\mid x_i=1\} \] 把逐坐标并、交、补分别对应到集合的并、交、补

\(B^3\) 的哈斯图就是立方体，\(B^4\) 则是四维超立方体的顶点偏序

定理 15.8.5 布尔代数与布尔环

布尔代数还可以换成环的语言

直观上，\(\wedge\) 变成乘法，异或式的对称差变成加法。这样一来，布尔代数和前面环论中的布尔环就是同一类结构的两种表示

设 \((B;\vee,\wedge,{}',0,1)\) 是布尔代数，定义 \[ a + b = (a \wedge b')\vee (a' \wedge b),\qquad a \cdot b = a \wedge b \] 则 \((B;+,\cdot,0,1)\) 是一个布尔环——也就是满足 \(a^2 = a\) 对所有 \(a\) 成立的含幺交换环

反过来，给定布尔环 \((R;+,\cdot,0,1)\)，定义 \[ a \vee b = a + b + ab,\qquad a \wedge b = ab,\qquad a' = 1 + a \] 则 \((R;\vee,\wedge,{}',0,1)\) 是布尔代数

这两种构造互逆，从而布尔代数与布尔环是同一个对象的两种语言

证明思路： 点击查看证明

加法 \(+\) 即”对称差”：\(a + b = (a \cup b)\setminus (a \cap b)\)（按 \(\mathcal{P}(X)\) 的直观）

从布尔代数到布尔环：

加法交换显然；零元：\(a + 0 = (a \wedge 1)\vee (a' \wedge 0)=a\)；逆元：\(a + a = (a \wedge a')\vee (a' \wedge a)=0\)，故每个元素加法逆为自身（特征 \(2\)）

加法结合性比较繁，但可借助”对称差为对称的二元布尔运算”或直接展开 \((a+b)+c\) 与 \(a+(b+c)\) 验证

\(a^2 = a \wedge a = a\)（幂等）

分配 \(a(b+c)=ab+ac\)：注意到 \(a \wedge \bigl((b \wedge c')\vee (b' \wedge c)\bigr)=(a \wedge b \wedge c')\vee (a \wedge b' \wedge c)\)，又 \((a \wedge b)+(a \wedge c)=(ab \wedge (ac)')\vee ((ab)' \wedge ac)=(a \wedge b \wedge (a' \vee c'))\vee \cdots\)，化简后相等

由 \(a^2 = a\) 可推出 \(a + a = 0\) 和 \(ab = ba\)。事实上 \((a+a)^2 = a + a\) 给出 \(a + a = 0\)；\((a+b)^2 = a+b\) 展开后给出 \(ab + ba = 0\)，结合 \(a + a = 0\) 得 \(ab = ba\)

从布尔环到布尔代数：

幂等、交换 \(ab = ba\) 直接由 \(a^2 = a\) 推出。验证 \(\vee,\wedge\) 满足吸收、分配等格律，再验证 \(a' = 1+a\) 满足 \(a \vee a' = 1\)、\(a \wedge a' = 0\) 即可

互逆：把两种构造前后串接，可验证回到出发点

这是 Stone（1936）的经典结论，意义有两点：

• 它说明布尔代数的全部结构可以通过两条二元运算（环的加和乘）描述——这是 Boolean ring 在公理上比 Boolean algebra 更精简的体现
• 它把布尔代数完全嵌入抽象代数的主流框架（环论），因此 ls13 关于环的一切（同态、理想、商环）在布尔代数上全部成立。比如布尔代数的“理想”（15.4 意义下）与布尔环的“理想”（13.3 意义下）一一对应

推论 15.8.6 布尔代数的特征

每个布尔代数视作布尔环时特征为 \(2\)：对每个 \(a\) 都有 \(a + a = 0\)

这把“二元链 \(\{0,1\}\) 即 \(\mathbb{Z}_2\)”的结论推广到全部布尔代数

定义 15.9 原子与有限布尔代数

有限布尔代数最接近幂集。要把这种直觉说精确，就需要找出“最小的非零块”，也就是原子

有限情形下，每个元素都可以由原子拼出来，因此整个布尔代数由原子集合决定

设 \(B\) 是有界格，\(a \in B\)。若 \(a \neq 0\) 且不存在 \(b\) 满足 \(0 < b < a\)，则称 \(a\) 为 \(B\) 的原子（atom）

若 \(B\) 中任意非零元都大于等于某个原子，则称 \(B\) 是原子的（atomic）；若每个元素都能写成某些原子的并，则称为原子可分的（atomistic）

记 \(\operatorname{Atom}(B)\) 为 \(B\) 的全体原子

定理 15.9.1 原子的性质

设 \(B\) 是布尔代数，\(a\) 是 \(B\) 的原子，则：

• 对任意 \(x \in B\)，\(a \leq x\) 与 \(a \leq x'\) 中恰有一个成立
• 若 \(a_1,a_2\) 是两个不同原子，则 \(a_1 \wedge a_2 = 0\)

证明： 点击查看证明

设 \(a \nleq x\)。考虑 \(a \wedge x\)：它 \(\leq a\) 且 \(\neq a\)（否则 \(a \leq x\)），故 \(a \wedge x = 0\)，即 \(a \leq x'\)

不能既有 \(a \leq x\) 又有 \(a \leq x'\)，否则 \(a \leq x \wedge x' = 0\)，矛盾

若 \(a_1 \wedge a_2 \neq 0\)，由原子定义 \(a_1 \wedge a_2 = a_1\)，同样 \(=a_2\)，故 \(a_1=a_2\)

定理 15.9.2 有限布尔代数的 Stone 表示

设 \(B\) 是有限布尔代数，则 \(B\) 同构于其原子集合的幂集 \[ B \cong \mathcal{P}(\operatorname{Atom}(B)) \] 特别地，有限布尔代数恰有 \(2^n\) 个元素，其中 \(n\) 是原子数

证明： 点击查看证明

定义 \[ \Phi:B \to \mathcal{P}(\operatorname{Atom}(B)),\qquad \Phi(x)=\{a \in \operatorname{Atom}(B)\mid a \leq x\} \]

由有限分配格表示定理（定理 15.6.5），\(B\) 同构于 \(\operatorname{Down}(\operatorname{Ji}(B))\)

在布尔代数中可证明：并不可约元就是原子

事实上若 \(a\) 是并不可约且 \(a \neq 0\)，要证 \(a\) 是原子：取 \(0 < b \leq a\)。由分配律 \(a=a \wedge 1 = a \wedge (b \vee b')=(a \wedge b)\vee (a \wedge b')\)。由并不可约 \(a = a \wedge b\) 或 \(a = a \wedge b'\)。前者得 \(a \leq b\)，故 \(a = b\)；后者得 \(a \leq b'\)，于是 \(b \leq a \leq b'\)，故 \(b = b \wedge b'=0\)，矛盾

故 \(b = a\)，即 \(a\) 是原子。反之原子显然并不可约

又有限布尔代数中，原子之间两两不可比，故 \(\operatorname{Atom}(B)\) 是反链，于是 \[ \operatorname{Down}(\operatorname{Atom}(B))=\mathcal{P}(\operatorname{Atom}(B)) \] 从而 \(\Phi\) 是格同构

由原子集合的反链结构与定理 15.9.1，\(\Phi\) 自动保补、保 \(0,1\)，故为布尔代数同构

推论 15.9.3 有限布尔代数的分类

• 任意两个有 \(2^n\) 个元素的有限布尔代数都同构
• 有限布尔代数的元素数必为 \(2\) 的幂

定义 15.10 极大滤子

一般布尔代数未必有足够多的原子，因此不能总用原子集合来表示

Stone 表示的做法是改用极大滤子来充当“点”，再把每个代数元素送到包含它的那些点所组成的集合

设 \(L\) 是有界格，\(L\) 的真滤子 \(F\) 若不被任何真滤子真包含，即没有真滤子 \(F'\supsetneq F\)，则称为极大滤子或超滤（ultrafilter）

类似定义极大理想

定理 15.10.1

设 \(B\) 是布尔代数，\(F \subseteq B\) 是真滤子。下列条件等价：

• \(F\) 是极大滤子
• \(F\) 是素滤子
• 对任意 \(a \in B\)，\(a \in F\) 或 \(a' \in F\) 中恰有一个成立

证明： 点击查看证明

\(1 \Rightarrow 3\)：若 \(F\) 极大，取 \(a \notin F\)，考虑 \(F' = \operatorname{fil}(F \cup \{a\})\)。\(F'\) 严格包含 \(F\)，故 \(F'=B\)，于是 \(0 \in F'\)，即存在 \(f \in F\) 使 \(f \wedge a \leq 0\)，亦即 \(f \leq a'\)，故 \(a' \in F\)。又若 \(a\) 和 \(a'\) 同时在 \(F\)，则 \(0 = a \wedge a'\in F\)，矛盾

\(3 \Rightarrow 2\)：若 \(a \vee b \in F\) 但 \(a,b \notin F\)，则 \(a',b'\in F\)，故 \(a' \wedge b'=(a \vee b)'\in F\)。又 \(a \vee b \in F\)，于是 \(0 = (a \vee b)\wedge (a \vee b)'\in F\)，与真性矛盾

\(2 \Rightarrow 1\)：设 \(F\) 素而不极大，则存在真滤子 \(F'\supsetneq F\)，取 \(a \in F'\setminus F\)。\(a \notin F\)，但 \(a \vee a'=1 \in F\) 且 \(F\) 素，故 \(a'\in F \subseteq F'\)，于是 \(0=a \wedge a'\in F'\)，与 \(F'\) 真性矛盾

特别地，布尔代数到 \(\{0,1\}\) 的同态与极大滤子一一对应——每个极大滤子 \(F\) 给出特征函数 \(\chi_F\)，每个同态给出 \(\varphi^{-1}(1)\)

定理 15.10.2 极大理想存在

设 \(B\) 是布尔代数，\(a \neq 0\)。则存在极大理想 \(P \subseteq B\) 使得 \(a \notin P\)

等价地：对 \(B\) 中任意一对不同元素 \(a \neq b\)，存在极大理想区分它们（即恰好一个属于 \(P\)）

证明： 点击查看证明

考虑所有不含 \(a\) 的理想族，按包含构成偏序集。链的并仍是不含 \(a\) 的理想，故每条链有上界，由 Zorn 引理取一个极大元 \(P\)

证 \(P\) 是极大理想：若有理想 \(Q \supsetneq P\)，则由极大性必有 \(a \in Q\)。但 \(Q \subseteq B\)，故 \(Q = B\)

证 \(P\) 是素理想：若 \(a_1 \wedge a_2 \in P\) 而 \(a_1,a_2 \notin P\)，则由 \(P\) 关于”不含 \(a\)“的极大性知 \(\operatorname{id}(P \cup\{a_i\})\) 都含 \(a\)，即存在 \(p_i \in P\) 使 \(a \leq p_i \vee a_i\)，于是 \[ a = a \wedge a \leq (p_1 \vee a_1)\wedge (p_2 \vee a_2)\leq (p_1 \vee p_2)\vee (a_1 \wedge a_2)\in P \] 矛盾

在布尔代数中，极大理想恰好与素理想等价（由定理 15.10.1 的对偶），故 \(P\) 极大

至于”区分两个不同元素”：若 \(a \neq b\)，则 \(a \wedge b' \neq 0\) 或 \(a' \wedge b \neq 0\)；对其中任一非零元应用前一结论即可

定理 15.10.3 Stone 表示定理

每个布尔代数 \(B\) 都能嵌入某集合 \(X\) 的幂集布尔代数 \(\mathcal{P}(X)\) 中

具体地，取 \(X\) 为 \(B\) 的所有极大滤子的集合，定义 \[ \sigma:B \to \mathcal{P}(X),\qquad \sigma(a)=\{F \in X \mid a \in F\} \] 则 \(\sigma\) 是布尔代数嵌入

证明： 点击查看证明

由定理 15.10.1，\(F\) 是极大滤子相当于布尔代数同态 \(\chi_F:B \to \{0,1\}\)，且 \(a \in F \iff \chi_F(a)=1\)

保 \(\vee\)：\(F \in \sigma(a \vee b)\iff a \vee b \in F \iff a \in F\) 或 \(b \in F\)（由素性）\(\iff F \in \sigma(a)\cup \sigma(b)\)

保 \(\wedge\)：滤子对交封闭，且若 \(a \wedge b \in F\) 则 \(a,b \in F\)（因为 \(F\) 上闭）

保 \(0,1\)：\(\sigma(0)=\varnothing\)（因为 \(0 \notin F\) 对任意真滤子），\(\sigma(1)=X\)

保 \('\)：\(F \in \sigma(a')\iff a'\in F \iff a \notin F \iff F \notin \sigma(a)\)

单射：由定理 15.10.2，存在极大滤子区分 \(a\) 与 \(b\)，故 \(\sigma(a)\neq \sigma(b)\)

这是布尔代数表示理论的核心：每个布尔代数都”长成集合的子集格”

把 15.9.2 中“有限布尔代数 \(\cong \mathcal{P}(\operatorname{Atom})\)”推广到一般情形，把“原子”换成了“极大滤子”

15.11 一些扩展

15.11.1 伪补

格 \(L\) 有 \(0\)，\(a \in L\)。若存在最大的 \(a^*\) 使 \[ a \wedge a^* = 0 \] 则称 \(a^*\) 为 \(a\) 的伪补（pseudocomplement）

若 \(L\) 中每个元素都有伪补，则称为伪补格

伪补未必满足 \(a \vee a^*=1\)；当满足时退化为通常的（唯一）补

布尔代数中每个元素的补元 \(a'\) 都是它的伪补；反之未必——例如三元链 \(\{0,a,1\}\) 中 \(a^*=0\)，但 \(a \vee 0 = a \neq 1\)，故 \(a\) 不是有补的，却仍是伪补的

有限分配格都是伪补格

15.11.2 伽罗瓦对应作为格反同构

ls14 给出的伽罗瓦理论基本定理，在本章的语言下可以直接重述为一条关于格的命题

设 \(F/K\) 是有限维伽罗瓦扩张，\(G = \operatorname{Aut}_K(F)\)。考虑两个格：

• \(\mathcal{L}(F/K)\)：\(F/K\) 的中间域全体，按 \(\subseteq\) 排序——它对包含构成完备格，\(E_1 \land E_2 = E_1 \cap E_2\)，\(E_1 \lor E_2 = E_1 E_2\)（复合域）
• \(\operatorname{Sub}(G)\)：\(G\) 的子群全体，按 \(\subseteq\) 排序——对包含构成完备格（且因 \(G\) 有限自动是有限格）

定义两个映射： \[ \Phi:\mathcal{L}(F/K)\to \operatorname{Sub}(G),\quad \Phi(E)=\operatorname{Aut}_E(F) \] \[ \Psi:\operatorname{Sub}(G)\to \mathcal{L}(F/K),\quad \Psi(H)=H'=\{u \in F\mid \sigma(u)=u,\forall \sigma \in H\} \]

则 ls14 中“伽罗瓦基本定理”的核心结论翻译成本篇语言就是：

• \(\Phi,\Psi\) 互为逆映射
• 反序：\(E_1 \subseteq E_2 \iff \Phi(E_2)\subseteq \Phi(E_1)\)
• 把“反序”换成“序”，即映射 \(E \mapsto \Phi(E)\) 是从 \(\mathcal{L}(F/K)\) 到 \(\operatorname{Sub}(G)^\partial\)（\(\operatorname{Sub}(G)\) 的对偶格）的格同构

换言之，伽罗瓦对应是中间域格与子群格之间的格反同构

由格反同构立得：

中间域侧	子群侧
包含 \(E_1 \subseteq E_2\)	反向包含 \(\Phi(E_2)\subseteq \Phi(E_1)\)
复合域 \(E_1 E_2\)	交 \(\Phi(E_1)\cap \Phi(E_2)\)
交 \(E_1 \cap E_2\)	生成 \(\langle \Phi(E_1)\cup \Phi(E_2)\rangle\)
最大元 \(F\)	最小元 \(\{e\}\)
最小元 \(K\)	最大元 \(G\)
\(E/K\) 伽罗瓦 ↔︎ \(\Phi(E)\triangleleft G\)	正规子群

在中间域侧“是否伽罗瓦”这一性质，对应到子群侧“是否正规”

它们本身都依赖更多结构（不是单纯的格性质），但在格反同构下对应

这就是 \(\Phi(E)\triangleleft G\) 时商群 \(G/\Phi(E)\) 又能推出 \(\operatorname{Aut}_K(E)\) 的原因

Stone 表示定理（15.10.3）也是同一形态的对偶：布尔代数 ↔︎ 集合的子集格

TODO：有时间补模的内容