歸納定義

歸納定義是定義集合的一種方法，對於用歸納定義給出的集合，要證明其中所有的元都有某個性質，通常用歸納證明。集合的歸納定義通常包括若干規則，用來生成其中的元，然後再說明，只有由這些規則生成的對象才是這個集合的元。歸納定義的一種等價的陳述是將所要定義的集合刻畫成封閉於這些規則的最小的集。

基本介紹

• 中文名：歸納定義
• 外文名：definition by induction
• 它是：定義集合的一種方法
• 基礎條款：規定某些元素為待定義集合成員

簡介

歸納定義是基於數學歸納法的一種定義方法，用於定義全體自然數集 上的函式。

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

步驟

具體的依據歸納定義的形式分為兩步。

第一步: 定義 f(0) 的值;

第二步: 依據那種事先給定的一致方法，從依照假定已經有定義的 f(n) 的值出發，進一步來定義 f(n+1) 的值。

當這兩步完成以後，就可以由數學歸納法確認f 在 上已經定義好了。這裡所要強調的是不會在定義過程中被改變的事先給定或者選定的那種一致方法的作用。如果沒有那樣的方法來保證，試圖定義的對象可能不會作為一個函式而存在。

歸納定義的可靠性可以形式化為如下定理：設 X 為一非空集合， 為一函式。則存在唯一的函式 滿足 及對任意這裡的函式 g 就是前面所說的那種事先給定或者選定的一致的方法。

在套用中，歸納定義的具體形式可以多種多樣。像數學歸納法一樣，歸納定義也有許多變種。例如，歸納定義更多地是用於定義序列而非函式(當然，嚴格地講，序列也是函式)。另外，複雜的歸納定義往往和證明及其他構造交織在一起，而非簡單地採用如上的標準形式。有時，出於某種原因，或是為了方便，歸納定義的第一步不是定義 f(0) 的值，而是對某個非 0 的 定義 f(a) 的值，或是同時定義多個的值。又有時，歸納定義的第二步假定所有，的值都已有定義，而進一步由此定義的值。等等。

在集合論中，歸納定義的定義域通常形式上被認為是所有有窮序數的集合 而非寫作 之所以會如此是因為數學歸納法的本質是利用了是一個秩序集的事實，並由此可以推廣數學歸納法到一般的秩序集甚至有秩關係上。

結構

基礎條款：規定某些元素為待定義集合成員，集合其它元素可以從基本元素出發逐步確定 。

歸納條款：規定由已確定的集合元素去進一步確定其它元素的規則 。

終極條款：規定待定義集合只含有基礎條款和歸納條款所確定的成員。

其中，基礎條款和歸納條款稱作“完備性條款”，必須保證毫無遺漏產生集合中所有成員。終極條款又稱“純粹性條款”，保證集合中僅包含滿足完備性條款的那些對象。

歸納定理

簡述

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

內容

給定a₀∈A及函式h: A→A，則存在唯一一個函式f: N→A，滿足：

(1) f(0)=a₀；

(2) f(n+)=h(f(n))。

證明

(唯一性)假設存在滿足條件(1)(2)的函式f₁: N→A和f₂: N→A。為了證明惟一性，只需證f₁≡f₂，亦即∀n∈N，f₁(n)=f₂(n)。對n歸納：n=0時，根據(1)，有f₁(0)=a₀=f₂(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,x₀)∈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,x₀)∈每一個歸納關係，故(0,x₀)∈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,x₀)∈f。假設x₀不是唯一的，即有x₁≠x₀，x₁∈a且(0,x₁)∈f，考慮集合f -{(0,x₁)}，它滿足

(Ⅰ)(0,x₀)∈f - {(0,x₁)}(因為x₁≠x₀)

(Ⅱ)設(n,x)∈f-{(0,x₁)}，由於f-{(0,x₁)}⊂f，所以(n,x)∈f，由於f是歸納關係，所以(n+,h(x))∈f。由於n+≠0，(n+,h(x))∈f - {(0,x₁)}。

根據(Ⅰ)(Ⅱ)，f-{(0,x₁)}也是歸納關係，這與f的最小性矛盾，因此∃!x∈A，(0,x)∈f。

2. 假設對m, ∃!x₁∈A，s.t. (m,x₁)∈f。下證對m+，∃!x∈A，(m+,x)∈f。因為根據歸納假設(m,x₁)∈f，又f滿足歸納關係的條件(Ⅱ)，因此(m+,h(x₁))∈f。下面考慮x的惟一性，假設∃t≠h(x₁)，s.t. (m+,t)∈f。考慮集合f-{(m+,t)}，它滿足

(Ⅰ)(0,x₀)∈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=x_1，所以h(x)=h(x₁)≠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,x₀)∈f；

Ⅱ. 若(n,x)∈f，則(n+,h(x))∈f。

因此，Ⅰ. f(0)=x₀；

Ⅱ. 當f(n)=x時, f(n+)=h(x)=h(f(n))。

於是，遞歸定義的合理性得到了圓滿的證明。