格的基本概念

有序集

0x01. 定义：偏序集

设$R$是集合$A$上的一个关系，如果$R$满足以下三个条件，则称$R$是集合$A$的偏序关系，简称偏序，记作“$\leq$”：

1. 自反性（Reflexivity）：$\forall a \in A, a \leq a$。
2. 反对称性（Antisymmetry）：$\forall a, b \in A, \text{如果} a \leq b \text{且} b \leq a, \text{则} a = b$。
3. 传递性（Transitivity）：$\forall a, b, c \in A, \text{如果} a \leq b \text{且} b \leq c, \text{则} a \leq c$。

若在集合$A$上给定一个偏序关系$\leq$，则称集合$A$按偏序关系$\leq$构成一个偏序集合，集合$A$和偏序$R$一起称为偏序集（Partially Ordered Set，Poset），记作$(A, \leq)$。具有偏序关系的集合$P$为偏序集（或称半序集、有序集、序集），记为$(P, \leq)$。

偏序集中的这种二元关系$\leq$通常被称为偏序关系。偏序集中的元素可以是任何对象，不仅限于数值。偏序集在数学、计算理论和其他领域的建模中有广泛应用。

有偏序集$(A, \leq )$，如果$x, y \in A$，存在$x \leq y$或者$y \leq x$，则称$x$与$y$是可比较较的，记作$x \nparallel y$，否则称$x$,$y$是不可比较的，记作$x \parallel y$。

若$A$中所有元都是可比较的，则称$A$是一个链（或者全序集）；若$A$中所有元都是不可比较的，则称$A$是一个反链（或称$A$是离散的）。

0x02. 定义：幂集

设$X$是一个非空集合，由$A$的所有子集（包括空集和$A$自身）构成的集合称为$X$的幂集，记作$2^A$或$\mathbb{P}(A)$，即：

$$\mathbb{P}(A) = \{S | S \subseteq A\}$$

例如，如果集合有$n$个元素，那么该集合的幂集将有$2^n$个元素，并且每一个元素都是一个集合。这是因为每个元素都可以选择是否出现在子集中，因此对于$n$个元素，我们有$2^n$种可能的子集。

0x03. 定义：对偶关系

若$R$是非空集合$A$的一个序关系，如果存在另一个关系 $R^*$ 满足

$$\forall x,y \in A , (x,y) \in R \iff (y,x) \in R^*$$

则称$R^*$ 是$R$的对偶关系。

其他定义参考：

对偶关系（Duality）是偏序集理论中一个重要的概念。在偏序集$(X, \leq )$中，如果集合$X$上存在一个关系$\leq^*$满足以下性质：

1. 自反性（Reflexivity）：$\forall x \in X$，有$x \leq^* x$。

2. 反对称性（Antisymmetry）：$\forall x, y \in X$，如果$x \leq y$则$y \leq^* x$。

3. 传递性（Transitivity）：$\forall x, y, z \in X$，如果$x \leq^* y$且$y \leq^* z$则$x \leq^* z$。

0x04. 定义：子序集

设$(A,\leq)$是一个有序集，D是A的一个子集。定义D上的一个序关系$\leq_{D}$如下：

$$(\forall x,y \in D) x \leq_{D} y \iff x \leq y$$

则$(D,\leq_{D})$是一个有序集，称为$(A,\leq)$的子序集。

0x05. 定义：区间与覆盖

设 $(E, \leq)$是一个有序集，$a,b \in E$ 并且 $a \leq b$，我们称为$E$的子集 $({x \in E | a \leq x \le b})$ 是$E$的 区间，记作 $[a,b]$。如果$a < b$并且 $[a,b]=\{a,b\}$，则称$b$覆盖$a$（或者$a$被$b$所覆盖）。我们用符号$b \succ a$ （或 $a \prec b$）表示$b$覆盖$a$；用$b \succeq a$ （$a \preceq b$）表示$b \succ a$($a \prec b$)或者$a=b$。

其他定义:

区间

