归纳定义原理

 在讨论归纳定义原理的一般形式之前，首先证明它的一个特殊情况——引理 7.2的证明中用到过这种情况。它有助于对一般情况的讨论，使证明中的关键思想更为清晰。
 对此，给定\(\mathbb{Z}_+\)的无限子集\(C\)，考虑函数\(h:\mathbb{Z}_+\rightarrow C\)的下述归纳公式：
$$\begin{aligned}  &h(1)=C\text{的最小元}\\  &h(i)=[C-h(\{1,\cdots,i-1\})]\text{的最小元},\text{对于}i>1\end{aligned}\tag{$*$}\label{*}$$我们证明存在唯一的一个函数\(h:\mathbb{Z}_+\rightarrow C\)满足这个归纳公式。
 第一步，证明存在定义在\(\mathbb{Z}_+\)的截上的函数满足\(\eqref{*}\)。
 引理8.1 给定\(n\in\mathbb{Z}_+\)，存在一个函数

\[f:\{1,\cdots,n\}\longrightarrow C\]
对于定义域中所有\(i\)满足\(\eqref{*}\)。
 证明 这个引理讲的是一个依赖于\(n\)的论断，因此可以用归纳法加以证明。设\(A\)为所有使引理成立的\(n\)的集合。我们证明\(A\)是一个归纳集，从而有\(A=\mathbb{Z}_+\)。
 当\(n=1\)时引理成立，因为由

\[f(1)=C\text{的最小元}\]
定义的函数\(f:\{1\}\rightarrow C\)满足\(\eqref{*}\)。
 假定引理对于\(n-1\)成立，以下证明引理对于\(n\)成立。根据归纳假定，存在函数\(f':\{1,\cdots,n-1\}\rightarrow C\)，对于定义域\(\{1,\cdots,n-1\}\)中的所有\(i\)满足\(\eqref{*}\)。用

\[\begin{aligned}  &f(i)=f'(i),\text{对于}i\in\{1,\cdots,n-1\}\\  &f(n)=[C-f'(\{1,\cdots,n-1\})]\text{的最小元}\end{aligned}\]
定义一个函数\(f:\{1,\cdots,n\}\rightarrow C\)。因为\(C\)为无限集，\(f'\)不是满射；因此集合\(C-f'(\{1,\cdots,n-1\})\)非空，并且\(f(n)\)有定义。这个定义是比较容易接受的，它不是用\(f\)自身而是用给定的函数\(f'\)来定义\(f\)。
 容易验证，\(f\)对于定义域中所有的\(i\)满足\(\eqref{*}\)。因为当\(i\leqslant n-1\)时，\(f\)等于\(f'\)，所以函数\(f\)满足\(\eqref{*}\)。当\(i=n\)时，\(f\)定义为

\[f(n)=[C-f'(\{1,\cdots,n-1\})]\text{的最小元}\]
而\(f'(\{1,\cdots,n-1\})=f(\{1,\cdots,n-1\})\)，所以\(f\)也满足\(\eqref{*}\)。

$\square$

 引理 8.2 设\(f:\{1,\cdots,n\}\rightarrow C\)与\(g:\{1，\cdots,m\}\rightarrow C\)对于它们各自定义域中的所有\(i\)都满足\(\eqref{*}\)。则对于两个定义域中所有公共的\(i\)，\(f(i)=g(i)\)。
 证明 设结论不真，令\(i\)为使得\(f(i)\ne g(i)\)的最小整数，根据\(\eqref{*}\)

\[f(1)=C\text{的最小元}=g(1)\]

所以整数\(i\)不是1。对于所有\(j1\end{aligned}\tag{$+$}\label{+}$$ \(\eqref{+}\)称为\(h\)的一个归纳公式（recursion formular）。它决定了\(h(1)\)，并且用\(h\)在所有小于\(i\)的正整数处的值来表出\(h\)在\(i>1\)处的值。

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

新版吗？好像是停更了吧。