数学归纳法在高中阶段就学过了，我在抽象代数系列课程安排这个主题是因为在证明数论定理时会经常用到数学归纳法。数学归纳法的作用是能够证明一个命题序列，而不只是单独的命题。数学归纳法有两个，叫第一数学归纳法和第二数学归纳法。

第一数学归纳法：

给定一组关于自然数n>=1的命题S（n），假设

(i) 基础步骤：S(1)成立；

(ii) 归纳步骤：若S(k)成立，则S(k 1)也成立。

那么对一切整数n>=1,S(n)都成立。

第二数学归纳法：

给定一组关于自然数n>=1的命题S（n），假设

基础步骤：S(1)成立；

(i) 基础步骤：S(1)成立；

(ii) 归纳步骤：若对n的所有前导k有S(k)成立，则S(n)也成立。

那么对一切整数n>=1,S(n)都成立。

现在来证明第一数学归纳法和第二数学归纳法等价。咋一看，好像第二归纳法有一个更强的归纳假设，也就是说如果一个命题能够被第一归纳法证明，那么它一定能被第二归纳法证明。现在设集合A包含所有能被第一归纳法证明的命题，集合B包含所有能被第二归纳法证明的命题。任意命题x属于A，那么显然它一定属于B，这样A就是B的子集，如果第二归纳法是正确的，说明B中的所有命题都是真命题，由于A是B的子集，则A中的所有命题也是真命题，所以第一归纳法也正确，这说明第二归纳法能推出第一归纳法。

实际上两种归纳法是等价的，要证明等价性，就还需要证明第一归纳法能推出第二归纳法，即证明B是A的子集。现在任取B中的一个命题序列p，由第二归纳法可知，p(1)成立，p(1)且p(2)且...且p(k-1)可以推出p(k),现在构造新的命题q(n)=p(1)且p(2)且...且p(n)，则q(k-1)可以推出q(k)，并且q(1)=p(1)成立，这说明命题q能被第一归纳法证明，而命题q成立，p肯定成立，所以p能被第一归纳法证明，则p属于A，说明B是A的子集，则第一归纳法也能推出第二归纳法。这样两种归纳法就是等价的。

这里要注意，我证明了两种归纳法等价，并没有证明两种数学归纳法是成立的，事实上数学归纳法是由最小整数公理导出的，它的叙述是：自然数集N的每个非空子集C中都含有一个最小整数。

现在我用它来证明第一归纳法。假设C是使得命题序列S（n）为假命题的所有正整数n构成的集合，则根据最小整数公理，C中一定含有最小整数。设它为m，因为S（1）是成立的，所以m必定大于等于2，m-1大于等于1。现在S(m)为假命题，由于m最小整数，所以S(m-1)就为真命题，而根据第一归纳法的归纳步骤，若S(m-1)成立则S(m)成立，这与S(m)为假命题矛盾，所以C是空集，即满足第一数学归纳法条件的命题序列都成立。