Home 数学 集合论

# 偏序

定义
设 XX 为集合，RR 为 XX 上的二元关系。
称 RR 为 XX 上的 偏序关系 (Partial Order)「順序関係」，当且仅当满足以下条件：

  • (R) 自反性 (Reflexivity)「反射律」：对任意 a∈Xa \in X，有 aRaaRa
  • (A) 反对称性 (Antisymmetry)「反対称律」：对任意 a,b∈Xa, b \in X，若 aRbaRb 且 bRabRa，则 a=ba = b
  • (T) 传递性 (Transitivity)「推移律」：对任意 a,b,c∈Xa, b, c \in X，若 aRbaRb 且 bRcbRc，则 aRcaRc
  • 一般地，若二元关系 RR 为偏序关系，则将 aRbaRb 记作 a⪯ba \preceq b，称为 aa 小于等于 bb
  • 并记 x⪯yx \preceq y 且 x≠yx \neq y 为 x≺yx \prec y
  • 对称地，存在关系 a⪰ba \succeq b 和 a≻ba \succ b，并且 a⪰b⟺b⪯aa \succeq b \iff b \preceq a

类似于等价关系，偏序关系是对小于等于号之类的推广

示例

  • 一般的相等关系 == 为偏序关系
  • 实数上的通常大小关系 ≤\leq 为偏序关系
  • 任取集合 YY，定义在 X=P(Y)X = \mathcal{P}(Y) 上的二元关系 ⊆\subseteq，则 ⊆\subseteq 为 XX 上的偏序关系。这是包含关系
  • 倍数关系：x,y∈N,x⪯y⟺yx∈Nx,y \in \mathbb N,\ x \preceq y \iff \dfrac{y}{x} \in \mathbb N，则 ⪯\preceq 为 N\mathbb N 上的偏序关系
  • 复数域上的模大小关系 zRw⟺∣z∣≤∣w∣zRw \iff |z| \leq |w| 不构成偏序关系，实际上因为 ∣1∣=∣i∣|1| = |i|，但 1≠i1 \neq i，所以不满足反对称性
  • 取 XX 上的偏序关系 ⪯\preceq 和子集 S⊆XS \subseteq X，则在 SS 上定义的二元关系 ⪯S\preceq_S 如下

a⪯Sb⟺a⪯b,a,b∈Sa \preceq_S b \iff a \preceq b, \quad a, b \in S

则 ⪯S\preceq_S 为 SS 上的偏序关系，称为 ⪯\preceq 在 SS 上的 限制 (Restriction)「制限」

集合与其偏序关系的组合 (X,⪯)(X, \preceq) 称为 偏序集 (Partially Ordered Set, Poset)「順序集合」。

# 全序

偏序关系如同字面意思，实际上是一个单向的蕴含链，一般来说即使 x⪯yx \preceq y 不成立，也不能说明 y⪯xy \preceq x 成立
例如在集合包含关系中，A⊈BA \not\subseteq B 并不意味着 B⊆AB \subseteq A 成立，因为二者可能只有一部分相交

称 xx 与 yy 可比较 (Comparable)「可比較」，当且仅当 x⪯yx \preceq y 或 y⪯xy \preceq x 成立

定义
令 XX 为集合，⪯\preceq 为 XX 上的偏序关系。称 ⪯\preceq 为集合 XX 上的 全序关系 (Total Order)「全順序関係」，当且仅当对任意 x,y∈Xx, y \in X，xx 与 yy 可比较。

  • 在全序关系下，x≺y,x≻yx \prec y, x \succ y 与 x=yx = y 三者必有且仅有一成立

示例

  • 实数上的通常大小关系 ≤\leq 为全序关系
  • 字典序关系：令 XX 为任意集合，定义在 XnX^n 上的二元关系 ≤\leq 如下

(x1,x2,…,xn)≤(y1,y2,…,yn)⟺∃k∈{1,2,…,n},s.t.x1=y1,x2=y2,…,xk−1=yk−1,xk⪯yk(x_1, x_2, \ldots, x_n) \le (y_1, y_2, \ldots, y_n) \iff {}^\exists k \in \{1, 2, \ldots, n\}, \text{ s.t. } x_1 = y_1, x_2 = y_2, \ldots, x_{k-1} = y_{k-1}, x_k \preceq y_k

