全順序 - 0b5vr

全順序

🔥.icon 集合とかまともに勉強したこと無いので、定義とか間違ってたらごめんね

全順序 (total order) とは、集合上の二項関係で、反射律・推移律・反対称律・完全律を満たすもの

全順序を満たす集合を全順序集合 (totally ordered set) という

定義

空でない集合$ Xについて、以下の4つの二項関係が満たされる場合、その集合は全順序

反射律: $ \forall a \in X : a \leq a

推移律: $ \forall a, b, c \in X : [(a \leq b \land b \leq c) \implies a \leq c]

反対称律: $ \forall a, b \in X : [(a \leq b \land b \leq a) \implies a = b]

完全律: $ \forall a, b \in X : (a \leq b \lor b \leq a)

上ではわかりやすさのため等号を使ったものの、本来は大小の関係でなく任意の二項関係であることを表すため、$ (a, b)と書いてやったほうがいいらしい

反射律・推移律・反対称律のみを満たすものを半順序という

反射律・推移律のみを満たすものを前順序という

例

自然数$ \mathbb N

実数$ \mathbb R

Unicodeに定められたキャラクター

単語の集合に辞書式順序を導入したら、それは全順序集合

プログラミング

Haskellでは、全順序であることを保証する型クラスとしてHaskell: Ordがある 🔗

Rustでは、全順序であることを表すRust: traitとしてRust: Ordがある 🔗

全順序であるとき、例えば以下のようなことができるようになる

まずもちろん、比較演算子 (<, <=, >, >=) を用いた比較

min, max, clamp

浮動小数点

IEEE 754に定められるところの浮動小数点は、NaNが比較不能で完全律を満たさないため、半順序

Rustにおける f64 はRust: PartialOrdなので、そのままではソートができないんですね

f64::total_cmp を使えば無理やり全順序の二項関係にしちゃえるので、それを使って sort_unstable_by してあげようね