序与格论基础

小平邦彦将抄书学习法发扬光大, 我则是用电脑抄书, 以期学会数学.

本书的优点是细致, 缺点或许也是细致. 这导致我在阅读的时候不得不仔细纠结于字面, 不能想当然, 必须参考定义, 以防止其和别的文献或者主流惯例有所不同. 许多时候的确是失之毫厘, 谬以千里!

第1章偏序集与格

第1.1节偏序集

定义1.1.1. 这个定义非常主流, 就不抄写了, 其定义了预序, 预序集, 偏序, 偏序集. 和主流不同的是, 其要求预序集和偏序集非空, 之后的论述的确也默认非空性, 必须小心.

例子1.1.1.

实数集 $ℝ$ , 有理数集 $ℚ$ , 整数集 $ℤ$ , 自然数集 $ℕ$ , 非负整数集 $ℕ^{⁎}$ 在通常的小于等于关系下构成偏序集, 其实就是通常的序关系下的意思. 这本书的一个背离当前主流记号的地方是 $ℕ$ 是不包含零的, 而 $ℕ^{⁎}$ 是加了零的.
如果使用 $|$ 表示整除, 即 $m | n$ 表示 $m$ 整除 $n$ , 那么 $(ℕ, |)$ 是一个偏序集.
定义 $ℝ$ 上的一个二元关系 $⪯$ 如下: $x ⪯ y ⟺ ⌊ x ⌋ \leq ⌊ y ⌋$ 则 $(ℝ, ⪯)$ 是一个预序集, 但不是偏序集.
对于集合 $X$ , 其幂集 $𝒫 (X)$ 在关系 $\subseteq$ 下是一个偏序集. 当然了, 这个幂集的非空子集继承了自然的序关系也成为偏序集. 原书要求 $X$ 非空是不必要的, 因为 $𝒫 (X)$ 即便在 $X$ 是空集的情况下也非空.
设 $G$ 是一个群, $Sub (G)$ 是由其所有子群构成的集合. 那么, $(Sub (G), \subseteq)$ 是一个偏序集.
设 $Σ^{⁎}$ 是由所有 $0, 1$ 字符的有限序列构成的集合, 定义 $a \leq b$ 当且仅当 $a$ 是 $b$ 的前缀, 则 $(Σ^{⁎}, \leq)$ 是一个偏序集.
设 $P$ 是一个偏序集 (当然已经默认非空了), $X$ 是一个集合, 定义 $P^{X}$ 上的关系 $\leq$ 为 $f \leq g ⟺ \forall x \in X . f (x) \leq g (x)$ 那么 $\leq$ 是一个偏序关系, 其被称为 $P^{X}$ 上的逐点序 (pointwise order). 原文需要 $X$ 非空, 实则不需要.
设 $I (ℝ) = {[a, b] | a \leq b, a, b \in ℝ}$ , 定义 $[a_{1}, b_{1}] ⊑ [a_{2}, b_{2}] ⟺ [a_{2}, b_{2}] \subseteq [a_{1}, b_{1}]$ 则 $(I (ℝ), ⊑)$ 是一个偏序集, 而 $⊑$ 是 $ℝ$ 上的区间序或者信息序. 信息序这个名字应该来源于指称语义学, 区间越小越精细, 信息越多.
设 $(X, O (X))$ 是一个拓扑空间, 定义 $\leq_{O (X)} = {(x, y) \in X \times X | x \in {y}^{-}}$ 那么 $\leq_{O (X)}$ 是一个预序, 称为 $X$ 的特殊化序 (specialization order). 记 $Θ (X, O (X)) = (X, \leq_{O (X)})$ . 容易证明, $\leq_{O (X)}$ 是一个偏序当且仅当 $X$ 是 $T_{0}$ 空间. 之所以称为特殊化, 或许是特殊化序还要另外一种刻画方式, 即 $x \leq y$ 当且仅当包含 $x$ 的开集族是包含 $y$ 的开集族的子集. 一个点所处于的开集越多, 也就越特殊.

设 $(P, \leq)$ 是一个偏序集, $Q$ 是 $P$ 的一个非空子集. 记 $\leq_{Q} = {(x, y) \in Q \times Q | x \leq y}$ 则 $\leq_{Q}$ 是 $Q$ 上的一个偏序, 称为 $Q$ 在 $P$ 中的继承序或者导出序或者诱导序或者限制序, 而 $(Q, \leq_{Q})$ 是 $(P, \leq)$ 的一个子偏序集. 对于 $n \in ℕ$ , 记 $n = {0, 1, 2, \dots, n - 1}$ 为 $ℕ^{⁎}$ 的子偏序集.

定义1.1.2. 设

P

是一个偏序集,

A \subseteq P

如果对于任意的 $x \in A$ 和 $y \in P$ , $x \leq y$ 可以推出 $y \in A$ , 那么称 $A$ 为上集 (upper set).
如果对于任意的 $x \in A$ 和 $y \in P$ , $y \leq x$ 可以推出 $y \in A$ , 那么称 $A$ 为下集 (lower set).

分别记

P

的所有下集和上集构成的集合为

D (P)

和

U (P)

, 它们都是

P

上的Alexandrov拓扑.

设 $P$ 是一个偏序集, $A \subseteq P$ , 令

定义1.1.3. 设

P

是一个偏序集, 对于

x, y \in P

, 如果

x < y

, 且对于每个

z \in P

x \leq z \leq y

可以推出

z = x

或

z = y

, 那么称

y

覆盖 (cover)

x

, 记作

x ≺ y

一般来说, 偏序集可以用Hasse图来描述. Hasse图存在几个方面, 或者说几种不同的含义. 一种可能是Hasse图是纯粹技术意义上的graph, 还有一种可能是Hasse图是一种图示. 不过, 我感觉还是图示意义下的Hasse图更频繁出现. 我们将具有覆盖关系的元素用线段连接, 一般较小元素安排在下方, 较大元素安排在上方, 无法比较的平行元素则一般尽可能安排在同一高度.

设 $P$ 是一个偏序集, $a \in P$ . 如果对于每个 $x \in P$ 有 $a \leq x$ , 那么称 $a$ 是 $P$ 的最小元或者底 (bottom), 记作 $0_{P}$ 或者 $0$ . 类似地可以定义 $P$ 的最大元并记作 $1_{P}$ 或者 $1$ . 具有最小元和最大元的偏序集称为有界的 (bounded). 如果对于每个 $x \in P$ 都有 $x \leq a$ 可以推出 $x = a$ , 那么就称 $a$ 为 $P$ 的极小元. 换言之, 没有其他元素比 $a$ 更小了. 类似地可以定义极大元. 显然, 最小元是一个极小元, 最大元是一个极大元. 设 $S$ 是 $P$ 的一个子偏序集, $S$ 的极小元集合记作 $\min (S)$ , 而极大元集合记作 $\max (S)$ . 它们当然都有可能是空集. 另外, 最小元记作 $Min (S)$ , 最大元记作 $Max (S)$ . 最小元和最大元并不一定存在, 但是若存在则显然唯一 (对于偏序集而言).

例子1.1.2.

定义1.1.4. 设

{(P_{i}, \leq_{i})}_{i \in I}

是一族偏序集, 在笛卡尔积

\prod_{i} P_{i}

上定义关系

\leq

如下:

{(x_{i})}_{i \in I} \leq {(y_{i})}_{i \in I} ⟺ \forall i \in I . x_{i} \leq_{i} y_{i}

易证

\leq

是

\prod_{i} P_{i}

上的一个偏序, 我们称其为逐点序, 而

(\prod_{i} P_{i}, \leq)

称为

{(P_{i}, \leq_{i})}_{i \in I}

的直积.

例子1.1.3.

定义1.1.5. 设

P

是一个偏序集,

A \subseteq P

, 我们定义

A^{u} = {x \in P | A \subseteq ↓ x}

A^{l} = {x \in P | A \subseteq ↑ x}

称

A^{u}

为

A

的上界集,

A^{l}

为

A

的下界集. 注意到

\emptyset^{u} = \emptyset^{l} = P

定理1.1.1. 设

P

是一个偏序集, 而

A

和

B

是

P

的子集, 那么

$A \subseteq B$ 可以推出 $B^{u} \subseteq A^{u}$ 和 $B^{l} \subseteq A^{l}$ .
$A \subseteq {A^{u}}^{l} \cap {A^{l}}^{u}$ .
$A^{u} = {A^{u}}^{l}^{u}$ , $A^{l} = {A^{l}}^{u}^{l}$ .

证明.