在偏序集 $E$ 上，区间通常是指偏序关系$\leq$ 下的连通子集。假设$E$是一个偏序集，$a, b \in E$ 且 $a \leq b$，那么 $a$ 和 $b$ 之间的区间可以定义为：

$$[a, b] = \{ x \in E \mid a \leq x \leq b \}$$

这里的 $[a, b]$ 表示 $a$ 和 $b$ 之间的所有元素构成的集合。

覆盖

假设 $E$ 是一个偏序集，$C$ 是 $E$ 的一个覆盖，那么 $C$ 中的元素覆盖了 $E$ 中的元素 $x$ ，如果不存在 $y \in C$使得 $y \leq x$ 且 $y \neq x$。

$$\forall x \in E, \exists y \in C : y > x$$

0x06. 定义：极大元与极小元

设 $(E, \leq)$是一个有序集。 称$x \in E$是一个极大元，如果

$$\forall y \in E, y \leq x$$

⭕ 定义不严谨，$x$与$y$可能不可比较，因此应该加上 $y \nparallel x$这一条件。

称$x$是最大元，如果

$$\forall y \in E, y \leq x 且 y \neq x$$

当最大元存在时，它是唯一的。

对偶的，可以得到极小元和最小元定义。

0x07. 定义：有序集的线性和与直和

设$(E,\leq_{E})$和$(F,\leq_{F})$是两个互不相交的有序集，$E$和$F$的线性和指并集$E \cup F$，并赋予其上一个序关系$\leq$:

$$x \leq y \iff (x,y \in E 并且 x \leq_{E} y) 或$$

$$(x,y \in F 并且x \leq_{F} y) 或$$

$$(x \in E, y \in F )$$

$E$与$F$的线性和用$E \oplus F$表示。

所谓$E和F$的直和$E \overline \oplus F$，是指$E$有最大元$1_{E}$及$F$有最小元$0_{F}$时，通过在$E和F$的线性和$E \oplus F$中恒等于$1_{E}$和$0_{F }$而得到的一个有序集。

⭕ 1. 没有定义什么是有序集的相关

⭕ 2. 等价符号的右侧似乎是不清晰的

⭕ 3. 整个定义非常含糊，不严谨

0x08. 定义：笛卡尔序直积

设$(E_{1},\leq_{1}),...,(E_{n},\leq_{n})$是$n$个有序集. 定义集合的笛卡尔直积$X_{i=1}^n E_{i}$的一个关系如下：

$$(x_{1},...,x_{n}) \leq (y_{1},...y_{n}) \iff x_{i} \leq_{i} y_{i} (i=1,2,3,...n)$$

容易验证 $\leq$ 是 $X_{i}^n E_{i}$的一个序关系，称为笛卡尔序关系。我们称$（X_{i}^n E_{i},\leq）是有序集(E_{i},\leq)(i=1,2,3,....n)$的笛卡尔序直积。

0x09. 定义：对偶定理

设$E$是非空集合，则关于$(E,\leq)$ 的任意一个命题，都存在与之对应的$(E,\geq)$上的一个命题。

保序映射

0x0A. 定义：保序映射

设$(E, \leq_{E})$和$(F, \leq_{F})$是两个有序集，称一个映射 $f: E \to F$是一个保序映射，如果

$$(\forall x,y \in E) x \leq_E y \implies f(x) \leq f(y)$$

称$f$是一个反射映射，如果

$$(\forall x,y \in E) x \leq_{E} y \implies f(x) \geq f(y)$$

注意：即使一个保序映射$f:E \to F$是一个双射，它的逆映射$f^{-1}:F \to E$也未必是保序的

⭕：未定义单射和满射

0x0B. 定义：保序同构

设$f: E \to F$是一个保序双射，如果$f$的逆映射$f^{-1}: F \to E$也是一个保序映射，则称$f$是一个保序同构映射,并称有序集$E和F$是保序同构，记作$E \simeq F$

0x0C. 定理：保序同构的充要条件

设$f: E \to F$ 是一个保序双射，如果$f$的逆映射$f^{-1}: F \to E$也是保序同构的，当且仅当以下条件成立:

