順序集合のカン拡張と特徴述語論理 - 檜山正幸のキマイラ飼育記 (はてなBlog)

圏論における随伴系やモナドの概念を、順序集合に関して考えるとガロア接続や閉包作用素になります。同様に、圏論におけるカン拡張を順序集合に関して考えることができます。が、それだけだと実感に乏しく面白くもありません。カン拡張（右カン拡張と左カン拡張）を、述語論理の限量子と捉えてみます。

内容：

圏と順序集合
基本的な言葉と記法
劣拡張と最大劣拡張
ミート完備な順序集合
最大劣拡張の構成
最小優拡張と書き方の約束
特徴述語論理
おわりに

圏と順序集合

圏論に関する話を、順序集合に関する話にダウングレードすると、議論が容易になります。例えば、2つの関手が随伴対であることは、2つの単調写像がガロア接続を形成することと同じです。それについては：

順序随伴性：ガロア接続の圏論

モナドの順序的対応物に関しては：

順序集合の上でモナドなど

「圏 → 順序集合」というダウングレードは簡単です。なぜなら、順序集合は特殊な圏とみなせるからです。Cがやせた圏〈thin category〉とは、次が成立することです。

A, B∈|C| に対して、ホムセット C(A, B) が空集合か単元集合のどちらか。

やせた圏は、プレ順序集合〈preordered set〉と同じです。さらに、やせた圏Cが次の性質を持てばとてもやせた圏〈very thin category〉です。

C(A, B) ≠ $\emptyset$ かつ C(B, A) ≠ $\emptyset$ ならば、A = B

とてもやせた圏は順序集合になります。より詳しくは次を参照：

はじめての圏論その第3歩：極端な圏達

何か圏論の一般的な概念があったとき、やせた圏／とてもやせた圏に制限すれば、それだけでプレ順序集合／順序集合に関する概念が出てきます。

基本的な言葉と記法

カン拡張に関しては、ここでは触れません。次の記事を参照してください。

圏の一般論と順序の理論の対応関係もいちいちは指摘しませんが、主要な用語の対応は次の表のとおりです。

圏の一般論	順序の理論
右拡張	劣拡張
右カン拡張	最大劣拡張
左拡張	優拡張
左カン拡張	最小優拡張

「カン拡張における上下左右：入門の前に整理すべきこと」で使った記号と、この記事内の記号との対応は：

圏の一般論	順序の理論
圏 C, D, E	順序集合 A, B, C
関手 K:C→D	単調写像 k:A→B
関手 F:C→E	単調写像 f:A→C
関手 G, H:D→E	単調写像 g, h:B→C
自然変換 α::F⇒G:C→D	不等式 f ≦ g on A in B
右カン拡張 ^KF	最大劣拡張 ^kf
左カン拡張 _KF	最小優拡張 _kf

ここから先、A, B, C などは順序集合を表し、その順序は一律に'≦'で表します。f, g, h などは単調写像〈{monotone | monotonic} {map | mapping | function}〉を表します。順序集合AからBへの単調写像の全体を B^A または [A, B] と書きます。AとBが順序集合のとき、次の文はすべて同じ意味です。

f:A→B は単調写像
f∈B^A
f∈[A, B]

f, g∈[A, B] に対して、f ≦ g は次のように定義します。

f ≦ g :⇔ ∀a∈A.( f(a) ≦ g(a) )

a, b∈A に対して、a ≦ b であることを次のようにも書きます。

a ≦ b in A

f ≦ g in [A, B] のことを次のようにも書きます。

f ≦ g on A in B

圏のホムセットと同じ記法を順序集合に対しても使います。A(a, b) は次のような集合です。

A(a, b) := if a ≦ b then {(a, b)} else $\emptyset$

この定義より、

A(a, b) は、空集合か単元集合のどちらか。
A(a, b) ≠ $\emptyset$ ⇔ a ≦ b

劣拡張と最大劣拡張

k:A→B と, f:A→C を2つの単調写像とします。g:B→C が、kに沿ったfの劣拡張〈lower extension of f along k〉だとは、次の不等式が成立することです。