则 ≤\leq 为 XnX^n 上的全序关系

  • 若 ⪯\preceq 为集合 XX 的全序关系，那么限制 ⪯S\preceq_S 也是子集 S⊆XS \subseteq X 上的全序关系

集合与其全序关系的组合 (X,⪯)(X, \preceq) 称为 全序集 (Totally Ordered Set, Totally Poset)「全順序集合」。

# 序同构

定义
令 (X,⪯X),(Y,⪯Y)(X, \preceq_X), (Y, \preceq_Y) 为偏序集。映射 f:X→Yf: X \to Y

  • 称 ff 为 保序 (Order-Preserving)「順序を保つ」，当且仅当对任意 a,b∈Xa, b \in X

a⪯Xb⟹f(a)⪯Yf(b)a \preceq_X b \implies f(a) \preceq_Y f(b)

  • 称 ff 为 反序 (Order-Reversing)「順序を逆にする」，当且仅当对任意 a,b∈Xa, b \in X

a⪯Xb⟹f(b)⪰Yf(a)a \preceq_X b \implies f(b) \succeq_Y f(a)

称 ff 为 序同构 (Order Isomorphism)「順序同型」，当且仅当 ff 为双射且 f,f−1f,f^{-1} 均为保序映射。
此时称 偏序集 (X,⪯X)(X, \preceq_X) 与 (Y,⪯Y)(Y, \preceq_Y) 序同构。记作 (X,⪯X)≅(Y,⪯Y)(X, \preceq_X) \cong (Y, \preceq_Y)。

  • 容易验证 ≅\cong 成为等价关系

命题
令 (X,⪯X),(Y,⪯Y),(Z,⪯Z)(X, \preceq_X), (Y, \preceq_Y), (Z, \preceq_Z) 为偏序集，映射 f:X→Y,g:Y→Zf: X \to Y, g: Y \to Z。

  1. 若 f,gf, g 均为保序映射，则复合映射 g∘f:X→Zg \circ f: X \to Z 亦为保序映射
  2. 若 f,gf, g 均为序同构映射，则复合映射 g∘f:X→Zg \circ f: X \to Z 亦为序同构映射
证明

(1)
任取 x1,x2∈Xx_1, x_2 \in X，使得 x1⪯Xx2x_1 \preceq_X x_2。由于 ff 保序，所以

f(x1)⪯Yf(x2)f(x_1) \preceq_Y f(x_2)

由于 gg 保序，所以

g(f(x1))⪯Zg(f(x2))g(f(x_1)) \preceq_Z g(f(x_2))

因此 g∘fg \circ f 保序。

(2)
由于 f,gf, g 均为双射，所以 g∘fg \circ f 亦为双射。且

(g∘f)−1=f−1∘g−1(g \circ f)^{-1} = f^{-1} \circ g^{-1}

根据条件，f−1,g−1f^{-1}, g^{-1} 均为保序映射，根据 (1) 可知 f−1∘g−1f^{-1} \circ g^{-1} 保序，因此 (g∘f)−1(g \circ f)^{-1} 保序。
□\square

命题
令 (X,⪯X),(Y,⪯Y)(X, \preceq_X), (Y, \preceq_Y) 为偏序集，且 (X,⪯X)≅(Y,⪯Y)(X, \preceq_X) \cong (Y, \preceq_Y)
如果 (X,⪯X)(X, \preceq_X) 为全序集，则 (Y,⪯Y)(Y, \preceq_Y) 亦为全序集

证明

取 f:X→Yf:X \to Y 为序同构，取 y1,y2∈Yy_1, y_2 \in Y
由于 XX 是全序的，所以

f−1(y1)⪯Xf−1(y2)orf−1(y2)⪯Xf−1(y1)f^{-1}(y_1) \preceq_X f^{-1}(y_2) \text{ or } f^{-1}(y_2) \preceq_X f^{-1}(y_1)

由于 f−1f^{-1} 保序，所以

y1⪯Yy2ory2⪯Yy1y_1 \preceq_Y y_2 \text{ or } y_2 \preceq_Y y_1

因此 YY 亦为全序集。
□\square

# 偏序链

基于抽象化后的大小比较关系，可以找到一系列较大或者较小的元。
但是注意：偏序集上并非是所有的元都可以比较，例如

X=P({1,2,3})X = \mathcal{P}(\{1, 2, 3\})

上定义包含关系 ⊆\subseteq，则 A={1},B={2}A = \{1\}, B = \{2\} 之间不可比较，实际上可以做比较的链路一共有

