[科普中国]-字典序

简单理解

设想一本英语字典里的单词，何者在前何者在后？

显然的做法是先按照第一个字母、以 a、b、c……z 的顺序排列；如果第一个字母一样，那么比较第二个、第三个乃至后面的字母。如果比到最后两个单词不一样长（比如，sigh 和 sight），那么把短者排在前。

通过这种方法，我们可以给本来不相关的单词强行规定出一个顺序。“单词”可以看作是“字母”的字符串，而把这一点推而广之就可以认为是给对应位置元素所属集合分别相同的各个有序多元组规定顺序：下面用形式化的语言说明。

形式定义给定两个偏序集A和B,(a,b)和(a′,b′)属于笛卡尔积A×B，则字典序定义为

(a,b) ≤ (a′,b′) 当且仅当a