【离散数学】偏序关系，全序关系，良序关系，哈斯图，格

偏序关系

定义

一个关系具有自反，反对称，传递的特性，就叫做偏序关系。一个集合S和一个偏序关系<并称为偏序集，写作（S,<）。例如大于等于符号就是一个偏序关系。

可比性

两个元素具有偏序关系，要么a<b,要么b<a，则称为a和b可比。否则称为不可比。例如（Z+,|）中，2不能整除5，2和5就是不可比的。

全序关系

定义

若一个偏序关系中，每个元素都是可比的，则称为全序关系。例如小于等于就是全序关系，因为每一个元素都有大小关系。

良序关系

定义

若一个全序关系中，存在一个最小元，则称为良序关系。例如小于等于关系在整数集中不是良序关系，因为没有最小元，而在正整数集中是良序关系，因为存在最小元1。

良序关系归纳定理

若（S,<）是一个良序集，P(x)为S的元素x的一个命题，求证如果对于所有y<x，P(y)为真的假定下能得到P(x)为真，则对于所有x属于S，P(x)为真。

证明：

假定成立的情况下，假设存在x使P(x)为假，则将所有为假的x划为一个集合，因为<为良序关系，则集合中一定存在最小元x0,则对于所有a<x0的a,P(a)为真，又因为假定，P(x0)必须为真，与P(x0)为假矛盾，所以对于所有x属于S，P(x)为真。

注释：

良序归纳法不需要基础步骤，是一种特殊的数学归纳法。即便x0为整个良序集的最小元，根据假定，对于所有属于S的x，因为x0<x，所以P(x)都为真。或者说不存在x属于S并且x<x0，使用空证明得出所有x<x0,P(x)为真。

哈斯图

在偏序关系的有向图中，可以省略去一些没必要画出来的边，自反的边可以删除，因为每一个元素必须有自反关系，因为传递性而产生的边可以删除，因为这些边必须存在。我们只需要画出一些完全由关系的要求而产生的边（不能是传递性产生的边），也就是覆盖关系。

覆盖关系

（S,<）是一个偏序关系，若存在x<y，其中不存在z使得x<z<y，则称y覆盖x。所有满足y覆盖x的有序对组成的集合称为（S,<）的覆盖关系。哈斯图表示的就是（S,<）覆盖关系，从下到上，低层的元素和高层的元素假如有边，则那个低层的元素为<左边（可以叫做小于）的元素，高层的元素为<右边（可以叫做大于）的元素，每一层元素都是不可比的。如图

最大元和最小元

最大元：在偏序集中，存在一个元素大于其它所有元素，即与所有元素有关系且都在关系右边（唯一）

最小元：在偏序集中，存在一个元素小于其它所有元素，即与所有元素有关系且都在关系左边（唯一）

极大元：在偏序集中，没有大于它的元素，可以有多个

极小元：在偏序集中，没有小于它的元素，可以有多个

例：

此偏序集有最小元1，没有最大元，有极大元8和12，有极小元1

格

如果一个偏序集的任意两个元素都有共同的最小上界和最大下界，则这个偏序关系称为偏序集。

最小上界：所有大于a的元素叫上界，所有上界中最小的上界就叫最小上界

最大下界：所有小于a的元素叫下界，所有下界中最大的下界就叫最大下界

如图，这个偏序关系并不是格，因为元素b,c都有上界d,e,f，但是d和e使不可比的，所以得不出哪个是最小上界，所以没有最小上界。