積と余積

$$ $$ 　古代ギリシャの劇作家エウリピデスは言った。「人はその人が付き合っている人に似ている（類は友を呼ぶ）」我々は関係によって定義されている。そのことがどこよりも明らかなのは圏論である。ある圏からある特別な対象を選択したいなら、他の対象（及びそれ自体）との関係性のパターンを表すだけでよい。このような関係性は射で定義される。
　圏論では普遍的構成と呼ばれる共通の構成があり、対象とそれらの関連性により定義される。これを行う一つの方法はあるパターン、即ち対象と射から構成されるある特定の形を選び取り、その圏のすべての発生を探し求める方法である。それが十分に共通なパターンで、その圏が大きいならば、非常にたくさんの適合する候補を得る公算が高い。これらの候補の間である種のランキングを構築し、何が最適なものを考えられるか選びとるのがコツである。
　この過程はウェブ検索する方法を連想させる。問い合わせはこのパターンに似ている。かなり一般的な問い合わせは大きな再現率、たくさんの適合する候補を与えるだろう。あるものは関連性があるかもしれないし、別のものは関連性がないかもしれない。関連性のない候補を取り除くため、問い合わせを見直す。それによって精度が増す。最終的に検索エンジンはその候補をランク付けし、うまくいけば、最も関心がある一つの結果がリストの最上位にくるだろう。

始対象

　最も単純な形は単一の対象である。ある圏を与えると、明らかに対象が存在するのと同じ数だけこの形のインスタンスが存在する。そこから選びとるには手間がかかる。ある種のランク付けを構築して、このヒエラルキーの最上位である対象を見つけようとする必要がある。我々が自由に使えるのは使えるのは射だけである。射を矢印として考えると、圏のある終端から別の終端への矢印のすべてのネットフローが存在することが可能である。順序圏、例えば半順序圏ではこれは成り立つ。対象aから対象bへの矢印（射）が存在すれば、aがb「より始まりに近い」とすることで対象の優先順位の概念を一般化出来る。すべての自身以外の対象への矢印を持つような対象を始対象と定義する。明らかにこのような対象が存在する保証はない。より大きな問題として、余りにたくさんのこのような対象が存在するかもしれない。適合率はよいが、精度は失われる。その答えは順序圏からヒントを得ることが出来る。即ち、任意の２つの対象の間には高々１つの矢印しかない。別の対象より小さい、または等しいと言う一方向だけが存在する。そこで次のような始対象の定義を導く。
$$ {\bf 始対象}はその圏の中の任意の対象へ向かう１つ、かつ唯一の射を持つ $$

　けれども（もし存在したとしても）始対象の一意性は保証されていない。しかし、一意性については次の最も良いことが保証されている、即ち同型の違いを除いて一意であると言うことである。同型は圏論では非常に重要であり、まもなく少し触れる。さしあたり、同型の違いを除いて一意であることが始対象の定義で対象を特定することが正当化される。
　ここで例を挙げる。半順序集合（よくposetと呼ばれる）での始対象は最小の要素である。始対象を持たない半順序集合も存在する。例えば、以下の関係を射とする、全ての整数、正数と負数の集合がある。
　集合と関数の圏では、始対象は空集合である。

終対象

　単一対象パターンを続けよう。今度は対象のランク付けの方法を変更する。もし対象bから対象aへの射（向きが逆）が存在すれば、aがb「より終わりに近い」ととする。圏の自身以外の対象より終わりに近い対象を探してみる。再び一意性を主張する。
$$ {\bf 終対象}はその圏の中の任意の対象から向かってくる１つ、かつ唯一の射を持つ。 $$ さらに再び、終対象は同型の違いを除いて一意である。これもまもなく触れる。最初に例を見ておこう。半順序集合では、終対象は、もし存在すれば、最大の対象である。集合の圏では、終対象はシングルトンである。既にシングルトンについては触れた。Javaではvoidがそれに対応する。それは唯一つの値を持つ型である。Javaでは暗黙的にである。任意の型から単位型への唯一つの純粋関数を構築出来る。

