0
大学数学基礎解説
文献あり

弱順序の cryptomorphic な三種の定義

107
0

弱順序とは

おはようございます(ユニバーサル挨拶),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を集合とします.

二項関係

X2の部分集合RX上の二項関係と呼ぶ.(x,y)RのときにxyR関係するといい,中置記法でxRyと表記する.

中置記法された二項関係Rに対して,RX2の部分集合(二項関係のグラフ)であることを明示したいとき,(R)と括弧で括って書くことにします.つまり,中置記法Rに対してそのグラフ(R)とは,
(R):={(x,y)X2xRy}
のことです.もちろん,どちらも直積集合の部分集合として同じものです.この記法があると,順序関係とそのグラフ()を視覚的に区別できて,二項関係に対する集合論的操作をするときに便利です.

中置記法には左右の区別があることにも注意してください.順序関係を表す記号に対して,その逆関係をで表すことにします.また,順序関係の否定(グラフとしては補集合)を, , などで表します.

狭義順序

X上の擬順序(反射推移関係)に対して,():=()()で定まるX上の二項関係を狭義擬順序と呼ぶ.X上の半順序(反対称的擬順序)に対して,():=()()で定まるX上の二項関係を狭義半順序と呼ぶ.狭義擬順序と狭義半順序をまとめてどちらも(そもそも同じ定義であるので)単に狭義順序と呼ぶ.

狭義順序の同値な定義について

不等号の等号部分を除き狭義順序と呼ぶという,通常の数の大小関係から類推しやすい流儀をここでは採用しました.ただ,少し注意が必要です.実は,元になる順序を考慮しなければ,狭義擬順序と狭義半順序の間には二項関係としての性質の差異は一切ありません.狭義擬順序は狭義半順序で,狭義半順序は狭義擬順序です.これは些細ですが誤解の元です.

実際,元となる順序を特定しない特徴付けもできます.それが非反射推移関係=非対称推移関係=非巡回推移関係です.いずれかの同値な定義を採用すべきですが,これはこれで説明が面倒です.非反射も非対称も非巡回も一見大きく異なるのに推移律下で同値という観点でこれも cryptomorphism と言えそうです.本稿では以後,狭義順序と非{反射,対称,巡回}推移関係の同値性は認めます.元となる擬順序・半順序を特定しない場面も多いので留意してください.

さて,狭義順序に対していったん比較可能関係・比較不能関係を導入します.

狭義順序による比較可能関係,比較不能関係

X上の狭義順序<に対して,():=(<)(>)で定まるX上の二項関係比較可能関係と呼ぶ.その否定()=()()によって定まるX上の二項関係比較不能関係と呼ぶ.

都合,今は狭義順序に対してのみ定義していることに気をつけてください.

狭義弱順序

さて,1つ目は狭義弱順序の定義です.

狭義弱順序

<X上の二項関係とする.<狭義弱順序であるとは,<が狭義順序であって,かつ<による比較不能関係が推移的であることをいう.すなわち,<が狭義弱順序であることは,以下の4性質が成り立つことと同値である:

  1. (推移的) 全てのx,y,zXに対して,x<yかつy<zならばx<z
  2. (非反射的) 全てのxXに対して,xx
  3. (非対称的) 全てのx,yXに対して,x<yならばxy
  4. (比較不能関係が推移的) 全てのx,y,zXに対して,xyかつyzならばxz

狭義弱順序は,この段階では「なんらかの弱順序があってその狭義版」という形の定義ではありません.1の推移律があるので2または3が狭義順序に対応し,いずれか片方で実は十分です.比較不能関係は定義より反射律と対称律を満たすため,ここに4を加えると比較不能関係が同値関係になります.つまり,「比較不能=引き分け」の関係が同値関係になるランク(順序)付けを狭義弱順序と呼ぶ訳です.

具体例を挙げていきます.どの例も難しくないので,折り畳んでおきます.定義を簡単に理解できた人は読み飛ばしても差し支えありません(以後同様).