任意の a∈A に対して、g(k(a)) ≦ f(a)

A⊆B で、kが包含写像（埋め込み写像）の場合を考えると：

fは、Bの部分集合Aでしか定義されてない。
gは、B全体で定義されている。この意味で拡張。
A上では、g ≦ f が成立しているので、gは順序的に劣〈下方 | lower〉である。

実際にはkは何でもいいのですが、上記の特殊な状況を考えると、劣拡張という呼び名が納得できるでしょう。ただし、kが包含写像でない場合は、「拡張」という呼び名は、国語辞書的にはまったく不適切になります。「概念が一般化されると呼び名が不適切になる」ことはよくあることなので、諦めましょう*1。

（kに沿った）fの劣拡張の全体を LowExt(k, f) とすると、

LowExt(k, f)⊆[B, C]
[B, C] の順序をそのまま受け継いで LowExt(k, f) も順序集合。

順序集合 LowExt(k, f) に最大元が在ることは保証されませんが、もし最大元があれば、それを、fの最大劣拡張〈greatest lower extension〉と呼びます。gが、（kに沿った）fの最大劣拡張であるとは次のことです。

g:B→C は、kに沿ったfの劣拡張である。
h:B→C がkに沿ったfの劣拡張であるならば、h ≦ g on B in C 。

最大劣拡張が存在するなら一意です。g, g':B→C が、kに沿ったfの最大劣拡張とします。gが最大劣拡張でg'が劣拡張であることから g' ≦ g 、同様に g ≦ g' 、これらより g = g' です。

Cがタチの良い順序集合のとき、k:A→B と f:A→C を元にして最大劣拡張を構成することができます。Cに要求される性質（タチの良さ）と、最大劣拡張の具体的構成を次節以降で述べます。

ミート完備な順序集合

Aが順序集合で、X⊆A とします。このとき、次のような要素 a∈A が存在すれば、それをXのミート〈meet〉と呼びます

∀x∈X.( a ≦ x )
b∈A が ∀x∈X.( a ≦ x ) を満たすならば、b ≦ a

一番目を満たすaは、Xの下界〈かかい | lower bound〉といいます。二番目の条件から、aは下界のなかで最大なものなので、ミートを最大下界〈greatest lower bound〉とか下限〈infimum〉とも呼びます。

AとXの選び方により、AにおけるXのミートは存在したりしなかったりですが、存在するなら一意に存在します（練習問題）。そのミートを、次のように書きます（どの書き方でもよい）。

∧_A(X)
inf_A(X)
glb_A(X)

ここでは、∧_A(X) という書き方を使い、Aが分かっているときは単に ∧(X) とも書きます。Iがインデックス集合で、α:I→A が写像のとき、∧(αの像) を色々な書き方で表します。

$\bigwedge_{i \in I} \alpha_i$
$\bigwedge (i \in I |\: \alpha_i)$
$\bigwedge (\alpha_i |\: i \in I)$
$\bigwedge \{\alpha_i |\: i \in I\}$

書き方の相違はホントにどうでもいいことなので、主に ∧(i∈I | α(i)) を使います（'∧'をデカくもしない）。

順序集合Aが、任意の X⊆ A に対してミートを持つとき、ミート完備〈meet complete〉と呼びます。Aがミート完備なら、Pow(A)をAのベキ集合として、写像

∧:Pow(A)→A

がチャンと定義されている〈well-defined〉ことになります。

Aがミート完備なら、任意の写像（インデックス族） α:I→A に関して、∧(i∈I | α(i)) は ∧(αの像) と同じなのでやはりチャンと定義されています。

最大劣拡張の構成

k:A→B, f:A→C という単調写像がある状況で、kに沿ったfの最大劣拡張を構成しましょう。ただし、Cはミート完備であるという条件を付けます。

上記のような k, f が与えられているとして、g:B→C を次のように定義します。

b∈B に対して、g(b) := ∧(x∈k^-1(b)| f(x))