如果 $x \in B^{u}$ , 那么 $B \subseteq ↓ x$ , 又因为 $A \subseteq B$ , 所以 $A \subseteq ↓ x$ , 于是 $x \in A^{u}$ . 另外一个的证明也是类似的.
设 $x \in A$ , 我们要证明 $x \in {A^{u}}^{l}$ 和 $x \in {A^{l}}^{u}$ . $x \in {A^{u}}^{l}$ 等价于 $A^{u} \subseteq ↑ x$ . 对于任意的 $y \in A^{u}$ , 我们知道 $A \subseteq ↓ y$ . 又因为 $x \in A$ , 所以 $x \in ↓ y$ , 这等价于 $y \in ↑ x$ , 由此得证. 另外一种情形是类似的.
根据1和2, 我们知道 ${A^{u}}^{l}^{u} \subseteq A^{u}$ 和 ${A^{l}}^{u}^{l} \subseteq A^{l}$ . 另外, 如果再次应用2, 将 $A^{u}$ 代入 $A$ , 就会发现 $A^{u} \subseteq {A^{u}}^{l}^{u}$ ; 将 $A^{l}$ 代入 $A$ , 就会发现 $A^{l} \subseteq {A^{l}}^{u}^{l}$ .

◻

第1.2节格与完备格

定义1.2.1. 定义了上确界 (join) 和下确界 (meet), 不再赘述.

评注1.2.1.

定义1.2.2. 设

L

是一个偏序集.

如果对于任意的 $x, y \in L$ 都有 $⋁ {x, y}$ 存在, 则称 $L$ 为并半格.
如果对于任意的 $x, y \in L$ 都有 $⋀ {x, y}$ 存在, 则称 $L$ 为交半格.
如果 $L$ 既是并半格又是交半格, 则称 $L$ 为格.

定理1.2.1. 设

L

是一个格, 则对于任意的

a, b, c \in L

, 运算

\lor

和

\land

满足

幂等
交换
结合
吸收: $a \lor (a \land b) = a$ , $a \land (a \lor b) = a$ .

证明. 根据上确界和下确界的定义很容易推出.

◻

例子1.2.1.

每个链都是格, 例如实数集, 有理数集, 自然数集.
设 $(X, O (X))$ 是一个拓扑空间, 则 $(O (X), \subseteq)$ 是一个格; 幂集 $𝒫 (X)$ 作为 $X$ 上的离散拓扑自然也是一个格.
$(ℕ, |)$ 是一个格, $m \lor n$ 是 $m$ 和 $n$ 的最小公倍数, $m \land n$ 是 $m$ 和 $n$ 的最大公约数.

定理1.2.2. 设

L

是一个偏序集, 那么

$L$ 是一个格当且仅当 $L$ 的任意有限非空子集都有上确界和下确界.
$L$ 是格当且仅当 $L^{op}$ 是格.

证明.

◻

定理1.2.3. 非空集合

L

可以作为一个格当且仅当

L

上存在两个二元运算

\otimes

和

\oplus

满足

$(L, \otimes)$ 和 $(L, \oplus)$ 都是交换幂等半群;
$\otimes$ 和 $\oplus$ 满足吸收律, 即 $x \otimes (x \oplus y) = x = x \oplus (x \otimes y)$ .

证明.

◻

定义1.2.3. 设

L

是一个格,

S

是

L

的一个非空子集.

如果对于任意的 $x, y \in S$ 都有 $x \land y, x \lor y \in S$ , 称 $S$ 为 $L$ 的子格.
如果 $L$ 是有界格, $S$ 是 $L$ 的子格且 $0, 1 \in S$ , 则称 $S$ 为 $L$ 的保界子格.

例子1.2.2.

定义1.2.4. 设

L

是一个偏序集, 如果

L

的每个子集 (包括空集) 都有上确界和下确界, 则称

L

是一个完备格.

定理1.2.4. 设

L

是一个偏序集, 则下列条件等价:

$L$ 是一个完备格;
$L^{op}$ 是一个完备格;
$L$ 的每个子集都有上确界;
$L$ 有最小元 $0$ 且每个非空子集都有上确界;
$L$ 的每个子集都有下确界;
$L$ 有最大元 $1$ 且每个非空子集都有下确界.

证明. 首先, 1和2, 3和4, 5和6显然都是等价的.

◻

推论1.2.1.

定义1.2.5. 设

P, Q

是偏序集,

f : P \to Q

是一个映射.

如果对于任意的 $x, y \in P$ 都有 $x \leq y$ 可以推出 $f (x) \leq f (y)$ , 就称 $f$ 为保序的, 或 $f$ 是从 $P$ 到 $Q$ 的序同态.
如果对于任意的 $x, y \in P$ 都有 $x \leq y$ 可以推出 $f (y) \leq f (x)$ , 则称 $f$ 为逆序的.

定理1.2.5. Knaster-Tarski不动点定理. 设

L

是一个完备格, 如果

f : L \to L

是一个保序映射, 则

f

有最大和最小不动点.

证明. 太过经典, 不写了.

◻

定义1.2.6. 设

P

是一个偏序集,

f : P \to P

是一个自映射. 如果

保序性: $x \leq y$ 可以推出 $f (x) \leq f (y)$ ;
增值性: $x \leq f (x)$ ;
幂等性: $f (f (x)) = f (x)$

则称

f

是

P

上的一个闭包算子 (closure operator).

定义1.2.7. 设

P

是一个偏序集,

g : P \to P

是一个自映射. 如果

保序性: $x \leq y$ 可以推出 $g (x) \leq g (y)$ ;
减值性: $g (x) \leq x$ ;
幂等性: $g (g (x)) = g (x)$

则称

g

是

P

上的一个内部算子 (interior operator).

设 $h : P \to P$ 是偏序集 $P$ 上的一个自映射. 记 $Im h = {h (x) | x \in P}$ . 当 $h$ 是幂等的, 那么 $Im h$ 恰是 $h$ 的所有不动点之集合. {译注: 实际上, 幂等性与 $Im h$ 是所有不动点之集合等价.} 幂等保序自映射也称为投影.

定理1.2.6. 设

L

是一个完备格,

f : L \to L

是一个闭包算子, 则

Im f

(在继承的序下)也是一个完备格, 其中对于

Im f

的任意子集

A

都有

\underset{f}{⋀} A = ⋀ A

\underset{f}{⋁} A = f (⋁ A)

证明. 由幂等性可知

Im f

是

f

的不动点集合. 设

A

是

Im f

的一个子集. 令

a = ⋀ A

, 如果

a \in Im f

, 那么

\underset{f}{⋀} A = ⋀ A

. 我们将要证明

a \in Im f

, 即

f (a) = a

f (a) = f (⋀ A) \leq ⋀ f (A) = ⋀ A = a

而又根据

f

是闭包算子, 所以

a \leq f (a)

, 于是

f (a) = a

. 我们已经证明了一半, 接着我们还需要证明

f (⋁ A)

是

A

在

Im f

中的上确界, 如果

A

是

Im f

的任意一个子集. 显然,

f (⋁ A)

是

f (A)

的一个上界, 也是

A

的一个上界. 因此,

f (⋁ A)

在

Im f

中也是

A

的一个上界. 如果

b \in Im f

也是

A

在

Im f

中的一个上界, 我们想要证明

f (⋁ A) \leq b

. 然而, 既然

b

在

Im f

中是

A

的上界, 那么在

L

中自然也是

A

的上界. 换言之,

⋁ A \leq b

. 根据

f

的保序性质, 立即得到

f (⋁ A) \leq f (b) = b

◻

译者注记. 上述证明用到了这样一个事实: 对于偏序集

P

, 对于其某个非空子集

S

S

继承了一个自然的偏序. 对于

A \subseteq S

, 如果

⋀ A

存在且

⋀ A \in S

, 那么

⋀ A

在子偏序集

S

中也是

A

的最大下界. 类似的事实当然对于

⋁

也成立.

推论1.2.2.

定义1.2.8. 设

P

是一个偏序集,

S \subseteq P

如果对于任意的 $x \in P$ 都有 $x = ⋁ (S \cap ↓ x)$ , 那么就称 $S$ 为 $P$ 的并生成子集, 或称 $P$ 可由 $S$ 生成.

例子1.2.3.

第1.3节序同构与格同构

定义1.3.1. 设

P, Q

是两个偏序集,

f : P \to Q

是一个映射.

如果对于任意的 $x, y \in P$ 都有 $x \leq y$ 当且仅当 $f (x) \leq f (y)$ , 则称 $f$ 为从 $P$ 到 $Q$ 的序嵌入, 记作

第1.4节分配格与Boole代数

定理1.4.1. 设

L

是一个格, 则下面两个有限分配律是等价的:

