[科普中国]-归纳定义

归纳定义是定义集合的一种方法，对于用归纳定义给出的集合，要证明其中所有的元都有某个性质，通常用归纳证明。集合的归纳定义通常包括若干规则，用来生成其中的元，然后再说明，只有由这些规则生成的对象才是这个集合的元。归纳定义的一种等价的陈述是将所要定义的集合刻画成封闭于这些规则的最小的集。

简介归纳定义是基于数学归纳法的一种定义方法，用于定义全体自然数集 上的函数。

例如，有一个定义城为 N的函数 f 需要定义。如果有某种可用的相对于全体自然数来讲是一致的方法，则可以利用这个方法来归纳地定义函数 f 。

步骤具体的依据归纳定义的形式分为两步。

第一步: 定义 f(0) 的值;

第二步: 依据那种事先给定的一致方法，从依照假定已经有定义的 f(n) 的值出发，进一步来定义 f(n+1) 的值。

当这两步完成以后，就可以由数学归纳法确认f 在 上已经定义好了。这里所要强调的是不会在定义过程中被改变的事先给定或者选定的那种一致方法的作用。如果没有那样的方法来保证，试图定义的对象可能不会作为一个函数而存在。

归纳定义的可靠性可以形式化为如下定理：设 X 为一非空集合， 为一函数。则存在唯一的函数 满足 及对任意这里的函数 g 就是前面所说的那种事先给定或者选定的一致的方法。

在应用中，归纳定义的具体形式可以多种多样。像数学归纳法一样，归纳定义也有许多变种。例如，归纳定义更多地是用于定义序列而非函数(当然，严格地讲，序列也是函数)。另外，复杂的归纳定义往往和证明及其他构造交织在一起，而非简单地采用如上的标准形式。有时，出于某种原因，或是为了方便，归纳定义的第一步不是定义 f(0) 的值，而是对某个非 0 的 定义 f(a) 的值，或是同时定义多个的值。又有时，归纳定义的第二步假定所有，的值都已有定义，而进一步由此定义的值。等等。

在集合论中，归纳定义的定义域通常形式上被认为是所有有穷序数的集合 而非写作 之所以会如此是因为数学归纳法的本质是利用了是一个秩序集的事实，并由此可以推广数学归纳法到一般的秩序集甚至有秩关系上。1

结构基础条款：规定某些元素为待定义集合成员，集合其它元素可以从基本元素出发逐步确定 。

归纳条款：规定由已确定的集合元素去进一步确定其它元素的规则 。

终极条款：规定待定义集合只含有基础条款和归纳条款所确定的成员。

其中，基础条款和归纳条款称作“完备性条款”，必须保证毫无遗漏产生集合中所有成员。终极条款又称“纯粹性条款”，保证集合中仅包含满足完备性条款的那些对象。

归纳定理简述归纳定理，又称递归定理，是对归纳定义合理性的一个严格说明。

内容给定a0∈A及函数h: A→A，则存在唯一一个函数f: N→A，满足：

(1) f(0)=a0；

(2) f(n+)=h(f(n))。

证明(唯一性)假设存在满足条件(1)(2)的函数f1: N→A和f2: N→A。为了证明惟一性，只需证f1≡f2，亦即∀n∈N，f1(n)=f2(n)。对n归纳：n=0时，根据(1)，有f1(0)=a0=f2(0)。

设f(n)=g(n)，根据(2)，有f1(n+)=h(f1(n))=h(f2(n))=f2(n+)。所以，根据数学归纳原理， f1≡f2，惟一性得证。

(存在性)定义N到A的归纳关系r(r⊂N×A)如下:

Ⅰ. (0,x0)∈r；

Ⅱ. 若(n,x)∈r, 则(n+,h(x))∈r。

易知，这样的归纳关系r一定是存在的，例如N×A即为一个归纳关系。(因为要寻找N到A的函数，而函数对每个原象只能映射到一个象，因此不妨考虑所有归纳关系中的最小者，下面来考虑寻找这个最小的归纳关系。)

令f={(n,x)∈N×A|(n,x)∈每个归纳关系}，则由于f⊂每个归纳关系，所以f具有最小性。下面来验证f满足归纳关系的条件Ⅰ,Ⅱ来证明f为最小的归纳关系。

考虑数学归纳法，首先由Ⅰ知(0,x0)∈每一个归纳关系，故(0,x0)∈f。假设(n,x)∈f，即(n,x)∈每一个归纳关系。由Ⅱ知(n+,h(x))∈每一个归纳关系，因此(n+,h(x))∈f。所以，根据数学归纳原理，f是N到A的一个归纳关系，且f具有最小性。

下证f是N到A的函数，即满足∀m∈N，∃!x∈A，(m,x)∈f。对m采用数学归纳法：

1. 当m=0，因为f是归纳关系，因此(0,x0)∈f。假设x0不是唯一的，即有x1≠x0，x1∈a且(0,x1)∈f，考虑集合f -{(0,x1)}，它满足

(Ⅰ)(0,x0)∈f - {(0,x1)}(因为x1≠x0)

(Ⅱ)设(n,x)∈f-{(0,x1)}，由于f-{(0,x1)}⊂f，所以(n,x)∈f，由于f是归纳关系，所以(n+,h(x))∈f。由于n+≠0，(n+,h(x))∈f - {(0,x1)}。

根据(Ⅰ)(Ⅱ)，f-{(0,x1)}也是归纳关系，这与f的最小性矛盾，因此∃!x∈A，(0,x)∈f。

2. 假设对m, ∃!x1∈A，s.t. (m,x1)∈f。下证对m+，∃!x∈A，(m+,x)∈f。因为根据归纳假设(m,x1)∈f，又f满足归纳关系的条件(Ⅱ)，因此(m+,h(x1))∈f。下面考虑x的惟一性，假设∃t≠h(x1)，s.t. (m+,t)∈f。考虑集合f-{(m+,t)}，它满足

(Ⅰ)(0,x0)∈f-{(m+,t)}(因为m+≠0)

(Ⅱ)设(n,x)∈f - {(m+,t)}，由于f - {(m+,t)}⊂f，所以(n,x)∈f。由于f是归纳关系，所以(n+,h(x))∈f。当n+=m+(即n=m)时，x=x1，所以h(x)=h(x1)≠t。所以(n+,h(x))≠(m+,t)，故(n+,h(x))∈f - {(m+,t)}。

根据(Ⅰ)(Ⅱ)，f-{(m+,t)}也是归纳关系，这与f的最小性矛盾，因此∃!x∈A，(m+,x)∈f。

至此, 根据数学归纳原理，f是N到A的函数。由于f满足：

Ⅰ. (0,x0)∈f；

Ⅱ. 若(n,x)∈f，则(n+,h(x))∈f。

因此，Ⅰ. f(0)=x0；

Ⅱ. 当f(n)=x时, f(n+)=h(x)=h(f(n))。

于是，递归定义的合理性得到了圆满的证明。2

本词条内容贡献者为:

尚华娟 - 副教授 - 上海财经大学