ランク関数による弱順序付け
X={0,1a,1b,1c,2a,2b,2c,3}とする.rank:XNを,添字を落とし添字無しの整数に写す関数とする(例えばrank(1a)=1, rank(3)=3).これをXのランク関数と呼ぶことにする.N上の通常の大小関係をランク関数で引き戻してXに擬順序Xを入れる.つまり,Xの要素間の大小Xをランク関数値の大小によって入れる(正確には後の定義11を参照せよ).このとき,Xの狭義擬順序Xは狭義弱順序である.非自明な比較不能関係は1122の形に限られる(には各々勝手な添字a,b,cを収めてよい).各要素は自明に自分自身と比較不能であることに注意すると,比較不能関係は確かに推移律を満たす.
狭義弱順序でない例
X={a,b,c}とし,X上の二項関係<a<bだけで定める.つまり,(<):={(a,b)}である.<X上の狭義順序ではあるが,狭義弱順序ではない.実際,acかつcbだがa<bであり,比較不能関係が推移的ではない.

全擬順序

次は全擬順序 (total quasiorder) です.これは線型前順序 (linear preorder) や完全擬順序と呼んでも良いです.「線型」と「完全」と頭の「全」,また「前順序」と「擬順序」はそれぞれ同義です.ChatGPT先生は「複数ある組み合わせの中で全前順序が普及しています」と言うのですが,私は全前順序とはゼンゼン言いたくないです.本当かよ.ただでさえややこしいのに…… なお,反射推移関係のことを前順序と呼ぶのが普及している訳ですが,全順序(完全半順序)と読みが紛らわしいのが嫌過ぎて,私はなるべく前順序の代わりに擬順序と言うようにしています.

さて,全擬順序は狭義でない弱順序に相当します.これを見るためにまず,擬順序に付随する同値関係を定義しておきます.

順序同値,付随する同値関係

X上の擬順序とする.x,yX順序同値とは,xyかつxyであることをいう.同値関係()()を擬順序付随する同値関係と呼ぶ.

二項関係()()は明らかに反射律・対称律・推移律を満たすので同値関係です.半順序でない擬順序は反対称律を満たさないため,xyかつxyでもx=yとは限りません.要素を順序に沿って縦に並べても一列にならず横並びが生じるイメージです.もちろん,反対称律の下では付随する同値関係は自明(等号)です.

次に,狭義でない順序に対する比較可能・不能を改めて定義します.

順序による比較可能関係,比較不能関係

X上の擬順序に対して,():=()()で定まるX上の二項関係を比較可能関係と呼ぶ.その否定(⋚̸)=()()によって定まるX上の二項関係⋚̸を比較不能関係と呼ぶ.

狭義順序の比較可能性との違い

「さっきと同じでは?」と思ったかもしれませんが,よく注意してください.定義式は全く同じ形ですが,狭義順序に対する比較可能関係と異なり,順序同値な要素同士が比較可能(特に自分自身)な定義になっています.本当は<>の間にを挟んだ記号を使い区別したいのですが,KaTeX が未対応なのでで妥協しました.

完全

X上の擬順序完全であるとは,いかなる二元も比較可能,つまり()=X2であることをいう.

記号が紛らわしいこともあり,以後,擬順序の比較可能関係の方は和()()で表すことにします.狭義順序の比較可能関係の記号は引き続き使います.

全擬順序

X上の二項関係全擬順序であるとは,が擬順序であって,かつ完全であることをいう.すなわち,が全擬順序であることは,以下の2性質が成り立つことと同値である:

  1. (完全)全てのx,yXに対して,xyまたはxy.
  2. (推移的)全てのx,y,zXに対して,xyかつyzならばxz.

全擬順序は,全順序から反対称律を落としたものと思っても良いです.反射律は完全律に含まれるのでなくても同値です.全擬順序は引き分けについては何も規定していませんが,全員のランク(順序)付けが(引き分け込みで)できることを要請している訳です.