$x \land (y \lor z) = (x \land y) \lor (x \land z)$ ;
$x \lor (y \land z) = (x \lor y) \land (x \lor z)$ .

证明. 1推出2: 设

x, y, z \in L

, 那么

\begin{array}{rcl} (x \lor y) \land (x \lor z) & = & ((x \lor y) \land x) \lor ((x \lor y) \land z) \\ = & x \lor ((x \lor y) \land z) \\ = & x \lor (x \land z) \lor (y \land z) \\ = & x \lor (y \land z) \end{array}

2推出1也是类似的.

◻

定义1.4.1. 设

L

是一个格, 如果

L

满足上述定理中描述的两个条件之一, 那么称

L

为分配格.

例子1.4.1.

每个链都是分配格.
$(ℕ, |)$ 是分配格.
设 $(X, O (X))$ 是拓扑空间, 则 $(O (X), \subseteq)$ 是分配格.

定理1.4.2. 设

L

是一个格, 则

L

是分配格当且仅当

L

不含有形如

M_{3}

或

N_{5}

的子格.

证明.

◻

定理1.4.3. 设

L

是一个格, 则

L

是分配格当且仅当

z \land x = z \land y 且 z \lor x = z \lor y 可以推出 x = y

证明.

◻

第1.5节理想和滤子

定义1.5.1. 设

P

是一个偏序集,

I

和

F

是

P

的子集.

如果 $I$ 是一个定向的下集, 则称 $I$ 是 $P$ 的理想 (ideal).
如果 $F$ 是一个滤过的上集, 则称 $F$ 是 $P$ 的滤子 (filter).

如果

S

是

P

的一个理想且

S \neq P

, 则称

S

为

P

的真理想. 类似地, 我们可以定义真滤子. 对于任意的

x \in P

, 子集

↓ x

都是一个理想, 其被称为关于

x

的主理想 (principal ideal). 类似地,

↑ x

都是一个滤子, 其被称为关于

x

的主滤子 (principal filter). 记

Idl (P)

为

P

的所有理想之集合,

Fil (P)

为

P

的所有滤子之集合. 读者应该注意的是, 理想和滤子首先都是非空的.

译者注记. 主理想也可以刻画为具有最大元的下集, 主滤子也可以刻画为具有最小元的上集.

例子1.5.1.

定理1.5.1. 设

L

是一个格,

I

是

L

的非空子集, 则下列条件等价:

$I$ 是理想;
$I$ 是对于 $\lor$ 封闭的下集;
$I$ 对于 $\lor$ 封闭, 对于 $\land$ 吸收.

I

对于

\land

吸收的意思是对于每个

a \in I

和

b \in L

, 都有

a \land b \in I

证明. 1推出2:

◻

对偶地, 我们有以下定理.

定理1.5.2.

定理1.5.3. 设

L

是一个格,

S

是

L

的一个非空子集, 令

定理1.5.4.

定理1.5.5.

推论1.5.1.

定义1.5.2.

定理1.5.6.

定理1.5.7.

第1.6节格中的特殊元素

定义1.6.1. 设

L

是一个格,

a \in L

但不是最大元素,

b \in L

但不是最小元素.

如果对于任意的 $x, y \in L$ , $x \land y \leq a$ 可以推出 $x \leq a$ 或 $y \leq a$ , 则称 $a$ 为交素元 (meet-prime element).
如果对于任意的 $x, y \in L$ , $x \land y = a$ 可以推出 $x = a$ 或 $y = a$ , 则称 $a$ 为交既约元 (meet-irreducible element).
如果对于任意的 $x, y \in L$ , $b \leq x \lor y$ 可以推出 $b \leq x$ 或 $b \leq y$ , 则称 $b$ 为并素元 (join-prime element).
如果对于任意的 $x, y \in L$ , $b = x \lor y$ 可以推出 $b = x$ 或 $b = y$ , 则称 $b$ 为并既约元 (join-irreducible element).

用

M (L)

表示

L

的交素元之集,

J (L)

表示

L

的并素元之集.

定理1.6.1. 设

L

是一个格, 那么

交素元必为交既约元, 并素元必为并既约元.
如果 $L$ 是分配格, 那么交素元等价于交既约元, 并素元等价于并既约元.

证明.

◻

定理1.6.2. 设

L

是一个格,

I

和

F

是

L

的子集, 那么

证明.

◻

定理1.6.3. 设

L

是一个格,

x \in L

, 那么

$x$ 是交素元当且仅当主理想 $↓ x$ 是素理想.
$x$ 是并素元当且仅当主滤子 $↑ x$ 是素滤子.

证明.

◻

定理1.6.4.

证明.

◻

定理1.6.5.

证明.

◻

习题1

练习1. 找出所有

4

元偏序集和

5

元格.

练习2.

练习3. 设

P

是一个偏序集,

f, g : P \to P

是闭包算子, 请证明下列条件等价:

$f \leq g$ ;
$f \circ g = g$ ;
$g \circ f = g$ ;
$Im g \subseteq Im f$ .

证明. 由1推出2: 对于每个

x \in P

, 我们知道

(f \circ g) (x) \geq g (x)

, 这是增值性. 另外, 由于

f \leq g

, 所以

f (g (x)) \leq g (g (x))

. 根据幂等性, 可以推出

(f \circ g) (x) \leq g (x)

. 因此,

(f \circ g) (x) = g (x)

, 即

f \circ g = g

.
由2推出3: 对于每个

x \in P

, 根据增值性和单调性, 我们有

g (f (x)) \geq g (x)

. 然后, 我们又知道

g = g \circ g = g \circ f \circ g

g \circ f

当然是单调的, 所以说

g (f (x)) \leq g (f (g (x)))

, 于是

g (f (x)) \leq g (x)

. 因此,

g \circ f = g

.
由3推出4: 对于

x \in Im g

, 我们知道存在

y \in P

使得

x = g (y)

. 现在我们希望说明存在

z \in P

使得

f (z) = g (y)

. 然而, 我们将要证明

f (g (y)) = g (y)

. 首先根据增值性,

f (g (y)) \geq g (y)

. 于是, 我们还需要证明

f (g (y)) \leq g (y)

. 不过, 我们有

g (y) = g (g (y)) = g (f (g (y)))

. 根据增值性这也是显然的.
由4推出1: 对于每个

x \in P

, 我们要证明

f (x) \leq g (x)

. 因为

Im g \subseteq Im f

, 所以既然

g (x) \in Im g

, 那么存在

y \in P

使得

g (x) = f (y)

. 接着, 我们可以推出

\begin{array}{rcl} g (x) & = & f (y) \\ = & f (f (y)) \\ = & f (g (x)) \end{array}

因为

x \leq g (x)

, 所以

f (x) \leq f (g (x))

, 即

f (x) \leq g (x)

◻

练习4.

练习5.

练习6. 设

L

是一个格,

d : L \to [0, + \infty)

是一个映射满足

d (x) + d (y) = d (x \lor y) + d (x \land y)

且

x < y

可以推出

d (x) < d (y)

, 我们称

(L, d)

是一个度量格. 定义

ρ : L \times L \to [0, + \infty)

为

ρ (x, y) = d (x \lor y) - d (x \land y)

证明

ρ

是

L

上的一个度量, 并描述其所诱导的拓扑的开集和闭集.

练习7.

练习8.

练习9.

练习10.

练习11.

第2章 Galois伴随和Galois连接

本章标题中的两个名字在许多文献中存在着大量混用的现象, 现在我们从历史发展的角度阐述它们的异同点. 特别指出, Galois伴随的英文是Galois correspondence或Galois adjunction, 而Galois连接 (也称Galois联络) 英文则是Galois connection, 两者都是两个偏序集之间满足一定条件的映射序对.

第2.1节 Galois伴随

虽然Galois连接出现得比Galois伴随更早, 然而从格论的角度来看, Galois伴随给人以更加自然和实用之感. 因此, 我们先在本节介绍Galois伴随及其相关结果.

定义2.1.1. 如图2.1所示, 设

f : P \to Q

和

g : Q \to P

是偏序集之间的保序映射, 如果对于任意的

a \in P

和

b \in Q

都有

f (a) \leq b ⟺ a \leq g (b)

则称

(f, g)

是从

P

到

Q

的一个Galois伴随, 记作

f ⊣ g : P ⇀ Q

如果

P = Q

, 则称

(f, g)

是

P

上的一个Galois伴随.

这里的 $f$ 和 $g$ 有位置之分: $f$ 位于不等号的左侧, 而 $g$ 位于右侧. 一般情况下, 称 $f$ 是 $g$ 的左伴随, $g$ 是 $f$ 的右伴随. 有些文献也将 $f, g$ 分别称为上伴随和下伴随.

