偏序关系和全序关系

一、关系 (relation)

https://www.youtube.com/watch?v=FI6j5QZNVx0&list=PLDDGPdw7e6Ag1EIznZ-m-qXu4XX3A0cIz&index=48

https://web.stanford.edu/class/archive/cs/cs103/cs103.1132/lectures/06/Slides06.pdf

1. 关系(relation)

集合A和集合B之间的关系R是A和B的笛卡尔积的一个子集。

# 例子

假设集合为$Z$Z（整数集合），集合$Z$Z上的关系为$G$G，$xGy$xGy表示x比y大。

那么$(1, 2)\notin G$(1,2)∈/​G，而$(2, 1)\in G$(2,1)∈G。

2. 描述关系的一些性质

下属性质用来描述关系，不是所有的关系都会满足下述性质

a. 反身性 (reflexive)

举个例子，对于整数集$Z$Z，规定关系$R$R为相等关系，也就是对于$a, b \in Z$a,b∈Z，若$a = b$a=b，则$(a,b) \in R$(a,b)∈R；若$a\neq b$a​=b，$(a,b) \notin R$(a,b)∈/​R。

对于上述关系$R$R，满足反身性。因为对于集合$Z$Z中任意一个元素$z$z，均有$(z, z) \in R$(z,z)∈R，即$zRz$zRz。

b. 对称性 (symmetric)

举个例子，对于整数集$Z$Z，规定关系$R$R为不等关系，也就是对于$a, b \in Z$a,b∈Z，若$a \neq b$a​=b，则$(a,b) \in R$(a,b)∈R；若$a = b$a=b，则$(a,b) \notin R$(a,b)∈/​R。

对于上述关系$R$R，满足对称性。因为对于集合$Z$Z中任意两个不等元素$a, b, a \neq b$a,b,a​=b，均有$b \neq a$b​=a。即$(a, b) \in R$(a,b)∈R且$(b, a) \in R$(b,a)∈R

c. 传递性 (transitive)

例子：小于关系

d. 反对称性 (Antisymmetric)

定义：集合$A$A上有关系$R$R，对于$a,b \in A$a,b∈A，如果$aRb$aRb且$bRa$bRa，则$a=b$a=b

---

例子：

• 小于等于关系
• 子集关系

e. total性质

二、偏序 (Partial Order)

• https://www.youtube.com/watch?v=R36F8CWAi2k&list=PLDDGPdw7e6Ag1EIznZ-m-qXu4XX3A0cIz&index=50&pbjreload=10
• https://en.wikipedia.org/wiki/Partially_ordered_set#Strict_and_non-strict_partial_orders

1. 非严格的偏序关系(non-strict partial order)

集合$A$A上的关系$R$R如果满足：

• 反对称性
  • 对于$\forall a, b \in A$∀a,b∈A，若$aRb$aRb且$bRa$bRa，则$a=b$a=b
• 反身性
  • 对于$\forall a\in A$∀a∈A，有$aRa$aRa
• 传递性
  • 对于$\forall a,b,c \in A$∀a,b,c∈A，若$aRb, bRc$aRb,bRc，则$aRc$aRc

则称关系$R$R为集合$A$A上的一个***(非严格的)偏序关系***，记做$\preceq$⪯。

# 非严格偏序的例子

小于等于关系

2. 严格的偏序关系 (strict partial order)

集合$A$A上的关系$R$R如果满足：

• 非对称性 (Asymmetry)：非对称性，not反对称性
  • 对于$\forall a, b \in A$∀a,b∈A，若$aRb$aRb，则不可能有$b R a$bRa
• 非反身性
  • 对于$\forall a\in A$∀a∈A，$(a, a) \notin R$(a,a)∈/​R
• 传递性
  • 对于$\forall a,b,c \in A$∀a,b,c∈A，若$aRb, bRc$aRb,bRc，则$aRc$aRc

则称关系$R$R为集合$A$A上的一个***(严格的)偏序关系***，记做$\preceq$⪯。

# 严格偏序的例子

(1) 编程语言中的happen-before。

• 对于任意两个操作A和B，若A happen before B，则不可能有B happen before A
• 对于任意三个操作A、B、C，若A happen before B且B happen before C，则A happen before C
• 对于任意一个操作A，不可能有A happen before A

(2) 字母表的顺序

三、全序(Total Order)

https://www.cs.odu.edu/~toida/nerzic/content/relation/order/order.html

1. 全序关系的定义

集合$A$A上的关系$R$R如果满足：

• $R$R是偏序关系(反对称性、反身性、传递性)，可以是严格的也可以是非严格的
• $R$R满足total性质
  • 即$\forall a, b\in A$∀a,b∈A，有$aRb$aRb或$bRa$bRa （它们二者有可能同时成立，此时根据反对称性，说明$a=b$a=b）

则称关系$R$R为集合$A$A上的一个全序关系，记做$\prec$≺。

2. 全序关系的例子

• 小于等于关系

四、偏序和全序的关系

偏序关系是全序关系的子集，某集合上的一个全序关系一定是该集合上的偏序关系。

全序关系相比偏序关系多出来一条要求——total。

这条要求是什么意思，举个例子，假设集合$Set$Set是26个英文字母的集合，关系$R$R是先后关系，$(l1, l2) \in R$(l1,l2)∈R表示字母表中字母$l1$l1排在$l2$l2的前面。可以验证，关系$R$R是全序关系。全序关系的total特性确保了对于Set中✅任意两个元素，都满足关系$R$R，即$\forall a,b \in Set$∀a,b∈Set(a和b可能相等)，都满足关系$R$R（要么$aRb$aRb, 要么$b R a$bRa）。

---

而考虑下面的例子：$Z_+$Z+​为正整数集合，$R$R为$Z_+$Z+​上的整除关系，显然$R$R是一个非严格的偏序关系，而不是全序关系，因为不是任意两个元素都有整除关系的。