全序

全序承诺“任意挑出两个元素，都能确定先后或相等”，并且比较结果前后一致。它没有承诺相邻位置、固定间隔或某种距离。整数中 $2$ 后面紧接着 $3$；实数中任意 $x<y$ 之间还有 $(x+y)/2$，却同样能够全序比较。

将任务依赖关系补成执行次序，是从偏序走向全序的典型过程。两项互不依赖的任务原本不可比，排定日程时可以任选一个先执行；这个额外方向来自排程选择，而不是新发现了一条依赖。保留所有原有比较的全序称为原偏序的线性扩张。

逐坐标序与字典序 ​

在 ${\mathbb{R}}^2$ 上，逐坐标序是

$(0,1)$ 与 $(1,0)$ 各有一个坐标更大，无法比较。字典序则先比较第一坐标，仅在第一坐标相等时才比较第二坐标：

因此 $(0,1){<}_{\mathrm{lex}}(1,0)$。任意两个不同的二元组总会在某个最先不同的坐标上分出先后；传递性也来自这个最先起决定作用的坐标。全序不是把两个偏序方向平均折中，而是明确规定优先级。

字符串字典序还需要约定真前缀的位置，通常令短前缀在前。即使字母表有限且有序，全体有限字符串的字典序也未必是良序：在 $a<b$ 时，$b>ab>aab>\cdots$ 严格下降，集合 $\{a^{n}b:n\ge 0\}$ 没有最小元。改用“先长度、再字典序”才会在有限字母表上得到良序。

端点、相邻与良序 ​

整数通常次序没有最小元和最大元；区间 $[0,1]$ 两端都有，但子集 $(0,1]$ 没有最小元。可见全序不保证端点，有全局端点也不保证每个子集都有端点。

良序要求每个非空子集都有最小元。自然数的通常次序是良序，整数和实数的通常次序不是。另一个独立问题是稠密性：有理数和实数的通常次序都稠密，只有后者具有上确界完备性。全可比、良序、稠密和完备描述的是不同结构，不能互相替代。

这些条件在存在性问题中各有用途。稠密线性序的量词消去公理库稠密线性序的量词消去Quantifier elimination for dense linear orders · DLO 量词消去在无端点稠密线性序中，以所有下界小于所有上界消去存在量词，并构造避开有限禁点的见证。把“存在元素高于全部有限下界、低于全部有限上界”化成每个下界小于每个上界；稠密性填补双侧空隙，无端点性处理只有单侧界的情况。整数在 $0<1$ 之间没有见证，而 $[0,1]$ 在 $1$ 右侧没有见证，分别显示两项假设不能省略。

集合的包含序通常不是全序，例如 $\{1\}$ 与 $\{2\}$ 不可比；限制到 $\varnothing \subseteq \{1\}\subseteq \{1,2\}$ 这一条链，才得到全序。改变集合本身或改变关系，都可能改变可比性。

排序键相同，不等于对象相同 ​

按成绩给学生排序，两个不同学生可能成绩相同。如果把“成绩不大于”直接当作学生集合上的非严格序，那么两个不同学生会双向可比，违反反对称性。它给出的是全预序；先按相同成绩形成商集公理库商集Quotient set · Set of equivalence classes等价关系的所有等价类组成的集合。，再在等价类之间比较，才能得到全序。

程序库常使用严格弱序：比较中的“互不小于”定义同一组，组之间全序排列。要给每个对象唯一位置，可以再加入唯一 ID 作为第二排序键；稳定排序则保留同键元素的原输入次序，二者解决的问题不同。

特殊数值也会破坏普通比较的三歧性。例如浮点 NaN 与数值做普通大小、相等比较时，三个方向可能都不成立。需要在业务比较规则中明确排除它，或指定它属于哪个排序组，而不是从“数值类型”推断已有全序。

有限集合能真正排成一列 ​

每个非空有限全序集都有唯一最小元。证明可以维护当前最小者：加入新元素时，全可比性允许选择两者中较小的一个，传递性保证它仍不大于此前全部元素。唯一性来自反对称性。类似地存在唯一最大元；反复取出最小元，就能把整个集合按严格递增顺序列完。

这个论证还解释比较算法为何不能容忍“剪刀、石头、布”式循环：即使每对对象都有胜负，缺少传递性也会让当前最小者失去一致意义。全可比性只负责每次能比较，传递性负责局部比较能够组成整体次序。

有限 DAG 的拓扑排序给依赖偏序选择线性扩张。每次从当前没有未完成前驱的任务中选一个，便得到合法次序；多个任务同时可选时，不同选择可以产生不同而同样正确的排序。

二分查找还需要比全序更多的条件：数据已经按该比较排序，或待判定谓词沿序单调，并且可以访问中间位置。全序提供比较语言，存储结构与单调性才支持“丢弃一半候选”的步骤。良序定理公理库良序定理Well-ordering theorem · Zermelo's theorem每个集合都能赋予一个使任意非空子集具有最小元的全序。则讨论能否为任意集合另选一个良序，并不把已有的全序自动变为良序。