偏序与全序关系

欢迎大家来到IT世界,在知识的湖畔探索吧!

1. 集合上的关系：

假设A是一个集合 {1,2,3} ；R是集合A上的关系，例如{<1,1>,<2,2>,< 3,3>,<1,2>,<1,3>,<2,3>}

自反性：任取一个A中的元素x，如果都有<x,x>在R中，那么R是自反的。

对称性：任取两个A中的元素x,y，如果<x,y> 在关系R上,那么<y,x> 也在关系R上，那么R是对称的。

反对称性：任取两个A中元素x,y(x!=y)，如果<x,y> 在关系R上,那么<y,x> 不在关系R上，那么R是反对称的。

传递性：任取三个A中元素x,y,z，如果<x,y>,<y,z> 在关系R上，那么 <x,z> 也在关系R上，那么R是传递的。

2. 偏序： 设R是非空集合A上的关系，如果R是自反的，反对称的，和传递的，则称R是A上的偏序关系。

偏序的定义：设R是集合A上的一个二元关系，若R满足：

Ⅰ 自反性：对任意x∈A，有xRx；

Ⅱ 反对称性（即反对称关系）：对任意x,y∈A，若xRy，且yRx，则x=y；

Ⅲ 传递性：对任意x, y,z∈A，若xRy，且yRz，则xRz。 则称R为A上的偏序关系。

3. 全序： 如果R是A上的偏序关系，那么对于任意的A集合上的 x,y，都有 x <= y，或者 y <= x，二者必居其一，那么则称R是A上的全序关系。

全序的定义：设集合X上有一全序关系，如果我们把这种关系用 ≤ 表述，则下列陈述对于 X 中的所有 a, b 和 c 成立：

如果 a ≤ b 且 b ≤ a 则 a = b (反对称性)

如果 a ≤ b 且 b ≤ c 则 a ≤ c (传递性)

a ≤ b 或 b ≤ a (完全性)

注意：完全性本身也包括了自反性。 所以，全序关系必是偏序关系。

全序关系‌指集合内任何一对元素在这个关系下都是相互可比较的。例如，有限长度的序列按字典序是全序的，最常见的是单词在字典中是全序的。全序关系满足反对称性、传递性和完全性，其中完全性条件蕴涵了自反性，即任何两个元素都可以比较大小。因此，全序关系是偏序关系的一种特殊形式，即满足“完全性”条件的偏序。

简而言之，偏序关系允许集合中的元素部分可比，而全序关系则要求集合中的任何两个元素都是可比的。全序关系可以视为一种特殊类型的偏序关系，其中所有元素都可以相互比较‌。

例如：

上图是偏序关系，其中S1和S2之间是无法比较的；

上图是全序关系，图中的任何两个元素都是可比较的。