例子2.1.1.

设 $R \subseteq X \times Y$ 是一个二元关系, 分别定义 $R^{\to} : 𝒫 (X) \to 𝒫 (Y)$ 和 $R^{\leftarrow} : 𝒫 (Y) \to 𝒫 (X)$ 为 $R^{\to} (A) = {y \in Y | \exists x \in A . (x, y) \in R}$ $R^{\leftarrow} (B) = {x \in X | (x, y) \in R \Rightarrow y \in B}$ 则 $R^{\to} ⊣ R^{\leftarrow} : 𝒫 (X) ⇀ 𝒫 (Y)$ .
设 $R \subseteq X \times Y$ 是一个二元关系, 分别定义 ${}^{\to}R : 𝒫 (X) \to 𝒫 (Y)$ 和 ${}^{\leftarrow}R : 𝒫 (Y) \to 𝒫 (X)$ 为 ${}^{\to}R (A) = {y \in Y | (x, y) \in R \Rightarrow x \in A}$ ${}^{\leftarrow}R (B) = {x \in X | \exists y \in B . (x, y) \in R}$ 则 ${}^{\leftarrow}R ⊣ {}^{\to}R : 𝒫 (Y) ⇀ 𝒫 (X)$ .
设 $f : X \to Y$ 是一个映射. 将 $f$ 视为二元关系 ${(x, f (x)) | x \in X}$ , 由1知 $f^{\to} ⊣ f^{\leftarrow} : 𝒫 (X) ⇀ 𝒫 (Y)$ 其中 $f^{\to} (A) = {f (x) | x \in A}$ $f^{\leftarrow} (B) = {x \in X | f (x) \in B}$

Galois伴随除了用当且仅当的方式定义之外, 还可以利用映射的复合与偏序关系进行刻画.

定理2.1.1. 设

f : P \to Q

和

g : Q \to P

是偏序集之间的保序映射, 则下列条件等价:

$f ⊣ g : P ⇀ Q$ ;
${id}_{P} \leq g f, f g \leq {id}_{Q}$ .

证明. 1推出2: 对于任意的

x \in P

, 由

f (x) \leq f (x)

可以推出

x \leq (g f) (x)

, 即

{id}_{P} \leq g f

. 对于任意的

y \in Q

, 由

g (y) \leq g (y)

可以推出

(f g) (y) \leq y

, 即

f g \leq {id}_{Q}

.
2推出1: 对于任意的

x \in P

和

y \in Q

, 如果

f (x) \leq y

, 根据单调性可知

(g f) (x) \leq g (y)

, 又因为

{id}_{P} (x) \leq (g f) (x)

, 于是

{id}_{P} (x) \leq g (y)

, 即

x \leq g (y)

. 如果

x \leq g (y)

, 那么根据单调性可知

f (x) \leq (f g) (y)

, 又因为

(f g) (y) \leq {id}_{Q} (y)

, 于是

f (x) \leq {id}_{Q} (y)

, 即

f (x) \leq y

◻

由以上定理易得如下结论:

定理2.1.2. 设

f ⊣ g : P ⇀ Q

, 则

$f g f = f$ , $g f g = g$ ;
$g f : P \to P$ 是闭包算子, $f g : Q \to Q$ 是内部算子.

证明.

我们知道 ${id}_{P} \leq g f$ , 于是对于每个 $x \in P$ 都有 $x \leq (g f) (x)$ . 根据单调性, 可知 $f (x) \leq (f g f) (x)$ . 另外, 根据 $f g \leq {id}_{Q}$ , 我们知道对于每个 $x \in P$ 都有 $(f g) (f (x)) \leq {id}_{Q} (f (x))$ , 即 $(f g f) (x) \leq f (x)$ . 因此, $f g f = f$ . 我们知道 $f g \leq {id}_{Q}$ , 于是对于每个 $y \in Q$ 都有 $(f g) (y) \leq y$ . 根据单调性, 可知 $(g f g) (y) \leq g (y)$ . 另外, 根据 ${id}_{P} \leq g f$ , 我们知道对于每个 $y \in Q$ 都有 ${id}_{P} (g (y)) \leq (g f) (g (y))$ , 即 $g (y) \leq (g f g) (y)$ . 因此, $g f g = g$ .
$g f$ 的保序性和增值性都是显然的. 为了说明幂等性, 我们需要证明对于每个 $x \in P$ 都有 $(g f g f) (x) = (g f) (x)$ 由1的结论这也是显然的. $f g$ 的保序性和减值性也是显然的, 而幂等性则需要证明 $(f g f g) (x) = (f g) (x)$ 由1的结论这也是显然的.

◻

虽然Galois伴随的两个偏序集不一定序同构, 但是我们可以通过缩小定义域和陪域的方式得到一组序同构的偏序集.

定理2.1.3. 如果

f ⊣ g : P ⇀ Q

, 则

f (P) ≅ g (Q)

证明. 将

f

限制为

φ : g (Q) \to f (P)

, 将

g

限制为

ψ : f (P) \to g (Q)

. 对于每个

x \in g (Q)

, 存在

y \in Q

满足

x = g (y)

, 于是

\begin{array}{rcl} (ψ φ) (x) & = & (g f) (x) \\ = & (g f) (g (y)) \\ = & (g f g) (y) \\ = & g (y) \\ = & x \end{array}

同理, 我们可以推出

(φ ψ) (y) = y

对于每个

y \in f (P)

成立. 也就是说,

φ

和

ψ

是可逆的保序映射, 也就是序同构.

◻

由定义2.1.1和定理2.1.1可以看出, Galois伴随的两个映射之间具有良好的协调关系, 以至于它们可以相互唯一确定.

定理2.1.4. 设

f : P \to Q

和

g : Q \to P

是偏序集之间的保序映射, 那么下列条件等价:

$f ⊣ g : P ⇀ Q$ ;
$\forall a \in P . f (a) = Min (g^{- 1} (↑ a))$ ;
$\forall b \in Q . g (b) = Max (f^{- 1} (↓ b))$ .

证明. 1推出2: 对于任意的

a \in P

, 由于

a \leq g (f (a))

, 我们有

f (a) \in g^{- 1} (↑ a)

; 任取

y \in g^{- 1} (↑ a)

, 我们有

a \leq g (y)

, 从而

f (a) \leq y

. 这说明

f (a) = Min (g^{- 1} (↑ a))

.
2推出1: 对于任意的

a \in P

和

b \in Q

, 如果

f (a) \leq b

, 则由

f (a) = Min (g^{- 1} (↑ a))

可知

f (a) \in g^{- 1} (↑ a)

, 于是

a \leq g (f (a))

, 再根据

g

的单调性就有

a \leq g (b)

; 反过来, 如果

a \leq g (b)

, 那么

g (b) \in ↑ a

b \in g^{- 1} (↑ a)

, 于是

f (a) \leq b

. 因此,

f ⊣ g : P ⇀ Q

.
通过类似的方法我们也可以证明1等价于3.

◻

定义2.1.2. 设

h : P \to Q

是偏序集之间的一个映射.

如果主理想的原像是主理想, 则称 $h$ 为剩余映射 (residuated mapping).
如果主滤子的原像是主滤子, 则称 $h$ 为残余映射 (residual mapping).

定理2.1.5. 设

h : P \to Q

是偏序集之间的一个保序映射, 那么

$h$ 有右伴随当且仅当 $h$ 是一个剩余映射;
$h$ 有左伴随当且仅当 $h$ 是一个残余映射.

证明. 2是1的对偶结论, 故我们只证明1.
左推右: 设

h

有右伴随, 根据前述定理, 对于任意的

b \in Q

h^{- 1} (↓ b)

都有最大元; 又因为

h

是保序的, 易知

h^{- 1} (↓ b)

是一个下集, 从而是一个主理想.
右推左: 对于任意的

b \in Q

, 由于

h^{- 1} (↓ b)

是一个主理想,

g (b) = Max (h^{- 1} (↓ b))

是良定的, 由此得到映射

g : Q \to P

g

按照定义自动是单调的. {译注: 原文说根据

h

的保序性, 这是不对的.} 由前述定理可知,

g

是

h

的右伴随.

◻

集合论中我们熟知对于映射 $f : X \to Y$ , 对应的 $f : 𝒫 (X) \to 𝒫 (Y)$ 保持并, $f^{- 1} : 𝒫 (Y) \to 𝒫 (X)$ 既保持并又保持交. 实际上, 映射序对的保并性和保交性是对于Galois伴随的一种刻画.

定理2.1.6. 在Galois伴随中, 左伴随保持任意存在的并, 右伴随保持任意存在的交.

