在集合论中,序关系(order relation)是描述集合的元素之间“大小”的概念。
集合的序[]
偏序集[]
如果一个非空集合
上定义的一个二元关系
满足
- 自反性:

- 反对称性:

- 传递性:

我们就称这个二元关系
为集合
上的一个偏序(partial ordering),集合
称为偏序集(partially ordered set, poset),记作
偏序集的非空子集依然是偏序集。
良序集[]
在偏序关系的基础上,我们进一步引入全序关系的概念:
设有一偏序集
,如果对集合
的任意有限非空子集
都有关于偏序
的最小元素,即

我们就称偏序

是
全序(total ordering),

是一个
全序集(totally ordered set)或
链(chain)。上述定义等价于

,总有

或

一者成立(集合

的任意两个元素之间可以比较大小)。
如果将全序集中关于“集合
的任意有限非空子集
”改为“集合
的任意非空子集
”,结论依然成立的集合
称为一个良序集(well ordered set, woset),此时
为集合
上的一个良序(well ordering)。
元素的大小[]
相关概念[]
在偏序集
中,
,如果
,我们就说
比
大,同时也说
比
小,也记
,如果还有
,我们称上述关系是严格的,并记
设有一个偏序集
,若存在
,对任意
,都有
,我们称
是偏序集
的最小元(minimal element);同理,若存在
,对任意
,都有
,我们称
是偏序集
的最大元(maximal element)。
设有一个偏序集
,若存在
,如果
能推出
,我们称
是偏序集
的一个极大元(maximum element);如果
能推出
,我们称
是偏序集
的一个极小元(minimum element)。
设在偏序集
中
是
的一个子集,
,若对任意
均有
,就称
是
的一个上界(upper bound);同理,
,若对任意
均有
,就称
是
的一个下界(lower bound)。
性质[]
最大最小元、极大极小元、上下界有如下性质:
- 一个偏序集不一定存在最大最小元。
- 一个偏序集不一定存在极大极小元,且若存在也不必唯一。
- 最大最小元一定是极大极小元,但反之未必。
- 所有极大元相同时最大元才会存在,且此时最大元就是极大元。
- 极大元不一定比极小元大,极小元不一定比极大元小,它们之间甚至可能无法比较大小。
- 子集的上下界未必在此子集中。
Hasse 图[]
在偏序集的元素较少(至多可列)或结构较为单纯的时候,可以使用 Hasse 图反映集合
元素之间的偏序关系,集合
的每一个元素代表图中的一个节点,若
且不存在
使得
,我们就称
覆盖(cover)
,这样在图中用一条线将
和
连起来,且要求
在
的下方,这样我们在遍历所有两组元素后便得到一个 Hasse 图。
例如下图就是集合
在整数之间的整除关系作为偏序关系时的 Hasse 图。
Hasse 图如果节点处只有一上一下两条线连接,这样就形成一个单链,它就是全序集对应的图。
从图中我们可以写出任意两元素之间的序关系,且极大元(若存在)位于每个支链的最顶端,极小元(若存在)位于每个支链的最低端。
运算[]
参见偏序集的运算。