例1, 例2の再訪
例1の擬順序Xは全順序のランク関数による引き戻しであったから,明らかに全擬順序である.
例2の狭義順序<の反射閉包()={(a,a),(a,b),(b,b),(c,c)})は半順序であるが,ca,bと比較可能でないため完全でない.

明らかに,狭義弱順序<と全擬順序は二項関係としては全く等しくありません(同値でないです).前者は二項関係からは引き分けを除外して比較不能関係の方で引き分けを表現し,後者は引き分け含め優劣関係を表現しています.両者の差異は引き分けを入れるか入れないかのみで,同じ弱順序概念を表現していることが以下のように分かります.

X上の狭義弱順序と全擬順序は以下の関係により一対一対応する.

  1. 狭義弱順序<に対して():=(<)()で定まる二項関係は全擬順序である.
  2. 全擬順序に対してその狭義擬順序は狭義弱順序である.

(i), (ii)の対応の下で,比較不能関係と同値関係()()は一致する.

証明は難しくないですが折り畳んでおきました.是非考えてみてください.引き分け関係の一致は各々成立するという主張なので(i), (ii)の証明内にまとめています.

(i)の証明
<を狭義弱順序とする.():=(<)()が全擬順序であることを示す.まず,<がどちらも推移的であるから,は明らかに推移律を満たす.の完全性を示す.
()()=(<)()(>)()=()()=X2.
ゆえに,は全擬順序である.また,<の非対称性から,に付随する同値関係は比較不能関係と一致する:
()()={(<)()}{(>)()}=().
(ii)の証明
を全擬順序とする.その狭義擬順序が狭義弱順序であることを示す.狭義擬順序による比較不能関係をとして,これが推移的であることを示せばよい.ここで,狭義擬順序の定義より()=()()=()()であるからその補集合は,
()=(()())=()().
よって,比較不能関係の定義より,
()=()()={()()}{()()}={()()}{()()}.
最後の等式変形は分配法則と()()=による.
ここで,の完全性より()()=X2であるから,ド・モルガンの法則により()()={()()}=である.以上より()=()()であり,の推移性から明らかにも推移律を満たす.また,これはに付随する同値関係にほかならない.
一対一対応の証明
(i)でも(ii)でも,狭義順序による比較不能関係と擬順序に付随する同値関係が一致したことを見た.(どちらを考えているにしても)これを():=()=()()と表記することにする.(<)()=および()()に注意する.すると,明らかに対応
(<)()=(<)(),()(<)=()()
は互いに逆写像の関係にある.
2点集合の冪集合における狭義包含関係は弱順序
冪集合X=2{0,1}={,{0},{1},{0,1}}上の半順序として包含関係を考える.明らかに,異なる一点集合{0}{1}は比較不能であり,(X,)は完全でない.対応する狭義半順序は真の包含関係である.これを(<):=()とおく.その比較不能関係は自明な関係と{0}{1}のみで,これは同値関係である.したがって,<X上の狭義弱順序である(要素数をランク関数にしたと見ると分かりやすい).ここから定理の対応で得られる全擬順序():=(<)()は包含関係とは異なる.実際,{0}{1}が順序同値となる点が異なる.
3点集合の冪集合における狭義包含関係は弱順序でない
冪集合X=2{0,1,2}上の半順序として包含関係を考える.先と同様に,狭義半順序を真の包含関係(<):=()とおく.すると,{0,1}{2}などの非自明な比較不能関係が複数あり,比較不能関係が同値関係ではない.よって,狭義弱順序ではない.実際,{0,1}{2}{0}であるが {0,1}>{0}であるため比較不能関係が推移的ではない.そこで,擬順序を,(<)()の推移閉包(つまりこれを包む最小の推移関係)によって定める.定義からは反射推移関係つまり擬順序である.すると,要素数が1または2Xの全ての元は順序同値である(例えば,{0}{0,1}{2}{0}よりこれらは全て順序同値).よって,の狭義擬順序と付随する同値関係は,A,BXに対して以下を満たす:
AB(#A,#B){(0,1),(0,2),(0,3),(1,3),(2,3)},AB(#A,#B){(0,0),(1,1),(1,2),(2,1),(2,2),(3,3)}.
ただし,ここで集合の要素数を#()で表記した.この弱順序は要素数により優劣をつけ,加えて(自明な引き分け以外にも)要素数12の組み合わせを引き分けにする.

このように,狭義弱順序と全擬順序の間の対応関係を紐解くと,引き分け部分をただ付け外ししているだけであることが分かります.狭義弱順序および全擬順序の定義だけを見比べてもこの点が明瞭ではなく一見謎めいていた訳ですが,分かればなんということはありません.

順序付き分割

最後に,順序付き分割です.これはもう同値関係で割るだけです.

X上の同値関係とし,その商集合X/上に全順序が備わっているとする.このとき,(X/,)X順序付き分割と呼ぶ.

前二つのいずれかの定義の弱順序を引き分けの同値関係で割ってやれば順序付き分割になります.引き分けを同値類で表し,優劣も同値類の間でつけるということです.そう難しくないですね.また,順序付き分割は list of sets とも呼ばれます.これはデータ構造としての実装を意図した呼び方で,同値類を表す集合が為す全順序の列ということです.

このことを定理として主張にまとめて整理する前に,商と順序に関わる基本的な用語と概念を定義しておきましょう.

商擬順序

(X,)を擬順序集合とし,その上の同値関係をR,商写像をq:XX/Rとする.二項関係の推移閉包を()+で表記する.(R):=(q×q)[{()R}+]で定まる商集合X/R上の擬順序Rを,Rによる商擬順序と呼ぶ.これはすなわち,全ての二点q(x),q(x)X/に対して,
q(x)Rq(x)X上の有向道(xi)i=0nが存在してx=x0x1xn=x
Rを定義するのと等しい.ただし,ここで有向道の各有向辺xixi+1xixi+1またはxiRxi+1いずれか少なくとも一方の成立を意味するものとする.また,擬順序集合の同値関係による商を(X,)/R:=(X/R,R)と表記する.

商順序は,商写像q:XX/Rが順序を保つような最小の擬順序と言い換えてもよいです.したがって,始域側が半順序であったとしても,割り方によっては終域側に半順序が入るとは限りません.

擬順序に付随する同値関係による商であれば商順序が必ず半順序になります.というのも,反対称律が成り立たない順序同値な部分を同一視して一点につぶすためです.擬順序から半順序を得る特別なこの商の構成は,実は半順序集合の圏から擬順序集合の圏への包含関手の左随伴を与えます.圏論の言葉では,一般に包含の左随伴はリフレクションと呼ばれ,今の場合は半順序集合リフレクションと呼べるものです(英語なら poset reflection と短く表現できスマートですが日本語だと長ったらしくてちょっと残念ですね……).グラフ理論の言葉では凝縮という用語もあります(割愛しますが同じような操作です).

擬順序の引き戻し

集合Xから擬順序集合(Y,)への写像をfとする.(f):=(f×f)1[()]で定まるX上の擬順序ffによる引き戻しと呼ぶ.これはすなわち,全ての二点x,xXに対して,
xfxf(x)f(x)
で擬順序fを定義するのと等しい.

引き戻した擬順序は,fが順序を保つような最大の擬順序と言い換えてもよいです.終域側が半順序であったとしても,引き戻し方によっては始域側に半順序が入るとは限りません.

さて,自然な商で全擬順序の半順序集合リフレクションをとれば順序付き分割になり,逆に順序付き分割を商写像で引き戻してやれば全擬順序が得られます.リフレクションと引き戻しによって全擬順序と順序付き分割が対応することを定理の形でまとめておきます.

X上の全擬順序とXの順序付き分割は以下の関係により一対一対応する.

  1. 全擬順序に対して付随する同値関係による商(X,)/は順序付き分割である.
  2. 順序付き分割(X/,)に対して商写像q:XX/によるの引き戻しは全擬順序である.

これも難しくないですが折り畳んでおきました.是非自分で証明してみてください.

(i)の証明
を全擬順序とし,付随する同値関係による商順序をとする.q:XX/を商写像とする.()()に注意すると,商の定義より
()=(q×q)[{()()}+]=(q×q)[()+]=(q×q)[()].
ここで,の完全性と商写像が全射であることより,
()()=(q×q)[()()]=(q×q)[X2]=(X/)2.
つまり,は全順序であり,商順序集合はXの順序付き分割を与える.
(ii)の証明
(ii) (X/,)を順序付き分割,q:XX/を商写像とする.引き戻しの定義との完全性より,
(q)(q)=(q×q)1[()()]=(q×q)1[(X/)2]=X2.
つまり,引き戻した順序qは全擬順序である.
一対一対応の証明
(i)と(ii)の対応
()(q×q)[()],()(q×q)1[()]
は互いに逆写像の関係にある.
有限集合の冪集合の要素数による弱順序付け
有限集合Sとその冪集合X=2Sを考える.ランク関数f:XNf(A):=#AAの要素数)で定める.ランク関数で引き戻したX上の擬順序をfとすると,これは明らかに全擬順序である.付随する同値関係fによる商(X,f)/fは,要素数が同じSの部分集合を同一視し,要素数の大小により同値類間の大小を比べる全順序が入った順序付き分割である.特に,全順序集合として(X,f)/f({0,1,,#S},)は明らかに順序同型である.

まとめ

どの弱順序概念も引き分けの形式化が異なるだけで,完全性を持つ順序であることが本質的には重要です.当然,割ればただの全順序です.これを聞いて「さっさと同一視して全順序だけでよくね?」と思うのが同一視大好きな数学の人の考え方で,引き分けの情報が乗っている部分に価値があると思うのがデータ構造大好きな計算機科学側の人の考え方です.知らんけど.どちらの考え方に立っても順序付き分割の方に行き着くというのは興味深いですね.

ところで,実は地味に証明を頑張りました.完全性が本質的であることが一目で分かるよう,そして対応関係を式で追って「そりゃそうだ」と思えるよう,だいぶ意識しました.始めは元をとるオーソドックスな証明を書いたのですが,推敲を重ね結果的に元をとらない証明になりました. 前の関係代数の記事 と同じで,意識的に元をとらなかった訳ではないのですが.必然というか二項関係を集合論的に操作するのはやはり相性が良いですね.畳んだ証明を飛ばした人も是非見直して来てください(笑).

せっかくなので今回出てきた諸性質をまた関係代数版とで並べた表にしておきましょう.まぁ,今回は最初から最後まで二項関係のグラフを重用していたので右側の列をずっと使っていましたが.

名前定義関係代数での言い換え
狭義擬順序xyxy()()
否定xRyR (=X2R)
比較可能x<yx>y()=(<)(>)
比較不能xyxy()=()()
非反射律x. xxIX()
非対称律x,y. x<yxy(<)()
完全律x,y. xyxy()()=X2
付随同値関係xyxy()() (=())
定理1(i)(引き分けの追加)(<)(<)()
定理1(ii)(引き分けの除外)()()()
定理2(i)(引き分けによる商)()(q×q)[()]
定理2(ii)(商による引き戻し)()(q×q)1[()]

本当は GW 中に投稿したかったのですが,色々調べたり推敲していたらずるずると GW が明けてしまいました.それでは今回はこの辺で.気が向いたら関係代数シリーズがまた続くかもしれませんね.

参考文献

投稿日:58
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

UDA です.応用数学をしています.

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. 弱順序とは
  2. 基本的な用語と記法の導入
  3. 狭義弱順序
  4. 全擬順序
  5. 順序付き分割
  6. まとめ
  7. 参考文献