偏序关系

偏序关系（partial order）描述“谁在谁之下”，但不要求任意两个对象都能比较。在集合 $A$ 上，关系 $⪯$ 必须自反、反对称、传递。反对称不是“不能双向成立”：若 $a⪯b$ 与 $b⪯a$ 同时成立，反对称要求 $a=b$。

整除给出的偏序

在正整数集合上令 $a⪯b$ 表示 $a\mid b$。每个数整除自己；若正整数 $a\mid b$ 且 $b\mid a$，便有 $a=b$；整除也能沿两步传递。因此这是偏序。数 2 与 3 却不可比：$2\nmid 3$，$3\nmid 2$。这正是“偏”字的含义。

集合包含是另一例：对固定全集的子集，以 $\subseteq$ 排序，$\{1\}$ 和 $\{2\}$ 不可比。若每一对元素都可比，偏序才称为全序；通常的实数大小关系 $\le$ 是全序。

极大元素与最大元素

在 $S=\{2,3,6,10\}$ 的整除偏序中，6 和 10 都没有严格大于自己的 $S$ 中元素，所以都是极大元素。但没有最大元素，因为 6 不整除 10，10 也不整除 6。最大元素若存在，必须位于每个元素之上；极大元素只要求没有更大的可比对象。这一区别在优化的可行方案排序里同样重要。

参考资料

• MIT，Mathematics for Computer Science，Relations and Partial Orders。
• MIT 6.042J Fall 2010，Mathematics for Computer Science 课程讲义。
• 继续阅读：等价关系、整数整除、优化。