弱順序の cryptomorphic な三種の定義
弱順序とは
おはようございます（ユニバーサル挨拶），UDA です．
今回のネタは弱順序です．元々は， 「ゃゅょ」がこの順番で出てくる言葉の大喜利 を Twitter で見かけ，当てはまる良い感じの数学用語がないかなと考えていたことでした．私はすぐ 「弱収束極限（じゃくしゅうそくきょくげん）」を思いついて ，短くてよく使われる用語だから芸術点が高いぞ，解析学徒の面目躍如だ，と一人で盛り上がっていました．その後「弱順序（じゃくじゅんじょ）」を挙げている人を見かけ，もっと短い用語があったか，と二項関係オタクとして悔しい気分になりました．
さて，弱順序とは何者なのか解説していきます．ざっくり概念を先に説明すると，弱順序とは引き分けがあり得る優劣（大小）関係の抽象化です．例えば，テストの点数で二者間に優劣をつけると，一般には同じ点数の人がいてそこは引き分けになり，点数が異なる人の間では明確に優劣がつきます．このように，なんらかのランク付けが弱順序であると考えると，実世界での具体例は枚挙に暇がありません．
ただこの弱順序，少し曲者です．実は，以下のように微妙な立ち位置の用語＆概念なのです：
- 順序関連の他の用語と比べて用語の使いどころが特殊
- 数学用語と見せかけて数学屋には逆にあまり知られていない（数学では使う場面がほぼない）
- 計算機科学（プログラミング）ではそれなりに見かける（例えば C++20 の
std::weak_order）
- 弱順序概念について一見異なるが本質的に等価な定義が複数ある
- 狭義弱順序 (strict weak ordering)
- 全擬順序 (total quasiorder)
- 順序付き分割 (ordered partitioning)
- 定義同士は互いに必要十分な関係でない
- 対象同士は互いに可逆な変換で写り合い同じ概念を表す
異なるが本質的に同じという説明は，一見奇異に映ることでしょう．このような定義や公理の間の関係性を cryptomorphic であると言うそうです．私は弱順序のことを調べていて初めて知りました． Wikipedia は次のように説明しています：
two objects (中略) are called cryptomorphic if they are equivalent but not obviously equivalent
見かけに同値と分からないが本質的には同値な2つの対象を cryptomorphic と呼ぶ．（日本語訳は筆者による）
最初は「明らかに同値ではないが同値であること…… ってなーーに言ってんだコイツぅ？？」となりました．見かけと本質について二つの意味で equivalent を用いているのですね．数学的対象によくある「同値な定義が複数ある」のともまたニュアンスが違い，非自明さ・意外さが大事みたいです．crypto はギリシャ語由来で「隠れた」という意味で，ここでは暗号ではないです．morphic の方は皆さんご存知の同型が近いですが，他の用例を見ると構造を保つ感じでもないです．まぁ，informal には暗号めいた同型と直訳できる場面もありそうですが，準同型暗号と混同しないように．短く自然に訳すなら潜在的等価といったところでしょうか．
そんな訳で，弱順序の潜在的等価な三つの定義を整理するのも意義があろうと思い本稿の執筆に至ります．なお，弱順序は数学では滅多に使われませんので，現時点では参考文献が Wikipedia ぐらいしかありません（束論の分厚い本に載っていたかもしれませんが出張中で確認できません）．予めご承知おきを．
基本的な用語と記法の導入
いくつか基本的な用語を最初に導入しておきます．以下，$X$を集合とします．
$X^2$の部分集合$R$を$X$上の二項関係と呼ぶ．$(x,y) \in R$のときに$x$と$y$は$R$関係するといい，中置記法で$x\mathrel{R}y$と表記する．
中置記法された二項関係$\bullet\mathrel{R}\bullet$に対して，$R$が$X^2$の部分集合（二項関係のグラフ）であることを明示したいとき，$(R)$と括弧で括って書くことにします．つまり，中置記法$R$に対してそのグラフ$(R)$とは，
$$
(R) \coloneqq \set{(x, y) \in X^2 \mid x \mathrel R y}
$$
のことです．もちろん，どちらも直積集合の部分集合として同じものです．この記法があると，順序関係$\le$とそのグラフ$(\le)$を視覚的に区別できて，二項関係に対する集合論的操作をするときに便利です．
中置記法には左右の区別があることにも注意してください．順序関係を表す記号$\le$や$\lesssim$に対して，その逆関係を$\ge$や$\gtrsim$で表すことにします．また，順序関係の否定（グラフとしては補集合）を$\nless$, $\nleq$, $\not\lesssim$などで表します．
$X$上の擬順序（反射推移関係）$\lesssim$に対して，$(\lnsim) \coloneqq (\lesssim) \setminus (\gtrsim)$で定まる$X$上の二項関係$\lnsim$を狭義擬順序と呼ぶ．$X$上の半順序（反対称的擬順序）$\le$に対して，$(\lneq) \coloneqq (\le) \setminus (\ge)$で定まる$X$上の二項関係$\lneq$を狭義半順序と呼ぶ．狭義擬順序と狭義半順序をまとめてどちらも（そもそも同じ定義であるので）単に狭義順序と呼ぶ．
不等号$\le$の等号部分を除き狭義順序と呼ぶという，通常の数の大小関係から類推しやすい流儀をここでは採用しました．ただ，少し注意が必要です．実は，元になる順序を考慮しなければ，狭義擬順序と狭義半順序の間には二項関係としての性質の差異は一切ありません．狭義擬順序は狭義半順序で，狭義半順序は狭義擬順序です．これは些細ですが誤解の元です．
実際，元となる順序を特定しない特徴付けもできます．それが非反射推移関係＝非対称推移関係＝非巡回推移関係です．いずれかの同値な定義を採用すべきですが，これはこれで説明が面倒です．非反射も非対称も非巡回も一見大きく異なるのに推移律下で同値という観点でこれも cryptomorphism と言えそうです．本稿では以後，狭義順序と非{反射,対称,巡回}推移関係の同値性は認めます．元となる擬順序・半順序を特定しない場面も多いので留意してください．
さて，狭義順序に対していったん比較可能関係・比較不能関係を導入します．
$X$上の狭義順序$<$に対して，$(\lessgtr) \coloneqq (<) \cup (>)$で定まる$X$上の二項関係$\lessgtr$を比較可能関係と呼ぶ．その否定$(\not\lessgtr) = (\nless) \cap (\ngtr)$によって定まる$X$上の二項関係$\not\lessgtr$を比較不能関係と呼ぶ．
都合，今は狭義順序に対してのみ定義していることに気をつけてください．
狭義弱順序
さて，1つ目は狭義弱順序の定義です．
$<$を$X$上の二項関係とする．$<$が狭義弱順序であるとは，$<$が狭義順序であって，かつ$<$による比較不能関係$\not\lessgtr$が推移的であることをいう．すなわち，$<$が狭義弱順序であることは，以下の4性質が成り立つことと同値である:
- (推移的) 全ての$x, y, z \in X$に対して，$x < y$かつ$y < z$ならば$x < z$．
- (非反射的) 全ての$x \in X$に対して，$x \nless x$．
- (非対称的) 全ての$x, y \in X$に対して，$x < y$ならば$x \ngtr y$
- (比較不能関係が推移的) 全ての$x, y, z \in X$に対して，$x \not\lessgtr y$かつ$y \not\lessgtr z$ならば$x \not\lessgtr z$．
狭義弱順序は，この段階では「なんらかの弱順序があってその狭義版」という形の定義ではありません．1の推移律があるので2または3が狭義順序に対応し，いずれか片方で実は十分です．比較不能関係は定義より反射律と対称律を満たすため，ここに4を加えると比較不能関係が同値関係になります．つまり，「比較不能＝引き分け」の関係が同値関係になるランク（順序）付けを狭義弱順序と呼ぶ訳です．
具体例を挙げていきます．どの例も難しくないので，折り畳んでおきます．定義を簡単に理解できた人は読み飛ばしても差し支えありません（以後同様）．
全擬順序
次は全擬順序 (total quasiorder) です．これは線型前順序 (linear preorder) や完全擬順序と呼んでも良いです．「線型」と「完全」と頭の「全」，また「前順序」と「擬順序」はそれぞれ同義です．ChatGPT先生は「複数ある組み合わせの中で全前順序が普及しています」と言うのですが，私は全前順序とはゼンゼン言いたくないです．本当かよ．ただでさえややこしいのに…… なお，反射推移関係のことを前順序と呼ぶのが普及している訳ですが，全順序（完全半順序）と読みが紛らわしいのが嫌過ぎて，私はなるべく前順序の代わりに擬順序と言うようにしています．
さて，全擬順序は狭義でない弱順序に相当します．これを見るためにまず，擬順序に付随する同値関係を定義しておきます．
$\lesssim$を$X$上の擬順序とする．$x, y \in X$が順序同値とは，$x \lesssim y$かつ$x \gtrsim y$であることをいう．同値関係$(\lesssim) \cap (\gtrsim)$を擬順序$\lesssim$に付随する同値関係と呼ぶ．
二項関係$(\lesssim) \cap (\gtrsim)$は明らかに反射律・対称律・推移律を満たすので同値関係です．半順序でない擬順序は反対称律を満たさないため，$x \lesssim y$かつ$x \gtrsim y$でも$x = y$とは限りません．要素を順序に沿って縦に並べても一列にならず横並びが生じるイメージです．もちろん，反対称律の下では付随する同値関係は自明（等号）です．
次に，狭義でない順序に対する比較可能・不能を改めて定義します．
$X$上の擬順序$\lesssim$に対して，$(\lesseqgtr) \coloneqq (\lesssim) \cup (\gtrsim)$で定まる$X$上の二項関係$\lesseqgtr$を比較可能関係と呼ぶ．その否定$(\not\lesseqgtr) = (\not\lesssim) \cap (\not\gtrsim)$によって定まる$X$上の二項関係$\not\lesseqgtr$を比較不能関係と呼ぶ．
「さっきと同じでは？」と思ったかもしれませんが，よく注意してください．定義式は全く同じ形ですが，狭義順序に対する比較可能関係と異なり，順序同値な要素同士が比較可能（特に自分自身）な定義になっています．本当は$<$と$>$の間に$\sim$を挟んだ記号を使い区別したいのですが，KaTeX が未対応なので$\lesseqgtr$で妥協しました．
$X$上の擬順序$\lesssim$が完全であるとは，いかなる二元も比較可能，つまり$(\lesseqgtr) = X^2$であることをいう．
記号$\lessgtr$と$\lesseqgtr$が紛らわしいこともあり，以後，擬順序の比較可能関係の方は和$(\lesssim) \cup (\gtrsim)$で表すことにします．狭義順序の比較可能関係の記号$\lessgtr$は引き続き使います．
$X$上の二項関係$\lesssim$が全擬順序であるとは，$\lesssim$が擬順序であって，かつ完全であることをいう．すなわち，$\lesssim$が全擬順序であることは，以下の2性質が成り立つことと同値である:
- （完全）全ての$x, y \in X$に対して，$x \lesssim y$または$x \gtrsim y$.
- （推移的）全ての$x, y, z \in X$に対して，$x \lesssim y$かつ$y \lesssim z$ならば$x \lesssim z$.
全擬順序は，全順序から反対称律を落としたものと思っても良いです．反射律は完全律に含まれるのでなくても同値です．全擬順序は引き分けについては何も規定していませんが，全員のランク（順序）付けが（引き分け込みで）できることを要請している訳です．
例2の狭義順序$<$の反射閉包$(\le) = \set{(a, a), (a, b), (b, b), (c, c)})$は半順序であるが，$c$が$a,b$と比較可能でないため完全でない．
明らかに，狭義弱順序$<$と全擬順序$\lesssim$は二項関係としては全く等しくありません（同値でないです）．前者は二項関係からは引き分けを除外して比較不能関係の方で引き分けを表現し，後者は引き分け含め優劣関係を表現しています．両者の差異は引き分けを入れるか入れないかのみで，同じ弱順序概念を表現していることが以下のように分かります．
$X$上の狭義弱順序と全擬順序は以下の関係により一対一対応する．
- 狭義弱順序$<$に対して$(\lesssim) \coloneqq (<) \cup (\not\lessgtr)$で定まる二項関係$\lesssim$は全擬順序である．
- 全擬順序$\lesssim$に対してその狭義擬順序$\lnsim$は狭義弱順序である．
(i), (ii)の対応の下で，比較不能関係$\not\lessgtr$と同値関係$(\lesssim) \cap (\gtrsim)$は一致する．
証明は難しくないですが折り畳んでおきました．是非考えてみてください．引き分け関係の一致は各々成立するという主張なので(i), (ii)の証明内にまとめています．
(i)の証明
$$ (\lesssim) \cup (\gtrsim) = (<) \cup (\not\lessgtr) \cup (>) \cup (\not\lessgtr) = (\lessgtr) \cup (\not\lessgtr) = X^2. $$
ゆえに，$\lesssim$は全擬順序である．また，$<$の非対称性から，$\lesssim$に付随する同値関係は比較不能関係と一致する：
$$(\lesssim) \cap (\gtrsim) = \{(<) \cup (\not\lessgtr)\} \cap \{(>) \cup (\not\lessgtr)\} = (\not\lessgtr).$$
(ii)の証明
$$ (\lnsim)^\complement = ((\lesssim) \cap (\not\gtrsim))^\complement = (\not\lesssim) \cup (\gtrsim). $$
よって，比較不能関係の定義より，
$$ (\not\lessgtr) = (\lnsim)^\complement \cap (\gnsim)^\complement = \{(\not\lesssim) \cup (\gtrsim)\} \cap \{(\not\gtrsim) \cup (\lesssim)\} = \{(\not\lesssim) \cap (\not\gtrsim)\} \cup \{(\lesssim) \cap (\gtrsim)\}. $$
最後の等式変形は分配法則と$(\lesssim) \cap (\not\lesssim) = \varnothing$による．
ここで，$\lesssim$の完全性より$(\lesssim) \cup (\gtrsim) = X^2$であるから，ド・モルガンの法則により$(\not\lesssim) \cap (\not\gtrsim) = \{(\lesssim) \cup (\gtrsim)\}^\complement = \varnothing$である．以上より$$(\not\lessgtr) = (\lesssim) \cap (\gtrsim)$$であり，$\lesssim$の推移性から明らかに$\not\lessgtr$も推移律を満たす．また，これは$\lesssim$に付随する同値関係にほかならない．
一対一対応の証明
$$ (<) \longmapsto (\lesssim) = (<) \cup (\sim) , \qquad (\lesssim) \longmapsto (<) = (\lesssim) \setminus (\sim) $$
は互いに逆写像の関係にある．
\begin{align*} A \lnsim B & \mathrel{\Longleftrightarrow} (\#A, \#B) \in \set{(0, 1), (0, 2), (0, 3), (1, 3), (2, 3)}, \\ A \sim B & \mathrel{\Longleftrightarrow} (\#A, \#B) \in \set{(0, 0), (1, 1), (1, 2), (2, 1), (2, 2), (3, 3)}. \end{align*}
ただし，ここで集合の要素数を$\#(\bullet)$で表記した．この弱順序は要素数により優劣をつけ，加えて（自明な引き分け以外にも）要素数$1$と$2$の組み合わせを引き分けにする．
このように，狭義弱順序と全擬順序の間の対応関係を紐解くと，引き分け部分をただ付け外ししているだけであることが分かります．狭義弱順序および全擬順序の定義だけを見比べてもこの点が明瞭ではなく一見謎めいていた訳ですが，分かればなんということはありません．
順序付き分割
最後に，順序付き分割です．これはもう同値関係で割るだけです．
$\sim$を$X$上の同値関係とし，その商集合$X/{\sim}$上に全順序$\le$が備わっているとする．このとき，$(X / {\sim}, \le)$を$X$の順序付き分割と呼ぶ．
前二つのいずれかの定義の弱順序を引き分けの同値関係で割ってやれば順序付き分割になります．引き分けを同値類で表し，優劣も同値類の間でつけるということです．そう難しくないですね．また，順序付き分割は list of sets とも呼ばれます．これはデータ構造としての実装を意図した呼び方で，同値類を表す集合が為す全順序の列ということです．
このことを定理として主張にまとめて整理する前に，商と順序に関わる基本的な用語と概念を定義しておきましょう．
$(X, \lesssim)$を擬順序集合とし，その上の同値関係を$R$，商写像を$q \colon X \to X / R$とする．二項関係の推移閉包を$(\bullet)^+$で表記する．$(\lesssim_R) \coloneqq (q \times q)\left[\{(\lesssim) \cup R\}^+\right]$で定まる商集合$X / R$上の擬順序$\lesssim_R$を，$\lesssim$の$R$による商擬順序と呼ぶ．これはすなわち，全ての二点$q(x), q(x') \in X / {\sim}$に対して，
$$
q(x) \lesssim_R q(x') \mathrel{\Longleftrightarrow}
\text{$X$上の有向道$(x_i)_{i=0}^n$が存在して}
x = x_0 \to x_1 \to \dots \to x_n = x'
$$
で$\lesssim_R$を定義するのと等しい．ただし，ここで有向道の各有向辺$x_i \to x_{i+1}$は$x_i \lesssim x_{i+1}$または$x_i \mathrel{R} x_{i+1}$いずれか少なくとも一方の成立を意味するものとする．また，擬順序集合の同値関係による商を$(X, \lesssim) / R \coloneqq (X / R, \lesssim_R)$と表記する．
商順序は，商写像$q \colon X \to X / R$が順序を保つような最小の擬順序と言い換えてもよいです．したがって，始域側が半順序であったとしても，割り方によっては終域側に半順序が入るとは限りません．
擬順序に付随する同値関係による商であれば商順序が必ず半順序になります．というのも，反対称律が成り立たない順序同値な部分を同一視して一点につぶすためです．擬順序から半順序を得る特別なこの商の構成は，実は半順序集合の圏から擬順序集合の圏への包含関手の左随伴を与えます．圏論の言葉では，一般に包含の左随伴はリフレクションと呼ばれ，今の場合は半順序集合リフレクションと呼べるものです（英語なら poset reflection と短く表現できスマートですが日本語だと長ったらしくてちょっと残念ですね……）．グラフ理論の言葉では凝縮という用語もあります（割愛しますが同じような操作です）．
集合$X$から擬順序集合$(Y, \lesssim)$への写像を$f$とする．$(\lesssim_f) \coloneqq (f \times f)^{-1}[(\lesssim)]$で定まる$X$上の擬順序$\lesssim_f$を$f$による$\lesssim$の引き戻しと呼ぶ．これはすなわち，全ての二点$x, x' \in X$に対して，
$$
x \lesssim_f x' \mathrel{\Longleftrightarrow} f(x) \lesssim f(x')
$$
で擬順序$\lesssim_f$を定義するのと等しい．
引き戻した擬順序は，$f$が順序を保つような最大の擬順序と言い換えてもよいです．終域側が半順序であったとしても，引き戻し方によっては始域側に半順序が入るとは限りません．
さて，自然な商で全擬順序の半順序集合リフレクションをとれば順序付き分割になり，逆に順序付き分割を商写像で引き戻してやれば全擬順序が得られます．リフレクションと引き戻しによって全擬順序と順序付き分割が対応することを定理の形でまとめておきます．
$X$上の全擬順序と$X$の順序付き分割は以下の関係により一対一対応する．
- 全擬順序$\lesssim$に対して付随する同値関係$\sim$による商$(X, \lesssim) / {\sim}$は順序付き分割である．
- 順序付き分割$(X / {\sim}, \le)$に対して商写像$q \colon X \to X / {\sim}$による$\le$の引き戻しは全擬順序である．
これも難しくないですが折り畳んでおきました．是非自分で証明してみてください．
(i)の証明
$$ (\le) = (q \times q)[\left\{(\lesssim) \cup (\sim)\right\}^+] = (q \times q)[(\lesssim)^+] = (q \times q)[(\lesssim)]. $$
ここで，$\lesssim$の完全性と商写像が全射であることより，
$$ (\le) \cup (\ge) = (q \times q)[(\lesssim) \cup (\gtrsim)] = (q \times q)[X^2] = (X / {\sim})^2. $$
つまり，$\le$は全順序であり，商順序集合は$X$の順序付き分割を与える．
(ii)の証明
$$ (\lesssim_q) \cup (\gtrsim_q) = (q \times q)^{-1}[(\le) \cup (\ge)] = (q \times q)^{-1}[(X / {\sim})^2] = X^2. $$
つまり，引き戻した順序$\lesssim_q$は全擬順序である．
一対一対応の証明
$$ (\lesssim) \longmapsto (q \times q)[(\lesssim)] , \qquad (\le) \longmapsto (q \times q)^{-1}[(\le)] $$
は互いに逆写像の関係にある．
まとめ
どの弱順序概念も引き分けの形式化が異なるだけで，完全性を持つ順序であることが本質的には重要です．当然，割ればただの全順序です．これを聞いて「さっさと同一視して全順序だけでよくね？」と思うのが同一視大好きな数学の人の考え方で，引き分けの情報が乗っている部分に価値があると思うのがデータ構造大好きな計算機科学側の人の考え方です．知らんけど．どちらの考え方に立っても順序付き分割の方に行き着くというのは興味深いですね．
ところで，実は地味に証明を頑張りました．完全性が本質的であることが一目で分かるよう，そして対応関係を式で追って「そりゃそうだ」と思えるよう，だいぶ意識しました．始めは元をとるオーソドックスな証明を書いたのですが，推敲を重ね結果的に元をとらない証明になりました． 前の関係代数の記事 と同じで，意識的に元をとらなかった訳ではないのですが．必然というか二項関係を集合論的に操作するのはやはり相性が良いですね．畳んだ証明を飛ばした人も是非見直して来てください（笑）．
せっかくなので今回出てきた諸性質をまた関係代数版とで並べた表にしておきましょう．まぁ，今回は最初から最後まで二項関係のグラフを重用していたので右側の列をずっと使っていましたが．
| 名前 | 定義 | 関係代数での言い換え |
|---|---|---|
| 狭義擬順序 | $x \lesssim y \land x \not\gtrsim y$ | $(\lesssim) \setminus (\gtrsim)$ |
| 否定 | $x \not\mathrel{R} y$ | $R^\complement$ ($= X^2 \setminus R$) |
| 比較可能 | $x < y \lor x > y$ | $(\lessgtr) = (<) \cup (>)$ |
| 比較不能 | $x \nless y \land x \ngtr y$ | $(\not\lessgtr) = (\nless) \cap (\ngtr)$ |
| 非反射律 | $\forall x. \ x \nless x$ | $I_X \subseteq (\nless)$ |
| 非対称律 | $\forall x,y. \ x < y \Rightarrow x \ngtr y$ | $(<) \subseteq (\ngtr)$ |
| 完全律 | $\forall x,y. \ x \lesssim y \lor x \gtrsim y$ | $(\lesssim) \cup (\gtrsim) = X^2$ |
| 付随同値関係 | $x \lesssim y \land x \gtrsim y$ | $(\lesssim) \cap (\gtrsim)$ ($= (\sim)$) |
| 定理1(i) | （引き分けの追加） | $(<) \mapsto (<) \cup (\sim)$ |
| 定理1(ii) | （引き分けの除外） | $(\lesssim) \mapsto (\lesssim) \setminus (\sim)$ |
| 定理2(i) | （引き分けによる商） | $(\lesssim) \mapsto (q \times q)[(\lesssim)]$ |
| 定理2(ii) | （商による引き戻し） | $(\le) \mapsto (q \times q)^{-1}[(\le)]$ |
本当は GW 中に投稿したかったのですが，色々調べたり推敲していたらずるずると GW が明けてしまいました．それでは今回はこの辺で．気が向いたら関係代数シリーズがまた続くかもしれませんね．