<A> void unit(A x) {
  return;
}

全ての終対象の条件は満たされている。
　この例で一意性は重要である。なぜなら、任意の集合から向かってくる射を持つ他の集合（実際には、空集合を除く全ての集合）が存在する。例えば、任意の型に対して定義されたブール値関数（述語）が存在する。

<A> Boolean yes(A x) {
  return true;
}

　しかし、Booleanは終対象ではない。少なくとももう一つの任意の集合から向かってくる射が存在する。

<A> Boolean no(A x) {
  return false;
}

一意性を主張することで終対象の定義を唯一つの型へ絞り込むための正しい精度を得ることができる。

双対性

　始対象と終対象を定義の対称性について気付かざるを得ない。二つの違いは射の向きだけである。任意の圏$C$に対してすべての矢印が逆向きにすることだけで反対圏$C^{op}$ を定義することができる。反対圏は同時に合成を再定義する限り、自動的に圏の要求をすべて満たす。もし元の圏で射$f:A \rightarrow B$と$g:B \rightarrow C$を合成して$h=g \circ f$で与えられる$h:A \rightarrow C$があった場合、反対向きの射$f^{op}:B \rightarrow A$と$g^{op}:C \rightarrow B$を合成すると$h^{op}=f^{op} \circ g^{op}$ で与えられる $h^{op}:C \rightarrow A$を得られるだろう。
　双対性は圏の非常に重要な性質である。それは圏論を扱う数学者の生産性を二倍にする。すべての構成に対して、反対が存在する。証明された定理に対して、もう一つ無料でついてくる。反対圏での構成は接頭辞「余(co)」を付けることが多い。例えば、積(product)と余積(coproduct)、モナド(monad)と余モナド(comonad)、錘(cone)と余錘(cocone)、極限(limit)と余極限(colimit)などである。余余モナドは存在しない。二回矢印を逆向きにしても元の状態に戻るからである。
したがって、終対象は反対圏の始対象である。

同型

プログラマーは皆等価を定義することが自明ではないことをよく知っている。二つのオブジェクトが等しいとはどういう意味だろうか？メモリ内で同じ場所を占めているなければならないのだろうか（ポインタの等値性）？それともそれらのコンポーネントの値が等しいことで十分なのであろうか？２つの複素数に対して、一方は実部と虚部で表され、他方は動径と偏角として表されている場合に、これらの複素数は等しいのだろうか？数学者が等値性の意味を見つけ出したと思うかもれないが、そうではない。数学者も多様な競合する等価の定義の同じ問題を持っている。命題的等値性(propositional equality)、内包的等値性(intensional equality)、外延的等値性(extensional equality)、及びホモトピー型理論での道(path)としての等値性が存在する。そして、より弱い概念である同型、さらにより弱い概念である同値性も存在する。
　直観的には同型な対象は同じように見える、即ち同じ形を持つ。それが意味するのは、一つの対象の各部が別の対象の部分に1対1の写像で対応することである。分かる範囲でその二つの対象はお互いの完全なコピーである。数学的に意味するのは、対象aから対象bへの写像が存在し、且つ対象bから対象aに戻る写像が存在し、これらの写像はお互い逆写像であるということである。圏論では写像を射に置き換える。同型は可逆な射であり、もしくは射のペアで一方が多少の逆射である。
　合成と恒等射で逆射を理解する。射$g$が射$f$の逆射であるとは、これらの射の合成が恒等射であることである。二つの射の合成は2方向存在するので、実際には二つの等式が存在する。
$$ f \circ g = id $$ $$ g \circ f = id $$ 始対象(終対象)は同型の違いを除いて一意であると述べたが、任意の二つの始対象(終対象)は同型と言う意味であった。実際に簡単なので見ていこう。二つの始対象$i_1$と$i_2$があると仮定しよう。$i_1$は始対象なので、$i_1$から$i_2$への一意な射$f$が存在する。同様に、$i_2$は始対象なので、$i_2$から$i_1$への一意な射$g$が存在する。これらの射の合成はどうなるだろうか？

