【正文】 如果 B無極小元，那么對(duì)每個(gè) a?B，可以找到某個(gè) a??B使得 a??a。 則可以從任意的a0?B開始，構(gòu)造一個(gè)無窮遞減序列 a0 ? a1 ? a2 ? … – 假定每個(gè)子集都有極小元 則不可能存在 a0 ? a1 ? a2 ? … ， 因該序列給出了無極小元的集合 {a0, a1, a2, … }。這個(gè)關(guān)系是良基關(guān)系 ? 良基關(guān)系的一些特點(diǎn) – 良基關(guān)系不一定有傳遞性 – 良基關(guān)系都是非自反的，即對(duì)任何 a?A， a ? a不成立；否則會(huì)出現(xiàn)無窮遞減序列 a ? a ? a ? … 歸 納 法 ? 引理 若 ?是集合 A上的二元關(guān)系， ?是良基的， 當(dāng)且僅當(dāng) A的每個(gè)非空子集都有極小元 ? 證明 – 假定 ?是良基的， 證明非空子集 B(B?A)有極小元 用反證法。 故 ?是良基的 歸 納 法 ? 命題 （良基歸納） 令 ?是集合 A上的良基關(guān)系， 令 P是 A上某個(gè)性質(zhì)， 若每當(dāng)所有的 P(b) (b ? a)為真，則 P(a)為真，即 ?a.(?b.(b ? a ? P(b)) ? P(a)) 那么，對(duì)所有的 a?A， P(a)為真 歸 納 法 ? 命題 （良基歸納） 若 ?a.(?b.(b ? a ? P(b)) ? P(a))，則 ?(a) ? 證明 – 若存在某個(gè) x?A使得 ?P(x)成立，則下面集合非空 B ? { a?A | ? P(a) } – 由引理 ， B一定有極小元 a?B – 但是 ， 對(duì)所有的 b ? a， P(b)一定成立 （ 否則 a不是B的極小元 ） – 這就和假定 ?b.(b ? a ? P(b)) ? P(a)矛盾 歸 納 法 ? 良基歸納法的使用 如何理解：若每當(dāng)所有的 P(b) (b ? a)為真，則 P(a)為真，即： (?b.(b ? a ? P(b)) ? P(a)) – 對(duì)某些 a，不存在 b，使得 b ? a，則 ?b.(b ? a ? P(b)) ? P(a) 等價(jià)于 P(a) （因?yàn)??b: ?. P(b)為真，其中 ?表示空集） – 對(duì)另一些 a，存在 b，使得 b ? a，則 ?b.(b ? a ? P(b)) ? P(a) 的證明是基于 ?b.(b ? a ? P(b)) 為真來推導(dǎo) P(a)為 真 歸 納 法 表 常用歸納形式的良基關(guān)系 歸納形式 良基關(guān)系 自然數(shù)歸納 (1) m ? n， 如果 m +1 ? n 自然數(shù)歸納 (2) m ? n， 如果 m ? n 結(jié)構(gòu)歸納 (1) e ? e?， 如果 e是 e?的直接子表達(dá)式 結(jié)構(gòu)歸納 (2) e ? e?， 如果 e是 e?的子表達(dá)式 基于證明的歸納 ? ? ??， 如果 ?是證明 ??的最后一步推導(dǎo)規(guī)則的某個(gè)前提的證明 歸 納 法 ? 自然數(shù)歸納 （ 形式 1） 為證明對(duì)所有 n， P(n)為真 ， 只需證明 P(0)以及證明對(duì)任何 m， 如果 P(m)為真則 P(m+1)必定為真 ? 自然數(shù)歸納 （ 形式 2） 為證明對(duì)所有 n， P(n)為真 ， 只需證明對(duì)任何 m，如果所有的 P(i) (i ? m)為真則 P(m)必定為真 ? 詞典序