ここで、k^-1(b) は、k:A→B の逆像集合です（記法k^-1が逆写像を意味しないので注意）。k^-1(b)はAの部分集合で、fをk^-1(b)に制限した写像（インデックス族） k^-1(b)→C に対するミートは、Cのミート完備性から一意に存在します。したがって、b|→g(b) はチャンと定義された写像です。

今定義した g:B→C が、kに沿ったfの最大劣拡張であることを示すには、次の2つのことを示すことになります。

gは、kに沿ったfの劣拡張である。
hがkに沿ったfの劣拡張ならば、h ≦ g 。

一番目を示しましょう。a∈A に対して、

g(k(a)) ≦ f(a)

が言えればOKです。gの定義から、x∈k^-1(b) ⇒ g(b) ≦ f(x) ですが、b = k(a) と置けば、a∈k^-1(b) なので、g(k(a)) = g(b) ≦ f(a) が成立します。これで一番目は示せました。

次にニ番目を示しましょう。b∈B に対して、

h(b) ≦ g(b)

が言えればOKです。gの定義 g(b) := ∧(x∈k^-1(b)| f(x)) から、c∈C がなんであっても、

[ア] 任意の x∈k^-1(b) に対して c ≦ f(x) ならば、c ≦ g(b)

b = k(a) となるaが存在するときを考えます。hがfの劣拡張であることから、

[イ] h(b) = h(k(a)) ≦ f(a)

上記の[ア]に、x←a, c←h(k(a)) と代入すれば、次が出ます。

[ウ] a∈k^-1(b) だから、h(k(a)) ≦ f(a) ならば、h(k(a)) ≦ g(b)

[イ]より実際に h(k(a)) ≦ f(a) なので、[ウ]を考慮すれば、

h(b) = h(k(a)) ≦ g(b) in C

が成立します。

b = k(a) となるaが存在しないときは、g(b) = ∧(x∈ $\emptyset$ | f(x)) = ∧( $\emptyset$ ) = (Cの最大元) 。

h(b) ≦ (Cの最大元) in C

はbがなんでも成立するので、この場合も h(b) ≦ g(b) は言えます。

以上から、bがなんであっても h(b) ≦ g(b) となり、gは劣拡張のなかで最大であることが分かりました。

最小優拡張と書き方の約束

今までの議論の不等号の向きを逆にすると、最小優拡張を定義できます。Cに関する条件としてはジョイン完備性を考えます。ほとんど繰り返しですが、ジョイン完備性の定義は書いておきましょう。

X⊆A に対して、次のような要素 a∈A が存在すれば、それをXのジョイン〈join〉と呼びます

∀x∈X.( x ≦ a )
b∈A が ∀x∈X.( x ≦ b ) を満たすならば、a ≦ b

一番目を満たすaは、Xの上界〈じょうかい | upper bound〉といいます。二番目の条件から、aは上界のなかで最小なものなので、ジョインを最小上界〈least upper bound〉とか上限〈supremum〉とも呼びます。Xのジョインが存在するなら一意的です。

順序集合Aが、任意の X⊆ A に対してジョインを持つとき、ジョイン完備〈join complete〉と呼びます。Aがジョイン完備なら、Pow(A)をAのベキ集合として、写像

∨:Pow(A)→A

がチャンと定義されます。

k:A→B, f:A→C の状況で：

g:A→C が、kに沿ったfの優拡張〈upper extension of f along k〉だとは、任意の a∈A に対して、f(a) ≦ g(k(a)) が成立すること。
g:A→C が、（kに沿った）fの最小優拡張であるとは：
1. g:B→C は、kに沿ったfの優拡張である。
2. h:B→C がkに沿ったfの優拡張であるならば、g ≦ h on B in C 。

Cがジョイン完備なとき、gを次のように定義すると、gは、kに沿ったfの最小優拡張になります。

g(b) := ∨(x∈k^-1(b) | f(x))

kに沿ったfの最大劣拡張と、kに沿ったfの最小優拡張を（それがあれば）次の書き方で表すことにします。

