フランツによる統計的独立性の定義

統計的独立性と線形独立性を共通に語ることは出来るのか?」では、シンプソン〈Alex Simpson〉による独立性構造を紹介しました。シンプソンの独立性は、かなり広い範囲の“独立性”概念をカバーするものです。もうひとつの独立性であるフランツ〈Uwe Franz〉による独立性は、モノイド積を持つ圏をベースに統計的独立性を定式化したものです。この記事では、フランツの独立性をザッと紹介します。

内容:

確率変数の独立性

確率空間を A = (ΩA, ΣA, μA) のように書きます。ΩAは台集合、ΣAはΩA上のσ代数、μAは確率測度です。記号の乱用で ΩA = A として、A = (A, ΣA, μA) とも書きます。

(A, ΣA, μA) が確率空間、(B, ΣB) が可測空間のとき、可測写像 f:(A, ΣA)→(B, ΣB) を(ここでは)確率変数〈{random | stochastic} variable〉と呼びます。台集合のあいだの写像を同じ文字 f:A→B で表し、逆像を対応させる写像を ΣfB→ΣA または f*B→ΣA と書きます。

確率変数 f:(A, ΣA)→(B, ΣB) があると、B上に前送り測度〈誘導測度〉 f*A) を構成できます。前送りされた測度を使って (B, ΣB, f*A)) を作ると、これは確率空間です。よって、確率変数は、確率空間のあいだの測度を保存する写像 f:(A, ΣA)→(B, ΣB, f*A)) とみなせます。

確率空間と測度を保存する可測写像からなる圏をProbとします。上の議論から、確率変数はProbの射とみなせます。そこで、以下では「確率変数=圏Probの射」だとします。

同一の域〈domain〉を持つ2つの確率変数、つまり2つの射 f:A→B, g:A→C in Prob が(統計的に)独立であることを定義しましょう。確率変数 f, g から、σ代数のあいだの射 f*B→ΣA, g*C→ΣA が誘導されます。f*, g* はσ代数のあいだの準同型写像になります。そして、f*, g* による像 Im(f*)⊆ΣA, Im(g*)⊆ΣA はσ代数ΣAの部分σ代数になります。この状況で:

  • f:A→B, g:A→C in Prob統計的に独立〈statistically independent〉であるとは、σ代数ΣAの部分σ代数 Im(f*) と Im(g*) が確率測度μAに関して独立なこと。

ここで、“部分σ代数の確率測度に関する独立性”概念が必要になります。S, T がσ代数ΣAの部分σ代数だとして、これらが確率測度μAに対して独立〈independent〉だとは:

  • 任意の ξ∈S, η∈T に対して、μA(ξ∩η) = μA(ξ)μA(η) が成立すること。

ここで、ξとηはσ代数の要素なので“事象”です。上で言っていることは、Sの事象とTの事象に関して、“確率の積の公式”が成立することです。

2つの像σ代数 Im(f*), Imf(g*) ⊆ΣA が確率測度μA に関して独立であることを丁寧に述べれば:

  • 任意の β∈ΣB, γ∈ΣC に対して、μA(f*(β)∩g*(γ)) = μA(f*(β))μA(g*(γ)) が成立する。

これは、fとgの統計的独立性の定義です。

確率空間のテンソル

A = (A, ΣA, μA) と B = (B, ΣB, μB) が確率空間、つまり圏Probの対象のとき、そのテンソル積 A\otimesB を定義できます。(以下で、Pow(X) はXのベキ集合です。)

  1. A\otimesB の台集合は、直積集合 A×B とする。
  2. A\otimesB のσ代数は、α∈ΣA, β∈ΣA に対する α×β∈Pow(A×B) から生成される Pow(A×B) の部分σ代数で最小なもの*1として定義する。このσ代数を ΣA\otimesΣB と書く。
  3. A\otimesB の確率測度は、μA⊗B(α×β) = μA(α)μB(β) を満たすように定義された ΣA\otimesΣB 上の測度。この測度を μA\otimesμB と書く。

定義を簡単に書けば:

  • A\otimesB := (A×B, ΣA\otimesΣB, μA\otimesμB)

以上で、Probの対象に対するテンソル積は定義できたので、次に、射に対するテンソル積を定義します。

f:A→B, g:C→D in Prob として、f\otimesg:A\otimesC→B\otimesD in Prob を次のように定義します。

  1. f\otimesg の台写像は、f×g:A×C→B×D in Set、(f×g)(a, b) := (f(a), g(b)) 。
  2. f\otimesg のσ代数準同型写像 f*\otimesg*B\otimesΣD→ΣA\otimesΣC は、ΣB\otimesΣD を生成する β×δ(β∈ΣB, δ∈ΣD)に対して、(f*\otimesg*)(β×δ) := f*(β)×g*(δ) として定義される準同型写像。ここで、'×'は部分集合の直積。

ΣA\otimesΣC 上に載っている確率測度 μA\otimesμC のf\otimesgによる前送り測度 (f×g)*A\otimesμC) が、ΣB\otimesΣD 上の確率測度 μB\otimesμD と一致することは、別に証明が必要です(割愛、比較的簡単)。

Probテンソル単位対象〈モノイド単位対象〉Iは次のように定義します。

  1. Iの台集合は、単元集合 1 = {0} 。
  2. Iのσ代数は、ΣI := {\emptyset, {0}}
  3. Iの確率測度は、μI(\emptyset) = 0, μI({0}) = 1 。

以上で、対象に対する演算 (-\otimes-)、射に対する演算 (-\otimes-)、特定された対象Iが決まりました。これらがProbのモノイド構造であるためには、まだ定義すべきこと/証明すべきことがあります。

  1. (\otimes):Prob×ProbProb が二項関手〈双関手〉であることを示す。
  2. 結合律子(結合律の一貫性同型射の族) αA,B,C:(A\otimesB)\otimesC→A\otimes(B\otimesC) を定義する。
  3. 左単位律子(左単位律の一貫性同型射の族) λA:I\otimesA→A を定義する。
  4. 右単位律子(右単位律の一貫性同型射の族) ρA:A\otimesI→A を定義する。
  5. 結合律子のあいだのマックレーンの五角形等式を示す。
  6. 結合律子/単位律子のあいだのマックレーンの三角形形等式を示す。

これらの作業をすれば、(Prob, \otimes, I, α, λ, ρ) が、テンソル積に関してモノイド圏となることが分かります。面倒ではありますが、やれば出来ることなので省略します*2

射影付きモノイド圏とフランツ独立性

Cを(Probとは限らない)モノイド圏とします。記号の乱用で C = (C, \otimes, I, α, λ, ρ) と書きます。C×C は直積圏だとします。Π1:C×CC, Π2:C×CC は直積の第1成分, 第2成分をとる関手とします。

  • Π1(x, y) = x
  • Π2(x, y) = y

モノイド圏C上の射影系〈projections〉とは、2つの自然変換 π1::(\otimes)⇒Π1:C×CC, π2::(\otimes)⇒Π21:C×CC です。π1, π2 には、自然変換であること以外に特に条件はありません。π1, π2 を成分で書けば:

  • π1A,B:A\otimesB→A
  • π2A,B:A\otimesB→B

射影系を備えたモノイド圏を、射影付きモノイド圏〈monoidal category with projections〉と呼びます。射影付きモノイド圏のよく知られた例は、モノイド積が直積を与えるデカルト・モノイド圏です。デカルト・モノイド圏には、標準的な射影が備わっています。

(C, π1, π1) が射影付きモノイド圏のとき、同じ域を持つ2つの射 f:A→B, g:A→C (スパンと呼ぶ)に対してフランツの意味の独立性を定義できます。fとgがフランツ独立〈Franz independent〉だとは:

  • h:A→B\otimesC が存在して、f = h;π1B,C, g = h;π2B,C が成立すること。

デカルト・モノイド圏では、すべてのスパンがフランツ独立になります。

フランツ独立性に関する注意

フランツ独立性は、任意の射影付きモノイド圏 (C, π1, π2) に関して定義できます。「独立である」の主語は、Cのスパンです。ただし、前節の定義では、2-スパン(同じ域を持つ2本の射)だけが対象物で、一般的なn-スパン(同じ域を持つn本の射)の独立性は定義されません。

n-スパンに対する独立性を定義するには、n個の射影の族 πn1, πn2, ..., πnn が必要になります。n ≧ 3 に対しては、π1 = π21, π2 = π22 を組み合わせて構成できます。例えば:

  • π31A,B,C := π21(A⊗B),C21A,B : (A\otimesB)\otimesC→A
  • π32A,B,C := π21(A⊗B),C22A,B : (A\otimesB)\otimesC→B
  • π33A,B,C := π22(A⊗B),C : (A\otimesB)\otimesC→C

n = 1 に関しては:

  • π11A := idA : A→A

辻褄を合わせるために n = 0 では:

  • π0 := idI : I→I

これらの射影の系があれば、n-スパンのフランツ独立性が定義できます。Aから出る1-スパン f:A→B は常に独立で、Aから出る0-スパンA(対象のみ)は、A→I という射が在れば独立になります。

有限のインデックスセットIを持つn-スパン (fi:A→Bi | i∈I) がフランツ独立であることは、スパンの射達/射影達と可換図式を構成する射hが存在することです。

  • h:A→\bigotimes_{i\in I}Bi

このhを、n-スパンの独立タプル〈independent tuple〉と呼ぶことにします。2-スパンの場合は独立ペア〈independent pair〉です。0-スパンの独立タプルは A→I という射です。

