证明数学归纳法和良序原理等价 李博文
定义 数学归纳法 良序原理 对于自然数n，假设P(n)是某种性质，若： 1、P(0)成立； 2、假设P(k)成立，且能够推出P(k+1)成 立 则P(n)对任意自然数成立。 即：(P(0)∧(P(k)→P(k+1))→nN, P(n) 设集合S，满足(SN)且(S),则 nS,mS,有n≤m。 即((SN)∧(S))→ nS,mS,(n≤m)
证明数学归纳法蕴含良序原理 令P(n)为以下陈述：“任意自然数的子集，若包含某一自然数 i,满足 i ≤ n，则必有最小元。” ，设子集为S (2)假设P(k)成立，即i S，i ≤ k.需证明P(k+1)成立. 设集合CN，C包含k+1，若C中不存在i，使得i<k+1，则k+1是最小元； 若存在i<k+1,由于i≤k,所以i<k+1成立， 即P(k+1)成立 故良序原理成立。
证明良序原理蕴含数学归纳法 假设数学归纳法不正确，则设自然数集S，S中的元素不满足性质P且S不为空集。由良序原理可知，S必有最小值m。已知如下两条为真： 1、P(0)成立； 2、假设P(k)成立，且能够推出P(k+1)成立 由1可知m不为零，故m-1也是自然数，记为n，又由2可知对于n+1，性质P成立，即对于m，性质P成立，矛盾。
皮亚诺公理 ⒈0是一个数； ⒉如n是一个数，那么n的后继者也是一个数； ⒊0不是任何一个数的后继者； ⒋如果n、m、都是自然数，并且有相等的后继者，则n、m相等； ⒌如果一个数的集合包含0，也包含它的元素的所有后继者，那么此集合包含全部 的数。