　合成$g \circ f$は$i_1$から$i_1$への射でなければならない。しかし、$i_1$は始対象であり、そのため$i_1$から$i_1$への射は唯一つだけ存在する。圏を扱っているので、$i_1$から$i_1$へ恒等射が存在することが分かっており、唯一つであるため、これはその合成と一致する。従って、$g \circ f$は恒等射と等しい。同様に、$i_2$から$i_2$に戻っていく射は唯一つであるため、$f \circ g$も恒等射に等しい。以上によって、$f$と$g$はお互いに逆射であることが証明された。従って、任意の二つの始対象は同型である。
　この証明では始対象からそれ自身はの射の一意性を使った。それなしでは「同型の違いを除いて」の部分を証明することはできない。しかし、なぜ$f$と$g$の一意性が必要なのであろうか？始対象は同型の違いを除いて一意であるだけでなく、一意な同型射の違いを除いて一意であるからである。原則としては二つの対象の間に一つ以上の射が存在するが、ここでは当てはまらない。この「一意な同型射の違いを除いて一意であること」はすべての普遍的構成の重要な性質である。

積

　次の普遍的構成は積である。二つの集合のデカルト積がペアの集合であることは知られている。しかし、構成する集合の積集合をつながるパターンとは何だろうか？もしそれを見つけ出したとして、他の圏へそれを一般化することはできるのであろうか？
　二つの関数、即ち積から各成分への射影が存在することは言える。これらの二つの関数$fst$と$snd$をそれぞれ次のように定義する。
$$ fst:(A, B) \rightarrow A $$ $$ fst(x, y) = x $$ $$ snd:(A, B) \rightarrow B $$ $$ snd(x, y) = y $$ 例えば、Javaで以下のように表すことができる。

class Pair<A,B> {
  final A first;
  final B second;
  Pair(A first, B second) {
    this.first = first;
    this.second = second;
  }
}

// (A,B)をPair<A,B>と同一視する
Function<Pair<A,B>, A> fst = p -> p.first;
Function<Pair<A,B>, B> snd = p -> p.second;

このような一見すると非常に限定された知識をもとにして、二つの集合$A$と$B$の積の成分を導くような集合の圏の対象と射のパターンを定義してみよう。このパターンは対象$c$と二つの射$p$及び$q$で構成され、それぞれ次のように対象$C$から$A$と$B$へ移す。
$$ p:C \rightarrow A $$ $$ q:C \rightarrow B $$

このパターンを満たす$C$はすべて積の候補と考えることができる。そのようなものが沢山存在するかもしれない。

　例えば、構成として、IntegerとBooleanを取り上げて、これらの積候補をサンプリングしてみよう。
　一つ目の候補を挙げる。Integerである。IntegerをIntegerとBooleanの積の候補として考えることができるのであろうか？実際にできる。次のような射影が存在する。

Function<Integer,Integer> p = x -> x;
Function<Integer,Boolean> q = x -> true;

かなり洗練さが足りないが、基準は満たしている。
　別の候補を挙げる。$(Integer,Integer,Boolean)$ である。三つの要素のタプル、トリプルである。これを正当な候補するような二つの射影は次のようなものである。クラスTripleを定義する。

class Triple<A,B,C> {
  final A first;
  final B second;
  final C third;
  Triple(A first, B second, C third){
    this.first = first;
    this.second = second;
    this.third = third;
  }
}

// (Integer,Integer,Boolean)をTriple<Integer,Integer,Boolean>と同一視する
Function<Triple<Integer,Integer,Boolean>,Integer> p = x -> x.first;
Function<Triple<Integer,Integer,Boolean>,Boolean> q = x -> x.third;