n-スパンが独立でも、その独立タプルが一意的に存在することは保証されません。「存在するなら一意的である」という条件を付けると話が簡単になることもあるので、射影付きモノイド圏が一意存在の性質を持つとき、シャープsharp | 鋭利〉であるということにします。

  • 射影付きモノイド圏 (C, π1, π2) がシャープ :⇔ n-スパンの独立タプルが存在するなら一意的である。

n-スパンには0-スパンも入ります。射影付きモノイド圏がシャープであり、すべてのn-スパンが独立である(独立タプルを持つ)とき、その射影付きモノイド圏はデカルト・モノイド圏になります。デカルト・モノイド圏は、射影付きモノイド圏のなかで、独立タプルの存在と一意性において最も“強い”圏として特徴付けられます。

統計的独立性とフランツ独立性

2-スパンのケースで、最初に述べた確率変数の統計的独立性と、射影付きモノイド圏Probのフランツ独立性が同じであることを示します。

ここで、念の為繰り返し注意をします; (A, ΣA, μA) という書き方は記号の乱用で、ほんとは (ΩA, ΣA, μA) と書くべきです。f:(A, ΣA, μA)→(B, ΣB, μB) の構成素は、ΩfA→ΩB と ΣfB→ΣA ですが、台写像(台集合のあいだの写像)Ωfを単にfと書き、σ代数の準同型写像Σfをf*と書きます(もちろん、記号の乱用で)。

Probには、確率空間のテンソル積(と可測写像テンソル積)によりモノイド構造が入ります。射影 π1A,B:A\otimesB→A, π2A,B:A\otimesB→B in Prob は、台集合の射影(集合圏の射影)と対応するσ代数の準同型写像(部分集合の引き戻し)で定義します。こうして定義された射影が、確率測度を保存することは容易に示せます(つうか、そうなるようにテンソル積を定義している)。

いま定義した射影により、(Prob, π1, π2) は射影付きモノイド圏になります。確率空間にその台集合を対応させる忘却関手 Ω:ProbSet は、Setも射影付きモノイド圏とみなして“射影付き圏のあいだの関手”になります。確率空間のテンソル積を集合の直積に移し、テンソル積確率空間の射影を直積集合の射影に移します。

Probが射影付きモノイド圏になったので、フランツ独立性を定義できます。まず、後で使う補題として、次の等式を示します; f:A→B, g:A→C in Prob に対して、h:A→B\otimesC in Prob がfとgの独立ペア(のひとつ)だとして:

  • [補題] α∈ΣA, γ∈ΣC に対して、h*(β×γ) = f*(α)∩g*(γ)

hがfとgの独立ペアなので、

  1. π1\circh = f : A→B in Prob
  2. π2\circh = g : A→C in Prob

これより、

  1. h*\circ1)* = f* : ΣB→ΣA
  2. h*\circ2)* = g* : ΣC→ΣA

α∈ΣA, γ∈ΣC に対して、

  1. (h*\circ1)*)(β) = f*(β)
  2. (h*\circ2)*)(γ) = g*(γ)

1)*(β) = β×C, (π2)*(γ) = B×γ なので、

  1. h*(β×C) = f*(β)
  2. h*(B×γ) = g*(γ)

h*(β×γ) = h*(β×C ∩ B×γ) = h*(β×C)∩h*(B×γ) に、すぐ上の等式を代入すると:

  • h*(β×γ) = f*(β)∩g*(γ)

これで補題の等式が示せました。

次に、fとgがフランツ独立(独立ペアを持つ)ならば、fとgは、確率変数として統計的に独立なことを示しましょう。

任意の β∈ΣB, γ∈ΣC に対して、μA(f*(β)∩g*(γ)) を計算します。補題から:

  • μA(f*(β)∩g*(γ)) = μA(h*(β×γ))

hが確率測度を保存することから、μA(h*(-)) は μB\otimesC(-) に等しいので、

  • μA(f*(β)∩g*(γ)) = μB\otimesC(β×γ)

μB\otimesCの定義から、μB\otimesC(β×γ) = μB(β)μC(γ) なので、

  • μA(f*(β)∩g*(γ)) = μB(β)μC(γ)

fもgも確率測度を保存することから、μA(f*(β)) = μB(β) かつ μA(g*(γ)) = μC(γ) なので、

  • μA(f*(β)∩g*(γ)) = μA(f*(β))μA(g*(γ))

これは、確率変数fとgが統計的に独立なことです。以上で、フランツ独立性から確率変数の統計的独立性が従うことが分かりました。

逆方向の命題「確率変数fとgが統計的に独立なら、fとgはフランツ独立である」も示す必要がありますが、台写像デカルト・ペア <f, g> : A→B×C in Set を台写像とする確率空間のあいだの射 h:A→B\otimesC を作って、それがfとgの独立ペアになることを示せばOKです。

おわりに

前回の記事「統計的独立性と線形独立性を共通に語ることは出来るのか?」で紹介したシンプソン独立性と、今回の記事のフランツ独立性を一緒に考えて、2つの独立性の関連を探ると、統計的独立性に関する理解が深まると思います。

また、シンプソン独立性/フランツ独立性は、統計的独立性以外の“独立性”概念の分析にも利用できるでしょう。

*1:射影 A×B→A と A×B→B が可測写像になるような最小のσ代数と言っても同じです。

*2:モノイド圏におけるマックレーンの五角形・三角形等式(一貫性制約)については「モノイド圏と加群圏に関するフォークロアとマックレーン五角形・三角形」に書いてあります。

統計的独立性と線形独立性を共通に語ることは出来るのか?

統計的独立性は確率・統計において重要な概念です。「独立」という言葉は色々な分野で使われます。おそらく一番お馴染みな独立性は、統計的独立性ではなくて線形独立性でしょう。単語として「独立」が使われているからといって、統計的独立性と線形独立性が関係するとは考えにくいですよね。

しかし、とある枠組み〈フレームワーク〉のなかでは、二者を統一的に説明することが可能です。

内容:

統計的独立性

確率的な試行をn回するとします。例えば、サイコロを3回ふる(試行=サイコロふり、n = 3)とかです。i回目(1 ≦ i ≦ n)の試行を、確率変数Xiで表現するとして、X1, X2, ..., Xn は、通常は独立だと仮定されます。

幾つかの確率変数が独立であることをチャンと定義するのは、けっこう難しい話になります。が、今は何らかの方法で独立性が定義できたとしましょう。「独立」という言葉は様々な分野で様々な意味で使われるので、サイコロふりなどで現れる独立性は、確率変数の確率的/統計的独立性と呼ぶことにします。ちょっと長すぎるので、次のように省略するのは許します(不用意に「独立性」とは言わない)。

  1. 確率変数の独立性〈independence of random variables〉
  2. 確率的独立性〈stochastic independence〉
  3. 統計的独立性〈statistical independence〉

統計的独立性を定義するために使われる諸々の概念・用語; 「確率変数」、「確率分布」、「母集団」などはだいぶ曖昧で混乱しています。その点については、次の記事とそこから参照されている他の記事を見てください。

フランツの定義とシンプソンの定義

統計的独立性(の一般化)を、圏論的に定義したものとして、ウヴェ・フランツの論文があります。

フランツによる統計的独立性の定義は、2つの確率空間(台集合、σ代数、確率測度の3つ組) (X, ΣX, μX), (Y, ΣY, μY) のテンソル積 (X×Y, ΣX\otimesΣY, μX\otimesμY) に基づいています。フランツの独立性は、必ずしも統計的独立性に限定はされませんが、「テンソル積〈モノイド積〉ありき」から出発します。

統計的独立性の定義が、いつでもテンソル積に基づいているわけではありません。事象の独立性やσ代数の独立性から、確率変数の独立性を定義するのが普通です。むしろ、確率空間のテンソル積を正面から導入するほうが珍しい(あまりやらない)でしょう*1

アレックス・シンプソンも、統計的独立性を含む一般的な独立性概念の圏論的な定式化を提案しています。

シンプソンの独立性は、テンソル積〈モノイド圏のモノイド積〉を使っていません。「個々のケースごとに独立性をどう定義すべきか?」という問題意識ではなくて、「一般的に「独立性」と呼ばれる性質を、できるだけ抽象的に捉えたい」という動機からの定式化です。

この記事では、シンプソンの定義(を多少変更したもの)に基づいて、統計的独立性と線形独立性を一様に説明できる枠組みを構成します。

線形独立性

話を簡単にするために、ベクトル空間は実数体R上の有限次元ベクトル空間に限ります*2。有限次元のR-ベクトル空間と線形写像の圏を FdVectR とします。ベクトル空間のテンソル積(モノイド構造)は考えません。

ベクトル空間Vの部分集合A(A⊆V)の線形独立性はご存知でしょう。単一の部分集合ではなくて、2つの部分集合 A, B⊆V に対して、AとBが線形独立であることを次の条件(すべて満たす)で定義します。

  1. AはV内で線形独立である。
  2. BはV内で線形独立である。
  3. Aが生成するVの部分ベクトル空間と、Bが生成するVの部分ベクトル空間の共通部分はゼロだけ。

この線形独立性の定義をもう少し扱いやすくしましょう。そのために、集合から生成された自由ベクトル空間を使います。集合Aから生成された自由ベクトル空間を R[A]1 とします。この記号のココロは、Aを不定元集合として生成された実係数多項式の集合 R[A] の(同次の)1次式部分ということです。

