中文数学 Wiki
Advertisement

在集合论中,序关系(order relation)是描述集合的元素之间“大小”的概念。

集合的序[]

偏序集[]

如果一个非集合上定义的一个二元关系满足

  1. 自反性:
  2. 反对称性:
  3. 传递性:

我们就称这个二元关系为集合上的一个偏序(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)。

性质[]

最大最小元、极大极小元、上下界有如下性质:

  1. 一个偏序集不一定存在最大最小元。
  2. 一个偏序集不一定存在极大极小元,且若存在也不必唯一。
  3. 最大最小元一定是极大极小元,但反之未必。
  4. 所有极大元相同时最大元才会存在,且此时最大元就是极大元。
  5. 极大元不一定比极小元大,极小元不一定比极大元小,它们之间甚至可能无法比较大小。
  6. 子集的上下界未必在此子集中。

Hasse 图[]

在偏序集的元素较少(至多可列)或结构较为单纯的时候,可以使用 Hasse 图反映集合元素之间的偏序关系,集合的每一个元素代表图中的一个节点,若且不存在使得,我们就称覆盖(cover),这样在图中用一条线将连起来,且要求的下方,这样我们在遍历所有两组元素后便得到一个 Hasse 图。

例如下图就是集合在整数之间的整除关系作为偏序关系时的 Hasse 图。

The Hasse graph of S(1to8)

Hasse 图如果节点处只有一上一下两条线连接,这样就形成一个单链,它就是全序集对应的图。

从图中我们可以写出任意两元素之间的序关系,且极大元(若存在)位于每个支链的最顶端,极小元(若存在)位于每个支链的最低端。

运算[]

参见偏序集的运算

Advertisement