证明. 设

(f, g)

是从偏序集

P

到偏序集

Q

的一个Galois伴随. 设

A \subseteq P

且

⋁ A

存在. 如果

A = \emptyset

, 那么

P

有最小元素

0_{P}

. 于是, 对于任意的

y \in Q

, 我们有

0_{P} \leq g (y)

, 而这等价于

f (0_{P}) \leq y

. 由于

y

的任意性,

f (0_{P})

是

Q

的最小元

0_{Q}

, 那么

f (⋁ \emptyset) = f (0_{P}) = 0_{Q} = ⋁ f (\emptyset)

. 如果

A \neq \emptyset

, 令

b = ⋁ A

, 我们需要证明

f (b) = ⋁ {f (a) | a \in A}

. 一方面, 由

f

的保序性可知,

f (b)

是

{f (a) | a \in A}

的一个上界. 另一方面, 设

c

也是

{f (a) | a \in A}

的一个上界, 那么对于每个

a \in A

都有

f (a) \leq c

, 于是

a \leq g (c)

. 也就是说,

g (c)

是

A

的一个上界. 那么,

b = ⋁ A \leq g (c)

. 这等价于

f (b) \leq c

. 所以说,

f (b)

是

{f (a) | a \in A}

的最小上界, 即

f (⋁ A) = ⋁ f (A)

. 类似地, 可以证明

g

保持任意存在的交.

◻

译者注记. 如果说得更清楚一些的话, 则是: 对于偏序集

P

和

Q

之间的Galois伴随

f

和

g

, 对于

S \subseteq P

, 若

⋁ S

存在, 则

⋁ f (S)

存在, 且

f (⋁ S) = ⋁ f (S)

; 对于

T \subseteq Q

, 若

⋀ T

存在, 则

⋀ g (T)

存在, 且

g (⋀ T) = ⋀ g (T)

定理2.1.7. 设

P, Q

是两个完备格.

保序映射 $f : P \to Q$ 保持任意的并当且仅当 $f$ 有右伴随 $g : Q \to P$ , 且 $g (y) = ⋁ {x \in P | f (x) \leq y}$ ;
保序映射 $g : Q \to P$ 保持任意的交当且仅当 $g$ 有左伴随 $f : P \to Q$ , 且 $f (x) = ⋀ {y \in Q | x \leq g (y)}$ .

证明. 2和1是对偶的, 这里仅证明1.
如果

f

有右伴随, 根据前述定理,

f

当然保持任意的并. 反过来, 如果

f

保持任意的并, 我们想要证明

f

有伴随. 令

g (y) = ⋁ {x \in P | f (x) \leq y}

. 对于任意的

x \in P

和

y \in Q

, 如果

f (x) \leq y

, 那么由于

g (y)

是

{x \in P | f (x) \leq y}

的一个上界, 所以有

x \leq g (y)

. 反过来, 如果

x \leq g (y)

, 那么

f (x) \leq f (g (y))

, 而

\begin{array}{rcl} f (g (y)) & = & f (⋁ {x \in P | f (x) \leq y}) \\ = & ⋁ f ({x \in P | f (x) \leq y}) \\ \leq & y \end{array}

即

f (x) \leq y

. 至于

g

的单调性, 由定义是容易看出来的. 因此,

g

是

f

的右伴随.

◻

定理2.1.8. 设

f ⊣ g : P ⇀ Q

, 则下列条件等价:

$f$ 是单射;
$g f = {id}_{P}$ ;
$g$ 是满射.

证明. 1推出2: 由定理2.1.2, 我们知道

f g f = f

. 换言之, 对于每个

x \in P

, 我们都有

f ((g f) (x)) = f (x)

. 因为

f

是单射, 所以

(g f) (x) = x

, 也就是

g f = {id}_{P}

.
2推出3: 我们知道

Im (g f) \subseteq Im g

, 又知道

Im (g f) = Im {id}_{P} = P

, 所以

g

是满射.
3推出2: 对于每个

x \in P

, 鉴于

g

是满射, 所以存在

y \in Q

使得

g (y) = x

. 于是, 我们有

(g f) (x) = (g f) (g (y)) = (g f g) (y) = g (y) = x

换言之,

g f = {id}_{P}

.
2推出1: 对于

x, y \in P

, 如果

f (x) = f (y)

, 那么

\begin{array}{rcl} g (f (x)) & = & (g f) (x) \\ = & {id}_{P} (x) \\ = & x \\ = & g (f (y)) \\ = & (g f) (y) \\ = & {id}_{P} (y) \\ = & y \end{array}

即

x = y

, 换言之则是

f

为单射.

◻

定理2.1.9. 设

f ⊣ g : P ⇀ Q

, 则下列条件等价:

$f$ 是满射;
$f g = {id}_{Q}$ ;
$g$ 是单射.

证明.

◻

推论2.1.1.

第2.2节内部算子和闭包算子与Galois伴随的关系

定理2.1.2指出从Galois伴随出发可以得到一个闭包算子和一个内部算子. 实际上, 每个闭包算子和内部算子也都可以分解为Galois伴随.

定理2.2.1.

定理2.2.2.

定理2.2.3.

第2.3节 Galois连接

Galois连接是一种逆序的映射对, 故常称为逆序Galois伴随或者对偶Galois伴随.

定义2.3.1.

第2.4节形式概念分析的格论基础

第2.5节偏序集的Dedekin-MacNeille完备化

习题2

练习1.

第3章 Heyting代数

Heyting代数由荷兰数学家A. Heyting于1930年引入. 由于其逻辑排中律一般不再成立, 所以Heyting代数可以看作直觉主义逻辑演算的Tarski-Lindenbaum代数. 在数学方面, Heyting代数是Boole代数的一般化, 曾被称为伪Boole代数或Brouwer格.

第3.1节 Heyting代数的基本概念

定义3.1.1. 设

H

是一个格, 若存在二元运算

\to : H \times H \to H

使得

\forall a, b, c \in H . c \land a \leq b ⟺ c \leq a \to b

则称

H

为Heyting代数.

容易验证, $H$ 有最大元但不一定有最小元. 有些文献会假定Heyting代数是一个有界格.

由Heyting代数的定义和第2章中Galois伴随之性质, 我们有以下定理.

定理3.1.1. 设

H

是一个格, 则下列条件等价:

$H$ 为Heyting代数;
对于任意的 $a \in H$ , $(a \land (-), a \to (-))$ 构成 $H$ 上的Galois伴随;
对于任意的 $a, b \in H$ , ${x \in H | a \land x \leq b}$ 存在最大元.

证明. 1推出2: 根据Galois伴随的定义, 我们需要证明对于任意的

x, y \in H

, 都有

a \land x \leq y ⟺ x \leq a \to y

而这由Heyting代数的定义所保证. 我们还需要说明这两个函数的单调性. 如果

x \leq y

, 那么

a \land x \leq a \land y

, 这可由定义得到. 如果

x \leq y

, 我们要证明

a \to x \leq a \to y

. 根据

a \to x \leq a \to x

, 根据剩余律我们有

(a \to x) \land a \leq x

, 鉴于

x \leq y

, 所以有

(a \to x) \land a \leq y

, 再用一次剩余律可知

a \to x \leq a \to y

.
2推出1: 根据1推出2的证明, 这就是立即可以得到的.
1推出3: 我们欲说明

a \to b

是

{x \in H | a \land x \leq b}

的最大元. 首先, 根据1推出2的证明过程, 我们知道

a \land (a \to b) \leq b

这一事实, 于是

(a \to b) \in {x \in H | a \land x \leq b}

. 其次, 如果

c \in H

满足

a \land c \leq b

, 那么根据剩余律

c \leq a \to b

. 由此, 我们知道

b \to c

就是最大元.
3推出1: 我们定义

(a \to b) ≔ Max ({x \in H | a \land x \leq b})

, 当然这是良定的. 接着, 我们需要证明剩余律. 对于任意的

a, b, c \in H

, 如果

c \land a \leq b

, 即

c \in {x \in H | a \land x \leq b}

c \leq a \to b

根据定义即得. 如果

c \leq a \to b

, 那么

c \land a \leq (a \to b) \land a \leq b

, 这就是根据

a \to b

的定义得到的.

◻

例子3.1.1.

定理3.1.2. 每个Heyting代数都是分配格.

证明. 仅需证明对于任意的

a, b, c \in H

都有

a \land (b \lor c) \leq (a \land b) \lor (a \land c)

, 因为另一个方向对于普通的格都成立. 令

RHS = (a \land b) \lor (a \land c)

. 因为

a \land b \leq RHS

, 所以

b \leq a \to RHS

