自然数 (5)再帰的定義
定理20
$X~$を空でない集合、$x_0\in X~$を元、$g:\mathbb{N}\times X\to X~$を写像とする。このとき、次の条件を満たす写像$~f:\mathbb{N}\to X~$がただ1つ存在する。 \begin{align} (1)&~f(0)=x_0\\ (2)&~f(n+1)=g(n,f(n)) \end{align}
$\varphi:\mathbb{N}\times X\to\mathbb{N}\times X~$を
\[
\varphi(n,x)=(n+1,g(n,x))
\]
となるように定める。
このとき、$(\mathbb{N}\times X,(0,x_0),\varphi)~$に対して定理1を用いると \begin{align} (\mathrm{i})&~f(0)=(0,x_0)\\ (\mathrm{ii})&~f\circ\sigma=\varphi\circ f \end{align} を満たす写像$~f:\mathbb{N}\to\mathbb{N}\times X~$がただ1つ存在する。
$f(n)=(f_1(n),f_2(n))~$と表すことにすると性質$(\mathrm{i}),(\mathrm{ii})$は \begin{align} (\mathrm{i})_1&~f_1(0)=0\\ (\mathrm{ii})_1&~f_1(n+1)=f_1(n)+1\\ (\mathrm{i})_2&~f_2(0)=x_0\\ (\mathrm{ii})_2&~f_2(n+1)=g(f_1(n),f_2(n)) \end{align} と書きかえられる。
$(\mathrm{i})_1,(\mathrm{ii})_1~$と命題3の一意性から$~f_1=\sigma_0~$となる。
つまり、すべての$~n\in\mathbb{N}~$に対して$~f(n)=n~$である。
よって、$(\mathrm{i})_2,(\mathrm{ii})_2~$は \begin{align} (\mathrm{i})_2&~f_2(0)=x_0\\ (\mathrm{ii})_2&~f_2(n+1)=g(n,f_2(n)) \end{align} となる。
したがって、$f_2:\mathbb{N}\to X~$が求めていた写像である。
$$\square$$
このとき、$(\mathbb{N}\times X,(0,x_0),\varphi)~$に対して定理1を用いると \begin{align} (\mathrm{i})&~f(0)=(0,x_0)\\ (\mathrm{ii})&~f\circ\sigma=\varphi\circ f \end{align} を満たす写像$~f:\mathbb{N}\to\mathbb{N}\times X~$がただ1つ存在する。
$f(n)=(f_1(n),f_2(n))~$と表すことにすると性質$(\mathrm{i}),(\mathrm{ii})$は \begin{align} (\mathrm{i})_1&~f_1(0)=0\\ (\mathrm{ii})_1&~f_1(n+1)=f_1(n)+1\\ (\mathrm{i})_2&~f_2(0)=x_0\\ (\mathrm{ii})_2&~f_2(n+1)=g(f_1(n),f_2(n)) \end{align} と書きかえられる。
$(\mathrm{i})_1,(\mathrm{ii})_1~$と命題3の一意性から$~f_1=\sigma_0~$となる。
つまり、すべての$~n\in\mathbb{N}~$に対して$~f(n)=n~$である。
よって、$(\mathrm{i})_2,(\mathrm{ii})_2~$は \begin{align} (\mathrm{i})_2&~f_2(0)=x_0\\ (\mathrm{ii})_2&~f_2(n+1)=g(n,f_2(n)) \end{align} となる。
したがって、$f_2:\mathbb{N}\to X~$が求めていた写像である。
定理21
$X,Y~$を空でない集合とし、
\begin{align}
&h:X\longrightarrow Y\\
&g:\mathbb{N}\times X\times Y\longrightarrow Y
\end{align}
を任意の写像とする。このとき、次の条件を満たす写像$~f:\mathbb{N}\times X\to Y~$がただ1つ存在する。 \begin{align} (1)&~f(0,x)=h(x)\\ (2)&~f(n+1,x)=g(n,x,f(n,x)) \end{align}
$x\in X~$を任意にとり固定する。
このとき、定理20より \begin{align} (1)&~f_x(0)=h(x)\\ (2)&~f_x(n+1)=g(n,x,f_x(n)) \end{align} となる写像$~f_x:\mathbb{N}\to Y~$がただ1つ存在する。
$f:\mathbb{N}\times X\to Y~$を \[ f(n,x)=f_x(n) \] と定めれば$~f~$が求めていた写像である。
$$\square$$
このとき、定理20より \begin{align} (1)&~f_x(0)=h(x)\\ (2)&~f_x(n+1)=g(n,x,f_x(n)) \end{align} となる写像$~f_x:\mathbb{N}\to Y~$がただ1つ存在する。
$f:\mathbb{N}\times X\to Y~$を \[ f(n,x)=f_x(n) \] と定めれば$~f~$が求めていた写像である。