设R是非空集合A上的一个二元关系,若R满足:
自反性:forall x in A,~~(x, x) in R
反对称性:forall x, y in A,~~((x, y) in R wedge (y, x) in R)~~ implies ~~ x = y
传递性:forall x, y, z in A, Mao((x, y) in R wedge (y, z) in R)~~implies~~(x, z) in R
则称R为A上的偏序关系,通常记作leq。
注意这里的leq并不是一般意义上的“小于等于”,而是表示在偏序关系中的顺序性。x leq y的含义是:依照这个序,x排在y前面或x就是y。根据不同的偏序关系的定义,对序有着不同的解释。例如整除关系是一个定义在整数集合上的一个偏序关系leq,3 leq 6的含义是3整除6。大于或等于也是定义在整数集合上的一个偏序关系,针对这个关系写5 leq 4是指在大于或等于关系中,5排在4的前面。
对于上述提到的自反性和传递性的举例解释:
集合A{a,b,c...}上的关系R是自反 指的是R有(a,a),(b,b),(c,c)...
R是传递指若有(a,b)和(b,c), 则必有(a,c).