离散数学——全序/偏序关系及应用

偏序关系和全序关系是公理集合论中的二元关系
偏序集合：配备偏序关系集合
全序集合：配备全序关系集合

偏序：集合内只有部分元素之间在这个关系下是可以比较的
比如复数集中不是所有的数都能比较大小，所以大小是复数集的偏序关系~

全序:在这种关系下，任何一对元素都是相互比较的
例如，有限长度的序列是按字典序列的~（最常见的是字典中的单词）

偏序定义：
如果R满足，设置R是集合A上的二元关系：
Ⅰ 自反:任意x∈A，有xRx；
Ⅱ 反对称(即反对称):对任意x,y∈A，若xRy，且yRx，则x=y；
Ⅲ 传递:任意x, y,z∈A，若xRy，且yRz，则xRz。
则称R为A偏序关系。

全序定义：
如果我们使用这种关系，集合X上有一个全序的关系 ≤ 对于表达，以下陈述 X 中的所有 a, b 和 c 成立：
如果 a ≤ b 且 b ≤ a 则 a = b (反对称)
如果 a ≤ b 且 b ≤ c 则 a ≤ c (传递性)
a ≤ b 或 b ≤ a (完全性)

注：完全性本身也包括自反性
因此，全序关系必须是偏序关系