∅⊆{1}⊆{1,2}⊆{1,2,3}∅⊆{1}⊆{1,3}⊆{1,2,3}∅⊆{2}⊆{1,2}⊆{1,2,3}∅⊆{2}⊆{2,3}⊆{1,2,3}∅⊆{3}⊆{1,3}⊆{1,2,3}∅⊆{3}⊆{2,3}⊆{1,2,3}\begin{aligned} &\emptyset \subseteq \{1\} \subseteq \{1, 2\} \subseteq \{1, 2, 3\} \\ &\emptyset \subseteq \{1\} \subseteq \{1, 3\} \subseteq \{1, 2, 3\} \\ &\emptyset \subseteq \{2\} \subseteq \{1, 2\} \subseteq \{1, 2, 3\} \\ &\emptyset \subseteq \{2\} \subseteq \{2, 3\} \subseteq \{1, 2, 3\} \\ &\emptyset \subseteq \{3\} \subseteq \{1, 3\} \subseteq \{1, 2, 3\} \\ &\emptyset \subseteq \{3\} \subseteq \{2, 3\} \subseteq \{1, 2, 3\} \end{aligned}

在这个例子中，很直观的是不管在哪个比较链路，空集都是最小的，而全集都是最大的
并且，如果同时考虑 {1}\{1\} 和 {2}\{2\}，则可以看出 {1,2}\{1, 2\} 同时大于它们，但是却无法与 {3}\{3\} 比较

这样的概念进行抽象化之后，可以得到如下定义

定义
令 (X,⪯)(X, \preceq) 为偏序集，S⊆XS \subseteq X。取 x∈Xx \in X

  • 称 xx 为 SS 的 上界 (Upper Bound)「上界」，当且仅当对任意 s∈Ss \in S，有 s⪯xs \preceq x
  • 称 xx 为 SS 的 下界 (Lower Bound)「下界」，当且仅当对任意 s∈Ss \in S，有 x⪯sx \preceq s
  • 若 SS 同时拥有上界与下界，则称 SS 为 有界 (Bounded)「有界」 集合

如果这样一个覆盖整个集合的元可以在集合内部取到，那么毫无疑问它将是集合内最大或者最小的元

定义
令 (X,⪯)(X, \preceq) 为偏序集，S⊆XS \subseteq X。取 x∈Xx \in X

  • 称 xx 为 SS 的 最大元 (Greatest Element)「最大元」，当且仅当 xx 为 SS 的上界，且 x∈Sx \in S，记为 x=max⁡Sx = \max S
  • 称 xx 为 SS 的 最小元 (Least Element)「最小元」，当且仅当 xx 为 SS 的下界，且 x∈Sx \in S，记为 x=min⁡Sx = \min S

最大元和最小元实际上可以通过另一种方式获取

定义
令 (X,⪯)(X, \preceq) 为偏序集，S⊆XS \subseteq X

  • 若 SS 的上界全体拥有最小元，则称其为 SS 的 上确界 (Supremum)「上限」，记为 sup⁡S\sup S
  • 若 SS 的下界全体拥有最大元，则称其为 SS 的 下确界 (Infimum)「下限」，记为 inf⁡S\inf S

这里不做证明，但是事实上，上下确界的存在性可以保证

定理 Weierstrass 定理

  • 若 SS 有上界，则 SS 存在上确界
  • 若 SS 有下界，则 SS 存在下确界

命题

  1. 若 SS 存在最大元 max⁡S\max S，则 max⁡S=sup⁡S\max S = \sup S
  2. 若 SS 存在最小元 min⁡S\min S，则 min⁡S=inf⁡S\min S = \inf S
证明

(1)
设 s=max⁡Ss = \max S，则 ss 为 SS 的上界。
任取 SS 的任意上界 uu，则有 s⪯us \preceq u，因此 ss 为 SS 的上界全体的最小元，即 sup⁡S=s\sup S = s。

(2)
设 s=min⁡Ss = \min S，则 ss 为 SS 的下界。
任取 SS 的任意下界 ll，则有 l⪯sl \preceq s，因此 ss 为 SS 的下界全体的最大元，即 inf⁡S=s\inf S = s。
□\square

示例
设 X=P({1,2,3,4})X = \mathcal{P}(\{1, 2, 3, 4\})，在 XX 上定义包含关系 ⊆\subseteq。取子集

