ELEMENTARY
初等的関数は限定原始再帰で閉じている。すなわち g, h と j が初等的であり
f ( t , u ̄ ) ≤ j ( t , u ̄ ) {\displaystyle f(t,{\bar {u}})\leq j(t,{\bar {u}})}
f ( 0 , u ̄ ) = g ( u ̄ ) {\displaystyle f(0,{\bar {u}})=g({\bar {u}})}
f ( t + 1 , u ̄ ) = h ( t , u ̄ , f ( t , u ̄ ) ) {\displaystyle f(t+1,{\bar {u}})=h(t,{\bar {u}},f(t,{\bar {u}}))}
ならば、 f もまた初等的である。
初等的関数は次の何れかの関数で支配される。すなわち任意の初等的関数は次に挙げる関数の何れかより小さい:
x , 2 x , 2 2 x , 2 2 2 x , ... {\displaystyle x,2^{x},2^{2^{x}},2^{2^{2^{x}}},\ldots }