natural number object (NNO)

圏論では自然数の対象(集合)も射で定義できる。自然数の対象を N としたとき次の2つの射が考えられる。ひとつめは N の要素のうちでゼロ要素 zero element を指し示す射 o だ。対象 N の特定の要素を表現するのに圏論では始対象 1 から N への射を用いる。

o : 1 -> N

ペアノの定義では自然数の要素 a があるときその後者 successor がありそれも自然数の要素だ。N の要素 a に対しその後者 successor を割り当てる関数 s は N -> N の射なので、次のようになる。

s : N -> N

これはオブジェクトと射を並べて次のように表すこともある。

1 -- o --> N -- s --> N

このダイアグラムが圏論の方法で表した自然数対象だ。しかし、実はこの表現だけでは不十分なのだ。たとえば N が要素 a だけを含む集合であるとする。すなわち、

N = { a }

だ。このとき始対象の要素を * とし、o : 1 -> N を次のように定義すると

a = o (*)

射 o は始対象 1 から対象 N のゼロ要素 a を指す射である。また、s : N -> N を N の要素 a からそれ自身の a への写像とすると、

a = s (a)

となって、s は対象 N から対象 N への endomap になる。したがってたったひとつの要素 a しか持たない集合 N について定義されたこの o と s もまた、

1 -- o --> N -- s --> N

というダイアグラムを満たしていることがわかる。これでは困るので実際の自然数対象 natural number object の定義はもう少し工夫してある。『圏論による論理学 高階論理とトポス』では自然数対象はつぎのように定義されている。

N をトポス E の対象とし、ζ、δ を各々 ζ : 1 -> N, δ : N -> N なるトポス E の射とする。その上で、1 - ζ -> N - δ -> N が次の条件 [#] をみたすとき、N は自然数対象 natural number object と呼ばれ、 nmo と略記される。

 条件 [#] : トポス E の任意の 1 - g -> A - h -> A なる対象と射に対して、下図を可換にする射 f : N -> N が一意的に存在する。

図を書くのが面倒なので、可換な関数を等号で結んだ式で代用する。

g = f . ζ : 1 -> A

h . f = f . δ : N -> A

最初の可換の式の意味は ζ がNのゼロ要素を表し、g が A のゼロ要素を表しているから、射 f によって N のゼロ要素を A のゼロ要素に変換できることを示している。

2番目の可換の式は N の要素に再帰関数 δ を関数適用した結果の N の要素をさらに f で対象 A の要素に変換したものが、N の要素をまず f で A の要素に変換して、その後にその要素に h を関数適用した結果が一致していることを示している。これはつまり、N の endomap δ と A の endomap h について f が準同型写像であることを意味している。

このダイアグラムが最初のダイアグラムで示した再帰性をしめす endomap を持った任意の A について成立するものが N である。つまり N は再帰的ダイアグラムの親玉というか、原型のような働きをもった対象である。

難しいことを言わなくても自然数の集合は N とみなしてよい。自然数が再帰的ダイアグラムの親方だといったが、それは次のような関数の再帰的定義をみればわかる。

fact 0 = 1
fact n = n * fact (n - 1)

Haskell ではおなじみの階乗の定義だ。ここで ζ : 1 -> N, g : 1 -> N を次のように定義する。

ζ = 0
g = 1

すると、

fact . ζ = g

という可換関係があることがわかる。

また、δ n = n + 1, h (fact(n)) = (n + 1) * (fact n) : N -> N

と定義すると fact n = n * fact (n-1) は

fact (δ (n-1)) = h (fact (n-1))

となるから、

fact . δ = h . fact

であることがわかる。したがって自然数対象 N から fact という関数によって階乗の対象 A の振る舞いが決定されることがわかる。

この例についてみると N = {0, 1, 2, 3, ... } という数列と A = {1, 1, 2, 6, 24, ... } という数列があって、数列 N については δ は自然数の次の数を求める関数で、h は階乗の数列の次の数を求める関数で、fact は自然数に対応する階乗の値を求める関数であると解釈できる。すると natural number object の抽象的なダイアグラムによる定義も至極当然の事のように思えてくる。

何気なく作っている Haskell のプログラムが実は圏論と密接な関係があることがわかると、取り付く島もなかった圏論というものに少し親しみを感じるようになった。
[PR]
by tnomura9 | 2014-05-10 19:46 | 圏論 | Comments(0)
<< 可換 付箋は前小口に貼る >>