偏序与格

偏序关系

满足自反性、反对称性 、传递性的关系。

格

概念

1. 偏序集 $(P;⩽)$ 包括一个运算
2. 格：偏序集中，所有元素的最小上界和最大下界都在里面
3. 完全格：偏序集中，所有子集 的最小上界和最大下界都存在，并且位于这个格中。

NOTE

偏序集里的元素不一定能两两比大小，格也是。能比大小的叫做全序集。

性质

• $a\wedge b⩽a⩽a\vee b$
• $a⩽b⟺a\wedge b=a⟺a\vee b=b$
  这条性质提供了把偏序关系转换成等式的方法。
• 吸收律：$a\vee (a\wedge b)=a,a\wedge (a\vee b)=a$

TIP

证明 $x=y$ 的方法：分别证明 $x⩽y$ 和 $x⩾y$。
证明 $x⩽y$ 的方法：证明 $x\wedge y=x$。

• $a\wedge b=a⟺a\vee b=b$
  根据吸收律可证。
• 保序性：$b⩽c\Rightarrow \{\begin{array}{l}a\wedge b⩽a\wedge c\\ a\vee b⩽a\vee c\end{array}$
• 分配不等式：$\{\begin{array}{l}(a\wedge b)\vee (a\wedge c)⩽a\wedge (b\vee c)\\ a\vee (b\wedge c)⩽(a\vee b)\wedge (a\vee c)\end{array}$

代数系统

格等价于任何一个满足格中 $\vee$ 和 $\wedge$ 运算性质的代数系统 $[L;\wedge ,\vee ]$。意思是可以通过偏序关系 $⩽$ 推出 $\vee$ 和 $\wedge$，也可以从 $\wedge$ 和 $\vee$ 推出偏序关系 $⩽$。

定义零元为格中 小于等于所有元素的元素，单位元为大于等于所有元素的元素。这和环的零元、单位元无关，一个格中也未必有这两个元素。有零元和单位元的格叫做有界格。

有界格不一定是完全格，比如取某个正实数 $a$ 情况下的 $\{0\}\cap (a,1]$。

子格

如果格 $[L;\wedge ,\vee ]$ 有子系统 $[T;\wedge ,\vee ]$ ，则 $[T;\wedge ,\vee ]$ 叫作它的子格。

IMPORTANT

子格需要对于 $\wedge$ 和 $\vee$ 封闭，而不是对 $⩽$ 封闭。

例如：设 $S:=\{1,2,5,10,20\}$ 关于整除关系是格，则 $T:=\{1,2,5,20\}$ 关于 $⩽$ 封闭，但是在 $T$ 中有 $2\vee 5=20$ 而在 $S$ 中 $2\vee 5=10$，二者不相等。所以 $T$ 不是 $S$ 的子格。

同态与同构

定义格的同态映射为满足条件的映射 $\phi$：

1. $\phi (a\wedge b)=\phi (a)\wedge \phi (b)$
2. $\phi (a\vee b)=\phi (a)\vee \phi (b)$

据此可以定义格的同态与同构。$\phi$ 是保序的，也就是 $a⩽b\Rightarrow \phi (a)⩽\phi (b)$。

如果 $\phi$ 是两个格之间的双射，则它是同构映射当且仅当 $a⩽b\Rightarrow \phi (a)⩽\phi (b)$。

对偶

对偶就是将一个格中进行以下替换得到的新的格：

1. 把 $⩽$ 换成 $⩾$
2. 把 $\wedge$ 换成 $\vee$
3. 把 $\vee$ 换成 $\wedge$

对偶原理：如果格上一个命题成立，则它进行上述替换之后在对偶格也成立。

特殊的格

有补格

对于有界格的元素 $a$，如果存在元素 $b$ 使得 $a\wedge b=0$ 和 $a\vee b=1$，则称 $b$ 是 $a$ 的补元。如果 $L$ 的元素都有补元，则 $L$ 是有补格。

NOTE

补元不一定唯一。

分配格

在分配不等式中取等的格，即满足 $\{\begin{array}{l}(a\wedge b)\vee (a\wedge c)=a\wedge (b\vee c)\\ a\vee (b\wedge c)=(a\vee b)\wedge (a\vee c)\end{array}$。

满足一条分配等式就会满足另一条。此外，只要 $L$ 中没有与 $M_5$ 或者 $N_5$ 同构的子格，那么 $L$ 就是分配格。

TIP

证明的时候可以直接说“没有与 $M_5$ 或 $N_5$ 同构的子格”，而不需要进一步解释。

布尔格

布尔格就是🈶补分配格。

性质

1. 补元唯一。
   证明：设 $b$ 和 $c$ 都是 $a$ 的补元，则 $b\wedge c=(b\wedge c)\vee (a\wedge b)=b\wedge (a\vee c)=b$，同理 $b\wedge c=c$。所以 $b=c$。
2. $(a\wedge b{)}^{\prime }=a^{\prime }\vee b^{\prime },(a\vee b{)}^{\prime }=a^{\prime }\wedge b^{\prime }$
3. $a\wedge b=0\iff a⩽b^{\prime }$

布尔代数

满足条件的代数系统叫做布尔代数：

1. 交换律 $a\wedge b=b\wedge a$ 等
2. 分配律 $a\wedge (b\vee c)=(a\wedge b)\vee (a\wedge c)$ 等
3. 存在零元和单位元
4. 任一元素存在补元

TIP

证明方法：给定运算规则时，验证它满足零元、补元、单位元的定义。

性质

1. 满足布尔格的性质
2. 优先的布尔代数一定是 $2^n$ 元的，而且同阶的布尔代数都同构
3. 定义加法为 $a+b:=(a\wedge b^{\prime })\vee (a^{\prime }\wedge b)$，乘法为 $a\cdot b:=a\wedge b$。