(kに沿ったfの最大劣拡張) = ^kf
(kに沿ったfの最小優拡張) = _kf

^kf は、右カン拡張 ^KF の順序集合バージョン、_kf は、左カン拡張 _KF の順序集合バージョンです。

特徴述語論理

k:A→B, f:A→C で、Cがミート完備かつジョイン完備である状況で考えます。順序集合 A, B, C を次のように解釈します。

Aは、個体の領域〈domain of individuals〉と考える。個体の領域を、述語論理では議論の領域〈domain of discourse〉と呼ぶこともある。
Bは、Aに属する個体を特徴づける値・量の領域と考える。
Cは、論理的真偽値の領域と考える。ただし、二値真偽値とは限らない。

Cが真偽値の領域なので、写像 f:A→C は、個体に真偽値を対応させる述語ということになります。Cがミート完備・ジョイン完備であることから、述語に対する ∧, ∨ や、論理定数 T, ⊥ を定義することができます。無限も許す∧演算として全称限量子∀、無限も許す∨演算として存在限量子∃も導入できます。

通常の述語論理でお目にかからないのは、領域Bと写像 k:A→B です。kはBの値によってAの個体を特徴付ける写像と考えます。分かりやすい例は、Bの要素が属性値であるときです。例えば、Aが人の集合で、B = N とします。k:A→B は、人に年齢を対応付ける写像とします。年齢は人を特徴付ける値のひとつです。

年齢とはまったく異なった例として、A⊆B であり、k:A→B は包含写像のときを考えます。この場合、kはAの各個体をより広い“場”であるB内に埋め込んでいます。別な場に置くことも特徴付けと（ちょっと無理矢理に）考えれば、kは特徴付けの写像と言ってもいいでしょう。以下では、k:A→B を特徴付け写像〈characterizer〉と呼びましょう。

個体領域Aと特徴付けのための領域Bも順序集合ですが、離散順序も順序なので、単なる集合 A, B と単なる写像 k:A→B であっても順序集合と単調写像だとみなせます。

これで、順序集合／単調写像に関する構造を述語論理として捉える状況設定が出来たので、kに沿ったfの最大劣拡張 ^kf 、kに沿ったfの最小優拡張 _kf を限量子付き命題として解釈しましょう。次の記法を導入します。

(^kf)(b) = (∀x∈A, k(x) = b.f(x))
(_kf)(b) = (∃x∈A, k(x) = b.f(x))

これらの命題（述語）は、B上の命題（述語）になり、そのインフォーマルな内容的解釈は、

k(x) = b であるすべてのxに対して f(x) である。
k(x) = b であるxで、f(x) であるxが存在する。

B = 1 = {0} として、k:A→B を自明な写像とするとき、∀x∈A, k(x) = 0.f(x) と ∃x∈A, k(x) = 0.f(x) は、特徴付けなしの ∀x∈A.f(x) と ∃x∈A.f(x) に同じになります。一方で、特徴付けを含む論理式の意味は、次の（通常の）論理式と同じです。

∀x∈A.(k(x) = b ⊃ f(x))
∃x∈A.(k(x) = b ∧ f(x))

おわりに

特徴述語論理に関しては、限量子を定義しただけですが、これがカン拡張（の一側面）の論理的対応物なのではないかと思います。述語論理は、ハイパードクトリン（短い記述はココ）などにより定式化できます。特徴述語論理を完全に定式化すると、いったいどんな構造になるのでしょう。

カリー／ハワード／ランベックの教義によれば、「圏論、論理、型理論／プログラム論」のあいだには対応関係（類似性）があるはずです。特徴述語論理をあいだにはさむことによって、カン拡張に対応する型理論／プログラム論的概念が見つかるかも知れません。限量子が関係するなら、依存型っぽいナニカかも知れません（よく知らんけど）。

*1:最近、僕がよくこのテの注意書きをするのは、国語辞書的な解釈に拘る人が、どうも相当数いるらしいと気付いたからです。「拡張してないのに、なんで『拡張』なんだ？」とか気にするのはまったく不毛です。