from 帰納的関数

代入とか、代入合成などとも言う

普通の関数合成f=h\circ gをn引数関数の場合へと一般化する

下の定義のm=n=1のときが普通のやつやね

g_1,\cdots,g_m, hが計算可能なら、それらを合成したf(\vec{x})=h(g_1(\vec{x}),\cdots,g_m(\vec{x}))も計算可能

古典的順序と図式順序

g\circ fのように書く

順序を逆転して書く

f;gのように書く

合成のそのままの順序で書く

これらの用語は、『みんなの圏論』 p.13で出てきた

でも日英ともにググってもヒットしないのであまり一般的な用語ではない気がする

定義

任意の関数

g_1,\cdots,g_m:\mathbb{N}^n\rightarrow\mathbb{N}

h:\mathbb{N}^m\rightarrow\mathbb{N}

から、次のようにして定義される関数f:\mathbb{N}^n\rightarrow\mathbb{N}を構成する操作を合成という

f(\vec{x})=h(g_1(\vec{x}),\cdots,g_m(\vec{x}))

補足

見ればわかるが、f,g_1,\cdots,g_mは全てn引数の全域関数

個数を特定しない変数の並びを以下のように表している

\vec{x}:=x_1,\cdots,x_k

「関数のクラスEが合成に関して閉じている」とは

\forall f,g_1\cdots,g_n\in E\Rightarrow\lambda\vec{x}.f(g_1(\vec{x}),\cdots,g_n(\vec{x}))\in E

部分関数の場合は

参考