序关系：层次结构，用于组织
偏序关系
集合 X X X上自反、反对称和传递的关系称为 X X X上的偏序关系（偏序），又称部分序关系（部分序）。
- 通常用 ≤ \leq ≤表示 x x x和 y y y满足这种偏序关系
偏序集
( X , ≤ ) (X,\leq) (X,≤)
若 ≤ \leq ≤是全序，则上述标记为全序集。
特殊的偏序关系
-
实数集上的小于等于关系 ( X , ≤ ) (X,\leq) (X,≤)、 ( X , ≥ ) (X,\geq) (X,≥)大于等于关系
-
非零自然数的整除关系 ( X , ∣ ) (X,|) (X,∣)
-
包含关系 ( A , ⊆ ) (\mathcal{A},\subseteq) (A,⊆)
例如
A = { a , b } , A 1 = { ∅ , { a } , { b } } , A 2 = { { a } , { a b } } A=\{a,b\},\mathcal{A}_1=\{\empty,\{a\},\{b\}\},\mathcal{A}_2=\{\{a\},\{ab\}\} A={a,b},A1={∅,{a},{b}},A2={{a},{ab}}
则
⊆ 1 = I A 1 ∪ { ( ∅ , { a } ) , ( ∅ , { b } ) } ⊆ 2 = I A 2 ∪ { ( { a } , { a , b } ) } \begin{aligned} \subseteq_1&=I_{\mathcal{A}_1}\cup\{(\empty,\{a\}),(\empty,\{b\})\} \\ \subseteq_2&=I_{\mathcal{A}_2}\cup\{(\{a\},\{a,b\})\} \end{aligned} ⊆1⊆2=IA1∪{(∅,{a}),(∅,{b})}=IA2∪{({a},{a,b})}
一般来说，全关系 E X E_X EX不是 X X X上的偏序关系
相关概念
可比
∀ x , y ∈ X , x 与 y 可 比 ⇔ x ≤ y ∨ y ≤ x \forall x,y\in X,x与y可比\Leftrightarrow x\leq y\vee y\leq x ∀x,y∈X,x与y可比⇔x≤y∨y≤x
严格小于
∀ x , y ∈ X , x < y ⇔ x ≤ y ∨ x ≠ y \forall x,y\in X,x<y\Leftrightarrow x\leq y\vee x\neq y ∀x,y∈X,x<y⇔x≤y∨x=y
覆盖
设 ( X , ≤ ) (X,\leq) (X,≤)为偏序集， ∀ x , y ∈ A \forall x,y\in A ∀x,y∈A，如果 x < y x<y x<y且不存在 z ∈ X z\in X z∈X使得 x < z < y x<z<y x<z<y，则称 y y y覆盖 x x x.
全序关系
若" ≤ \leq ≤"是 X X X上的偏序，且 ∀ x , y ∈ X \forall x,y\in X ∀x,y∈X， x , y x,y x,y可比，则称“ ≤ \leq ≤”为 X X X上的全序关系（全序/线序）。
哈斯图
规定结点 x , y x,y x,y之间有无向边当且仅当 y y y覆盖 x x x，且 y y y位于 x x x的上方。
全序集的哈斯图是一条直线（充要条件）。
偏序关系中的特殊元素
最大/小元
y
y
y是
B
B
B的最大元
∀
x
(
x
∈
B
⇒
x
≤
y
)
\forall x(x\in B\Rightarrow x\leq y)
∀x(x∈B⇒x≤y)
y
y
y是
B
B
B的最小元
∀
x
(
x
∈
B
⇒
y
≤
x
)
\forall x(x\in B\Rightarrow y\leq x)
∀x(x∈B⇒y≤x)
极大/小元
y
y
y是
B
B
B的极大元
∀
x
(
x
∈
B
∧
y
≤
x
⇒
x
=
y
)
\forall x(x\in B\wedge y\leq x\Rightarrow x=y)
∀x(x∈B∧y≤x⇒x=y)
y
y
y是
B
B
B的极小元
∀
x
(
x
∈
B
∧
x
≤
y
⇒
x
=
y
)
\forall x(x\in B\wedge x\leq y\Rightarrow x=y)
∀x(x∈B∧x≤y⇒x=y)
也就是说，对于极大（小）元来说，不存在比它更大（小）的元素，但允许存在与它不可比的元素。