大一上学期学离散数学，不懂什么是数学结构，数据结构。也不知道学的离散数学到底有什么用，用在什么地方。后来知道，数据结构课程中的各种数据结构都可以用离散数学中的数学定义来解释，使得这些数据结构有相对严格的数学基础。而相对严格的数学基础，能够更加精确地描述数据结构。
现在工作用到了很多离散数学的知识，得慢慢学习，将以前学习的知识补回来。所以在工作中实际上有必要重新温故或者重新学一遍。跟工作实践相结合。相信能够对这些计算机基础有更深的理解，最重要的是，帮助理解工作中要用到的一些核心概念。
哦，对。现代数学的基础就是集合论。
偏序与格理论的应用
-
- 分布式系统：vector clocks and global predicate detection
-
- 并发理论：pomsets and occurrence nets
-
程序语言语义（Programming Semantic）：fixed-point semantics。个人研究方向相关，所以主要关注在这个领域的应用
-
- 数据挖掘：concept analysis
-
- 数学：组合学，数论，群论
1. 关系
关 系 R 定 义 在 任 意 集 合 X 上 ， 它 是 X × X 的 子 集 ， 即 ： R ⊆ X × X 关系R定义在任意集合X上，它是X \times X的子集，即：R \subseteq X \times X 关系R定义在任意集合X上，它是X×X的子集，即：R⊆X×X
例如 X = {a, b, c}, 某个定义在X上的关系R为 R = { (a, c), {a, a}, {b, c}, {c, a} }
从图的角度描述关系：
X
为
顶
点
的
集
合
,
(
x
,
y
)
∈
R
,
当
且
仅
当
图
上
存
在
一
条
有
向
边
x
→
y
:
X为顶点的集合, (x,y) \in R, 当且仅当图上存在一条有向边x \rightarrow y:
X为顶点的集合,(x,y)∈R,当且仅当图上存在一条有向边x→y:
关系的性质有
自反性（reflexive）： r e f l e x i v e : ∀ x ∈ X , ( x , x ) ∈ R reflexive: \forall x \in X, (x, x) \in R reflexive:∀x∈X,(x,x)∈R- 图的角度：图的每个节点都有一条自环边
- 定义在正整数N上的整除关系 / / /
-
非自反性（irreflexive）： i r r e f l e x i v e : ∀ x ∈ X , ( x , x ) ∉ R irreflexive: \forall x \in X, (x, x) \notin R irreflexive:∀x∈X,(x,x)∈/R- 图的角度：图上每个节点不存在任何自环边
- 定义在整数N上的小于关系 < < <
-
对称性（symmetric）： s y m m e t r i c : ∀ x , y ∈ X : ( x , y ) ∈ R ⇒ ( y , x ) ∈ R symmetric: \forall x, y \in X: (x, y) \in R \Rightarrow (y, x) \in R symmetric:∀x,y∈X:(x,y)∈R⇒(y,x)∈R- 图的角度：可以表示成无向图
反对称性（anti-symmetric）：
a n t i − s y m m e t r i c : ∀ x , y ∈ X : ( x , y ) ∈ R 并 且 ( y , x ) ∈ R ⇒ x = y anti-symmetric: \forall x, y \in X: (x, y) \in R \ 并且 \ (y, x) \in R\Rightarrow x = y anti−symmetric:∀x,y∈X:(x,y)∈R 并且 (y,x)∈R⇒x=y- 定义在整数上的 小于等于关系 ≤ \le ≤ : 1 ≤ 2 ≤ 3 ≤ 4 ≤ . . . 1 \le 2 \le 3 \le 4 \le \ ... 1≤2≤3≤4≤ ...
-
不对称（asymmetric）： a s y m m e t r i c : ∀ x , y ∈ X : ( x , y ) ∈ R ⇒ ( y , x ) ∉ R asymmetric: \forall x, y \in X: (x, y) \in R \Rightarrow (y, x) \notin R asymmetric:∀x,y∈X:(x,y)∈R⇒(y,x)∈/R- 定义在整数上的 小于关系 < < <
- 不对称的关系总是非自反的
-
传递性（transitive）： t r a n s i t i v e : ∀ x , y , z ∈ X : ( x , y ) ∈ R 并 且 ( y , z ) 并 且 R ⇒ ( x , z ) ∈ R transitive: \forall x, y, z \in X: (x, y) \in R 并且 (y, z) 并且 R \Rightarrow (x, z) \in R transitive:∀x,y,z∈X:(x,y)∈R并且(y,z)并且R⇒(x,z)∈R- 定义在整数上的小于等于关系 ≤ \le ≤
-
对等（equivalence）： e q u i v a l e n c e ⇔ 自 反 的 并 且 对 称 的 并 且 传 递 的 equivalence \Leftrightarrow 自反的 并且 对称的 并且传递的 equivalence⇔自反的并且对称的并且传递的- 如果关系R是对等的，我们使用记号 x ≡ R y 或 者 x ≡ y , 当 ( x , y ) ∈ R x \equiv_R y \ \ 或者 x \equiv y, 当(x, y) \in R x≡Ry 或者x≡y,当(x,y)∈R
等价类（equivalence class）： x 的 等 价 类 [ x ] R : 所 有 满 足 条 件 y 的 集 合 ： y ∈ R , y ≡ R x x的等价类[x]_R: 所有满足条件y的集合：y \in R, y \equiv_R x x的等价类[x]R:所有满足条件y的集合：y∈R,y≡Rx-
定
义
在
正
整
数
N
上
的
R
=
{
(
x
,
y
)
∣
x
m
o
d
5
=
y
m
o
d
5
}
定义在正整数N上的R = \{\ (x, y) \ | \ x \ mod \ 5 = y \ mod \ 5 \}
定义在正整数N上的R={ (x,y) ∣ x mod 5=y mod 5} 则
R将N分隔(partitions)为5个等价类
-
定
义
在
正
整
数
N
上
的
R
=
{
(
x
,
y
)
∣
x
m
o
d
5
=
y
m
o
d
5
}
定义在正整数N上的R = \{\ (x, y) \ | \ x \ mod \ 5 = y \ mod \ 5 \}
定义在正整数N上的R={ (x,y) ∣ x mod 5=y mod 5} 则
-
非自反传递闭包（irreflexive transitive closure）：-
i r r e f l e x i v e t r a n s i t i v e c l o s u r e R + : ∀ x , y ∈ X : ( x , y ) ∈ R + ⇔ ∃ x 0 , x 1 , . . . , x j j ≥ 1 , x 0 = x , y j = y , ∀ i : 0 ≤ i < j : ( x i , x j ) ∈ R irreflexive \ transitive \ closure \ \ R^+: \forall x, y \in X: (x, y) \in R^+ \Leftrightarrow \exists x_0,x_1,...,x_j \\ j \ge 1, \ \ x_0 = x, \ \ y_j = y, \ \forall i: 0 \le i < j : (x_i, x_j) \in R irreflexive transitive closure R+:∀x,y∈X:(x,y)∈R+⇔∃x0,x1,...,xjj≥1, x0=x, yj=y, ∀i:0≤i<j:(xi,xj)∈R
-
从图上理解： ( x , y ) ∈ R + ⇔ 存 在 一 条 从 x 到 y 的 非 空 路 径 (x, y) \in R^+ \Leftrightarrow 存在一条从x到y的非空路径 (x,y)∈R+⇔存在一条从x到y的非空路径
-
-
自反传递闭包（irreflexive transitive closure）：-
R ∗ = R + ∪ { ( x , x ) ∣ x ∈ X } R^* = R^+ \ \cup \ \{ \ \ (x, x) \ | \ x \in X \ \} R∗=R+ ∪ { (x,x) ∣ x∈X }
-
图上理解： ( x , y ) ∈ R ∗ ⇔ 存 在 一 条 从 x 出 发 , 取 0 条 或 者 多 条 边 可 达 y 的 路 径 (x, y) \in R^* \Leftrightarrow 存在一条从x出发,取0条或者多条边可达y的路径 (x,y)∈R∗⇔存在一条从x出发,取0条或者多条边可达y的路径
-
2. 偏序
-
自反偏序/非严格偏序（reflexible partial order / nonstrict partial order）：关系R是自反偏序/非严格偏序，如果R是自反的/反对称的/传递的。- ( x , y ) ∈ R ： x ≤ R y 或 者 x ≤ y (x, y) \in R：x \le_R y \ 或者 \ x \le y (x,y)∈R：x≤Ry 或者 x≤y
自反偏序集(reflexible partial ordered set)，我们也简写为poset除非有特别的说明，下文中以偏序来表示poset。 P = ( X , ≤ ) 表 示 P 为 定 义 在 X 上 的 自 反 偏 序 集 P = (X, \ \le)表示P为定义在X上的自反偏序集 P=(X, ≤)表示P为定义在X上的自反偏序集- 正整数上的整除关系 ；整数上的小于等于关系
-
非自反偏序/严格偏序：关系R是非自反偏序/严格偏序，如果R是非自反的/传递的。-
非自反/传递 => 非对称的
- 已 知 ： R 是 非 自 反 的 ， 传 递 的 。 证 明 R 是 非 对 称 的 ∀ ( x , y ) ∈ R 如 果 ( y , x ) ∈ R , 由 于 传 递 性 ⇒ ( x , x ) ∈ R 而 R 是 非 自 反 的 ， 所 以 ( y , x ) ∈ R 假 设 不 成 立 所 以 ∀ ( x , y ) ∈ R , ( y , x ) ∉ R ⇒ R 是 非 对 称 的 ( a s y m m e t r i c ) \begin{aligned} &已知：R是非自反的，传递的。证明R是非对称的\\ &\forall (x, y) \in R \\ &如果 (y, x) \in R, 由于传递性 \Rightarrow (x, x) \in R \\ &而R是非自反的，所以(y, x) \in R假设不成立 \\ &所以\forall (x, y) \in R, \ (y, x) \notin R \Rightarrow R是非对称的(asymmetric) \end{aligned} 已知：R是非自反的，传递的。证明R是非对称的∀(x,y)∈R如果(y,x)∈R,由于传递性⇒(x,x)∈R而R是非自反的，所以(y,x)∈R假设不成立所以∀(x,y)∈R, (y,x)∈/R⇒R是非对称的(asymmetric)
-
( x , y ) ∈ R ： x < R y 或 者 x < y (x, y) \in R：x <_R y \ 或者 \ x < y (x,y)∈R：x<Ry 或者 x<y
-
非自反偏序集(irreflexible partial ordered set)。 P = ( X , < ) 表 示 P 为 定 义 在 X 上 的 非 自 反 偏 序 集 P = (X, \ <)表示P为定义在X上的非自反偏序集 P=(X, <)表示P为定义在X上的非自反偏序集 -
定义在整数N上的小于关系
-
-
自反偏序和非自反偏序本质上是一样的（are essential the same）- 给 定 一 个 自 反 偏 序 P = ( X , ≤ ) , 我 们 能 定 义 非 自 反 偏 序 为 P 1 = ( X , < ) = { ( x , y ) ∣ ( x , y ) ∈ P 并 且 x ≠ y } 给定一个自反偏序P = (X, \ \le), 我们能定义非自反偏序为P^1 = (X, <) = \{\ (x, y) \ | \ (x,y) \in P 并且x \neq y \ \} 给定一个自反偏序P=(X, ≤),我们能定义非自反偏序为P1=(X,<)={ (x,y) ∣ (x,y)∈P并且x=y }
- 给 定 一 个 非 自 反 偏 序 P = ( X , < ) , 我 们 能 定 义 自 反 偏 序 为 P 1 = ( X , ≤ ) = { ( x , y ) ∣ ( x , y ) ∈ P 或 者 x = y } 给定一个非自反偏序P = (X, <), 我们能定义自反偏序为P^1 = (X, \le) = \{ \ (x, y) \ | (x, y) \in P \ 或者 \ x = y \ \} 给定一个非自反偏序P=(X,<),我们能定义自反偏序为P1=(X,≤)={ (x,y) ∣(x,y)∈P 或者 x=y }
-
全序（Total order）：R 是 偏 序 , ∀ x , y ∈ X , x ≠ y : ( x , y ) ∈ R 或 者 ( y , x ) ∈ R R是偏序, \forall x,y\in X, x \neq y: (x, y) \in R 或者(y, x) \in R R是偏序,∀x,y∈X,x=y:(x,y)∈R或者(y,x)∈R- 从X中任意取两个元素，它们都可以进行"比较"
- 整数的自然顺序是全序；正整数的整除关系不是全序
-
有限偏序集（Finite posets）通常可以用Hasse图来表示-
∀ x , y ∈ X , y c o v e r s x : ( x < y 并 且 ∀ z ∈ X : x ≤ z < y ) ⇒ z = x \forall x, y \in X, y \ covers \ x: (x < y \ 并且 \forall z\in X: x \le z < y) \Rightarrow z = x ∀x,y∈X,y covers x:(x<y 并且∀z∈X:x≤z<y)⇒z=x
-
也就是说y covers x，那么不会存在任何的元素z使得x < z < y -
y c o v e r s x ， 我 们 记 作 x < c y y \ covers \ x，我们记作 x <_c y y covers x，我们记作x<cy
-
x < c y , 我 们 也 称 y 是 x 的 一 个 u p p e r c o v e r ， x 是 y 的 一 个 l o w e r c o v e r x <_c y, 我们也称y是x的一个upper\ cover，x是y的一个lower\ cover x<cy,我们也称y是x的一个upper cover，x是y的一个lower cover
-
偏序的Hasse图： x 到 y 存 在 一 条 边 ， 当 且 仅 当 x < c y x到y存在一条边，当且仅当 x <_c y x到y存在一条边，当且仅当x<cy
-
X = { q , p , r , s } ; ≤ = { ( p , q ) ( q , r ) ( p , r ) ( p , s ) } X = \{q, p, r, s\}; \ \le \ = \{ \ (p, q) \ (q,r) \ (p,r) \ (p,s) \} X={q,p,r,s}; ≤ ={ (p,q) (q,r) (p,r) (p,s)} 则 P = ( X , ≤ ) ， P 偏 序 的 H a s s e 图 表 示 如 下 ： P = (X, \le)，P偏序的Hasse图表示如下： P=(X,≤)，P偏序的Hasse图表示如下：
-
r q p s 图6
-
-
子偏序集（subposet）：( Y , ≤ ) 为 偏 序 集 ( X , ≤ ) 的 子 偏 序 集 ， 那 么 ( Y , ≤ ) = { ( x , y ) ∣ Y ⊆ X , x , y ∈ Y , x ≤ X y } (Y, \le)为偏序集(X, \le)的子偏序集，那么(Y, \le) = \{ \ (x, y) \ | \ Y \subseteq X, x,y \in Y, x \le_X y \} (Y,≤)为偏序集(X,≤)的子偏序集，那么(Y,≤)={ (x,y) ∣ Y⊆X,x,y∈Y,x≤Xy} -
可比较的（Comparable）：-
x , y ∈ X 并 且 x ≠ y 如 果 x < y 或 者 x > y , 那 么 我 们 说 x , y 是 c o m p a r a b l e , 如 果 x 与 y 既 不 存 在 x < y 也 不 存 在 x > y , 那 么 我 们 说 x , y 是 i n c o m p a r a b l e , 记 作 x ∣ ∣ y \begin{aligned} &x,y \in X \ 并且 \ x \neq y \\ &如果 \ x < y \ 或者 \ x > y, 那么我们说x,y是comparable, \\ &如果x与y既不存在x < y 也不存在 x > y, 那么我们说x,y是incomparable, 记作x || y \end{aligned} x,y∈X 并且 x=y如果 x<y 或者 x>y,那么我们说x,y是comparable,如果x与y既不存在x<y也不存在x>y,那么我们说x,y是incomparable,记作x∣∣y
-
A n A_n An：表示n个不可比较的元素组成的偏序
-
-
链（Chain）与反链（antichain）：-
P = ( Y , ≤ ) （ 或 者 ( X , ≤ ) 的 某 个 子 偏 序 集 P ） 被 称 之 为 c h a i n ， 当 Y 中 每 对 不 同 的 元 素 对 都 是 c o m p a r a b l e 类 似 地 ， P 为 a n t i c h a i n ， 当 Y 中 每 两 个 元 素 是 i n c o m p a r a b l e \begin{aligned} & P = (Y, \le) （或者(X, \le)的某个子偏序集P）被称之为chain，当Y中每对不同的元素对都是comparable \\ & 类似地，P为antichain，当Y中每两个元素是incomparable \end{aligned} P=(Y,≤)（或者(X,≤)的某个子偏序集P）被称之为chain，当Y中每对不同的元素对都是comparable类似地，P为antichain，当Y中每两个元素是incomparable
-
如图6中， ( { p , q , r } , ≤ ) 是 一 个 c h a i n ， 而 ( { q , s } , ≤ ) 是 a n t i c h a i n (\ \{ \ p,q,r \ \}, \ \le \ )是一个chain，而(\ \{ \ q,s \ \}, \ \le \ )是antichain ( { p,q,r }, ≤ )是一个chain，而( { q,s }, ≤ )是antichain
-
n ：表示一个长度为n的链对应的偏序。如图7对应的偏序是 4
-
-
最长链（longest chain） 与 最大反链（largest antichain）
- P = ( X , ≤ ) 的 某 个 链 C 是 一 个 最 长 链 ， 当 没 有 其 它 链 包 含 的 元 素 比 C 多 ， 最 大 反 链 有 类 似 的 定 义 P = (\ X, \le )的某个链C是一个最长链，当没有其它链包含的元素比C多，最大反链有类似的定义 P=( X,≤)的某个链C是一个最长链，当没有其它链包含的元素比C多，最大反链有类似的定义
- 偏序的高度：一个poset的高度为最长链的元素个数
- 偏序的宽度：一个poset的宽度为最大反链的元素个数
- 图6的偏序高度为3（最长链为 {p, q, r}），宽度为2（最大反链为{q, s}）
-
区间（Interval）：偏 序 ( X , ≤ ) 上 的 区 间 定 义 ： [ x , y ] = { z ∣ x ≤ z ≤ y } 偏序\ (X, \ \le) \ 上的区间定义： \ [x,y] \ = \ \{ \ z \ | \ x \le z \le y \ \} 偏序 (X, ≤) 上的区间定义： [x,y] = { z ∣ x≤z≤y }-
区间 (x, y)，[x, y)，(x, y]的定义类似
-
local finite：一个偏序是local finite的，如果它的所有区间都是有限的。一般这里讨论的大多数偏序都是local finite的。 -
well-founded：一个偏序是well-founded的，当且仅当它没有无限递减的链。- 自然数的 ≤ \le ≤关系是well-founded，然而整数的 ≤ \le ≤ 不是well-founded
-
-
继承（extends）：Q = ( X , ≤ Q ) e x t e n d s P = ( X , ≤ P ) ， 当 ∀ x , y ∈ X : x ≤ P y ⇒ x ≤ Q y Q = (X, \ \le_Q) \ extends \ P = (X, \ \le_P)，当\forall x,y \in X: x \le_P y \Rightarrow x \le_Q y Q=(X, ≤Q) extends P=(X, ≤P)，当∀x,y∈X:x≤Py⇒x≤Qy-
线性继承（linear extension）：如 果 Q 是 全 序 ， 我 们 称 Q 是 P 的 线 性 继 承 如果Q是全序，我们称Q是P的线性继承 如果Q是全序，我们称Q是P的线性继承 -
图6定义了P, 那么可以定义P的一个线性继承: Q = ( { p , q , r , s } , X p ∪ { ( q , s ) , ( r , s ) } ) Q = (\{p,q,r,s\}, X_p \cup \{ (q,s), (r,s) \}) Q=({p,q,r,s},Xp∪{(q,s),(r,s)})
-
r q p s 图7
-
3. Join 与 Meet 操作
定义集合X的子集上的操作：meet和join。
-
meet操作也叫 infimum（或者inf）。
infimum中文翻译为下确界 -
join操作也叫supremum（或者sup）。
supremum中文翻译为上确界
最大下界（greatest lower bound，glb）的概念：
(
X
,
≤
)
是
一
个
偏
序
，
Y
⊆
X
,
对
于
m
∈
X
,
我
们
说
m
=
i
n
f
Y
（
m
是
Y
的
下
确
界
）
，
当
且
仅
当
1.
∀
y
∈
Y
,
m
≤
y
并
且
2.
∀
m
′
∈
X
:
(
∀
y
∈
Y
:
m
′
≤
y
)
=
>
m
′
≤
m
条
件
1
保
证
m
是
Y
的
一
个
下
界
条
件
2
保
证
m
是
Y
的
下
界
中
最
大
的
\begin{aligned} & (X,\ \le)是一个偏序，Y \subseteq X, 对于m \in X, 我们说m = inf \ Y \ （m是Y的下确界），当且仅当 \\ & 1. \ \forall y \in Y, m \le y \ 并且 \\ & 2. \ \forall m' \in X: (\forall y \in Y: m' \le y) => m' \le m & \\ \\ & 条件1保证m是Y的一个下界 \\ & 条件2保证m是Y的下界中最大的 \end{aligned}
(X, ≤)是一个偏序，Y⊆X,对于m∈X,我们说m=inf Y （m是Y的下确界），当且仅当1. ∀y∈Y,m≤y 并且2. ∀m′∈X:(∀y∈Y:m′≤y)=>m′≤m条件1保证m是Y的一个下界条件2保证m是Y的下界中最大的
m = inf Y，m也叫做Y的glb。显然，glb是唯一的。
注意，m不一定是Y中的元素
同样我们也能够定义最小上界（leatest upper bound，lub）的概念：
(
X
,
≤
)
是
一
个
偏
序
，
Y
⊆
X
,
对
于
s
∈
X
,
我
们
说
s
=
s
u
p
Y
（
s
是
Y
的
上
确
界
）
，
当
且
仅
当
1.
∀
y
∈
Y
,
y
≤
s
并
且
2.
∀
s
′
∈
X
:
(
∀
y
∈
Y
:
y
≤
s
′
)
=
>
s
≤
s
′
条
件
1
保
证
m
是
Y
的
一
个
下
界
条
件
2
保
证
m
是
Y
的
下
界
中
最
大
的
\begin{aligned} & (X,\ \le)是一个偏序，Y \subseteq X, 对于s \in X, 我们说s = sup \ Y \ （s是Y的上确界），当且仅当 \\ & 1. \ \forall y \in Y, y \le s \ 并且 \\ & 2. \ \forall s' \in X: (\forall y \in Y: y \le s') => s \le s' & \\ \\ & 条件1保证m是Y的一个下界 \\ & 条件2保证m是Y的下界中最大的 \end{aligned}
(X, ≤)是一个偏序，Y⊆X,对于s∈X,我们说s=sup Y （s是Y的上确界），当且仅当1. ∀y∈Y,y≤s 并且2. ∀s′∈X:(∀y∈Y:y≤s′)=>s≤s′条件1保证m是Y的一个下界条件2保证m是Y的下界中最大的
s = sup Y，s也叫Y的lub。显然，lub是唯一的
注意，s不一定是Y中的元素
我们定义特殊的符号：
-
a
⊓
b
:
i
n
f
{
a
,
b
}
a \sqcap b \ : \ inf \ \{a, \ b\}
a⊓b : inf {a, b}
- 引理： x ≤ y ⇔ ( x ⊓ y ) = x x \le y \Leftrightarrow (x \sqcap y) = x x≤y⇔(x⊓y)=x
-
a
⊔
b
:
s
u
p
{
a
,
b
}
a \sqcup b \ : \ sup \ \{a, \ b \}
a⊔b : sup {a, b}
- 引理： x ≤ y ⇔ ( x ⊔ y ) = y x \le y \Leftrightarrow (x \sqcup y) = y x≤y⇔(x⊔y)=y
格（lattice）是一个特殊的偏序集，能够使用meet和join操作来定义：
一
个
偏
序
(
X
,
≤
)
是
一
个
L
a
t
t
i
c
e
,
当
且
仅
当
:
∀
x
,
y
∈
X
：
x
⊔
y
和
x
⊓
y
存
在
一个偏序(X, \ \le) \ 是一个Lattice,\ 当且仅当: \forall x,y \in X：x \sqcup y \ 和 \ x \sqcap y \ 存在
一个偏序(X, ≤) 是一个Lattice, 当且仅当:∀x,y∈X：x⊔y 和 x⊓y 存在
-
半格：
-
∀ x , y ∈ X : x ⊔ y 存 在 ， 那 么 它 就 是 一 个 s u p s e m i l a t t i c e \forall x, y \in X: x \sqcup y存在，那么它就是一个sup \ semilattice ∀x,y∈X:x⊔y存在，那么它就是一个sup semilattice
-
∀ x , y ∈ X : x ⊓ y 存 在 ， 那 么 它 就 是 一 个 i n f s e m i l a t t i c e \forall x, y \in X: x \sqcap y存在，那么它就是一个inf \ semilattice ∀x,y∈X:x⊓y存在，那么它就是一个inf semilattice
-
半格的定义等效于要求有限大小的集合存在lub，glb。
-
-
完全格：对任意集合的格都有lub和glb
-
可分配格： 一 个 格 L 是 可 分 配 的 ， 当 ∀ a , b , c ∈ L : a ⊓ ( b ⊔ c ) = ( a ⊓ b ) ⊔ ( a ⊓ c ) 一个格L是可分配的，当\forall a,b,c \in L: a \sqcap (b\sqcup c) = (a\sqcap b)\sqcup (a\sqcap c) 一个格L是可分配的，当∀a,b,c∈L:a⊓(b⊔c)=(a⊓b)⊔(a⊓c)
- 可分配格等效于： 当 ∀ a , b , c ∈ L : a ⊔ ( b ⊓ c ) = ( a ⊔ b ) ⊓ ( a ⊔ c ) 当\forall a,b,c \in L: a \sqcup (b\sqcap c) = (a\sqcup b)\sqcap (a\sqcup c) 当∀a,b,c∈L:a⊔(b⊓c)=(a⊔b)⊓(a⊔c)
4. 偏序上的操作
-
不相交和（disjoint sum）:- 给 定 两 个 偏 序 P ， Q ， 它 们 的 不 相 交 和 表 示 为 P + Q ， P + Q 中 ， 任 取 元 素 x ， y ， x ≤ y ， 当 且 仅 当 1. x , y ∈ P 并 且 x ≤ P y 或 者 2. x , y ∈ Q 并 且 x ≤ Q y \begin{aligned} & 给定两个偏序P，Q，它们的不相交和表示为P+Q，P+Q中，任取元素x，y，x \le y，当且仅当 \\ & 1. \ x, y \in P 并且 x \le_P y \ 或者 \\ & 2. \ x, y \in Q 并且 x \le_Q y \end{aligned} 给定两个偏序P，Q，它们的不相交和表示为P+Q，P+Q中，任取元素x，y，x≤y，当且仅当1. x,y∈P并且x≤Py 或者2. x,y∈Q并且x≤Qy
-
偏序的叉积（Cross product of posets）：-
给 定 偏 序 P ， Q ， 它 们 的 叉 积 为 P × Q : ( P × Q , ≤ ) : ( p 1 , q 1 ) ≤ ( p 2 , q 2 ) , 那 么 ( p 1 ≤ P p 2 并 且 q 1 ≤ Q q 2 ) \begin{aligned} & 给定偏序P，Q，它们的叉积为P\times Q: (P\times Q, \le): \\ & (p_1, q_1) \le (p_2, q_2) \ ,那么 \ (\ p_1 \le_P p2 \ \ 并且 \ q1 \le_Q q2 \ ) \end{aligned} 给定偏序P，Q，它们的叉积为P×Q:(P×Q,≤):(p1,q1)≤(p2,q2) ,那么 ( p1≤Pp2 并且 q1≤Qq2 )
-
下图8中三幅图分别表示P，Q，P × \times × Q
0 1 2' 1' 0' 1,2' 1,1' 0,2' 0,1' 1,0' 0,0' 图8
-
-
线性和（Linear sum）- 给 定 两 个 偏 序 P ， Q ， 它 们 的 线 性 和 表 示 为 P ⊕ Q ， P ⊕ Q 中 ， 任 取 元 素 x ， y ， x ≤ y ， 当 且 仅 当 ( x ≤ P y ) 或 者 ( x ≤ Q y ) 或 者 [ x ∈ P 并 且 y ∈ Q ] \begin{aligned} & 给定两个偏序P，Q，它们的线性和表示为P\oplus Q，P\oplus Q中，任取元素x，y，x \le y，当且仅当 \\ & (x \le_P y) 或者 \ (x \le_Q y) \ 或者 \ [ \ x \in P \ 并且 \ y \in Q \ ] \end{aligned} 给定两个偏序P，Q，它们的线性和表示为P⊕Q，P⊕Q中，任取元素x，y，x≤y，当且仅当(x≤Py)或者 (x≤Qy) 或者 [ x∈P 并且 y∈Q ]
-
down-sets（order ideals）：我 们 称 一 个 子 集 Y ⊆ X 为 一 个 d o w n − s e t ， 当 ∀ y , z ∈ X : z ∈ Y 并 且 y ≤ z ⇒ y ∈ Y 我们称一个子集Y\subseteq X为一个down-set，当\forall y,z \in X: z \in Y 并且 y \le z \Rightarrow y \in Y 我们称一个子集Y⊆X为一个down−set，当∀y,z∈X:z∈Y并且y≤z⇒y∈Y- D [ x ] = { y ∈ X ∣ y ≤ x } D[x] = \{ \ y \in X \ | \ y \le x \} D[x]={ y∈X ∣ y≤x} D[x]一般也称之为principal order ideals
-
up-sets（order filters）：我 们 称 自 己 Y ⊆ X 为 一 个 u p s e t ， 当 y ∈ Y 并 且 y ≤ z ⇒ z ∈ Y 我们称自己Y\subseteq X为一个upset，当y\in Y 并且 y \le z \Rightarrow z\in Y 我们称自己Y⊆X为一个upset，当y∈Y并且y≤z⇒z∈Y- U [ x ] = { y ≤ X ∣ x ≤ y } U[x] = \{ \ y \le X \ | \ x \le y \ \} U[x]={ y≤X ∣ x≤y } U[x]一般也称之为principal order filters
引理：
- x ≤ y ⇔ U [ y ] ⊆ U [ x ] x \le y \Leftrightarrow U[y] \subseteq U[x] x≤y⇔U[y]⊆U[x]
- x = s u p Y ⇔ U [ x ] = ⋂ y ∈ Y U [ y ] x = sup \ Y \Leftrightarrow U[x] = \bigcap_{y\in Y}U[y] x=sup Y⇔U[x]=⋂y∈YU[y]
另外：
-
U ( x ) = { y ∈ X ∣ x < y } U(x) = \{ \ y \in X \ | \ x < y \} U(x)={ y∈X ∣ x<y} U(x) 也叫x的upper-holdings
-
D ( x ) = { y ∈ X ∣ y < x } D(x) = \{ \ y \in X \ | \ y < x \} D(x)={ y∈X ∣ y<x} D(x) 也叫x的lower-holdings
-
U [ A ] = { y ∈ X ∣ ∃ x ∈ A : x ≤ y } U[A] = \{ \ y \in X \ | \ \exists x \in A: x \le y \ \} U[A]={ y∈X ∣ ∃x∈A:x≤y }
5. 偏序上的特殊元素
-
底元素（Bottom Element）：元 素 x 是 偏 序 P 的 一 个 b o t t o m e l e m e n t ( 或 者 m i n i m u m e l e m e n t ) ， 当 x ∈ P 并 且 ∀ y ∈ P : x ≤ y 元素x是偏序P的一个bottom \ element(或者minimum \ element)，当x\in P并且 \forall y \in P: x \le y 元素x是偏序P的一个bottom element(或者minimum element)，当x∈P并且∀y∈P:x≤y- ⊥ 表 示 B o t t o m e l e m e n t \bot 表示 Bottom \ element ⊥表示Bottom element
-
顶元素（Top Element）：元 素 x 是 偏 序 P 的 一 个 t o p e l e m e n t ( 或 者 m a x i m u m e l e m e n t ) ， 当 x ∈ P 并 且 ∀ y ∈ P : y ≤ x 元素x是偏序P的一个top \ element(或者maximum \ element)，当x \in P 并且 \forall y \in P: y \le x 元素x是偏序P的一个top element(或者maximum element)，当x∈P并且∀y∈P:y≤x- ⊤ 表 示 T o p e l e m e n t \top表示Top \ element ⊤表示Top element
很显然， ⊤ 和 ⊥ 是 唯 一 的 \top和\bot是唯一的 ⊤和⊥是唯一的
最小元素（minimal element）：$元素x是偏序P的minimal \ element，如果\forall y \in P: y \not < x $最大元素（maximal element）：元 素 x 是 偏 序 P 的 m a x i m a l e l e m e n t ， 如 果 ∀ y ∈ p : y ≯ x 元素x是偏序P的maximal \ element，如果\forall y \in p: y \not > x 元素x是偏序P的maximal element，如果∀y∈p:y>x
6. 其它概念
-
irreducible elements
-
dissector elements
其它概念 TODO 补充
更多推荐
偏序与格理论 基础
发布评论