4. 归纳定义和归纳证明
·一个集合的归纳定义(inductive definition)通常分为三步：
·归纳基：一些基本的元素属于该集合；
·归纳步：定义一些规则（或者说操作），从该集合中已有的元素来生成该集合的新的元素；
·最小化：该集合中的所有元素都是通过基本元素以及所定义的规则生成的，换句话说，该集合是由基本元素及规则所生成的最小的集合。
·自然数集N的归纳定义：
[1]. 归纳基：0是一个自然数，即0Î N。
[2]. 归纳步：若n是自然数，则n的后继也是自然数。记n的后继为succ(n)，即若nÎN，则succ(n)ÎN。为方便起见，后面也记n的后继为n+1。
[3]. 最小化：所有的自然都通过步骤[1]和[2]得到，或者说自然数集是通过步骤[1]和[2]得到的最小集合。
·这种定义方式可推广到对其他一些概念的定义，例如上述多个集合的并、交、笛卡尔积以及多个元素的有序n元组都可通过递归的方式定义。例如，对于多个集合的并可定义为：
·归纳基：A1ÈA2 = {x | xÎA1或者xÎA2}
·归纳步：A1ÈA2…ÈAn = (A1ÈA2…ÈAn-1) È An
·这里不需要最小化，因为这里不是定义集合。
·数学归纳法：关于自然数的许多性质都可通过数学归纳法来证明，对于性质R，如果它对0成立，而且如果对于n成立的话，能够得到它对于n+1也成立，那么性质R对所有的自然数成立。这种证明方法的正确性本身可通过自然数的归纳定义来得到证明：
·定义集合S = {nÎN | 性质R对n成立}
·归纳基：根据上面的定义有0ÎS
·归纳步：根据上面的定义有如果nÎS，则n+1ÎS，所以S是满足上面自然数集的归纳定义中的1、2点的一个集合，而自然数集N是满足这两点的最小集合，所以有N ÍS，而显然有SÍN，所以S = N。
·数学归纳法举例：使用数学归纳法证明1 + 2 + … + n = (n * (n+1))/2
·归纳基：当n = 0时显然成立。
·归纳步：如果对于n成立，则有1 + 2 + … + n = (n * (n+1))/2（这称为归纳假设），现在要证对于n+1也成立。显然有：
1 + 2 + … + n + (n + 1) = (n * (n+1))/2 + (n+1) // 根据归纳假设
= (n * (n+1) + 2 * (n+1))/2 = ((n+1) * ((n+1) + 1))/2
因此要证的公式对于n+1成立，所以对于所有的自然数成立。
·显然在数学归纳法中，对于归纳基改为R对于自然数k成立，归纳步不变的话，则可证明R对于所有大于k的自然数都成立。
·在数学归纳法中，也可将归纳步改为如果R对于所有小于n的自然数成立，则推出R对于n也成立，即归纳步是假设对于所有小于n的自然数性质R成立来导出性质R对于自然数n成立。这种形式的数学归纳法通常称为第二数学归纳法。
