证明数学归纳法和良序原理等价

证明数学归纳法和良序原理等价 李博文

证明数学归纳法和良序原理等价 李博文

定义 数学归纳法 良序原理 对于自然数n,假设P(n是某种性质,若:设集合S,满足(cN且S)则 彐n∈S,m∈S有n≤m。 1、P(0成立 2、假设成立,且能够推出Pk+)2即(SN)A(S=2)→ aneS, vmeS, nsm 立 则P(对任意自然数成立。 即:(P(0)A(P(k)→P(k+1)→neN,P(n)

定义 数学归纳法 对于自然数n，假设P(n)是某种性质，若： • 1、P(0)成立； • 2、假设P(k)成立，且能够推出P(k+1)成 立 则P(n)对任意自然数成立。 即：(P(0)∧(P(k)→P(k+1))→nN, P(n) 良序原理 设集合S，满足(SN)且(S),则 nS,mS,有n≤m。 即((SN)∧(S))→ nS,mS,(n≤m)

证明数学归纳法蕴含良序原理 令Pn为以下陈述:“任意自然数的子集,若包含某一自然数满足i≤n,则必有最小 元。”,设子集为S 然P(成立 2)设P成立,即∈S,i≤k需证明Pk+1成立 设集合C∈N,C包含k+1,若C中不存在,使得<k+1,则+1是最小元; 若存在<k+1由于k所以<k+1成立, 即P化k+1)成立 故良序原理成立

证明数学归纳法蕴含良序原理 令P(n)为以下陈述：“任意自然数的子集，若包含某一自然数 i,满足 i ≤ n，则必有最小 元。” ，设子集为S (1)显然P(0)成立 (2)假设P(k)成立，即i  S，i ≤ k.需证明P(k+1)成立. 设集合CN，C包含k+1，若C中不存在i，使得i<k+1，则k+1是最小元； 若存在i<k+1,由于i≤k,所以i<k+1成立， 即P(k+1)成立 故良序原理成立

证明良序原理蕴含数学归纳法 假设数学归纳法不正确,则设自然数集,$中的元素不满足性质P且S不为空集。 由良序原理可知,S必有最小值m。已知如下两条为真 1、P(成立; 2、假设Pk成立,且能够推出P(k+1)成立 由1可知m不为雾,故m-1也是自然数,记为n,又由2可知对于n+1,性质P成立 即对于m,性质P成立,矛盾

证明良序原理蕴含数学归纳法 假设数学归纳法不正确，则设自然数集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成立，矛盾

皮亚诺公理 10是一个数 2如n是一个数,那么n的后继者也是一个数 3.0不是任何一个数的后继者; 4如果n、m、都是自然数,并且有相等的后继者,则、m相等 5如果一个数的集合包含0,也包含它的元素的所有后继者,那么此集合包含全部 的数

皮亚诺公理 ⒈0是一个数； ⒉如n是一个数，那么n的后继者也是一个数； ⒊0不是任何一个数的后继者； ⒋如果n、m、都是自然数，并且有相等的后继者，则n、m相等； ⒌如果一个数的集合包含0，也包含它的元素的所有后继者，那么此集合包含全部 的数