Ologの再起関数の例：階乗

下記のExample 6.6.1のOlogが面白かったのでメモ。

Ologs: A Categorical Framework for Knowledge Representation

階乗のOlog

階乗のOlogをテキトーに翻訳して描いてみた。
（TikZで頑張る気力が出ないので、スライドでざっと描いている）

階乗を表していると言われてもぱっと見まったくわからない。
式変形を追わないと理解できそうにないので、とりあえず等式を抜き出す。

• $${s; p = \text{id}_A}$$

• $${s; q = d; f}$$

• $${i_0; f = \omega}$$

• $${i_1; f = s; m}$$

ただ、図式順のポイントフリースタイルは馴染みがないので、見慣れた形式に書き換える。

1. $${p(s(n)) = \text{id}_A(n)}$$

2. $${q(s(n)) = f(d(n))}$$

3. $${f(i_0(0)) = \omega(0)}$$

4. $${f(i_1(n)) = m(s(n))}$$

二つ組

射影$${p, q}$$、恒等写像$${\text{id}_A}$$の性質と式1, 2から、$${s}$$がどのような二つ組を作るかわかる。

$$
s(n) = ( \text{id}_A(n), f(d(n))) = (n, f(d(n)))
$$

s(n)の第一成分がわかる

s(n)の第二成分がわかる

場合分け

$${s}$$の式を式4と合わせておく。

$$
f(i_1(n)) = m(s(n)) = m(n, f(d(n)))
$$

さらに、直和に伴う包含写像$${i_0, i_1}$$の性質と式3から、次のように場合分けで書ける。

$$
f(n) = \left\{ \begin{array}{ll}
\omega(0) & \text{if}  n = 0\\
m(n, f(d(n))) & \text{if}  n \gt 0
\end{array} \right.
$$

n = 0の場合がわかる

n > 0の場合がわかる

残りの関数の選定

ここで、$${\omega, d, m}$$のそれぞれを、1への定数関数、前者関数、積とする。

• $${\omega(0) = 1}$$

• $${d(n) = n - 1}$$

• $${m(x, y) = x \times y}$$

すると、$${f}$$は次のように書けて、確かに階乗になる。

$$
f(n) = \left\{ \begin{array}{ll}
1 & \text{if}  n = 0\\
n \times f(n - 1) & \text{if}  n \gt 0
\end{array} \right.
$$

実用性は感じないけど、パズルっぽくて面白い。