複製鏈接
請複製以下鏈接發送給好友

歸納定義

鎖定
歸納定義是定義集合的一種方法,對於用歸納定義給出的集合,要證明其中所有的元都有某個性質,通常用歸納證明。集合的歸納定義通常包括若干規則,用來生成其中的元,然後再説明,只有由這些規則生成的對象才是這個集合的元。歸納定義的一種等價的陳述是將所要定義的集合刻畫成封閉於這些規則的最小的集。
中文名
歸納定義
外文名
definition by induction
它    是
定義集合的一種方法
基礎條款
規定某些元素為待定義集合成員
定    義
定義全體自然數集上的函數

目錄

歸納定義簡介

歸納定義是基於數學歸納法的一種定義方法,用於定義全體自然數集
上的函數。
例如,有一個定義域為 N的函數 f 需要定義。如果有某種可用的相對於全體自然數來講是一致的方法,則可以利用這個方法來歸納地定義函數 f 。

歸納定義步驟

具體的依據歸納定義的形式分為兩步。
第一步: 定義 f(0) 的值;
第二步: 依據那種事先給定的一致方法,從依照假定已經有定義的 f(n) 的值出發,進一步來定義 f(n+1) 的值。
當這兩步完成以後,就可以由數學歸納法確認f 在
上已經定義好了。這裏所要強調的是不會在定義過程中被改變的事先給定或者選定的那種一致方法的作用。如果沒有那樣的方法來保證,試圖定義的對象可能不會作為一個函數而存在。
歸納定義的可靠性可以形式化為如下定理:設 X 為一非空集合,
為一函數。則存在唯一的函數
滿足
及對任意
這裏的函數 g 就是前面所説的那種事先給定或者選定的一致的方法。
在應用中,歸納定義的具體形式可以多種多樣。像數學歸納法一樣,歸納定義也有許多變種。例如,歸納定義更多地是用於定義序列而非函數(當然,嚴格地講,序列也是函數)。另外,複雜的歸納定義往往和證明及其他構造交織在一起,而非簡單地採用如上的標準形式。有時,出於某種原因,或是為了方便,歸納定義的第一步不是定義 f(0) 的值,而是對某個非 0 的
定義 f(a) 的值,或是同時定義多個
的值。又有時,歸納定義的第二步假定所有
,的值都已有定義,而進一步由此定義
的值。等等。
在集合論中,歸納定義的定義域通常形式上被認為是所有有窮序數的集合
而非寫作
之所以會如此是因為數學歸納法的本質是利用了
是一個秩序集的事實,並由此可以推廣數學歸納法到一般的秩序集甚至有秩關係上。 [1] 

歸納定義結構

基礎條款:規定某些元素為待定義集合成員,集合其它元素可以從基本元素出發逐步確定 。
歸納條款:規定由已確定的集合元素去進一步確定其它元素的規則 。
終極條款:規定待定義集合只含有基礎條款和歸納條款所確定的成員。
其中,基礎條款和歸納條款稱作“完備性條款”,必須保證毫無遺漏產生集合中所有成員。終極條款又稱“純粹性條款”,保證集合中僅包含滿足完備性條款的那些對象。

歸納定義歸納定理

歸納定義簡述

歸納定理,又稱遞歸定理,是對歸納定義合理性的一個嚴格説明。

歸納定義內容

給定a0∈A及函數h: A→A,則存在唯一一個函數f: N→A,滿足:
(1) f(0)=a0
(2) f(n+)=h(f(n))。

歸納定義證明

(唯一性)假設存在滿足條件(1)(2)的函數f1: N→A和f2: N→A。為了證明惟一性,只需證f1≡f2,亦即∀n∈N,f1(n)=f2(n)。對n歸納:n=0時,根據(1),有f1(0)=a0=f2(0)。
設f(n)=g(n),根據(2),有f1(n+)=h(f1(n))=h(f2(n))=f2(n+)。所以,根據數學歸納原理, f1≡f2,惟一性得證。
(存在性)定義N到A的歸納關係r(r⊂N×A)如下:
Ⅰ. (0,x0)∈r;
Ⅱ. 若(n,x)∈r, 則(n+,h(x))∈r。
易知,這樣的歸納關係r一定是存在的,例如N×A即為一個歸納關係。(因為要尋找N到A的函數,而函數對每個原象只能映射到一個象,因此不妨考慮所有歸納關係中的最小者,下面來考慮尋找這個最小的歸納關係。)
令f={(n,x)∈N×A|(n,x)∈每個歸納關係},則由於f⊂每個歸納關係,所以f具有最小性。下面來驗證f滿足歸納關係的條件Ⅰ,Ⅱ來證明f為最小的歸納關係。
考慮數學歸納法,首先由Ⅰ知(0,x0)∈每一個歸納關係,故(0,x0)∈f。假設(n,x)∈f,即(n,x)∈每一個歸納關係。由Ⅱ知(n+,h(x))∈每一個歸納關係,因此(n+,h(x))∈f。所以,根據數學歸納原理,f是N到A的一個歸納關係,且f具有最小性。
下證f是N到A的函數,即滿足∀m∈N,∃!x∈A,(m,x)∈f。對m採用數學歸納法:
1. 當m=0,因為f是歸納關係,因此(0,x0)∈f。假設x0不是唯一的,即有x1≠x0,x1∈a且(0,x1)∈f,考慮集合f -{(0,x1)},它滿足
(Ⅰ)(0,x0)∈f - {(0,x1)}(因為x1≠x0)
(Ⅱ)設(n,x)∈f-{(0,x1)},由於f-{(0,x1)}⊂f,所以(n,x)∈f,由於f是歸納關係,所以(n+,h(x))∈f。由於n+≠0,(n+,h(x))∈f - {(0,x1)}。
根據(Ⅰ)(Ⅱ),f-{(0,x1)}也是歸納關係,這與f的最小性矛盾,因此∃!x∈A,(0,x)∈f。
2. 假設對m, ∃!x1∈A,s.t. (m,x1)∈f。下證對m+,∃!x∈A,(m+,x)∈f。因為根據歸納假設(m,x1)∈f,又f滿足歸納關係的條件(Ⅱ),因此(m+,h(x1))∈f。下面考慮x的惟一性,假設∃t≠h(x1),s.t. (m+,t)∈f。考慮集合f-{(m+,t)},它滿足
(Ⅰ)(0,x0)∈f-{(m+,t)}(因為m+≠0)
(Ⅱ)設(n,x)∈f - {(m+,t)},由於f - {(m+,t)}⊂f,所以(n,x)∈f。由於f是歸納關係,所以(n+,h(x))∈f。當n+=m+(即n=m)時,x=x1,所以h(x)=h(x1)≠t。所以(n+,h(x))≠(m+,t),故(n+,h(x))∈f - {(m+,t)}。
根據(Ⅰ)(Ⅱ),f-{(m+,t)}也是歸納關係,這與f的最小性矛盾,因此∃!x∈A,(m+,x)∈f。
至此, 根據數學歸納原理,f是N到A的函數。由於f滿足:
Ⅰ. (0,x0)∈f;
Ⅱ. 若(n,x)∈f,則(n+,h(x))∈f。
因此,Ⅰ. f(0)=x0
Ⅱ. 當f(n)=x時, f(n+)=h(x)=h(f(n))。
於是,遞歸定義的合理性得到了圓滿的證明。 [2] 
參考資料
  • 1.    王元,文蘭,陳木法.數學大辭典:科學出版社,2010
  • 2.    汪芳庭.數學基礎.北京:科學出版社,2001:82