Cry's Blog

定義：[厳密な]全順序([Strict] Total Order)

C++ STL 数学

集合 $S$ 上の2項関係 $\mathrm{comp}$ が全順序であるとは，以下の条件を満たすことである．

非対称性 - $\mathrm{comp}(a,b) \Rightarrow \neg\mathrm{comp}(b,a)$
推移性 - $\mathrm{comp}(a,b) \wedge \mathrm{comp}(b,c) \Rightarrow \mathrm{comp}(a,c)$
3分律(Trichotomy) - は以下の3つのうちのいずれかを満たす．
- $\mathrm{comp}(a,b)$
- $\mathrm{comp}(b,a)$
- $a = b$

（注：非反射性は非対称性からただちに得られる）