最初の候補は小さ過ぎる。積のIntegerの次元しか網羅できていないためである。次の候補は大き過ぎる。Integerの次元が不正に重複しているためである。
　しかし、普遍的な構成の別の部分である、ランク付けを探究していない。ここでのパターンの二つの例を比較できるようにしたい。一つの候補、対象$C$と二つの射影$p$と$q$を別の候補、対象$C'$ と二つの射影$p'$ と$q'$ を比較したい。$C'$ から$C$への射が存在すれば$C$は$C'$ と比べて「より良い」としたい。しかし、それでは弱すぎる。$C$の射影もまた$C'$ の射影と比べて「より良い」または「より普遍的である」としたい。それが意味することは、射影$p'$ と$q'$ が$ m $を使って、$p$と$q$から再構成できることである。
$$ p' = p \circ m $$ $$ q' = q \circ m $$ これらの等式を別の見方をすると、$ m $が$p'$ と$q'$ を分解している。これらの等式を自然数で、合成を乗算と見なすと、$ m $は$p'$ と$q'$ の公約数である。

　直観を働かせるため、二つの標準的な射影、$fst$と$snd$を持つペア $(Integer, Boolean)$ が、既に挙げた二つの候補より真に「より良い」ことを示そう。

　$(Integer,Boolean)$ をPair<Integer,Boolean>と見なして、最初の候補に対する写像$ m $は次のようになる。

Function<Integer,Pair<Integer,Boolean>> m = x -> new Pair<>(x, true);

実際、二つの射影$p$と$q$は次のように再構成できる。

Function<Integer,Integer> p = x -> fst.apply(m.apply(x));
Function<Integer,Boolean> q = x -> snd.apply(m.apply(x));

2番目の例に対する$ m $は同様に一意に次のように定められる。

Function<Triple<Integer,Integer,Boolean>,Pair<Integer,Boolean>> m = x -> new Pair<>(x.first,x.third);

$(Integer,Boolean)$ が二つの候補のどちらとも比べてもより良いこと示すことができた。なぜ反対は真ではないことを見ていこう。$p$と$q$から$fst$と$snd$を再構成するような$m'$ を見つけてみよう。
$$ fst = p \circ m' $$ $$ snd = q \circ m' $$ 最初の例では、$q$は常にtrueを返し、ペアの二つ目の成分はfalseを取りうる。$q$から$snd$を再構成することはできない。
　2番目の例は異なっている。$p$または$q$を実行した後十分な情報を得られる。しかし、$fst$と$snd$を分解する１つ以上の方法が存在する。$p$と$q$はトリプルの２つ目の成分を無視しているので、そこに値を設定することができない。次のようなものが得られる。

Function<Pair<Integer,Boolean>,Triple<Integer,Integer,Boolean>> m' = x -> new Triple<>(x.first, x.first, x.second);

もしくは

Function<Pair<Integer,Boolean>,Triple<Integer,Integer,Boolean>> m' = x -> new Triple<>(x.first, 42, x.second);

などである。
　すべてをまとめると、二つの射影$p$と$q$を持つ任意の型$C$を与えると、$C$からデカルト積 $(A, B)$ への一意で、デカルト積を分解するような$ m $が存在する。事実、それは$p$と$q$を結合してペアを作る。
$$ m:C \rightarrow (A, B) $$ $$ m(x) = (p(x), q(x)) $$ こうすることでデカルト積 $(A, B)$ はベストマッチする。それはこの普遍的構成が集合の圏において働くことを意味する。それは任意の二つの集合の積を選び取っているのである。
　今は集合については忘れ、同じ普遍的構成を使って任意の圏の二つの対象の積を定義しよう。このような積が常に存在するとは限らないが、存在するときは一意な同型の違いを除いてそれは一意である。

二つの対象$A$と$B$の${\bf 積}$は二つの射影を持つ対象$C$であり、二つの射影を持つ任意の他の対象$C^{'}$に対して、それらの射影を分解するような$C^{'}$から$C$への一意な射が存在する。

二つの候補から分解関数$ m $を生み出すような(高次な)関数はしばしば因子化(factorizer)と呼ばれる。ここでは、次のような関数である。
$$ factorizer:(C \rightarrow A) \rightarrow (C \rightarrow B) \rightarrow (C \rightarrow (A, B)) $$ $$ factorizer(p,q)(x) = (p(x), q(x)) $$

