ELEMENTARY

初等帰納的関数の定義は原始帰納を限定和と限定積に置き換わっている点を除けば原始帰納的関数と同様に定義される。（通常、減算は原始帰納的関数の基本関数に含めないが、原始帰納的である。）全ての関数は自然数に対して作用するものとする。基本関数は次のものからなる：

1. ゼロ関数： ${\displaystyle Z({\overrightarrow {x}})=0}$
2. 後者関数： ${\displaystyle S(x)=x+1}$
3. 射影関数: ${\displaystyle P_{\mu }^{\nu }({\overrightarrow {x}})=x_{\mu }}$
4. 減算関数: ${\displaystyle x{\dot {-}}y={\begin{cases}x-y&{\mbox{if }}x\geq y\\0&{\mbox{otherwise}}\end{cases}}}$

これらの基本関数に次の基本構成を繰り返して得られる関数が初等帰納的関数である：

1. 合成: ${\displaystyle h({\overrightarrow {x}})=f(g_{1}({\overrightarrow {x}}),g_{2}({\overrightarrow {x}}),\ldots ,g_{\mu }({\overrightarrow {x}}))}$
2. 限定和: ${\displaystyle f({\overrightarrow {x}},y)=\sum \limits _{z<y}g({\overrightarrow {x}},z)}$
3. 限定積: ${\displaystyle f({\overrightarrow {x}},y)=\prod \limits _{z<y}g({\overrightarrow {x}},z)}$

初等的関数の例としては次のものがある：

乗算関数： ${\displaystyle x\cdot y=\sum \limits _{z<y}x}$

加算関数： ${\displaystyle x+y=S(x)\cdot S(y){\dot {-}}S(x\cdot y)}$

冪乗関数： ${\displaystyle x^{y}=\prod \limits _{z<y}x}$

素数列： ${\displaystyle p_{n}=2,3,5,7,11,\ldots }$

初等的関数は限定原始再帰で閉じている。すなわち g, h と j が初等的であり

${\displaystyle f(t,{\bar {u}})\leq j(t,{\bar {u}})}$

${\displaystyle f(0,{\bar {u}})=g({\bar {u}})}$

${\displaystyle f(t+1,{\bar {u}})=h(t,{\bar {u}},f(t,{\bar {u}}))}$

ならば、 f もまた初等的である。

初等的関数は次の何れかの関数で支配される。すなわち任意の初等的関数は次に挙げる関数の何れかより小さい：

${\displaystyle x,2^{x},2^{2^{x}},2^{2^{2^{x}}},\ldots }$

このリストを枚挙する原始帰納的関数 ${\displaystyle f(c,x)=\underbrace {2^{2^{\cdot ^{\cdot ^{x}}}}} _{c}}$ は初等的でない：対角線論法による。${\displaystyle f(c,x)}$ が初等的と仮定する。すると ${\displaystyle f(x,x)}$ もまた初等的であるから、ある c に対して ${\displaystyle f(x,x)<f(c,x)}$ が成り立つ。ところがここで ${\displaystyle x=c}$ とすると不合理を得る。同様の増大度を持つテトレーションもまた初等的でない原始帰納的関数である。

クラス ELEMENTARY はレベル3のグジェゴルチク階層、深さ2のループプログラムで計算可能な関数のクラス、時間計算量が指数関数の定数回の反復で抑えられる関数のクラスなどと一致する。

限定積を用いずに定義できる初等的関数は低初等帰納的（英: lower elementary recursive）という。すなわち、低初等帰納的関数はゼロ関数, 後者関数, 射影関数, 減算関数から始めて関数合成と限定和を取る操作を有限回繰り返して得られる関数をいう。低初等的関数のクラスを LOWER-ELEMENTARY と書く。スコーレムの初等関数としても知られる^[1][2]。

初等的関数が潜在的に指数的な増大度を持つが、他方で低初等的関数は多項式の増大度を持つ。すなわち低初等的関数は多項式関数で支配される。したがって指数関数は初等的だが低初等的でない。

これは初等関数における同様の結果のアナロジーとして、低初等的関数もまた幾つかの単純な関数の合成によって記述できる^[2][3]。すなわち、多項式で抑えられる関数が低初等的であるのは、それが次の関数の合成で表せるとき、かつそのときに限る：射影, ${\displaystyle n+1}$, ${\displaystyle nm}$, ${\displaystyle n\,{\stackrel {.}{-}}\,m}$, ${\displaystyle n\wedge m}$, ${\displaystyle \lfloor n/m\rfloor }$, 指数関数　(${\displaystyle 2^{n}}$ または ${\displaystyle n^{m}}$) 。ただし二つ以上の指数関数の底を含まないものとする。例えば ${\displaystyle xy(z+1)}$ は底を1つ含み、${\displaystyle (x+y)^{yz+x}+z^{x+1}}$ は2つ含み、${\displaystyle 2^{2^{x}}}$ は3つ含む。ここで ${\displaystyle n\wedge m}$ はビットごとのANDを表す。

初等的関数のクラスは次の何れかの集合と射影の合成に関する閉包と一致する： ${\displaystyle \{n+1,n{\stackrel {.}{-}}m,\lfloor n/m\rfloor ,n^{m}\}}$, ${\displaystyle \{n+m,n{\stackrel {.}{-}}m,\lfloor n/m\rfloor ,2^{n}\}}$, ${\displaystyle \{n+m,n^{2},n{\bmod {m}},2^{n}\}}$ ここで ${\displaystyle n{\dot {-}}m=\max\{n-m,0\}}$は上で定義した減算関数である。^[4] したがって例えば素数列はこれらの関数と自由代入とを用いた表示を持つことになる。