Skip to content

Order theory

排序问题是计算机科学中的一类典型问题, 有很多的问题最终都可以转换为排序问题,比如(TODO 增加一些例子,如循环依赖图),本章将研究排序的理论:order theory进行总结,经过本章,我们将对order有一个更加科学的认识。

Order theory非常重要,它对于实现computation非常重要,正如在Relation-structure-computation\Make-it-computational章节所总结的:

只有**有序**才能够实现computation,才能够实现可靠性

wikipedia Order theory

笔记

通过维基百科Order theory,我们可以看到,Order theory是建立在binary relation之上的,它所研究的是**同一**集合中的元素之间的关系。Order theory将“排序”的概念进行了拓广,它告诉我们集合中的元素按照怎样的关系来进行组织,则它们是可以进行“排序”的,下面的Binary relations 章节对此进行了总结。

后面章节中,我们将依据这个理论,建立起非常多的概念,这些概念有一些是我们平时所熟知的,但是从order theory的,我们将会获得新的认知。

Binary relations

下面是维基百科Binary relations中所总结的一些binary relation,我们重点关注的是order。

Symmetric Antisymmetric Connex Well-founded Has joins Has meets
Equivalence relation
Preorder (Quasiorder)
Partial order
Total preorder
Total order
Prewellordering
Well-quasi-ordering
Well-ordering
Lattice
Join-semilattice
Meet-semilattice

A "✓" indicates that the column property is required in the row definition. For example, the definition of an equivalence relation requires it to be symmetric. All definitions tacitly require transitivity and reflexivity.

NOTE: transitivity 是可以进行“排序”的前提条件。