. 因为

a \land c \leq RHS

, 所以

c \leq a \to RHS

. 因此,

b \lor c \leq a \to RHS

. 于是,

a \land (b \lor c) \leq RHS

◻

定理3.1.3. 每个有限分配格都是Heyting代数.

证明. 设

H

是一个有限分配格. 对于任意的

a, b \in H

, 令

S = {x \in H | a \land x \leq b}

. 我们想要说明

⋁ S \in S

. 换言之, 我们要证明

a \land ⋁ S \leq b

, 即

⋁ (a \land S) \leq b

. 根据

S

的定义,

a \land S

的元素都小于等于

b

. 换言之,

b

是

a \land S

的一个上界, 当然有

a \land ⋁ S \leq b

. 这说明

H

是一个Heyting代数.

◻

定理3.1.4. 每个Boole代数都是Heyting代数.

证明.

◻

定理3.1.5. 设

H

是一个Heyting代数, 则对于任意的

a, b, c \in H

, 我们有

$b \leq a \to b$ ;
$1 \to a = a$ ;
$a \to b = 1 ⟺ a \leq b$ ;
$a \land (a \to b) = a \land b$ ;
$a \to (-)$ 保序, $(-) \to a$ 逆序;
$a \to (b \land c) = (a \to b) \land (a \to c)$ ;
$(a \lor b) \to c = (a \to c) \land (b \to c)$ ;
$a \to (b \to c) = (a \land b) \to c$ ;
$a \leq (a \to b) \to b$ ;
$((a \to b) \to b) \to b = a \to b$ ;
$(a \to b) \land (b \to c) \leq a \to c$ ;
如果 $a$ 是交素元, 那么 $b \to a = 1$ 或 $b \to a$ 也是交素元.

证明.

由 $b \land a \leq b$ 和剩余律立即得到.
由1可知 $a \leq 1 \to a$ , 另外 $1 \to a \leq (1 \to a) \land 1 \leq a$ , 由此可知 $1 \to a = a$ .
如果 $a \leq b$ , 那么 $a \to a \leq a \to b$ , 即 $1 \leq a \to b$ , 又因为 $a \to b \leq 1$ , 故 $a \to b = 1$ . 反过来, 如果 $a \to b = 1$ , 那么 $1 \leq a \to b$ , 于是 $1 \land a \leq b$ , 即 $a \leq b$ .
$a \land (a \to b) \leq a$ 是 $\land$ 的定义的一部分, $a \land (a \to b) \leq b$ 可以根据剩余律轻松得到, 于是 $a \land (a \to b) \leq a \land b$ . 由1知 $b \leq a \to b$ , 故根据 $\land$ 的保序性有 $a \land b \leq a \land (a \to b)$ . 因此, 我们有 $a \land (a \to b) = a \land b$ .
如果 $x \leq y$ , 我们需要证明 $a \to x \leq a \to y$ . 首先, 我们有 $a \to x \leq a \to x$ , 于是 $(a \to x) \land a \leq x$ , 接着由 $x \leq y$ 可知 $(a \to x) \land a \leq y$ , 最后得到 $a \to x \leq a \to y$ . 如果 $x \leq y$ , 我们需要证明 $y \to a \leq x \to a$ . 因为 $x \leq y$ , 所以 $(y \to a) \land x \leq (y \to a) \land y \leq a$ , 于是 $y \to a \leq x \to a$ .
因为 $b \land c \leq b$ 和 $b \land c \leq c$ , 所以说 $a \to (b \land c) \leq a \to b$ 且 $a \to (b \land c) \leq a \to c$ , 于是 $a \to (b \land c) \leq (a \to b) \land (a \to c)$ . 我们还需要证明 $(a \to b) \land (a \to c) \leq a \to (b \land c)$ . 这等价于证明 $a \land (a \to b) \land (a \to c) \leq b \land c$ . 我们知道 $\begin{array}{rcl} a \land (a \to b) \land (a \to c) & = & (a \land a) \land (a \to b) \land (a \to c) \\ = & (a \land (a \to b)) \land (a \land (a \to c)) \end{array}$ 鉴于 $a \land (a \to b) \leq b$ 和 $a \land (a \to c) \leq c$ , 所以 $(a \land (a \to b)) \land (a \land (a \to c)) \leq b \land c$ .
因为 $a \lor b \geq a$ 和 $a \lor b \geq b$ , 所以 $(a \lor b) \to c \leq a \to c$ 且 $(a \lor b) \to c \leq b \to c$ , 于是 $(a \lor b) \to c \leq (a \to c) \land (b \to c)$ . 我们还需要证明 $(a \to c) \land (b \to c) \leq (a \lor b) \to c$ . 这等价于证明 $(a \lor b) \land (a \to c) \land (b \to c) \leq c$ . 于是, 我们有 $\begin{array}{cl} (a \lor b) \land (a \to c) \land (b \to c) \\ = & (a \land (a \to c) \land (b \to c)) \lor (b \land (a \to c) \land (b \to c)) \\ \leq & (c \land (b \to c)) \lor (c \land (a \to c)) \\ \leq & c \end{array}$
对于每个 $x \in H$ , 我们有 $\begin{array}{cl} x \leq a \to (b \to c) \\ ⟺ & x \land a \leq b \to c \\ ⟺ & x \land a \land b \leq c \\ ⟺ & x \leq (a \land b) \to c \end{array}$ 分别取 $x = a \to (b \to c)$ 和 $x = (a \land b) \to c$ 就能得到等式.
由 $a \to b \leq a \to b$ 可知 $(a \to b) \land a \leq b$ , 于是 $a \leq (a \to b) \to b$ .
首先根据9, 我们可以知道 $a \to b \leq ((a \to b) \to b) \to b$ . 因此, 我们还需要证明 $((a \to b) \to b) \to b \leq a \to b$ . 根据 $(-) \to b$ 的逆序性, 再次应用9, 可以得到这个结果.
$a \land (a \to b) \land (b \to c) \leq b \land (b \to c) \leq c$ , 于是 $(a \to b) \land (b \to c) \leq a \to c$ .

◻

定理3.1.6. 设

H

是一个有最大元

1

的格,

\to : H \times H \to H

是一个二元运算, 则

H

在

\to

下是Heyting代数当且仅当对于任意的

a, b, c \in H

, 有

$a \to a = 1$ ;
$a \land (a \to b) = a \land b$ ;
$(a \to b) \land b = b$ ;
$a \to (b \land c) = (a \to b) \land (a \to c)$ .

证明.

◻

定理3.1.7. 设

H

是具有最小元

0

的Heyting代数, 定义

