おはようございます(ユニバーサル挨拶),UDA です.
今回のネタは弱順序です.元々は, 「ゃゅょ」がこの順番で出てくる言葉の大喜利 を Twitter で見かけ,当てはまる良い感じの数学用語がないかなと考えていたことでした.私はすぐ 「弱収束極限(じゃくしゅうそくきょくげん)」を思いついて ,短くてよく使われる用語だから芸術点が高いぞ,解析学徒の面目躍如だ,と一人で盛り上がっていました.その後「弱順序(じゃくじゅんじょ)」を挙げている人を見かけ,もっと短い用語があったか,と二項関係オタクとして悔しい気分になりました.
さて,弱順序とは何者なのか解説していきます.ざっくり概念を先に説明すると,弱順序とは引き分けがあり得る優劣(大小)関係の抽象化です.例えば,テストの点数で二者間に優劣をつけると,一般には同じ点数の人がいてそこは引き分けになり,点数が異なる人の間では明確に優劣がつきます.このように,なんらかのランク付けが弱順序であると考えると,実世界での具体例は枚挙に暇がありません.
ただこの弱順序,少し曲者です.実は,以下のように微妙な立ち位置の用語&概念なのです:
std::weak_order
)異なるが本質的に同じという説明は,一見奇異に映ることでしょう.このような定義や公理の間の関係性を cryptomorphic であると言うそうです.私は弱順序のことを調べていて初めて知りました. Wikipedia は次のように説明しています:
two objects (中略) are called cryptomorphic if they are equivalent but not obviously equivalent
見かけに同値と分からないが本質的には同値な2つの対象を cryptomorphic と呼ぶ.(日本語訳は筆者による)
最初は「明らかに同値ではないが同値であること…… ってなーーに言ってんだコイツぅ??」となりました.見かけと本質について二つの意味で equivalent を用いているのですね.数学的対象によくある「同値な定義が複数ある」のともまたニュアンスが違い,非自明さ・意外さが大事みたいです.crypto はギリシャ語由来で「隠れた」という意味で,ここでは暗号ではないです.morphic の方は皆さんご存知の同型が近いですが,他の用例を見ると構造を保つ感じでもないです.まぁ,informal には暗号めいた同型と直訳できる場面もありそうですが,準同型暗号と混同しないように.短く自然に訳すなら潜在的等価といったところでしょうか.
そんな訳で,弱順序の潜在的等価な三つの定義を整理するのも意義があろうと思い本稿の執筆に至ります.なお,弱順序は数学では滅多に使われませんので,現時点では参考文献が Wikipedia ぐらいしかありません(束論の分厚い本に載っていたかもしれませんが出張中で確認できません).予めご承知おきを.
いくつか基本的な用語を最初に導入しておきます.以下,
中置記法された二項関係
のことです.もちろん,どちらも直積集合の部分集合として同じものです.この記法があると,順序関係
中置記法には左右の区別があることにも注意してください.順序関係を表す記号
不等号
実際,元となる順序を特定しない特徴付けもできます.それが非反射推移関係=非対称推移関係=非巡回推移関係です.いずれかの同値な定義を採用すべきですが,これはこれで説明が面倒です.非反射も非対称も非巡回も一見大きく異なるのに推移律下で同値という観点でこれも cryptomorphism と言えそうです.本稿では以後,狭義順序と非{反射,対称,巡回}推移関係の同値性は認めます.元となる擬順序・半順序を特定しない場面も多いので留意してください.
さて,狭義順序に対していったん比較可能関係・比較不能関係を導入します.
都合,今は狭義順序に対してのみ定義していることに気をつけてください.
さて,1つ目は狭義弱順序の定義です.
狭義弱順序は,この段階では「なんらかの弱順序があってその狭義版」という形の定義ではありません.1の推移律があるので2または3が狭義順序に対応し,いずれか片方で実は十分です.比較不能関係は定義より反射律と対称律を満たすため,ここに4を加えると比較不能関係が同値関係になります.つまり,「比較不能=引き分け」の関係が同値関係になるランク(順序)付けを狭義弱順序と呼ぶ訳です.
具体例を挙げていきます.どの例も難しくないので,折り畳んでおきます.定義を簡単に理解できた人は読み飛ばしても差し支えありません(以後同様).
次は全擬順序 (total quasiorder) です.これは線型前順序 (linear preorder) や完全擬順序と呼んでも良いです.「線型」と「完全」と頭の「全」,また「前順序」と「擬順序」はそれぞれ同義です.ChatGPT先生は「複数ある組み合わせの中で全前順序が普及しています」と言うのですが,私は全前順序とはゼンゼン言いたくないです.本当かよ.ただでさえややこしいのに…… なお,反射推移関係のことを前順序と呼ぶのが普及している訳ですが,全順序(完全半順序)と読みが紛らわしいのが嫌過ぎて,私はなるべく前順序の代わりに擬順序と言うようにしています.
さて,全擬順序は狭義でない弱順序に相当します.これを見るためにまず,擬順序に付随する同値関係を定義しておきます.
二項関係
次に,狭義でない順序に対する比較可能・不能を改めて定義します.
「さっきと同じでは?」と思ったかもしれませんが,よく注意してください.定義式は全く同じ形ですが,狭義順序に対する比較可能関係と異なり,順序同値な要素同士が比較可能(特に自分自身)な定義になっています.本当は
記号
全擬順序は,全順序から反対称律を落としたものと思っても良いです.反射律は完全律に含まれるのでなくても同値です.全擬順序は引き分けについては何も規定していませんが,全員のランク(順序)付けが(引き分け込みで)できることを要請している訳です.
明らかに,狭義弱順序
(i), (ii)の対応の下で,比較不能関係
証明は難しくないですが折り畳んでおきました.是非考えてみてください.引き分け関係の一致は各々成立するという主張なので(i), (ii)の証明内にまとめています.
このように,狭義弱順序と全擬順序の間の対応関係を紐解くと,引き分け部分をただ付け外ししているだけであることが分かります.狭義弱順序および全擬順序の定義だけを見比べてもこの点が明瞭ではなく一見謎めいていた訳ですが,分かればなんということはありません.
最後に,順序付き分割です.これはもう同値関係で割るだけです.
前二つのいずれかの定義の弱順序を引き分けの同値関係で割ってやれば順序付き分割になります.引き分けを同値類で表し,優劣も同値類の間でつけるということです.そう難しくないですね.また,順序付き分割は list of sets とも呼ばれます.これはデータ構造としての実装を意図した呼び方で,同値類を表す集合が為す全順序の列ということです.
このことを定理として主張にまとめて整理する前に,商と順序に関わる基本的な用語と概念を定義しておきましょう.
で
商順序は,商写像
擬順序に付随する同値関係による商であれば商順序が必ず半順序になります.というのも,反対称律が成り立たない順序同値な部分を同一視して一点につぶすためです.擬順序から半順序を得る特別なこの商の構成は,実は半順序集合の圏から擬順序集合の圏への包含関手の左随伴を与えます.圏論の言葉では,一般に包含の左随伴はリフレクションと呼ばれ,今の場合は半順序集合リフレクションと呼べるものです(英語なら poset reflection と短く表現できスマートですが日本語だと長ったらしくてちょっと残念ですね……).グラフ理論の言葉では凝縮という用語もあります(割愛しますが同じような操作です).
集合
で擬順序
引き戻した擬順序は,
さて,自然な商で全擬順序の半順序集合リフレクションをとれば順序付き分割になり,逆に順序付き分割を商写像で引き戻してやれば全擬順序が得られます.リフレクションと引き戻しによって全擬順序と順序付き分割が対応することを定理の形でまとめておきます.
これも難しくないですが折り畳んでおきました.是非自分で証明してみてください.
どの弱順序概念も引き分けの形式化が異なるだけで,完全性を持つ順序であることが本質的には重要です.当然,割ればただの全順序です.これを聞いて「さっさと同一視して全順序だけでよくね?」と思うのが同一視大好きな数学の人の考え方で,引き分けの情報が乗っている部分に価値があると思うのがデータ構造大好きな計算機科学側の人の考え方です.知らんけど.どちらの考え方に立っても順序付き分割の方に行き着くというのは興味深いですね.
ところで,実は地味に証明を頑張りました.完全性が本質的であることが一目で分かるよう,そして対応関係を式で追って「そりゃそうだ」と思えるよう,だいぶ意識しました.始めは元をとるオーソドックスな証明を書いたのですが,推敲を重ね結果的に元をとらない証明になりました. 前の関係代数の記事 と同じで,意識的に元をとらなかった訳ではないのですが.必然というか二項関係を集合論的に操作するのはやはり相性が良いですね.畳んだ証明を飛ばした人も是非見直して来てください(笑).
せっかくなので今回出てきた諸性質をまた関係代数版とで並べた表にしておきましょう.まぁ,今回は最初から最後まで二項関係のグラフを重用していたので右側の列をずっと使っていましたが.
名前 | 定義 | 関係代数での言い換え |
---|---|---|
狭義擬順序 | ||
否定 | ||
比較可能 | ||
比較不能 | ||
非反射律 | ||
非対称律 | ||
完全律 | ||
付随同値関係 | ||
定理1(i) | (引き分けの追加) | |
定理1(ii) | (引き分けの除外) | |
定理2(i) | (引き分けによる商) | |
定理2(ii) | (商による引き戻し) |
本当は GW 中に投稿したかったのですが,色々調べたり推敲していたらずるずると GW が明けてしまいました.それでは今回はこの辺で.気が向いたら関係代数シリーズがまた続くかもしれませんね.