S={{1,2},{1,3},{1,2,3}}S = \{\{1, 2\}, \{1, 3\}, \{1, 2, 3\}\}

  • SS 的上界为 {1,2,3},{1,2,3,4}\{1, 2, 3\}, \{1, 2, 3, 4\}，其中最大元为 \
  • SS 的下界为 ∅,{1}\emptyset, \{1\}，二者都不在 SS 中，因此 SS 不存在最小元
  • SS 的上确界为 \
  • SS 的下确界为 \

如上述示例，最大元与最小元的存在性并非能时刻得到保证，这时需要一个能稳定分析偏序链的端点定义

定义
令 (X,⪯)(X, \preceq) 为偏序集，S⊆XS \subseteq X。取 s∈Ss \in S

  • 称 ss 为 SS 的 极大元 (Maximal Element)「極大元」，当且仅当 ∀t∈S,s⪯t⟹s=t{}^\forall t \in S,\ s \preceq t \implies s = t
  • 称 ss 为 SS 的 极小元 (Minimal Element)「極小元」，当且仅当 ∀t∈S,t⪯s⟹s=t{}^\forall t \in S,\ t \preceq s \implies s = t
  • 注意这里定义的不同，取的元本身就是 SS 内的元

极大元的定义决定了它是一定存在的。并且实际上极大元就是各个偏序链的 “顶点”

命题

  1. 若 SS 存在最大元 max⁡S\max S，则 max⁡S\max S 为 SS 的唯一极大元
  2. 若 SS 存在最小元 min⁡S\min S，则 min⁡S\min S 为 SS 的唯一极小元
证明

(1)
由定义 max⁡S∈S\max S \in S
任取 t∈St \in S，使得 max⁡S⪯t\max S \preceq t，最大性可以得到 max⁡S⪯t\max S \preceq t，因此 max⁡S=t\max S = t，所以 max⁡S\max S 为极大元。
若 mm 亦为 SS 的极大元，则由最大性可以得到 m⪯max⁡Sm \preceq \max S，由极大性可知 m=max⁡Sm = \max S，所以 max⁡S\max S 为唯一极大元。

(2)
由定义 min⁡S∈S\min S \in S
任取 t∈St \in S，使得 t⪯min⁡St \preceq \min S，最小性可以得到 t⪯min⁡St \preceq \min S，因此 t=min⁡St = \min S，所以 min⁡S\min S 为极小元。
若 mm 亦为 SS 的极小元，则由最小性可以得到 min⁡S⪯m\min S \preceq m，由极小性可知 m=min⁡Sm = \min S，所以 min⁡S\min S 为唯一极小元。
□\square

实际上正如刚刚所说：极大极小元是各自偏序链上的端点
对于全序集合来说，只存在一条偏序链，因为所有的元都可比较
因此，全序集合上极大极小元与最大最小元是等价的
事实上可以将全序集的要求稍微放宽一些

  • 对于 SS 的极大元 ss，若其与任意其他元均可比较，则 ss 必为 SS 的最大元
  • 对于 SS 的极小元 ss，若其与任意其他元均可比较，则 ss 必为 SS 的最小元

这允许一些非极大的元出现在单独地偏序链上

显然这些概念都会被保序映射维持
令 (X,⪯X),(Y,⪯Y)(X, \preceq_X), (Y, \preceq_Y) 为偏序集，映射 f:X→Yf: X \to Y 为序同构，子集 S⊆XS \subseteq X，对于 x∈Xx \in X

  • 若 xx 为 SS 的上界，则 f(x)f(x) 为 f(S)f(S) 的上界
  • 若 xx 为 SS 的下界，则 f(x)f(x) 为 f(S)f(S) 的下界
  • 若 xx 为 SS 的下确界，则 f(x)f(x) 为 f(S)f(S) 的下确界
  • 若 xx 为 SS 的上确界，则 f(x)f(x) 为 f(S)f(S) 的上确界
  • 若 xx 为 SS 的最大元，则 f(x)f(x) 为 f(S)f(S) 的最大元
  • 若 xx 为 SS 的最小元，则 f(x)f(x) 为 f(S)f(S) 的最小元
  • 若 xx 为 SS 的极大元，则 f(x)f(x) 为 f(S)f(S) 的极大元
  • 若 xx 为 SS 的极小元，则 f(x)f(x) 为 f(S)f(S) 的极小元