原始再帰関数の道具箱

次はいずれも原始再帰的である。

1. $x+y$、$x\cdot y$、$x^y$、$x!$、前者 $\mathrm{pd}(x)$（$\mathrm{pd}(0)=0$, $\mathrm{pd}(x+1)=x$）、切り捨て差 $x\dot-y=\max(x-y,0)$、符号 $\mathrm{sg}(x)$（$x=0$ なら $0$、それ以外 $1$）。
2. 原始再帰的な述語の否定・論理積・論理和。原始再帰的な関数による場合分け定義。
3. $f$ が原始再帰的ならば、有界和 $\sum_{i<y}f(\vec{x},i)$ と有界積 $\prod_{i<y}f(\vec{x},i)$。
4. $P$ が原始再帰的述語ならば、有界量化 $\exists i<y\,P(\vec{x},i)$、$\forall i<y\,P(\vec{x},i)$、および有界最小化 $\mu i<y\,[P(\vec{x},i)]$（そのような $i$ のうち最小のもの。なければ $y$）。
5. 商 $\lfloor x/y\rfloor$、余り $x\bmod y$、約数関係 $y\mid x$、素数述語、$i$ 番目の素数 $p_i$（$p_0=2$）、素因数分解における指数 $(n)_i$（$n$ の素因数分解での $p_i$ の指数）。