圏論の図で見る順序
(abuseofnotation.github.io)- 要素集合上の二項関係が反射性・推移性・反対称性のような法則を満たすと、順序構造が成り立つ
- 線形順序は任意の2要素が比較可能な構造で、全順性を取り除くと半順序になる
- 半順序では鎖、最大元・最小元、join・meet、Hasse 図によって構造を把握できる
- 色の混合、可除性、集合の包含関係は半順序の例であり、join と meet をともに持つ場合はlatticeをなす
- preorderは反射性と推移性だけを持つ構造で、あらゆる preorder は任意の2対象のあいだに高々1つの射しかない圏として解釈できる
順序
- 順序は要素の集合とその上の二項関係から構成され、特定の法則を満たすと数学的構造をなす
- 順序の基準そのものよりも、要素同士の関係がどのような性質を持つかが核心
- 二項関係とは集合の2要素のあいだの関係であり、矢印でも表せる
- 順序は、集合論では元の集合と自分自身との直積の部分集合として、プログラミングでは2つのオブジェクトを比較する関数の形で表現できる
- ただし、どんな比較関数や要素対の集合でも順序を定義できるわけではなく、初期配置と無関係に一貫した結果を与えるには一定の規則が必要になる
線形順序
-
線形順序はすべての要素が互いに位置づけられる順序であり、ある要素が別の要素より前にあるかどうかが曖昧でない構造
- 例として、光の波長の長さや虹における並びに基づく色の順序が挙げられる
- 線形順序は反射性、推移性、反対称性、全順性を満たす二項関係として定義される
- この4つの法則が順序関係を構成する条件である
-
反射性
- すべての要素は自分自身以上でなければならず、任意の $a$ に対して $a \le a$ が成り立つ
- これは基底事例を扱う規則であり、逆に自分自身と関係しないように定義すると strict order に似た別種の構造になる
-
推移性
- $a \le b$ かつ $b \le c$ なら $a \le c$ でなければならないという規則
- 順序の本質を大きく規定する法則
-
反対称性
- 矛盾した比較結果を禁じる規則であり、$x \le y$ かつ $y \le x$ である場合は $x = y$ のときにのみ許される
- 同率が許されないという表現とともに整理される
-
全順性
- 任意の2要素は必ず比較可能でなければならず、任意の2要素について $a \le b \lor b \le a$ が成り立つ
- どの2要素についても、一方が他方以上でなければならない
- 全順性は $a$ と $b$ が同じ場合を含むので、反射性を特殊な場合として含んでいる
- 全順性を取り除くと 半順序 になり、線形順序は total order とも書かれる
-
自然数の順序
- 自然数は以上の関係のもとで線形順序をなす
- すべての有限線形順序は、最初の要素を1、2番目の要素を2に対応させることで、自然数の部分集合と同型になる
- したがって、同じ大きさを持つすべての有限線形順序は互いに同型である
- 圏論の観点では、すべての有限線形順序と大半の無限線形順序の図式が同じように見えることも触れられる
半順序
- 半順序は線形順序から全順性を取り除いた構造であり、反射性、推移性、反対称性だけを保つ
- partially-ordered set、poset という名称も使われる
- すべての線形順序は半順序だが、すべての半順序が線形順序であるわけではない
- 半順序は同値関係ともつながっており、同値関係の対称性の代わりに反対称性が入った構造である
- サッカーの実力比較の例では、直接または間接に比較可能な一部の人物だけなら線形順序が可能だが、互いに試合をしたことのない人物が含まれると非線形構造となり、半順序が形成される
- 半順序では、誰がより優れているかという問いに常に決定的な答えを与えられるとは限らない
-
鎖
- 半順序は複数の線形部分集合から成ることがあり、そのような線形部分集合を chain と呼ぶ
- 例として $m \to g \to f$ と $d \to o$ の2つの鎖が示される
- 鎖は完全に分離している必要はなく、すべてのつながりが1対1に連なって1本の鎖にまとまってしまわない限り、半順序は保たれる
- 例では $d \le g$ と $f \le g$ は分かるが、$d$ と $f$ の関係は未定である
-
最大元と最小元
- ある要素 $a$ がすべての他の要素 $x$ に対して $x \le a$ を満たすなら、その要素は greatest element である
- こうした要素を持つ半順序もあり、例の図式では $m$ が greatest element である
- 複数の要素がすべて他の要素より大きくても、それらが互いに同一でなければ greatest element は存在しない
- 同様に least element も定義される
-
join
- 2つの要素に対する最小上界を join と呼ぶ
- 定義条件は2つある
- $A \le G$ かつ $B \le G$ でなければならない
- $A$ と $B$ より大きい任意の別の要素 $P$ に対して $G \le P$ でなければならない
- ある要素が別の要素より大きいなら、join は大きい方の要素そのものである
- 線形順序では任意の2要素の join はそのまま大きい方の要素になる
- 同じ大きさの複数の上界があると join は存在せず、join は一意でなければならない
-
meet
- 2つの要素以下である要素のうち最も大きい要素を meet と呼ぶ
- join と同じ規則が逆向きに適用される
-
Hasse 図
- この節で使う図式は Hasse diagrams である
- より大きい要素を常により上に配置するという追加の規則がある
- 矢印があるなら、矢印の向かう先の点は常により上に位置する
- この配置によって、2点の上下関係を見るだけで比較でき、join も共通につながる要素のうち最も低いものを探すことで識別できる
-
色の混合の半順序
- 各色がそれ自身を含む色へ向かうように定義した color-mixing partial order が示される
- 任意の2色の join は、その2色を混ぜたときにできる色である
-
割り切れることによる数の半順序
- 数を大きさではなく可除性で並べると半順序になる
- $a$ が $b$ を割り切るなら、$a$ は $b$ に先行すると定義する
- 例として $2 \times 5 = 10$ なので、2 と 5 は 10 に先行するが、3 は 10 に先行しない
- この順序では、join は 最小公倍数、meet は 最大公約数 である
-
包含の半順序
- いくつかの集合が共通要素の一部を含むとき、inclusion order を定義できる
- 集合 $a$ が $b$ を含む、あるいは言い換えると $b$ が $a$ の部分集合であるとき、$a$ が $b$ に先行する
- この場合、join は 和集合、meet は 共通部分 である
- 各集合に含まれる色を混ぜると、先に見た色混合の半順序と同じ構造になる
- 数の可除性順序は、重複を許す素数集合または prime powers の包含順序と同型である
- これは、すべての数が素数の積としてただ1通りに表せるという算術の基本定理によって確認できる
Birkhoff の表現定理
- 色の混合と数の可除性の半順序は、どちらもある基本要素の取りうる集合の組合せに対する包含順序として表現できる
- 前者では基本要素は原色、後者では素数または素数冪である
- どの有限半順序がこのように表せるかを Birkhoff’s representation theorem が規定する
- 条件は2つある
- すべての要素対について join と meet が存在する
- join と meet が互いに 分配的 であること。記法 $∨$, $∧$ を使えば $x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z)$
- 条件は2つある
- すべての要素が join と meet を持つ半順序は lattice である
- それらの演算が互いに分配的なら distributive lattice である
- 包含順序を構成する「素数的」な要素とは、他の要素の join として表せない要素であり、join-irreducible elements と呼ばれる
- この定理は、各 distributive lattice は自分自身の join-irreducible elements の inclusion order と同型であるという形でも述べられる
- distributive lattice でない半順序も inclusion order と同型でありうるが、その場合は可能な組合せをすべて含んではいない inclusion order に対応する
格子
- lattice は、任意の2要素が join と meet を持つ半順序である
- すべての lattice は半順序だが、すべての半順序が lattice であるわけではない
- ある規則で生成された多くの半順序は distributive lattice であり、前節の例も完全に描けば distributive lattice になる
- 色の混合の例では、上側に黒い球、下側に白い球を追加する
- そうしないと上側の3要素には join がなく、下側の3要素には meet がない
-
有界格子
- greatest element と least element の両方を持つ lattice を bounded lattice と呼ぶ
- 色混合 lattice では黒い球が greatest element、白い球が least element である
- すべての有限 lattice は bounded であることにも触れられる
順序同型
- 順序同型とは、2つの順序の基底集合のあいだの可逆関数であり、順序の矢印を保存する関数である
- 数の可除性順序と素数の包含順序を例にすると、2つの関数で構成される
- 素数の包含順序から数の順序へ向かう関数は、集合要素の乗法である
- 数の順序から素数の包含順序へ向かう関数は、数を積に分解する prime factorization である
- 順序同型の核心条件は、2要素 $a$, $b$ に対して $a \le b$ であることと、そのときに限って $F(a) \le F(b)$ である
- このような関数は order-preserving 関数と呼ばれる
前順序
- preorder は線形順序から 反対称性 を取り除いた構造であり、反射性 と 推移性 だけを保つ
- 比較可能性の観点で見ると
- 線形順序では $a \le b$ または $b \le a$
- 半順序ではそのどちらかであることも、どちらでもないこともある
- 前順序ではそのどちらか、どちらでもない、あるいは 両方とも真 もありうる
- 前順序は日常的な意味での順序とは異なり、任意の点から別の点へ矢印が向かいうる
- サッカーで「誰が誰に勝ったか」を、直接勝利だけでなく間接勝利まで含めてモデル化する例が示される
- 推移性のため、間接勝利も直接の関係のように追加され、その結果、循環関係があると複数の対象が互いにすべて結びついた構造になる
-
前順序と同値関係
- 前順序は 半順序 と 同値関係 の中間にある構造
- 異なるのは (反)対称性 の点だけだからである
- 前順序の中で互いに双方向につながった要素は 対称性 を満たすため、同値関係をなす
- それらの要素をまとめると、前順序の equivalence classes ができる
- 各同値類どうしのつながりだけに移すと、そのつながりは 反対称性 を満たすようになり、半順序をなす
- したがって、すべての前順序に対して その前順序の同値類上の半順序 を定義できる
前順序と圏
- 前順序の 推移性 は、$a \le b$ と $b \le c$ があれば $a \le c$ が生じる規則であり、関係の合成として解釈できる
- 圏の定義には次の2条件が含まれる
- 各対象に 恒等射 が存在する
- 適切な2つの射を 合成 でき、その合成が結合的である
- 前順序では推移性が合成を担い、反射性 が恒等射の役割を果たす
- したがって すべての前順序は圏である
- 一般の圏では2対象のあいだに複数の射がありうるが、前順序では任意の2対象のあいだに 高々1つの射 しか存在しない
- $a \le b$ があるかないかのどちらかだからである
- モノイドが1つの対象を持つ圏であるのと同様に、順序は2対象のあいだに高々1つの射しか持たない圏として整理できる
- この性質のため、前順序では すべての図式が可換 である
-
半順序と前順序の圏論的性質
- 半順序も前順序もともに前順序の特殊な場合なので、圏でもある
- 前順序は圏論では skeletal categories として言及され、同型な対象が区別されたまま共存しない圏である
-
積と余積
- 圏の coproduct の定義は2つの射 $A \to A + B$, $B \to A + B$ と普遍性から成る
- これは順序における join の定義と正確に同じ形である
- 順序ではすべての射が一意なので、「より大きい」が「一意な射が存在する」に対応する
- したがって 前順序の圏における categorical coproduct は join である
- 双対性により product は meet に対応する
-
形式的定義
- 圏論では、順序のように2対象のあいだに高々1つの射しか持たない圏を thin categories と呼ぶ
- すべての前順序はこのような thin category と見なせ、逆にそのような圏は前順序として解釈できる
- thin category は、一般の圏より理解しやすい文脈で圏の概念を探るために利用される
- meet と join を理解すると、より一般的な圏の概念である product と coproduct を理解する助けにもなる
- また、対象のあいだにある複数の射の違いには関心がなく、単純な構造だけが必要なときに有用な枠組みでもある
1件のコメント
Hacker Newsのコメント
[1, 3, 2].sort((a, b) => { if (a > b) { return true } else { return false } })のようなコードは有効な comparatorではない。API は負数、0、正数を期待しているのに boolean を返しており、私の Chrome では[1, 3, 2]のままだった。私には、記事の数学的正確さもこれと同じ程度に見え、詳しい指摘はこのコメントにまとめてある<=が成り立つかどうかを確かめる問題に還元できる。もちろん慣れるまでにはかなり考える必要があるが、逆に日常的な作業へ何度も持ち込んでいけば、だんだん親しみが湧いてくる。そうなるとテストを見ながら「この条件式はある preorder としてモデル化できそうだな」と感じられるようになる