ベクトル空間Vに対して A, B⊆V ならば、次の写像達が誘導されます。(使っている概念・記号に関しては、この節最後の補足コラムで説明しています。)

  1. 包含写像 i:A→V
  2. 包含写像 j:B→V
  3. iとjのコタプル写像 [i, j]:(A + B)→V
  4. iに伴う線形写像 i#:R[A]1→V
  5. jに伴う線形写像 j#:R[B]1→V
  6. i#とj#のコタプル線形写像 [i#, j#]:R[A]1\oplusR[B]1→V

また、集合AとBの直和を A + B と書けば、次のベクトル空間の同型が成立します。

  • R[A]1\oplusR[B]1 \stackrel{\sim}{=} R[A + B]1

よって、上記の最後のコタプル線形写像は、R[A + B]1→V とみなすこともできます。

さて、A, B⊆V が線形独立であることは、コタプル線形写像を用いて次のように表現できます。

  • コタプル線形写像 [i#, j#]:R[A]1\oplusR[B]1→V が単射である。

より一般に、A1, ..., An⊆V に対して、これらが線形独立であることを次のように定義します。

  • コタプル線形写像 [(i1)#, ..., (in)#]:R[A1]1\oplus ... \oplusR[An]1→V が単射である。

単一の部分集合 A⊆V に対しては、

となり、部分集合の個数に関係せずに、幾つかの部分集合達の線形独立性が定義できます*3

[補足]
集合AとBの直和は、「共通部分〈交わり〉なしの合併」と考えればいいのですが、具体的な定義が欲しいときは:

  • A + B := {(x, i)∈(A∪B)×{1, 2} | (x∈A かつ i = 1) または (x∈B かつ i = 2)}

この具体的な定義を使うことにして、f:A→X と g:B→X のコタプル写像 [f, g]:(A + B)→X は:

  • [f, g](x, i) := if (i = 1) then f(x) else /* i = 2 */ g(x) endif

包含写像とは恒等写像を部分集合に制限したものなので、i, j が包含写像なら:

  • [i, j](x, i) := if (i = 1) then x else /* i = 2 */ x endif

Vはベクトル空間として f:A→V の線形拡張 f#:R[A]1→V は:

  • f#a∈A ξaa) := Σa∈A ξaf(a) (ξaR

線形写像 φ:U→V と ψ:W→V のコタプル線形写像 [φ, ψ]:U\oplusW→V は:

  • [φ, ψ](u, w) := φ(u) + ψ(w)

[/補足]

コスパン独立性

前節で、ベクトル空間Vの部分集合達 A1, ..., An が線形独立であることを定義しました。線形独立性の定義には、n個の線形写像 (i1)#:R[A1]1→V, ..., (in)#:R[An]1→V が使われました。であるならば、n個の線形写像 f1:U1→V, ..., fn:Un→V に対して線形独立性を定義してもいいでしょう。

余域がVであるn個の線形写像 f1:U1→V, ..., fn:Un→V が線形独立であるとは:

  • コタプル線形写像 [f1, ..., fn]:U1\oplus ... \oplusUn→V が単射である。

「独立である」の主語は、n個の集合からn個の線形写像に変化しています。さらに、線形写像を一般的な射に置き換えることにより、任意の圏C上の独立性構造〈independence structure〉を定義します。「独立である」の主語は、n個(むしろn本)のCの射になります。ただし、それらの射の余域は同一です。

Cを圏として、同一の余域を持つn本の射のリスト (f1:A1→B, ..., An→B) をn-コスパ〈n-cospan〉と呼びます。n = 0, 1 の場合、つまり (), (f:A→B) もコスパンとして認めます。射を矢印で描くと、n-コスパンは、ひとつの点に合流する矢の並びになります。n = 0 のときは、先端点である対象Bだけがあると考えます。

Cの、“対象Bを余域とするn-コスパン”の全体を Cospn(C, B) と書きます。Cが小さい圏でないなら、Cospn(C, B) は集合(小さい集合)とは限らず、真クラス〈proper class〉になるかも知れません。なので、「クラス」という言葉を使いますが、サイズの問題はあまり気にしません。次の記号も使います。

  • Cosp(C, B) := \bigcup(n∈N | Cospn(C, B))
  • Cospn(C) := \bigcup(B∈Obj(C) | Cospn(C, B))
  • Cosp(C) := \bigcup(n∈N, B∈Obj(C) | Cospn(C, B))

Cosp(C)は、圏Cのすべてのコスパンのクラスです。

コスパンを構成する射を識別するインデックスには、通常は自然数 1, 2, ..., n を使いますが、任意の有限集合をインデックスセットに許したほうが便利です。コスパンを (fi | i∈I) のように書いたとき、Iは必ずしもNの部分集合とは限らない有限集合だとします。

Cのすべてのコスパンのクラス Cosp(C) の部分クラスを、X, Y などの斜体文字で表すことにします。以下、X, Y などは(圏C上の)コスパンのクラスです。

C上のコスパンのクラスXが次を満たすとき、Xインデックスセットの全単射取り替えに対して安定〈stable under bijective change of index-set〉といいます*4

  • (fi:Ai→B | i∈I)∈X、τ:J→I が全単射のとき、(fτ(j):Aτ(j)→B | j∈J)∈X

今後考えるコスパンのクラスは、常にインデックスセットの全単射取り替えに対して安定だとします。別な言い方をすると、射のリストの並び順は気にしなくてもいいことになります(無視はしないほうがいいけど)。

C上のコスパンのクラスX(インデックスセットの全単射取り替えに対して安定は前提)が次を満たすとき、X複圏〈multicategory〉をなすといいます。

  1. 任意の対象 A∈|C| に対して、単一射からなるコスパン (idA)∈Cosp1(C, A) は X に属する。
  2. (g:Bj→C | j∈J)∈X、j∈J ごとに、(fj,i:Aj,i→Bj | i∈Ij)∈X、このとき、(fj,i;gj:Aj,i→C | (j, i)∈Σ(j∈J | Ij)) 。

二番目の条件は、木の接ぎ木結合〈grafting〉に対して閉じていることです。接ぎ木結合は、m本の枝を持つ木gとm本の木fi(合計(m + 1)本の木)に対して、gの各枝にfiの根を接合して大きな木を作ることです。

ちなみに、今定義した複圏の構造は、対称色付きオペラッド〈symmetric coloured operad〉とも呼びます。

R上の有限次元ベクトル空間の圏FdVectRにおいて、線形独立なコスパン (fi:Ui→V | i∈I) の全体をXとすると*5

  1. Xは、インデックスセットの全単射取り替えに対して安定。
  2. Xは、複圏をなす。

さらに、Xはインデックスセットの全単射取り替えに対する安定性より強い性質を持ちます。それは:

  • (fi:Ui→V | i∈I)∈X、τ:J→I が単射のとき、(fτ(j):Uτ(j)→V | j∈J)∈X

全単射だけではなくて、インデックスセットの単射取り替えに対する安定性〈stability under injective change of index-set〉を持ちます*6

一般に、圏C上のコスパンのクラスCosp(C)の部分クラスXが指定されており、Xがインデックスセットの単射取り替えに対して安定な複圏構造を持つとき、XC上のコスパン独立性構造〈cospan independence structure〉と呼びます。コスパン独立性構造をコスパン独立性とも呼びます。誤解の恐れがなければ、単に独立性ともいいます。

FdVectR上の線形独立なコスパンの全体は、コスパン独立性構造の事例です。

スパン独立性

シンプソンの論文における独立性は、前節のコスパン独立性に対して、「矢印の向きを反対にする」という意味で双対的なものです。

Cを圏として、同一の域を持つn本の射のリスト (f1:A→B1, ..., A→Bn) をn-スパン〈n-cospan〉と呼びます。圏Cの、“対象Aを域とするn-スパン”の全体を Spann(C, A) と書きます。次の記号も使います。

  • Span(C, A) := \bigcup(n∈N | Spann(C, A))
  • Spann(C) := \bigcup(A∈Obj(C) | Spann(C, A))
  • Span(C) := \bigcup(n∈N, A∈Obj(C) | Spann(C, A))

C上のコスパンのクラスXに対して、Xインデックスセットの全単射取り替えに対して安定〈stable under bijective change of index-set〉であることも前節と同様に定義します。

複圏の双対概念を余複圏〈comulticategory〉として、クラスXが余複圏をなすことも前節と同様です。木〈ツリー〉の向きが「葉から根」に対して「根から葉」の向きに変わります。

CのスパンのクラスXがスパン独立性構造〈span independence structure〉だとは:

  1. Xは、インデックスセットの全単射取り替えに対して安定。
  2. Xは、余複圏をなす。
  3. (fi:A→Bi | i∈I)∈X、τ:J→I が単射のとき、(fτ(j):A→Bτ(j) | j∈J)∈X

三番目から一番目は出るので、冗長な条件になっていますが、このほうが分かりやすくでしょう。スパン独立性構造をスパン独立性とも呼びます。誤解の恐れがなければ、単に独立性ともいいます。

シンプソンの独立性は、もうひとつ条件が加わっています。それは:

  • 任意の射 f:A→B に対して、単一の射からなるスパン (f:A→B) はXに所属する。

この条件をシングルトン条件〈singleton condition〉と呼びましょう。このシングルトン条件を独立性構造の定義に入れなかったのは、前節の線形独立性がシングルトン条件を満たさないからです。コスパン独立性、スパン独立性を広い範囲で考えたいなら、シングルトン条件は追加・削除が可能な形にしておいたほうが良さそうです。

確率空間と確率測度を保存する可測写像の圏をProbとすると、確率変数(=確率測度を保存する可測写像)の独立性は、圏Prob上のn-スパン (f1:A→B1, ..., fn:A→Bn) のスパン独立性になります。単一の確率変数からなる1-スパン (f:A→B) は独立とみなすので、圏Prob上の(標準的な)スパン独立性はシングルトン条件を満たします。

コスパン生成性とスパン生成性

コスパン独立性とスパン独立性は互いに双対の関係になります。これとは別な双対性があります。コスパン独立性の別な双対としてコスパン生成性、スパン独立性の別な双対としてスパン生成性を考えましょう。

コスパン生成性は、線形独立性に対する線形生成性から思い付いたものです。まずは、線形生成性から説明します。線形写像 f:U→V が線形生成〈linear generation〉だとは、fが全射であることだと定義します。部分集合 A⊆V が生成系〈generating system〉であるとき、包含写像の線形拡張 R[A]1→V は線形生成(つまり全射)になります。

FdVectR上のn-コスパン (fi:Ui→V | i∈I) が線形生成であることは、コタプル写像 [fi | i∈I]:(\oplusi∈IUi)→V が全射であることだと定義します。

FdVectR上の、すべての線形生成コスパンからなるクラスXは次の性質を持ちます。

  1. Xは、インデックスセットの全単射取り替えに対して安定。
  2. Xは、複圏をなす。
  3. (fi:Ui→V | i∈I)∈X、τ:J→I が全射のとき、(fτ(j):Uτ(j)→V | j∈J)∈X

線形独立コスパンのクラスとの違いは、インデックスセットの(単射ではなくて)全射取り替えに対して安定していることです。

線形生成コスパンのクラスを一般化して、圏C上のコスパン生成性構造〈cospan generation structure〉を定義できます。その定義はもう明らかでしょう。矢印を逆転させる双対をとって、圏C上のスパン生成性構造〈span generation structure〉も定義できます。

次の4つの構造は双対性で互いに結び付けられているので、一緒に考えたほうがいいと思います。

  1. コスパン独立性構造
  2. スパン独立性構造
  3. コスパン生成性構造
  4. スパン生成性構造

*1:潜在的には、確率空間のテンソル積を使っていることになりますが。

*2:今回の話では、有限次元じゃなくても難しくはなりません。気分的に簡単な印象があるだけです。

*3:定義から分かるように、A1, ..., An の線形独立性は、単一の集合 A1∪ ... ∪An の線形独立性に帰着されます。その意味では、複数の集合に関する線形独立性が必須とは言えません。

*4:シンプソンは、単に安定と呼んでいます。

*5:線形独立なコスパンは、jointly monic cospan です。関連する話題が「余関係=関係の双対概念」にあります。

*6:シンプソンは、この安定性をアフィン〈affine〉と呼んでいます。

随伴系の二重圏

ひとつ前の記事「随伴系の圏の多様性」にて:

1AdjL(Cat)(あるいは、1AdjR(Cat))だけでも、モナド/コモナドを調べる道具に使えます。が、やはり随伴系の二重圏が欲しい。というわけで、随伴系の二重圏についても述べたいとは思っています(いつかわからんが)。

随伴系の二重圏は色々と使い途があるので、早めに定義しておきます。

内容:

形式論と具体論

モナドや随伴の理論には、形式論〈formal theory〉と具体論〈concrete theory〉があります。「最近のモナド論の概観と注意事項 1/2 // モナド論を分類すれば」では、形式論と“非形式論”という言葉を使ったのですが、ここでは具体論にします。

形式論は、一般的な厳密2-圏(または弱2-圏=双圏)Kを舞台として理論を展開します。それに対して、具体論は K = Cat と固定した理論になります。この記事では、主に具体論を扱いますが、ほとんどは形式論でも通用する話です。形式論の用語もけっこう使います。念の為に、「形式論 vs. 具体論」の対応表を載せておきます。

形式論 具体論
K Cat
対象=0-射
射=1-射 関手
2-射 自然変換

形式論におけるモナド/随伴系を、形式モナド/形式随伴系と言う人もいますが、そこまで区別するのは面倒だし意味もないと思うので区別しません。

厳密2-圏K内のモナドの全体を Mnd(K)、随伴系の全体を Adj(K) と書きます。しかし、モナドの全体も随伴系の全体も色々な種類があるので、'Mnd'と'Adj'に対して左下付きと右下付きで様々な修飾をします(「最近のモナド論の概観と注意事項 2/2」と「随伴系の圏の多様性」参照)。

上下左右の使い方

圏論、特に高次圏論の学習では、“上下左右”に慣れることが肝だと思います。なので、上下左右の話は、何度も何度も何度も繰り返しています*1。比較的最近だと:

その後の記事でも再度注意しています。

随伴系に関して言えば、2つの関手が構成素〈constituent | ingredient〉として含まれます。その2つの関手の片方を左関手と呼び、もう一方を右関手と呼びます。「左右」は単にペア〈カップル | コンビ〉における役割を区別するだけなので、「左関手・右関手」の代わりに「妻関手・夫関手」でも「ボケ関手・ツッコミ関手」でもかまいません。(次の記事も参照。)

一方で、図(ペースティング図とストリング図)を描いたとき、ほんとの空間的な位置・方向として上下左右を使うこともあります。さらには、空間的位置・方向にちなんで用語〈テクニカルターム〉が決められることもあります。ところがさらに、図の描き方(描画方向)が多様なので、描き方を変えると空間的位置・方向と用語は一致しなくなります。

圏論の極限を具体的に // 関手の極限の復習」に挙げた例ですが、次の圏論用語は同義語(「右カン拡張」は類義語)です。

  • 極限=逆極限=左根≒右カン拡張

もうほんとにどうにもならないグチャグチャ状況で、改善は無理でしょう。やれることは、注意して混乱や誤解を避けることだけ。今回の二重圏の話では、上下左右の議論がウンザリするほど登場します。ご注意ください。

2-射の形状

この記事では、圏を対象として随伴系を水平射として、関手を垂直射とする二重圏〈double category〉を考えます。二重圏やその実例については、次の記事に書いてあります。

随伴系の二重圏と言っても、作り方のオプションがいっぱいあるのですが、とりあえずは曖昧かつ総称的に、単に「二重圏」と呼んでおきます。

二重圏で注目すべきはその2-射〈2-セル〉です。2-射の図は2次元的な四角形になります。ここから先の説明で出てくる「上下左右」は、基本的には空間的な位置・方向のことです。ただし、左関手/右関手、(後で出てくる)左自然変換/右自然変換の「左右」は役割を識別する「左右」です。水平射を左から右、垂直射を上から下に描くことにします。

この描画方向で、二重圏の2-射αは次のようになります。

 C --(A)-→ D
 |         |
(F)   α   (G)
 |         |
 v         v
 C' -(A')→ D'

AとA'はそれぞれ随伴系で、水平射としての方向は随伴系の左関手の方向に合わせています。A = (η, ε: L -| R, L:CD), A' = (η', ε': L' -| R', L':C'D') とすれば、方向は次のようです:

  • A:CD は、L:CD と同じ方向。R:DC とは逆方向。
  • A':C'D' は、L':C'D' と同じ方向。R':D'C' とは逆方向。

もちろん、随伴系の方向を右関手の方向に合わせても何の不都合もなく、水平射の方向の選択はまったく恣意的です。

二重圏の2-射αは、実は2つの自然変換(もとにする厳密2-圏Catの2-射)から構成されます。α = (αleft, αright) とします。αleftとαrightが何モノであるか分かるように絵を描くと:

αleftは、上下辺が左関手LとL'である四角形(図のピンクの四角形)として描かれます。なので、左自然変換〈left natural transformation〉と呼ぶことにします。左関手/左自然変換の「左」は空間的位置・方向ではなくて、役割を識別する形容詞です。同様に、上下辺が右関手RとR'である四角形(図で奥側の水色の四角形)として描かれる自然変換は右自然変換〈right natural transformation〉です。左自然変換と右自然変換のペアが二重圏の2-射を構成します。

2-射αの構成素である左自然変換αleftを考えると、その方向の選び方は二種類あります。

  1. αleft: F*L'⇒L*G (下図の左側)
  2. αleft: L*G⇒F*L' (下図の右側)

一番目の方向を(地図の方向から)北東〈North-East〉方向、二番目の方向を南西〈South-West〉方向と呼ぶことにします。

2-射αの右自然変換αrightの方向の選び方も同様に2つの方向があります。

  1. αleft: R*F⇒G*R' (下図の左側)
  2. αleft: G*R'⇒R*F (下図の右側)

ただし、この図では、随伴系の右関手 R, R' のアローの方向が右から左になっています。通常の左から右にすれば、自然変換の方向も変化して見えます。我々は、右関手を逆向きに描くこの描画法を採用します。最初の立体的な絵において、左自然変換の面を正面に見る方向から観測して描いていると思ってください(裏側からは見ない)。図の左側が南東〈South-East〉方向、図の右側が北西〈North-West〉方向です。

αleft, αrightの方向の組み合わせは4種類になります。

  1. αleftが北東方向、αrightが南東方向
  2. αleftが北東方向、αrightが北西方向
  3. αleftが南西方向、αrightが南東方向
  4. αleftが南西方向、αrightが北西方向

しかし、とある条件(次節)を付けてふるい落とすと一種類だけが残ります。左自然変換が北東方向、右自然変換が南東方向が我々が使う組み合わせです。最初に選ぶ随伴系の方向を右関手に合わせると、右自然変換が南西方向、左自然変換が北西方向になります。とある条件については、次節で説明します。

メイト

前節で多様な方向について述べました。随伴系の方向の選び方が2種あり、それぞれについて、二重圏の2-射(=左自然変換と右自然変換のペア)の方向の選び方が4種あるので、二重圏としての方向の選び方は8種あり、方向の定義が異なる8つの二重圏が出来ます。

しかし、モナドと随伴系の関係を調べる目的では、8つの二重圏は無駄に一般的過ぎるようです。モナド論のなかでは、2-射の左自然変換と右自然変換が無関係である場合は出現しないからです。2-射の左自然変換と右自然変換には次の条件を課します。

  • 2-射を構成する左自然変換と右自然変換は、互いにメイト〈mate〉である。

今からメイトの説明をしますが、「互いにメイト」の特殊ケースでよく知られたものがあります。紹介しておきます。

  1. 随伴系によるホムセットの同型 D(L(A), Y) \stackrel{\sim}{=} C(A, R(Y)) により、射 g:L(A)→Y と f:A→R(Y) が互いに転置になる。
  2. ベクトル空間のあいだの2つの線形写像 f:V→W と g:W*→V* が互いに双対になる。

「互いに転置」「互いに双対」は、「互いにメイト」の特殊ケースです。今日は、メイトの一般論とその特殊ケースの関係を論じることはしませんが、随伴系の転置、線形写像の双対については次の記事で述べています。

さて、メイトという言葉をどのように使うかを説明します。実際の定義は次節です。

  • とある2つの自然変換の集合のあいだに1:1の対応がある。この対応をメイト対応〈mate correspondence〉、またはメイト同型〈mate isomorphism〉と呼ぶ。
  • メイト対応で対応付けられる2つの自然変換は互いにメイト〈mate〉であるという。

メイト対応

A = (η, ε: L -| R, L:CD) と A' = (η', ε': L' -| R', L':C'D') を2つの随伴系とします。次のような自然変換の集合を考えます。

  1. Nat(F*L', L*G:CD') : 関手 F*L':CD' から関手 L*G:CD' への自然変換の集合
  2. Nat(R*F, G*R':DC') : 関手 R*F:DC' から関手 G*R':DC' への自然変換の集合
  3. Nat(L*G, F*L':CD') : 関手 L*G:CD' から関手 F*L':CD' への自然変換の集合
  4. Nat(G*R', R*F:DC') : 関手 G*R':DC' から関手 R*F:DC' への自然変換の集合

先に導入した左自然変換/右自然変換と、自然変換の地図的方向を使って表現すれば:

  1. Nat(F*L', L*G:CD') : 北東方向の左自然変換の集合
  2. Nat(R*F, G*R':DC') : 南東方向の右自然変換の集合
  3. Nat(L*G, F*L':CD') : 南西方向の左自然変換の集合
  4. Nat(G*R', R*F:DC') : 北西方向の右自然変換の集合

地図的方向は、左自然変換を正面に見る視点から観測して言ってることで、右関手は奥側を右から左に向かっています。

さて、メイト対応は、次のような対応です。

  • Nat(F*L', L*G:CD') ←→ Nat(R*F, G*R':DC')

互いに逆写像であるペアなので、2つの写像があります。それらは、絵(ストリング図)を使えば簡単で印象的に表せます。

写像に名前を付けるより、次のような象形文字風の演算子記号を使うと分かりやすいでしょう。

  • (-):Nat(F*L', L*G:CD')→Nat(R*F, G*R':DC')
  • (-):Nat(R*F, G*R':DC')→Nat(F*L', L*G:CD')

(-)(-) が互いに逆なのは、随伴のニョロニョロ関係式〈snake relation〉から明らかです。

Nat(L*G, F*L':CD') と Nat(G*R', R*F:DC') のあいだでは、随伴系の単位・余単位を使ったメイト対応がうまく定義できないことが(やってみれば)分かります。随伴は完全な対称性は持ってないのですよね。ただし、(ストリング図で言えば)左右のワイヤーを交換するノードがあれば、メイト対応もどきが定義できるかも知れません(未確認)。

互いにメイトである自然変換のペアをメイトペア〈mate pair〉と呼ぶことにします。メイトペアの相方〈パートナー〉を求めるには、演算子 (-) または (-) を適用すれば済みます。

二重圏としてのAdjの定義

メイトペアの準備ができれば、随伴の二重圏を定義できます。

まず、水平圏として 1AdjL(Cat) か 1AdjR(Cat) のどちらかを選びます。今は 1AdjL(Cat) を選んだとしましょう。2-射は、互いにメイトになっている左自然変換と右自然変換のペアを選びます。こうして作った二重圏を次のように書きます。

  • dAdjL(Cat)

水平圏を 1AdjR(Cat) に選ぶと、次の二重圏ができます。

  • dAdjR(Cat)

dAdjL(Cat) と dAdjR(Cat) の2-射の状況は、次のように図示できます。バッテンに交差した2本の二重矢印は、互いにメイトである自然変換を表します。

dAdjL(Cat), dAdjR(Cat) が二重圏の公理を満たすことを確認する必要がありますが、ペースティング図かストリング図を使えば容易に確認できます。

二重圏Adjの利用

今回定義したような随伴の二重圏は、1960年代後半には、パルムクイスト〈Paul H. Palmquist〉*2により調べられていたようです。(紙の出版物でしかアクセスできないので、実物は見てません。)

  • Paul H. Palmquist. The Double Category of Adjoint Squares. PhD thesis, University of Chicago, 1969.

メイト対応を含めた随伴系の全体を把握するために、二重圏に編成するのはとても良いアイデアだと思います。二重圏の基本理論を適用して、随伴系達の構造がハッキリと見えるようになります。

二重圏を定義する場合、随伴系を水平射とするか垂直射とするかもオプションなので、随伴系を垂直射とした定義もあります。当然ながら、上下左右の話は丸っきり変わってしまいます。(が、本質的には同じこと。)

具体的な厳密2-圏Catをベースに話をしましたが、一般的・抽象的な厳密2-圏Kに対しても二重圏 dAdjL(K), dAdjR(K) を定義できます。さらには、弱2-圏〈双圏〉Kに対しても同様な議論ができます。

メイト」の節でちょっと触れたように、双対ベクトル空間/双対線形写像は、単対象弱2-圏とみなした VectK(Kは適当なスカラー体)に対する dAdjL(VectK) を使って定式化できます。

そしてもちろん dAdj(K)(右下の'□'には'L'か'R'が入る) は、モナドと随伴系の関係を調べるときの基本的な道具になります。モナドの圏は、dAdj(K) に埋め込むことができます。

dAdj(K) に、さらに3-射を加えて3次元の圏を作れます。この3次元構造は、モナドの2-射(モナドのあいだの射のあいだの射)を調べるときに必要となります。

また、dAdj(K) は、二重圏の事例としても面白いと思います。パラメータKを変えれば様々な二重圏を作れるので、事例の供給源になりそうです。

*1:自分(檜山)が上下左右のような空間認識が苦手で苦労しているので、過度に強調しているかも知れません。

*2:https://ja.forvo.com/search/Palmquist/ によると、"Pa"は「パ」とは発音しないようですが、うまくカタカナ表記できないし、綴りが連想できるように「パ」にしました。

随伴系の圏の多様性

随伴系〈adjunction | adjoint system〉の全体を、圏に編成することができます。しかし、その編成の方法と出来上がる圏は実に様々です。この多様性を捨て去るのではなくて、多様性自体を主題にするのも面白いかもな、と思います。

この記事は、モナド関連の話をダラダラするゆるいシリーズの一環。同じ話題のひとつ前の記事は「複合モナドから花輪積へ」。

内容:

随伴系の圏の次元と射の形状

随伴系の全体を圏に仕立てる場合、圏の次元が色々あり得ます。

  • 随伴系の1-圏
  • 随伴系の2-圏
  • 随伴系の3-圏

随伴系の1-圏(通常の圏)は、圏を対象として、そのあいだの随伴系を射とするものです。2-圏と3-圏は、随伴系の1-圏にそれぞれ、2-射と3-射を追加したものです。僕が想定しているケースでは、2-圏/3-圏は球体モデル〈globular model〉の圏ではありません。つまり、2-射/3-射の形状〈shape〉が2-球体〈円板 | ニ辺形〉/3-球体〈二面体〉ではありません。2-射の形状は四角形〈方形〉、3-射の形状は円柱形です。

随伴系の1-圏は普通の圏〈ordinary category〉で、随伴系の2-圏は二重圏〈double category〉の構造を持ちます。

  • 随伴系の1-圏 = 随伴系の圏
  • 随伴系の2-圏 = 随伴系の二重圏

随伴系の圏は、随伴系の二重圏のなかに水平圏(対象と水平射の圏)として埋め込まれます。

随伴系の3-圏は、… ンート … もっと複雑になります。今日のところはこれ以上説明はしません。(短い説明が出来ない。)

圏の次元と射の形状を今述べたように決めても、作り方にさらにいくつかの選択肢があります。随伴系の圏は射の方向が違う2種類、随伴系の二重圏は射(1-射と2-射)の方向〈direction〉と弱さ〈weakness〉*1で特徴付けられます。随伴系の二重圏がいったい何種類になるかは、勘定の仕方が(僕は)分からなくてハッキリしません。

随伴系の3-圏が何種類できるかは、もっと(僕は)分かりません。

随伴系の1-圏

とりあえず、圏を対象として随伴系を射とする(通常の)圏を考えます。この圏を 1Adj(Cat) とします。左下付きの'1'は1-圏であることを示します。右下付きの四角マーク'□'のところには'L'または'R'が入ります。小さい圏の厳密2-圏Catのなかで随伴系を考えますが、任意の厳密2-圏Kに対して*2 1Adj(K) を考えることができます。

随伴に馴染みがない方は、事前に次の記事を呼んでおくといいかも知れません。

L:CD, R:DC in Cat が関手の対〈ペア〉だとして、単位自然変換 η::C^⇒L*R:CC 、余単位自然変換 ε::R*L⇒D^:DD があり、(η, ε: L -| R) が随伴系になっているとします。(X^ は IdX の意味です。)

この随伴系の“向き”を左関手Lと同じ向きだと考える場合は、

  • (η, ε: L -| R, L:CD)

と書き、右関手Rの向きだと考えるなら次のように書きます。

  • (η, ε: L -| R, R:DR)

A = (η, ε: L -| R, L:CD), B = (ι, δ: M -| S, M:DE) のとき、

  • A:CD in 1AdjL(Cat)
  • B:DE in 1AdjL(Cat)

と考えます。1AdjLにおける下付きの'L'は、左関手〈left functor〉の向きに合わせることを意味します。

随伴系AとBの結合 A*B は次のように定義します。

  • A*B := (ε;(L*ι*R), (S*ε*M);δ : L*M -| S*R , L*M:CE)

アスタリスク'*'を結合の図式順記号に使ったのは、この結合を後で横(水平)方向の結合とみなす心積もりからです。定義の右辺に出てくる'*'は横結合またはヒゲ結合で、';'は縦結合です。

絵(ストリング図)を描いてみれば、定義の由来は明らかでしょう。この結合に関する結合律と単位律も絵で容易に示せます。

1AdjR(Cat) は、1AdjL(Cat) と同様に定義しますが、随伴系の向きを右関手〈right functor〉の向きにとります。一般的厳密2-圏Kに対する 1AdjL(K), 1AdjR(K) も同じ議論で定義できます。



1AdjL(Cat)(あるいは、1AdjR(Cat))だけでも、モナド/コモナドを調べる道具に使えます。が、やはり随伴系の二重圏が欲しい。というわけで、随伴系の二重圏についても述べたいとは思っています(いつかわからんが)。

*1:「弱さ」というと弱点/弱みという感じで否定的な感じがしますね。別な言葉がないかな? でも、意味は「弱さ」としか言いようがない。

*2:厳密2-圏ではなくて、弱2-圏=双圏に対しても随伴系の圏は定義できます。

素粒子の質を作り変えよう

おおおおー、すげーな、これ。

素粒子の質を作り変えるのかぁ。となると、加速器が必要でしょうね。例えば、CERN〈欧州原子核研究機構〉のLHC〈Large Hadron Collider | 大型ハドロン衝突型加速器〉は周長27kmの巨大施設。

CERNといえば、最近(2019年1月)、次世代の加速器建設計画を発表したようです。

周長100kmの加速器、建設費用は3兆円で、2050年代後半に稼働予定だそうです。

今なら、3兆円もかけずに無料で素粒子の質を作り変えることができるそうです、まー素敵。

松本さんはアイスクリームつくります

柔道の松本薫(元)選手、精悍な顔つきと俊敏な動きがとてもカッコよくて好きです。

でも、現役は引退なんですね。次の目標の「アイスクリームつくります」もなんかいいなー。

零項演算とは何か?

セミナーで受けた質問シリーズ(なのか?)、その3: 過去に何度も聞かれたことがある一般的な質問; 数の足し算・掛け算、集合の合併・共通部分などの演算に対して、オペランド(演算すべき対象物)が一つもないときどうなるのか?

内容:

オペランドが一つもないとき

幾つかの数 a1, a2, ..., an を全部足し算すること(あるいはその結果である総和)を次のように書きます。

  • \sum_{i = 1}^{n} a_i

a1, a2, ..., an を全部掛け算するなら:

  • \prod_{i = 1}^{n} a_i

幾つかの集合 A1, A2, ..., An を全部合併することは次のように書きます。

  •  \bigcup_{i = 1}^{n} A_i

A1, A2, ..., An 達すべての共通部分なら:

  •  \bigcap_{i = 1}^{n} A_i

これらは、数や集合のリストに対する演算と思えるので、次のように書いてもいいでしょう。

  •  \sum (a_1, a_2, \cdots, a_n)
  •  \prod (a_1, a_2, \cdots, a_n)
  •  \bigcup (A_1, A_2, \cdots, a_n)
  •  \bigcap (A_1, A_2, \cdots, a_n)

n = 2 の場合は:

  •  \sum (a_1, a_2) =  a_1 + a_2
  •  \prod (a_1, a_2) =  a_1 \times a_2
  •  \bigcup (A_1, A_2) = A_1 \cup A_2
  •  \bigcap (A_1, A_2) = A_1 \cap A_2

n = 1 の場合は次でいいでしょう。

  •  \sum (a_1) =  a_1
  •  \prod (a_1) =  a_1
  •  \bigcup (A_1) = A_1
  •  \bigcap (A_1) = A_1

さて、n = 0 の場合はどうなるのでしょうか?

  •  \sum () =  ?
  •  \prod () =  ?
  •  \bigcup () = ?
  •  \bigcap () = ?

[補足]
ここで言っている零項演算は、最初に二項演算があり、その二項演算から作ったn項演算において、n = 0 としたものです。つまり、「二項演算ありき」の状況設定です。二項演算がなくて、いきなり集合X上の零項演算〈無項演算 | nullary operation〉と言った場合は、X0→X という写像のことです。集合Xの零乗は単元集合なので、1→X となり、(いきなりの)零項演算はXの特定要素と同一視できます。例えば、付点集合〈poited set〉は、零項演算〈無項演算〉をひとつ備えた構造になります。
[/補足]

リストの連接から考える

2つのリスト (a1, ..., an), (b1, ..., bm) に対してその連接〈concatenation〉を次のように定義します。

  • (a1, ..., an) # (b1, ..., bm) := (a1, ..., an, b1, ..., bm)

'#'が連接演算の演算子記号です。連接の単位元〈中立元〉は空リスト () になります。

  • () # (a1, ..., an) = (a1, ..., an)
  • (a1, ..., an) # () = (a1, ..., an)

リストは太字で書くことにすれば、

  • () # a = a
  • a # () = a

前節の「リストの要素全部をナニカする」演算と、リストの連接には次の関係があります。

  •  \sum ({\bf a} \;\#\; {\bf b}) = \sum {\bf a} \,+\, \sum {\bf b}
  •  \prod ({\bf a} \;\#\; {\bf b}) = \prod {\bf a} \,\times\, \prod {\bf b}
  •  \bigcup ({\bf A} \;\#\; {\bf B}) = \bigcup {\bf A} \,\cup\, \bigcup {\bf A}
  •  \bigcap ({\bf A} \;\#\; {\bf B}) = \bigcap {\bf A} \,\cap\, \bigcap {\bf A}

足し算に関して、連接の片側を空リストに置いてみると:

  •  \sum {\bf a} = \sum (() \;\#\; {\bf a}) = \sum () \,+\, \sum {\bf a}
  •  \sum {\bf a} = \sum ({\bf a} \;\#\; ()) = \sum {\bf a}  \,+\, \sum ()

これより、 \sum () は足し算の単位元〈中立元 | 零元〉でなければならないことが分かります。足し算以外も同様で:

  •  \sum () = 0
  •  \prod () = 1
  •  \bigcup () = \emptyset
  •  \bigcap () = X

ここで、Xは部分集合の親となる全体集合です。

集合演算の定義から直接導く

集合演算の場合は、その定義から直接に零項演算の結果が何であるかが分かります。

Iをインデックスセットとします。I = {1, 2, ..., n} だと思ってもかまいません。Iでインデックス付けられた集合族〈I-indexed family of sets〉の合併と共通部分は、次の論理同値で定義されます:

  •   \mbox{For} \;x \in X,\: (x \in \bigcup_{i \in I} A_i) \:\Leftrightarrow\: \exists k \in I.(x \in A_k)
  •   \mbox{For} \;x \in X,\: (x \in \bigcap_{i \in I} A_i) \:\Leftrightarrow\: \forall k \in I.(x \in A_k)

ここで、インデックスセットIを空集合に置いてみると:

  •   \mbox{For} \;x \in X,\: (x \in \bigcup_{i \in \emptyset} A_i) \:\Leftrightarrow\: \exists k \in \emptyset.(x \in A_k)
  •   \mbox{For} \;x \in X,\: (x \in \bigcap_{i \in \emptyset} A_i) \:\Leftrightarrow\: \forall k \in \emptyset.(x \in A_k)

「i∈\emptyset に対する Ai」が不思議ですが、空集合をインデックスセットとするような部分集合の族は(ただ一つだけ)存在し、それがAなのです -- Aは空リストのことだと思ってもいいです。さて、上記の同値の右側の条件を変型すると:

  •   \mbox{For} \;x \in X,\: \exists k \in \emptyset.(x \in A_k) \:\Leftrightarrow\: \exists k.(k \in \emptyset \land x \in A_k)
  •   \mbox{For} \;x \in X,\: \forall k \in \emptyset.(x \in A_k) \:\Leftrightarrow\: \forall k.(k \in \emptyset \Rightarrow x \in A_k)

 k \in \emptyset は偽ですから:

  •   \mbox{For} \;x \in X,\: \exists k.(k \in \emptyset \land x \in A_k) \:\Leftrightarrow\: \exists k.(False \land x \in A_k) \:\Leftrightarrow\: False
  •   \mbox{For} \;x \in X,\: \forall k.(k \in \emptyset \Rightarrow x \in A_k) \:\Leftrightarrow\: \forall k.(False \Rightarrow x \in A_k) \:\Leftrightarrow\: True

下側(二番目)の同値では、含意の前件(左側)が偽なら含意命題は問答無用に真になることを使っています。

以上より:

  •   \mbox{For} \;x \in X,\: (x \in \bigcup_{i \in \emptyset} A_i) \:\Leftrightarrow\: False
  •   \mbox{For} \;x \in X,\: (x \in \bigcap_{i \in \emptyset} A_i) \:\Leftrightarrow\: True

つまり、次が言えます。

  •   \forall x \in X.(x \notin \bigcup_{i \in \emptyset} A_i)
  •   \forall x \in X.(x \in \bigcap_{i \in \emptyset} A_i)

結局:

  •   \bigcup_{i \in \emptyset} A_i = \emptyset
  •   \bigcap_{i \in \emptyset} A_i = X

順序集合の上限と下限

前節の議論を、少し別な観点から見てみましょう。インデックスセットIでインデックス付けられたXの部分集合族〈I-indexed family of subsets of X〉Aは、A:I→Pow(X) という写像のことです(Pow(X)はXのベキ集合)。

写像A単射の場合は、写像Aの代わりにその像集合

  • {S∈Pow(X) | S = Ai (Ai = A(i)) となる i∈I が在る}

を考えても同じことです。また、部分集合族の表現として、単射写像を選ぶことができるので、「Iでインデックス付けられたXの部分集合族 ←→ Pow(X)の部分集合」という相互変換(1:1ではない*1)が出来ます。

話を一般化して、ベキ集合Pow(X)とは限らない順序集合 L = (L, ≦) を考えます。Lの部分集合Aに対して、Aの上限〈supremum | 最小上界 | least upper bound〉とAの下限〈infimum | 最大下界 | greatest lower bound〉を定義しましょう。

a∈L が A⊆L の上限だとは、aが次の条件を満たすことです。

  1. x∈A ならば x ≦ a
  2. 「x∈A ならば x ≦ b」となるbに対して、a ≦ b

下限の定義は順序関係をひっくり返すだけです。aがAの下限だとは:

  1. x∈A ならば a ≦ x
  2. 「x∈A ならば x ≦ b」となるbに対して、b ≦ a

勝手に選んだAに対して上限・下限が存在することは(一般には)保証されませんが、在るならそれらを sup(A), inf(A) と書きます。

さて、空集合\emptysetに対して sup(\emptyset), inf(\emptyset) が在るとして、それはどんなものでしょうか? 上限の定義のAのところに\emptysetを入れると:

  1. x∈\emptyset ならば x ≦ a
  2. 「x∈\emptyset ならば x ≦ b」となるbに対して、a ≦ b

一番目の条件は常に真(前件が偽だから)なので、二番目だけ考えればいいですね。二番目の条件内の「x∈\emptyset ならば x ≦ b」も常に真なので、bに関する縛りは何もなくなって:

  • 任意のbに対して、a ≦ b

論理式で書くなら:

  • ∀b∈L.(a ≦ b)

これは a = sup(\emptyset) がLの最小元〈least element〉であることを意味します。同様に、inf(\emptyset) はLの最大元〈greatest element〉になります。

  • sup(\emptyset) = least(L)
  • inf(\emptyset) = greatest(L)

(L, ≦) として (Pow(X), ⊆) を取ったときは:

  • sup(\emptyset) = least(Pow(X)) =  \emptyset
  • inf(\emptyset) = greatest(Pow(X)) = X

ここで、\emptysetが、\emptyset⊆Pow(X) と \emptyset⊆X の意味で登場することに注意してください。

前節の話との関連性は:

  •  sup(\emptyset) = \bigcup_{i \in \emptyset} A_i
  •  inf(\emptyset) = \bigcap_{i \in \emptyset} A_i

*1:インデキシングの写像全射単射に分解して、その単射部分を取り出せば、像集合と同一視できます。

三段論法とは何か?

昨日に引き続き、セミナーで受けた質問で一般的なものを; 「三段論法とは何ですか?」に答えておきます。

内容:

アリストテレスがやっていたヤツ

「三段論法」という言葉は、割とよく耳にしますが、数理論理学のテクニカルタームとしては定義されてないと思います。ローカルに定義する人がいるかも知れませんが、広く合意された定義はないでしょう。国語辞典に載っている言葉(日常語、非専門語)として解釈したほうが無難です。

言語運用状況の統計的証拠はありませんが、「三段論法」の用法で多そうなのは、アリストテレスがやっていた論理の手法を指す場合だと思います。僕は歴史に疎いので、古代ギリシアの論理はよく知りませんが、「大前提/小前提/結論」という形式があるので「三段」と呼ぶんじゃないかと想像します。でも、英語(もとはギリシャ語)だと"syllogism"〈シロジズム〉で、特に「三」の意味はないようです。

モーダスポネンス

次のような推論の形式をモーダスポネンス〈modus ponens | MP〉といいます。モーダスポネンスはラテン語みたい。

   A   A⇒B
  ----------MP
      B

モーダスポネンスをシーケントで書くなら:

  • A, A⇒B → B

このモーダスポネンスを三段論法と呼ぶこともあるようです。アリストテレスのシロジズムにもモーダスポネンスのような論法はあるので、モーダスポネンスがアリストテレスとまったく無関係とは言いにくく、モーダスポネンスを三段論法と呼んでも別にいいんじゃないかな、と思います。

あるいはまた、次のような推論を三段論法と思っている人もいるかも知れません。

   A⇒B   B⇒C
  -------------
      A⇒C

これは、モーダスポネンスから導くことができます。自然演繹風の証明図(セミナーでは、証明図ではなくて推論図と呼んでます*1)で描くなら:

  #1
  ---
   A  A⇒B
  ---------MP
      B       B⇒C
     --------------MP
          C
        -------#1
         A⇒C

ここで、二箇所に'#1'と書いてあるのは、仮定のAを消して含意の前件に持ってきたことを示します -- カリー化とかラムダ抽象に相当する*2操作です。

上記の証明(推論)の仮定と結論だけをシーケントで書けば:

  • A⇒B, B⇒C → A⇒C

これも、A, B, C という三つの命題が出てくるから三段論法なのかもね。

カット

論理式のリストを、Γ, Δ などのギリシャ文字大文字で表すことにして、シーケント計算における次の規則(セミナーではシーケントの推論規則を基本リーズニングと呼んでます*3)をカット〈cut〉といいます*4

  Γ → A   A, Δ → B
 ======================Cut
    Γ, Δ → B

先に出てきた自然演繹風証明図と区別するため、横棒は二本棒にしています。

カットが部分的な結合〈partial composition〉であることは見て取れると思いますが、通常の結合があれば、カット=部分結合は導くことができます。

                ☆
             ========
  Γ → A    Δ → Δ
 =====================Prod
    Γ, Δ → A, Δ          A, Δ → B
   ===================================Comp
       Γ, Δ → B

ここでは、ゲンツェンのLKシーケントとは違って、右辺のカンマも連言の意味です。Prodは、左辺どうし/右辺どうしをそのまま連接する操作で、Compは順次結合する操作です。ProdやCompについてより詳しいこと、あるいはもっとグラフィカルな表現については:

えーとそれで、カット〈部分結合〉のことも三段論法と呼ぶことがあります。



結局、「三段論法」という言葉は大変に曖昧です。もともとが曖昧なんだから、どんな意味で使おうが目くじらは立てませんが、曖昧性を避けたいなら使わないのが吉です。

*1:証明図と呼ばず推論図と呼ぶには事情があります。

*2:「相当する」は、カリー/ハワード対応により関係付けられることを意味します。

*3:推論/証明とは呼ばずリーズニングと呼ぶには事情があります。

*4:もう少し一般的な形にすることが多いかも。

論理式の集合とは何か?

セミナーで受けた質問ですが、一般的な話なので、応答をこちらに書きます。命題を形式化した構文的対象物が論理式です。この論理式の集合を正確に定義するとどうなるのか? という話です。

内容:

用途と論理を決める

論理式には、絶対的唯一の定義があると思っている方がいるかも知れませんが、それは誤解です。プログラミング言語が何十何百もあるのはご存知でしょう。プログラミング言語ごとにその構文は違います。同様に、論理式(の言語)も人工言語なので、何十何百もあります。論理式の言語と集合は、使用状況と好みに応じてその場その場で作る(定義する)ものだと考えたほうがいいでしょう。

ただし、論理式(の言語と集合)を定義するための、だいたいのガイドラインはあります。このガイドラインも唯一ではなくて、いくつもあります。多様多彩な世界なんです。ここでは、典型的なガイドラインと、そのガイドラインに沿った構文定義の実例をひとつ挙げます。

まず用途が決まらないと、論理式を定義することが出来ないので、ここでは、自然数の計算や、自然数に関わる推論を行うことを目的にします。そして、どんな論理を使うかを決めます。ここでの例では、一番ポピュラーな古典論理を使うことにします。

基本記号を全部挙げる

目的と論理が決まったら、使う記号をすべて列挙します。このとき、記号を分類するガイドラインが役に立ちます。

  1. 定数記号
  2. 変数記号
  3. 演算記号〈関数記号〉
  4. 述語記号〈関係記号〉
  5. 論理記号〈論理結合子記号と限量子記号〉
  6. 補助記号

説明は後にして、各種の記号を並べてしまいます。

  1. 定数記号: '0', '1'
  2. 変数記号: すぐ下で定義する
  3. 演算記号: '+', '*'
  4. 述語記号: '=', '≦'
  5. 論理記号: '∧', '¬', '∀'
  6. 補助記号: '(', ')', ',', '.'

変数記号は無限個あるので、書き並べるわけにいきません。変数記号は次のように決めます。

  • 英字〈ラテン文字〉小文字1文字、またはその後に数字〈digit〉を任意個付けたもの。

例えば、'x', 'a', 'x1', 'k123' などは変数です。'x1'のような複数文字でも、全体としてひとつの記号とみなします。'x'と'1'に分解したりはしません。

上記の基本記号を選んだ方針や理由を述べておきましょう。利便性は考慮せず(実際、不便になります)基本記号を節約する方針です。

  • 定数記号は'0'と'1'だけなので、例えば2を表すには "1 + 1"とする。
  • 演算記号は'+'と'*'だけなので、引き算や割り算は(必要なら)後で定義する。
  • 述語記号も、'≧'や'<'が必要なら後で定義する。
  • 論理記号も通常より少ない。古典論理を使うので、ド・モルガンの法則などを根拠に後から定義できる。
    • A∨B は、¬(¬A∧¬B) と後で定義する。
    • ∃x.A は、 ¬∀x.¬A と後で定義する。
    • A⇒B は、¬A∨B と後で定義する。
  • 自然数しか扱わないので、型の指定はしない。したがって型を表す記号は入ってない。

今までに挙げた記号を基本記号〈{basic | atomic | primitive} symbol〉と呼びます。いくつかの基本記号を、デタラメでもいいので並べたものを記号列〈{string | sequence} of symbols〉と呼びます。複数文字の単一記号もあるので、記号列内の記号をピッタリくっつけるわけにはいきません。空白を挟むことにします。また、記号列全体は二重引用符で囲みます。例えば:

  • "a1 0 ¬ k123 * ≦ ∀ . 1"

こういうデタラメな記号列では、空白(区切り記号)が必要ですが、文法〈構文規則〉で制限した記号列(それが後述する項や論理式)では、空白は必須ではなくなります。例えば、次の記号列は論理式ですが、実際には空白は不要です。

  • "∀ n , m . ¬ ∀ q , r . ( ¬ ( ( n = ( ( q * m ) + r ) ) ∧ ( ( r ≦ m ) ∧ ¬ ( r = n ) ) ) )"

'∃'や'<'を使うことを許して、括弧も適宜省略して書くなら:

  • "∀n,m.∃q,r.(n = q*m + r ∧ r < m)"

構文の定義

記号列のほとんどはデタラメなゴミです。ゴミではない、我々が使うべき記号列をハッキリさせる規則が構文規則〈文法〉です。構文規則の記述には、BNFバッカス/ナウア形式〉が便利であり標準的でもあります。

プログラミング言語に多少の馴染みがあるのなら、次の記事を読むと構文定義(や意味定義)の方法が手っ取り早く分かるでしょう。

BNFに関しては、「UMiToL言語の構文」の節に簡単な例と他の記事への参照があります。

というわけで、構文の定義にはBNFを使うことにします。構文定義の際に、項の定義と論理式の定義の二段階に分けます。〈term〉とは、(今の場合)自然数を表す式のことで、論理式〈formula〉は命題を表す式です。

「項と論理式に分けて定義する」というのもガイドラインのひとつで、「分けないで定義する」というガイドライン(流儀)もあります*1。僕は、分けたほうが分かりやすいと感じています。

項の定義
基本項 ::= '0' | '1' | 変数記号
項 ::= 基本項 | '(' 項 '+' 項 ')' |  '(' 項 '*' 項 ')' | '(' 項 ')'

次は基本項の例です。

  • 0
  • 1
  • x
  • a
  • x1
  • k123

基本項は、記号ひとつからなる記号列なので、"0", "1", "x1" のように書くべきでしょうが、もう二重引用符や空白を律儀に書くのはやめます。

変数記号は無限個あるので、基本項も無限個あります。次は、基本項とは限らない一般の項の例です。

  • ((1 + 0) + 1)
  • ((x*1) + (((1 + 1) + 1)*k123))

上記の構文規則に従えば、演算するごとに括弧で囲むので、括弧が大量に付きます。0, 1, 2, 3, 4 のような定数も次の項で表現します。

  • 0
  • 1
  • (1 + 1)
  • ((1 + 1) + 1)
  • (((1 + 1) + 1) + 1)

人が読み書きするにはひどく不便ですが、機械による処理が単純化されます。

論理式の定義
基本論理式 ::= '(' 項 '=' 項 ')' | '(' 項 '≦' 項 ')'
論理式 ::= 基本論理式 | 論理式 '∧' 論理式 | '¬' 論理式 | '∀' 変数並び '.' '(' 論理式 ')' | '(' 論理式 ')'
変数並び ::= 変数 | 変数並び ',' 変数

この規則から、括弧が相当にうるさい論理式が定義されます。とりあえずは、処理しやすい(構文解析木が作りやすい)構文定義をしました。人間の読み書きのためには、別に略記の規則を導入すればいいでしょう。

もちろん、最初から人間可読性〈human readability〉に優れた構文を定義してもいいですが、構文定義も構文解析処理も複雑になります。ここらへんの兼ね合いは、なかなかに難しいですね。

論理式の集合

最初に決めた基本記号の集合をSymbolとします。

  • Symbol = {'0', '1', '+', '*', '=', '≦', '∧', '¬', '∀', '(', ')', ',', '.', 'x', 'a', 'x1', 'k123', ...}

集合Symbolの要素を並べたものである記号列の集合をSymbol*と書きます。右肩の星はクリーネスターと呼び、「並べたもの」を表す星です。集合Symbol*の要素を幾つか挙げれば:

  • "a1 0 ¬ k123 * ≦ ∀ . 1" ∈ Symbol*
  • "(((1 + 1) + 1) + 1)" ∈ Symbol*
  • "∀ n , m . ¬ ∀ q , r . ( ¬ ( ( n = ( ( q * m ) + r ) ) ∧ ( ( r ≦ m ) ∧ ¬ ( r = n ) ) ) )" ∈ Symbol*

集合Symbol*のなかで、項と認められる記号列の集合をTermとします。もちろん、Term⊆Symbol* です。さらに、論理式と認められる記号列の集合をFormulaとします。Formula⊆Symbol* です。

以上で、集合Formulaがちゃんと定義されました。ここで重要な注意は、集合Formulaは、今ここで「自然数の計算や、自然数に関わる推論を行うこと」を目的に「古典論理を使うこと」を前提に作られたことです。別な目的で別な論理を使うなら、別なFormulaが定義されます。この世に唯一のFormulaが在るわけじゃありません。たくさんのたくさんのFormulaが在り得るのです。

コンテキストに関する注意

集合Formulaの要素、つまり論理式に対してその“意味”を考えます。通常は、論理式の意味は外延(あるいは真理集合)として与えます。例えば、"(x + y = 10)∧(x ≦ y)" の意味なら、{(x, y)∈N2 | (x + y = 10)∧(x ≦ y)} という集合がその意味になります。

しかし、外延(真理集合)が {(x, y, z)∈N3 | (x + y = 10)∧(x ≦ y)} であってもかまいません。「zという変数は入ってないからダメ」とか言うと、「3次元空間R3内で、x2 + y2 = 1 は円筒を表す」といった主張も禁止することになります。何がマズイのかと言うと、変数を含む(含まなくてもいいのだが)論理式と、変数の領域を一緒に考えてないことです。

変数(複数かも知れない)が走る領域に対する指定をコンテキスト〈context〉と呼びます。コンテキストが明示されず、暗黙の前提で済まされることは多いです。そんなときは、「論理式」にコンテキストが暗黙に刷り込まれていると解釈します。

暗黙の前提は、誤解と混乱の原因になるのでやめたほうがいい(あるいは、ほどほどにしたほうがいい)と僕は思いますが、現実には多用されているのでご注意ください。

*1:この例で言えば、型Natと型Boolを導入すれば、項だけで話が済みます。

花輪?

昨日「複合モナドから花輪積へ」で、花輪積〈wreath product | リース積〉の話をしたのですが、花輪だから次のような画像を添えました。

*1

でも、「お花がたくさん」はふさわしくなくて、次のようなモノかも。

*2

後で気が付いたんだけど、モナドの文脈では、木の枝とか蔦を絡めて作った輪が、リースの意味するところじゃないのかな?

ベックの分配法則(特に混合分配法則)を"entwining"とも呼びます。"entwine"の意味は、「からみつく、巻きつく、からませる、まつわらせる、からませる、編む、織り込む」だそうです。おそらく(想像だが)、複数の素材が絡まった構造をリースと呼んだのでしょう。

リース積は、小枝や蔦が絡まった輪から、別な絡み輪を作る操作、って感じなのでしょう。そう思うと割と腑に落ちる。ストリング図の計算は、絡んだ蔦をいじっているみたいだからね。