(1) $f$是满射

(2) $(\forall x,y \in E) x \leq y \iff f(x) \leq f(y)$

0x0D. 定义：降集与升集

设$(E,\leq)$是一个有序集，$A$是$E$的一个子序集，若对任意$x \in A$和任意$y \in E$，$y \leq x \Rightarrow y \in A$,则称$A$是$E$的一个降集（下降集）。

对偶的，称$A$是$E$的升集（上升集）。

即，若 $A \subseteq E$，

$$A^{\downarrow} = \{y \in E \quad | \quad (\exists x \in A) y \leq x \}$$

$$A^{\uparrow} = \{y \in E \quad | \quad (\exists x \in A) y \geq x \}$$

则$A^{\downarrow}$和$A^{\uparrow}$分别是$E$的降集和升集。

0x0E. 定义：像与逆像

设$E,F$是两个集合，$B$是$F$的一个子集. 又设$f: E \to F$是一个映射. 记 $Im f = \{ f(x) | x \in E\}$，称为$f$的像. 记$f^{-1}(B)=\{x \in E | f(x) \in B\}$为$f$关于$B$的逆像。

⭕ 上述像的定义中，没有涉及到$B$? 尤其结合逆像的定义，貌似像的定义不完整。

0x0F. 定理

设$E$和$F$是两个有序集, $f: E \to F$是一个映射，则下面的论断等价：

(1) $f$是保序映射；

(2) $F$是任意主降集$y^{\downarrow}$的逆像$f^{-1}(y^{\downarrow})$是$E$的降集；

(3) $F$是任意主升集$y^{\uparrow}$的逆像$f^{-1}(y^{\uparrow})$是$E$的升集.

0x10. 定义：闭包映射

设$E$是一个有序集，我们称一个保序映射$f: E \to F$是$E$的闭包映射,如果$f=f^2 \geq id_E$. 这里$id_E$表示$E$上的恒等映射。

⭕ 这里的$\geq id_E$是什么意思？

0x11. 定义：闭包子集

称一个有序集$E$的子集$A$是闭包子集，如果存在一个闭包映射$f:E \to E$使得$A=Im f$.

0x12. 定理

一个有序集$E$的子集$A$是$E$的闭包子集，当且仅当对每个$x \in E$，集合$x^{\uparrow} \cap A$有最小元。

格与半格

0x13. 定义： 上界，下界

设$E是一个有序集， $A \subseteq E$. 我们称$x \in E$是$A$的上界，如果对所有$a \in A$ 有 $a \leq x$. 对偶的，称 $x \in E$是$A$的下界，如果对所有$a \in A$，有 $x \leq a$.

$A$的最小上界称为上确界，记作$sup_E\ A$（或$sup\ A$）

$A$的最打下界称为下确界，记作$inf_E\ A$（或$inf\ A$）

上界集$A^u$：$A$在$E$中所有上界的集合。

下界集$A^l$：$A$在$E$中所有下界的集合。

半格

• 交半格

  有有序集$E$，如果

  $$\forall x, y \in E, \text{都有} inf\{x,y\} \text{存在}$$

  则$E$是一个交半格，记作 $\land$ -半格

• 并半格

  有有序集$E$，如果

  $$\forall x, y \in E, \text{都有} sup\{x,y\} \text{存在}$$

  则$E$是一个并半格，记作 $\lor$ -半格

⭕ 证明：交半格的有限子集$\{x_1,x_2,...,x_n\}$，存在$inf\{x_1,x_2,...,x_n\}$，且等于$x_1 \land x_2 \land ... \land x_n$.

对称关系与等价关系

• 对称关系

有有序集$E$及其上的关系$R$，如果

$$\forall x,y \in E, \quad xRy \iff yRx$$

则$R$是对称关系

• 等价关系

有有序集$E$及其上的关系$R$，如果$R$满足

(1)自反性

$$\forall x \in E, \quad xRx$$

(2)对称性

$$\forall x,y \in E, \quad xRy \implies yRx$$

