证明数学归纳法和良序原理等价 李博文
证明数学归纳法和良序原理等价 李博文
定义 数学归纳法 良序原理 对于自然数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))→nN, P(n) 良序原理 设集合S,满足(SN)且(S),则 nS,mS,有n≤m。 即((SN)∧(S))→ nS,mS,(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)成立. 设集合CN,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,也包含它的元素的所有后继者,那么此集合包含全部 的数