定义 数学归纳法 良序原理 对于自然数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成立,矛盾