余積

　圏論の各構成と同様に、積も双対を持ち、これを余積と呼ぶ。積の矢印を逆向きにすると、二つの単射、即ち$a$及び$b$から$c$への射$i$と$j$を持つような対象$c$と言う結果となる。 $$ i:A \rightarrow C $$ $$ j:B \rightarrow C $$ ランク付けもまた反転する。対象$C$が単射$i^{'}$ と単射$j^{'}$ を持つ対象$C^{'}$ と比べて「より良い」とは、次のように単射を分解する$C$から$C^{'}$ への射$ m $が存在することである。
$$ i^{'} = m \circ i $$ $$ j^{'} = m \circ j $$ 「最も良い」このような対象、即ちそこから任意の他のパターンにつながるような一意な射を持つ対象であり、このような対象を余積と呼ぶ。もし余積が存在すれば、一意な同型の違いを除いて一意である。

二つの対象$A$と$B$の${\bf 余積}$は二つの単射を持つ対象$c$であり、二つの単射を持つ任意の他の対象$C^{'}$に対して、それらの単射を分解するような$C$から$C^{'}$への一意な射が存在する。

集合の圏では、余積は二つの集合の直和である。$A$と$B$の直和の要素は$A$の要素、または$B$の要素のいずれかである。二つの集合が重なっているならば、直和は共通部分の二つのコピーを含んでいる。直和の要素は元の集合を特徴付ける識別子でタグ付けされたものとして考えることができる。
　Javaには共用体がないので、タグ付けされた共用体で直和を定義することはできないが、次のようにして、直和を定義することができる。

interface Contact {
  enum tag {isPhone, isEmail};
  tag tag();
}
class PhoneNum<A> implements Contact {
  final A phoneNum;
  PhoneNum(A phoneNum) {
    this.phoneNum = phoneNum;
  }
  @Override
  public tag tag() {
    return tag.isPhone;
  }
}
class EmailAddr<A> implements Contact {
  final A emailAddr;
  EmailAddr(A emailAddr) {
    this.emailAddr = emailAddr;
  }
  @Override
  public tag tag() {
    return tag.isEmail;
  }
}

Contact helpdesk = new PhoneNum<Integer>(22222222);

ここで、タグは列挙型として定義し、PhoneNumとEmailAddrがコンストラクタ(単射)を提供している。
次のようなEitherを導入することでより標準的な実装を定義することができる。

abstract class Either<A,B> {
  abstract Boolean isLeft();
  abstract Boolean isRight();

  static class Left<A,B> extends Either<A,B> {
    final A left;
    Left(A left) {
      this.left = left;
    }
    @Override
    Boolean isLeft() {
      return true;
    }
    @Override
    Boolean isRight() {
      return false;
    }
  }

  static class Right<A,B> extends Either<A,B> {
    final B right;
    Right(B right) {
      this.right = right;
    }
    @Override
    Boolean isLeft() {
      return false;
    }
    @Override
    Boolean isRight() {
      return true;
    }

  }
}

これは二つの型引数AとBによる総称型で、Leftが型Aの値を取り、Rightが型Bの値を取る。
　積で因子化を定義したのと同様に、余積に対する因子化を定義できる。候補となる型$A$と二つの候補となる単射$i$と$j$を与えられたとき、(Either<A,B>に対応する)$A \oplus B$に対する因子化は次のような関数で構成される。
$$ factorizer:(A \rightarrow C) \rightarrow (B \rightarrow C) \rightarrow A \oplus B \rightarrow C $$ $$ factorizer(i,j)(a) = i(a) $$ $$ factorizer(i,j)(b) = j(b) $$

非対称