x^{'} = x \to 0

, 那么对于任意的

a, b \in H

, 我们有

$0^{'} = 1$ , $1^{'} = 0$ ;
$a^{'} \land a = 0$ ;
${(-)}^{'} : H \to H$ 是逆序的;
${(a \lor b)}^{'} = a^{'} \land b^{'}$ ;
$a \leq {a^{'}}^{'}$ ;
$a^{'} = {a^{'}}^{'}^{'}$ .

证明.

$0^{'} = 0 \to 0 = 1$ 是显然的, 因为 $a \to a = 1$ , 不论 $a$ 是什么元素. $1^{'} = 1 \to 0 = Max ({x \in H | x \leq 0}) = Max ({0}) = 0$ .
我们知道 $(a \to 0) \land a \leq 0$ , 于是 $a^{'} \land a = 0$ .
此即 $(-) \to a$ 总是逆序的推论.
定理3.1.5的第7条的推论.
由 $a^{'} \land a = 0$ 和剩余律立即得到, 或者说是定理3.1.5的第9条的推论.
定理3.1.5的第10条的推论.

◻

定理3.1.8. 设

H

是一个有最小元

0

的Heyting代数, 则下列条件等价:

$H$ 相对于 ${(-)}^{'}$ 运算是一个Boole代数;
$\forall a \in H . a^{'} \lor a = 1$ ;
$\forall a, b \in H . a \to b = a^{'} \lor b$ ;
对于任意的 $a \in H$ , $a \to H = {a \to x | x \in H}$ 是上集;
$\forall a, b \in H . (a \to b) \to b = a \lor b$ ;
$\forall a \in H . {a^{'}}^{'} = a$ ;
${(-)}^{'} : H \to H$ 是满射;
对于任意的 $a \in H$ , 如果 $a^{'} = 0$ , 那么 $a = 1$ .

证明. 1推出2: 定义.
2推出3: 先证明

a^{'} \lor b \leq a \to b

. 这等价于证明

a^{'} \leq a \to b

和

b \leq a \to b

. 鉴于

0 \leq b

, 所以

a \to 0 \leq a \to b

. 第二个不等式等价于

b \land a \leq b

, 这个根据定义即得. 现在我们要证明

a \to b \leq a^{'} \lor b

. 鉴于

a^{'} \lor a = 1

, 我们有

a \to b = (a \to b) \land (a^{'} \lor a) = ((a \to b) \land a^{'}) \lor ((a \to b) \land a)

我们知道这个析取左支小于等于

a^{'}

, 这个析取右支小于等于

b

, 而这正是我们想要的.
3推出4: 对于

x \in (a \to H)

, 存在

x_{0} \in H

使得

x = a \to x_{0}

. 根据3的条件, 即

x = a^{'} \lor x_{0}

. 对于

y \in H

满足

x \leq y

, 我们知道

a^{'} \lor x_{0} \leq y

, 于是

\begin{array}{cl} (a^{'} \lor x_{0}) \lor y \\ = & a^{'} \lor (x_{0} \lor y) \\ = & a \to (x_{0} \lor y) \\ = & y \end{array}

即

y \in H

.
4推出5: 首先,

a \lor b \leq (a \to b) \to b

在任意的Heyting代数中均成立, 所以我们仅需要证明

(a \to b) \to b \leq a \lor b

◻

设 $H$ 是一个有最小元 $0$ 的Heyting代数, 如果元素 $a$ 满足 ${a^{'}}^{'} = a$ , 则称 $a$ 为 $H$ 的一个正则元素, 或者说Boole元素. 记 $B (H)$ 为 $H$ 的正则元素全体构成的集合, 显然 $0, 1 \in B (H)$ , 而且 $a \in B (H)$ 当且仅当存在 $b \in H$ 满足 $a = b^{'}$ .

定理3.1.9. 设

H

是一个Heyting代数, 如果

x, y \in B (H)

, 那么

x \land y, x \to y \in B (H)

证明.

◻

第3.2节滤子和同余关系之间的一一对应

第4章 Frame和拓扑表示定理

第4.1节 Frame的定义和基本性质

定义4.1.1. 设

L

是一个完备格, 如果对于任意的

a \in L

和

S \subseteq L

, 都有

\begin{array}{lcr} a \land ⋁ S = \underset{s \in S}{⋁} (a \land s) & (IFD) \end{array}

则称

L

为一个frame. 我们将IFD这种性质叫做无限分配律.

定义4.1.2. 设

f : A \to B

是frame之间的一个映射, 如果

f

保持有限的交和任意的并 (包括空集的交和并), 则称

f

是从

A

到

B

的frame同态. 全体frame和frame同态构成的范畴记为

Frm

评注4.1.1.

若 $f : A \to B$ 是一个frame同态, 那么 $f (0) = 0$ , $f (1) = 1$ .
当 $A$ 和 $B$ 仅为完备格时, 如果 $f : A \to B$ 保持有限交和任意的并, 我们仍然将这种映射称为frame同态.

例子4.1.1.

定义4.1.3. 设

L

是一个完备格,

F \in Fil (L)

. 如果对于任意的

S \subseteq L

都有

⋁ S \in F

可以推出

S \cap F \neq \emptyset

, 则称

F

为

L

的完全素滤子.

第4.2节空间式frame和sober空间

第5章 Domain与连续格

第5.1节基本domain结构

定义5.1.1. 设

L

是一个偏序集, 如果

L

的每个定向子集都有上确界, 那么称

L

为定向完备偏序集 (dcpo).

定义5.1.2. 设

L

是一个dcpo,

x, y \in L

. 如果对于

L

的任意定向子集

D

x \leq ⋁ D

可以推出

y \in ↓ D

, 则称

y

双小于 (way below)

x

, 记作

x ≪ y

. 并且, 我们记

⇓ x = {y \in L | y ≪ x}

⇑ x = {z \in L | x ≪ z}

评注5.1.1.

定理5.1.1. 设

L

是一个dcpo, 那么对于任意的

u, x, y, z \in L

, 我们有

$x ≪ y$ 可以推出 $x \leq y$ ;

第6章完全分配格

第7章剩余格

第7.1节剩余格的基本概念

定义7.1.1. 设

L

是一个有界格,

0

和

1

分别是其最小元和最大元,

\otimes, \to : L \times L \to L

是两个其上的二元运算. 如果

$(L, \otimes, 1)$ 是交换幺半群;
对于任意的 $a, b, c \in L$ 都有 $a \otimes b \leq c ⟺ a \leq b \to c$

则称

(L, \otimes, \to)

为剩余格. 当

L

还是完备格时, 则称

L

为完备剩余格.

定理7.1.1. 设

L

是一个剩余格, 则对于任意的

a, b, c \in L

, 我们有

$a \otimes b \leq a \land b$ ;
$a \otimes 0 = 0, 1 \to a = a$ ;
$b \leq a \to b$ ;
$a \leq b$ 当且仅当 $a \to b = 1$ ;
如果 $a \leq b$ , 那么 $a \otimes c \leq b \otimes c$ , $c \to a \leq c \to b$ , $b \to c \leq a \to c$ ;
$a \otimes (a \to b) \leq a \land b$ ;
$b \leq a \to (a \otimes b)$ ;
$a \to (b \to c) = (a \otimes b) \to c = b \to (a \to c)$ ;
$(a \to b) \otimes (b \to c) \leq a \to c$ ;
$a \to (a \otimes (a \to b)) = a \to b$ ;
$a \lor b \leq (a \to b) \to b$ ;
$((a \to b) \to b) \to b = a \to b$ ;
$(a \lor b) \to c = (a \to c) \land (b \to c)$ ;
$a \to (b \land c) = (a \to b) \land (a \to c)$ ;
$b \to c \leq (a \land b) \to (a \land c)$ , $b \to c \leq (a \lor b) \to (a \lor c)$ ;
$b \to c \leq (a \to b) \to (a \to c)$ , $b \to c \leq (c \to a) \to (b \to a)$ ;
$(a \lor b) \to b = a \to b = a \to (a \land b)$ ;

如果

L

是完备剩余格, 那么对于任意的

证明.

由 $a \leq a$ 和 $1$ 为 $\otimes$ 的单位元可知 $1 \otimes a \leq a$ , 而这等价于 $1 \leq a \to a$ . 因此, $a \to a = 1$ . (这是一般性的结论.) 根据 $a \leq b \to b$ 可知 $a \otimes b \leq b$ , 根据 $b \leq a \to a$ 可知 $b \otimes a \leq a$ , 即 $a \otimes b \leq a$ . 于是, $a \otimes b \leq a \land b$ .
由 $a \leq 0 \to 0$ 可知 $a \otimes 0 \leq 0$ , 于是 $a \otimes 0 = 0$ . 由 $x \leq 1 \to a$ 等价于 $x \otimes 1 \leq a$ , 即 $x \leq a$ , 可知 $1 \to a = a$ .
由 $a \leq b \to b$ 可知 $a \otimes b \leq b$ , 于是 $b \otimes a \leq b$ , 因此 $b \leq a \to b$ .
$a \to b = 1$ 和 $1 \leq a \to b$ 是等价的. $1 \leq a \to b$ 和 $1 \otimes a \leq b$ 是等价的. $1 \otimes a \leq b$ 和 $a \leq b$ 是等价的. 于是, $a \leq b$ 和 $a \to b = 1$ 是等价的.
因为 $b \otimes c \leq b \otimes c$ , 那么 $b \leq c \to (b \otimes c)$ , 又因为 $a \leq b$ , 所以 $a \leq c \to (b \otimes c)$ , 于是 $a \otimes c \leq b \otimes c$ . 因为 $c \to a \leq c \to a$ , 所以 $(c \to a) \otimes c \leq a$ , 又因为 $a \leq b$ , 所以 $(c \to a) \otimes c \leq b$ , 于是 $c \to a \leq c \to b$ . 因为 $b \to c \leq b \to c$ , 所以 $(b \to c) \otimes b \leq c$ , 于是 $b \leq (b \to c) \to c$ , 又 $a \leq b$ , 可知 $a \leq (b \to c) \to c$ , 于是 $a \otimes (b \to c) \leq c$ , 最终得到 $b \to c \leq a \to c$ .
由 $a \to b \leq a \to b$ 可知 $a \otimes (a \to b) \leq b$ , 而由1我们知道 $a \otimes (a \to b) \leq a \land (a \to b) \leq a$ , 于是 $a \otimes (a \to b) \leq a \land b$ .
由 $a \otimes b \leq a \otimes b$ 可知 $b \leq a \to (a \otimes b)$ .
设 $x \in L$ , 我们有 $\begin{array}{cl} x \leq a \to (b \to c) \\ ⟺ & x \otimes a \leq b \to c \\ ⟺ & x \otimes a \otimes b \leq c \\ ⟺ & x \leq (a \otimes b) \to c \\ ⟺ & x \otimes b \otimes a \leq c \\ ⟺ & x \otimes b \leq a \to c \\ ⟺ & x \leq b \to (a \to c) \end{array}$
$\begin{array}{cl} a \otimes (a \to b) \otimes (b \to c) \\ \leq & b \otimes (b \to c) \\ \leq & c \end{array}$ 于是, 我们有 $(a \to b) \otimes (b \to c) \leq a \to c$ .
设 $x \in L$ , 我们有 $\begin{array}{cl} x \leq a \to (a \otimes (a \to b)) \\ ⟹ & x \otimes a \leq a \otimes (a \to b) \\ ⟹ & x \otimes a \leq b \\ ⟹ & x \leq a \to b \end{array}$ 于是 $a \to (a \otimes (a \to b)) \leq a \to b$ . 另外, 根据 $a \otimes (a \to b) \leq a \otimes (a \to b)$ , 可知 $a \to b \leq a \to (a \otimes (a \to b))$ .
首先, $a \leq (a \to b) \to b$ 等价于 $a \otimes (a \to b) \leq b$ , 这显然成立. 其次, $b \leq (a \to b) \to b$ 等价于 $a \to b \leq b \to b$ , 这也显然成立.
根据 $(a \to b) \otimes ((a \to b) \to b) \leq b$ 这一事实, 可以得到 $a \to b \leq ((a \to b) \to b) \to b$ . 另外, 根据11我们有 $a \leq (a \to b) \to b$ , 再根据5可得 $((a \to b) \to b) \to b \leq a \to b$ .
因为 $a \lor b \geq a$ , 所以 $(a \lor b) \to c \leq a \to c$ . 因为 $a \lor b \geq b$ , 所以 $(a \lor b) \to c \leq b \to c$ . 因此, $(a \lor b) \to c \leq (a \to c) \land (b \to c)$ . 我们还需要证明 $(a \to c) \land (b \to c) \leq (a \lor b) \to c$ . 令 $x = (a \to c) \land (b \to c)$ . 因为 $x \leq a \to c$ , 所以 $a \leq x \to c$ . 同理, $b \leq x \to c$ . 于是, $a \lor b \leq x \to c$ . 那么, $x \leq (a \lor b) \to c$ , 即 $(a \to c) \land (b \to c) \leq (a \lor b) \to c$ .
因为 $b \land c \leq b$ 和 $b \land c \leq c$ , 所以 $a \to (b \land c) \leq a \to b$ 且 $a \to (b \land c) \leq a \to c$ , 于是 $a \to (b \land c) \leq (a \to b) \land (a \to c)$ . 我们还需要证明 $(a \to b) \land (a \to c) \leq a \to (b \land c)$ . 这等价于 $a \otimes ((a \to b) \land (a \to c)) \leq b \land c$ . 我们将其处理为分别证明 $a \otimes ((a \to b) \land (a \to c)) \leq b$ 和 $a \otimes ((a \to b) \land (a \to c)) \leq c$ . 先来看第一个, 第二个的证明是类似的. 我们知道 $(a \to b) \land (a \to c) \leq a \to b$ , 再根据单调性, 我们有 $a \otimes ((a \to b) \land (a \to c)) \leq a \otimes (a \to b) \leq b$ . 这就是我们所要的, 另一个是差不多的.
对于第一条, 这等价于证明 $(a \land b) \otimes (b \to c) \leq a \land c$ 而这等价于 $(a \land b) \otimes (b \to c) \leq a 且 (a \land b) \otimes (b \to c) \leq c$ 对于右边的不等式, 我们可以这样证明: $\begin{array}{rcl} (a \land b) \otimes (b \to c) & \leq & b \otimes (b \to c) \\ \leq & c \end{array}$ 对于左边的不等式, 我们需要用到1来证明: $\begin{array}{rcl} (a \land b) \otimes (b \to c) & \leq & (a \land b) \land (b \to c) \\ \leq & a \land b \\ \leq & a \end{array}$ 对于第二条, 这等价于证明 $b \to c \leq (a \to (a \lor c)) \land (b \to (a \lor c))$ 而这又等价于证明 $a \otimes (b \to c) \leq a \lor c 且 b \otimes (b \to c) \leq a \lor c$ 左边的证明: $\begin{array}{rcl} a \otimes (b \to c) & \leq & a \land (b \to c) \\ \leq & a \\ \leq & a \lor c \end{array}$ 右边的证明: $\begin{array}{rcl} b \otimes (b \to c) & \leq & c \\ \leq & a \lor c \end{array}$
对于第一条, 这等价于 $(a \to b) \otimes (b \to c) \leq a \to c$ 这就是9. 对于第二条, 这等价于 $(b \to c) \otimes (c \to a) \leq b \to a$ 这还是9.
根据13, 我们有 $(a \lor b) \to b = (a \to b) \land (b \to b) = (a \to b) \land 1 = a \to b$ 根据14, 我们有 $a \to (a \land b) = (a \to a) \land (a \to b) = 1 \land (a \to b) = a \to b$

◻

定理7.1.2. 设

L

是一个有界格,

\otimes, \to : L \times L \to L

是两个运算, 其中

\otimes

是以

1

为单位元的交换幺半群运算, 那么

(L, \otimes, \to)

构成剩余格当且仅当对于任意的

a, b, c \in L

有

$(a \otimes b) \to c = a \to (b \to c)$ ;
$(a \otimes (a \to b)) \lor b = b$ ;
$a \to (a \lor b) = 1$ .

证明. 由剩余格推出这三条性质, 根据前述定理, 基本上是显然的. 显然我们证明反方向, 对于满足这些性质的运算, 我们说明

(L, \otimes, \to)

构成了一个剩余格.

◻

定理7.1.3. 在剩余格中, 如果

\otimes

是幂等运算, 那么

\otimes = \land

. 换言之, 有界Heyting代数是唯一一类乘法运算具有幂等性的剩余格.

证明.

◻

设 $L$ 是一个剩余格, 定义 ${(-)}^{'} : L \to L$ 为 $a^{'} = a \to 0$ . 称 $a^{'}$ 为 $a$ 的否定.

定理7.1.4. 设

L

是一个剩余格, 那么

$0^{'} = 1$ , $1^{'} = 0$ ;
$a \leq {a^{'}}^{'}$ , ${a^{'}}^{'}^{'} = a^{'}$ ;
$a \otimes a^{'} = 0$ ;

证明.

◻

设 $L$ 是一个剩余格, 定义 $\oplus, ⊖ : L \times L \to L$ 为 $a \oplus b = {(a^{'} \otimes b^{'})}^{'}, a ⊖ b = a \otimes b^{'}$ 显然, $\oplus$ 是一个交换的半群运算.

定理7.1.5. 设

L

是一个剩余格, 那么对于任意的

a, b, c \in L

, 我们有

$a ⊖ b \leq a \leq a \oplus b$ ;
$a \leq b$ 可以推出 $a ⊖ b = 0$ ;

序与格论基础

第1章 偏序集与格

第1.1节 偏序集

第1.2节 格与完备格

第1.3节 序同构与格同构

第1.4节 分配格与Boole代数

第1.5节 理想和滤子

第1.6节 格中的特殊元素

习题1

第2章 Galois伴随和Galois连接

第2.1节 Galois伴随

第2.2节 内部算子和闭包算子与Galois伴随的关系

第2.3节 Galois连接

第2.4节 形式概念分析的格论基础

第2.5节 偏序集的Dedekin-MacNeille完备化

习题2

第3章 Heyting代数

第3.1节 Heyting代数的基本概念

第3.2节 滤子和同余关系之间的一一对应

第4章 Frame和拓扑表示定理

第4.1节 Frame的定义和基本性质

第4.2节 空间式frame和sober空间

第5章 Domain与连续格

第5.1节 基本domain结构

第6章 完全分配格

第7章 剩余格

第7.1节 剩余格的基本概念

第1章偏序集与格

第1.1节偏序集

第1.2节格与完备格

第1.3节序同构与格同构

第1.4节分配格与Boole代数

第1.5节理想和滤子

第1.6节格中的特殊元素

第2.2节内部算子和闭包算子与Galois伴随的关系

第2.4节形式概念分析的格论基础

第2.5节偏序集的Dedekin-MacNeille完备化

第3.2节滤子和同余关系之间的一一对应

第4.2节空间式frame和sober空间

第5.1节基本domain结构

第6章完全分配格

第7章剩余格

第7.1节剩余格的基本概念