(3)传递性

$$\forall x,y,z\in E, \quad xRy,\quad yRz \implies xRz$$

则$R$是等价关系，记作$\equiv$

⭕ 如果$\varphi$,$\theta$ 是等价关系，如何理解 $\varphi \land \theta$?

半群

有代数系统$(G;\cdot)$,其中$G$是非空集, $\cdot$是$G$上的二元运算，即

$$\forall x,y \in G, x \cdot y \in G$$

且满足结合律，即：

$$(a \cdot b) \cdot c = a \cdot (b \cdot c )$$

则称 $(G;\cdot)$是半群。

定理：半格与半群的关系

一个半格$(E;\land)$是一个交换幂等半群.反之，每个交换幂等半群都形成一个$\land$-半格

⭕ 证明关键：在交互幂等半群$(E;\cdot)$上构造一个关系$R$如下：

$$xRy \Leftrightarrow xy = x$$

定义：格

有序集$(L;\leq)$是一个格，如果

$$\forall x,y \in L, \ \exist z=inf\{x,y\}, \text{且} z \in L$$

$$\forall x,y \in L, \ \exist z=sup\{x,y\}, \text{且} z \in L$$

将 $inf\{x,y\}$ 记作 $x \land y$,$sup\{x,y\}$ 记作 $x \lor y$,格$L$记为$(L;\land, \lor)$,并称 $\land$ , $\lor$ 为 $L$ 中的两个格运算。

如果$L$存在最大元1和最小元0，则称$L$为有界格。

定理：格的充要条件

非空集合$L$的是一个格，当且仅当$L$上的两个运算$\circ$,$\oplus$满足:

(1) $(L,\circ)$和$(L,\oplus)$都是交换幂等半群

(2) $L$满足吸收率，即 $(\forall x,y \in L) \quad x \circ (x \oplus y) = x, x \oplus (x \circ y) = x$

⭕ 证明关键：在证明充分性时，需要证明两个运算 $\circ$和$\oplus$所定义的序关系是一致的，即证

$$x \circ y = x \Leftrightarrow x \oplus y = y$$

定理：

格$(L;\land, \lor)$上的二元运算满足幂等性、交换律、结合律、吸收律。即

（L1） $a \land a = a, a \lor a = a$

（L2） $a \land b = b \land a, a \lor b = b \lor a$

（L4） $(a \land b) \land c = a \land (b \land c), (a \lor b) \lor c = a \lor (b \lor c)$

（L4） $a \land (a \lor b) = a ,a \lor (a \land b) = a$

注意：证明的依据只能是目前格的定义，也就是基于如下事实：$(L,\leq)$ 是偏序集, 以及：

$$(\forall a,b \in L),\quad \exist sup(a,b) \in L$$

以及：

$$(\forall a,b \in L),\quad \exist inf(a,b) \in L$$

因此，关键还是要找到（或者构造）$\land,\lor$ 与 $\leq$ 的关系

---

⭕ 事实上，有的教科书就是以本定理作为格的定义。

定义：子群格

代数系统 $(G;\cdot)$ 是一个群，其中$G$为非空集，且二元运算 $\cdot$ 满足以下条件:

(1) 结合律： $(\forall a,b,c \in G) \quad (a \cdot b) \cdot c = a \cdot (b \cdot c)$

(2) 存在单元元$e$使得 $(\forall a \in G) \quad e \cdot a = a \cdot e=a$

(1) 存在逆元：$(\forall a \in G) (\exist b \in G)\quad a \cdot b = b \cdot a = e$

衍生定义：

交换群: 当群$(G;\cdot)$满足交换律时

子群: 设$H \subseteq G$,且$G$对于$G$的乘法也是群

⭕ 什么叫$H$地$G$的乘法？

正规子群: $H$是$G$的子群，且满足 $(\forall x \in G) \quad x^{-1}Hx=H$

正规子群格: $\mathcal{N}(G)$是$G$的所有正规子群集，则$(\mathcal{N}(G);\land,\lor)$是格，称之为正规子群格