　２種類の双対な定義を見てきた。終対象は始対象の定義から矢印の向きを逆にすることで得ることができる。同様に余積は積の定義から得ることができる。しかし集合の圏論では、始対象は終対象と著しく異なっており、余積は積と著しく異なっている。後で触れるように、積は乗算のよに振る舞い、終対象は1の役割を担う。一方で、余積は加算のように振る舞い、始対象は零の役割を担う。特に有限集合に対して、積のサイズは個々の集合のサイズの積になり、余積のサイズは個々の集合のサイズの合計になる。
　次に集合の圏は矢印の反転の点で対称でないことを示す。
　空集合は任意の集合への一意な射を持つ一方で、空集合に戻ってくる射は持たない。シングルトンは任意の集合から自身への一意な射を持つだけでなく、(空集合を除く)任意の集合への射も持つ。既に見たように、終対象から出ていく射は他の集合の要素を選び取ると言う非常に重要な役割を担っている(空集合は要素を持たない。よって選び取ることもない)。
　積に対するシングルトン集合の関係は余積とは別である。かなり劣ったものであるが、シングルトン集合を使って、積のパターンに対する候補を考えてみよう。それは次のような二つの射影$p$と$q$、即ちシングルトンから各成分への関数を持つ。各々それぞれの集合から具体的な要素を選択する。積は普遍的であるので、ここでの候補、シングルトンから積への(一意な)射$ m $もまた存在する。この射は積集合から要素を選択する。即ち、それは具体的なペアを選択する。それはまた次のように二つの射影に分解する。
$$ p = fst \circ m $$ $$ q = snd \circ m $$ シングルトンの値()、即ちシングルトン集合の唯一の要素に作用すると、次のような等式が成り立つ。

p() = fst(m())
q() = snd(m())

m()は$ m $によって選び取られた積の要素なので、これらの等式によって示されているように、最初の集合から$p$によって選び取られた要素p()は$ m $によって選び取られたペアの最初の成分と一致する。同様にq()は２番目の成分に等しい。このことは、積の要素は成分集合からの要素のペアであると言う理解と完全に一致している。
　余積ではこのような単純な解釈はない。シングルトン集合から要素を抜き出す試みで、余積に対する候補としてシングルトン集合を試してみることができる。しかし、その場合、シングルトン集合から出ていく二つの射影ではなく、シングルトン集合に向かう二つの単射を使うことになる。それらは始域については何の情報ももたらさない(事実それらは入力引数を無視する)。余積からシングルトンへの一意な射も得られない。集合の圏は始対象から見たのと終対象からみたのと比べるとかなり異なっていることが分かる。
　次は集合の固有の性質ではなく、関数の性質、即ち ${\bf Set}$での射としての関数の性質である。一般的に関数は非対称である。では説明しよう。
　関数は始域の各要素に対して定義されるはずである(プログラミングでは、そのような関数を全値関数と呼ぶ)。しかし、それは終域全体を網羅しているとは限らない。その極端な場合を見てきた。シングルトン集合からの関数である。それは終域の唯一つの要素だけを選択する関数である(実際には、空集合からの関数は本当に極端である)。始域のサイズが終域のサイズより小さい場合、このような関数を終域の中への始域の埋め込みとして考えることが多い。例えば、シングルトン集合からの関数は終域の唯一つの要素の埋め込みとして考えることができる。そのような関数を埋め込み関数と呼ぶが、数学者は反対側の名前を与えることをより好む。終域を隙間なく占める関数を 全射(surjective) または 上の(onto)と読んでいる。
　非対称の他のケースとして、始域の多くの要素を終域の一つの要素へ写す関数がある。それはそれらの始域の要素を潰している。極端なケースは集合全体をシングルトンへ写す関数である。既に見たように多態関数unitがそれに当たる。潰すことは合成によって混ぜ合わせられることでしかできない。二つの潰すような関数の合成は個々の関数以上にさらに潰していく。数学者は潰さない関数に対して、単射(injective) または １対１(one-to-one) と呼んでいる。
　もちろん埋め込むでも潰すでもない関数も存在する。それらは 全単射(bijection) と呼ばれ、正確に対称である。なぜなら、それらは可逆であるからである。集合の圏では、同型は全単射と同じである。

knight_rose’s diary

Javaプログラマーのための圏論（５．積と余積）

積と余積

始対象

終対象

双対性

同型

積

余積

非対称