配列について考えます。この記事では、配列、リスト、タプル、シーケンスなどの言葉をあまり区別せずに、総称的に用語「配列」を使います。
内容：
配列のスライスとセレクション
配列aのn番目の項目（要素）を取り出すには、a[n] というインデックス記法がよく使われます。お馴染みですよね。最初の項目を a[0] と書くことが多いですが、1から始まるインデックスも使われるので、ここでは a[1] が最初の項目だとします。
配列の4番めから7番めを取り出すために a[4:7] とか a[4..7] とか書けるプログラミング言語があります。これは便利ですね（お尻のインデックスが言語により1ズレたりしますが）。こういう部分配列をスライスと呼ぶようです。
「4番めから7番め」は連続した範囲ですが、パランパランの部分を取り出したいときはどう書けばいいでしょう。Perlだと、a[1, 4, 6] のような書き方ができます。これもスライスと呼んでいるようですが、連続範囲とは違うので配列のセレクションと呼ぶことにします。
連続範囲のスライスは、セレクションの特別なものです。例えば：
- a[4..7] は a[4, 5, 6, 7] と同じ。
4..7 は、4, 5, 6, 7 の簡潔な略記と考えればいいでしょう。
セレクションの演算
aが十分に長い配列だとして、a[1, 4, 6] は長さ3の配列になります。新しい配列 a[1, 4, 6] に対してさらにセレクションを取ることを、a[1, 4, 6][1, 3] のように書きましょう。a[1, 4, 6][1, 3] は、a[1, 6] と同じであることは分かりますよね。
では、a[3, 4, 7, 8, 10, 11][1, 4, 6][1, 3] はどうでしょう？ 落ち着いて考えればこれも分かります。[1, 4, 6][1, 3] = [1, 6] は既に確認したので、a[3, 4, 7, 8, 10, 11][1, 4, 6][1, 3] = a[3, 4, 7, 8, 10, 11][1, 6] = a[3, 11] のような計算ができます。あるいは、別な順序で計算して：
a[3, 4, 7, 8, 10, 11][1, 4, 6][1, 3] = (a[3, 4, 7, 8, 10, 11][1, 4, 6])[1, 3] = a[3, 8, 11][1, 3]) = a[3, 11]
この計算を見ると、先頭のaは関係なくて実質は次のような計算です。
[3, 4, 7, 8, 10, 11][1, 4, 6][1, 3] = ([3, 4, 7, 8, 10, 11][1, 4, 6])[1, 3] = [3, 8, 11)[1, 3] = [3, 11]
最初にやったほうの計算は次の順序でした。
[3, 4, 7, 8, 10, 11][1, 4, 6][1, 3] = [3, 4, 7, 8, 10, 11]([1, 4, 6][1, 3]) = [3, 4, 7, 8, 10, 11][1, 6] = [3, 11]
つまり、セレクション操作のあいだに積（掛け算、二項演算）が定義されていて、それが結合法則を満たすことになっています。
これってモノイド？ いや、待ってください。モノイドの単位元（中立元）はありますか？ …… なんか見つかりません。単位元はありませんが、[1, 2, 3, 4, 5, 6][1, 4, 6] = [1, 4, 6] とか、[1, 4, 6][1, 2, 3] = [1, 4, 6]とかは成立しています。
そう、セレクションの全体は圏になるんです。
セレクションのダイアグラム表示
セレクションの全体はどんな圏を構成するのでしょうか。それを分かりやすく表示するために、絵を描いてみましょう。
まず、1からnまでの整数を横に並べます。以下の例では n = 7 です。次に、それらの整数のなかからいくつを選んで（セレクトして）、縦棒を描きます。縦棒の端（下側）には、1からmまでの整数で連番をふります。mは縦棒の本数です。以下の例では m = 3 です。
この図形の域は整数n（例では7）、余域は整数m（例では3）とします。域と余域の組は n→m と書きます。例では、7→3 です。
番号と縦棒からなる図形が2つあって、それをAとBとしたとき、cod(A) = dom(B) のとき、それらを繋ぐことができます。図形を縦に並べて連結して、まんなかの番号を消してしまいます。繋がってない中途半端な縦棒も消します。
図で縦棒が出ている番号がセレクトされた所なので、A = [1, 4, 6]7、B = [1, 3]3 です。下付きの7と3は、dom(A)、dom(B) を表します。dom(-)は、図の上側にならぶ整数の個数を表します。
なので、結合 A;B が作れて、dom(A;B) = dom(A) = 7、cod(A;B) = cod(B) = 2 となるはずですが、実際にそうなっています。
単調単射の圏
目先を変えて、別な圏の話をします。でも、セレクションと無関係な話ではありません。
[n] = {1, 2, ..., n} と記号の約束をします。[0] = 空集合、[1] = {1}、[2] = {1, 2} となります。写像 f:[n]→[m] が次の条件を満たすとき単調写像（monotonic/monotone mapping/function）と呼びます。
- i ≦ j ならば、f(i) ≦ f(j) （i, j∈[n]）
次を満たすときは、厳密単調写像（strictly monotonic/monotone mapping/function）です。
- i ＜ j ならば、f(i) ＜ f(j) （i, j∈[n]）
厳密単調写像は単射になるので、単調単射（monotonic/monotone injection）と言っても同じです。
[n]の形をした集合を対象として、単調単射を射とする圏ができます。この圏をMonotInj（固有名詞なので太字）としましょう。圏MonotInjは次のようなものです。
- Obj(MonotInj) = |MonotInj| = {[n] | n = 0, 1, 2, ...}
- MonotInj([n], [m]) = {f:[n]→[m] | i, j∈[n] に対して、i ＜ j ならば、f(i) ＜ f(j) である写像}
- dom(f) = (fの写像としての域)
- cod(f) = (fの写像としての余域)
- f;g = (写像としての結合)
- id[n] = (恒等写像)
圏MonotInjは集合圏Setの部分圏です。
セレクションの圏と単調単射の圏は同じ
セレクションの圏と単調単射の圏は、実は同じものです。矢印（射）の向きが逆になりますが、それ以外の違いはありません。セレクションの圏をSelecとすると、次が等式が成立します。
- Selec = MonotInjop
右肩のopは反対圏（opposite category）の意味です。
Selec = MonotInjop を納得するのは簡単です。セレクションの図形表示を見てください。図形を下から上の方向に見て、縦棒を整数値のあいだの対応関係とみなします。すると、単調単射の図示になるでしょう。上から下に見ればセレクション、下から上に見れば単調単射なのです。だから、反対だが同型な圏となるのです。
「可愛い圏」という記事で、身近にある小さな圏をいくつか紹介しました。SelecとMonotInjも可愛いでしょ。
