數學證明與數學/數字/自然數原理

之前，我們根據集合論公理，將自然數構造為集合。

現在，我們從算術的角度來研究自然數，我們將看到如何從後繼運算推匯出我們熟悉的加法和乘法的概念。由於我們正在從集合論轉向算術，我們將用 $\mathbb {N}$ 來代替 $\omega$ 表示自然數。由於我們即將引入算術，但尚未進行，在本節中我們將暫時使用S(n) 代替n + 1 來表示n 的後繼。

定義

定義加法由 0 和後繼函式透過以下兩條規則定義：

定義 1	a + 0 = a
定義 2	a + S(b) = S(a + b)

我們將首先看到這個定義如何證明我們之前對a + 1 作為a 後繼的使用是合理的。

對於每個自然數a，我們有：

	S(a)
=	S(a + 0)	[根據定義 1]
=	a + S(0)	[根據定義 2]
=	a + 1	[根據 1 的定義]

歸納原理

我們現在將展示如何從定義中推匯出你在學校學習過的所有加法的性質。

這些證明依賴於歸納原理。回憶一下定理：

歸納原理 假設 $P(x)$ 是自然數的一個性質，對於該性質， $P(0)$ 成立，並且對於所有自然數 $n$ ，如果 $P(n)$ 成立，那麼 $P(n+1)$ 也成立。那麼 $P(n)$ 對於每個自然數 $n$ 成立。

當使用歸納原理進行證明時，我們稱 $P(0)$ 的證明為基本情況，稱 $P(a+1)$ 從 $P(a)$ 的證明為歸納步驟。在歸納步驟的證明中，我們將使用我們可以假設 $P(a)$ 的事實，並將其稱為歸納假設。讓我們看看它在實踐中的應用。

與 0 的加法

定義 [定義 1] 直接說明 0 是一個右單位元，也就是說，對於任何數a，a + 0 = a。

我們證明 0 是一個左單位元，也就是說，0 + a = a，方法是對自然數a 進行歸納。

定理對於每個自然數a，0 + a = a.

對於基本情況a = 0，根據定義 [定義 1]，0 + 0 = 0。

因此，我們繼續進行歸納步驟。我們可以假設歸納假設，即 0 + a = a。那麼

	0 + S(a)
=	S(0 + a)	[根據定義 2]
=	S(a)	[根據歸納假設]

因此，我們已經證明了0 + S(a) = a，前提是假設 0 + a = a。因此，我們可以根據歸納原理得出結論，0 + a = a，對於每個自然數a 都成立。

結合律

讓我們嘗試一個更復雜的例子，結合律。

定理對於任何三個自然數a, b 和c，(a + b) + c = a + (b + c).

首先要注意的是，我們這裡有三個數字，*a*、*b* 和 *c*。所以我們將固定 *a* 和 *b* 為任意數字，並將歸納原理應用於 *c*。

更準確地說，性質 $P(c)$ 是 $(a+b)+c=a+(b+c)$ .

對於基本情況 *c* = 0，

(*a*+ *b*) + 0 = *a* + *b* = *a* + (*b* + 0)

每個等式都根據定義 [Def. 1] 得出；第一個是 *a* + *b*，第二個是 *b*。

現在，對於歸納步驟。我們假設歸納假設，也就是說，我們假設對於某個自然數 *c*，

(*a* + *b*) + *c* = *a* + (*b* + *c*)

然後它隨之而來，

	(a + b) + S(c)
=	S((a + b) + c)	[根據定義 2]
=	S(a + (b + c))	[根據歸納假設]
=	a + S(b + c)	[根據定義 2]
=	a + (b + S(c))	[根據定義 2]

換句話說， $P$ 對 *S*(*c*) 成立。因此，關於 *c* 的歸納是完整的。

交換律

另一個你從學校就會知道的重要的性質是交換律：當加兩個數字時，順序無關緊要。

定理對於任意兩個自然數 *a* 和 *b*，*a* + *b* = *b* + *a*。

由於這更加複雜，我們首先介紹一個引理。

一個有用的引理

引理對於任意兩個自然數 *a* 和 *b*，*S(a) + b = S(a + b)*。

讓我們對 *b* 進行歸納，從基本情況 *b = 0* 開始

	S(a) + 0
=	S(a)	[根據定義 1]
=	S(a + 0)	[根據定義 1]

現在是歸納步驟

	S(a) + S(b)
=	S(S(a) + b)	[根據定義 2]
=	S(S(a + b)	[根據歸納假設]
=	S(a + S(b))	[根據定義 2]

就這樣 - 關於 *b* 的歸納是完整的。

交換律的證明

從這個簡短的離題，我們獲得了可以用來證明交換律的性質。

我們將再次透過對 *b* 進行歸納來進行，從基本情況開始

	a + 0
=	a	[根據定義 1]
=	0 + a	[根據右單位元定理]

請注意，基本情況只是我們上面顯示的單位元性質的直接結果。

現在，假設對於所有自然數 *a*，我們有 *a* + *b* = *b* + *a*。我們必須證明對於所有自然數 *a*，我們有 *a* + *S*(*b*) = *S*(*b*) + *a*。我們有

	a + S(b)
=	S(a + b)	[根據定義 2]
=	S(b + a)	[根據歸納假設]
=	S(b) + a	[根據引理]

這完成了關於 *b* 的歸納。

乘法

到目前為止，我們介紹了加法，並推匯出關於自然數上加法的基本性質。但算術不僅僅是加法，當然。因此，就像我們從後繼關係推匯出加法一樣，我們將從加法推匯出乘法

定義乘法由 0、加法和後繼函式根據以下兩個規則推匯出

Def. 3	$a\cdot 0=0$
Def. 4	$a\cdot S(b)=a\cdot b+a$

我們可以很快地在腦海中檢查這兩個方程是否確實在我們對自然數的直覺中成立。

由於您現在熟悉瞭如何使用歸納法解決問題，我們把交換律和結合律的證明留給您。

分配律

但是，在我們讓您去做之前，讓我們再瞭解一個由兩個不同的運算子的存在而產生的性質。它被稱為分配律。

定理對於任意三個自然數 *a*、*b* 和 *c*， $a\cdot (b+c)=(a\cdot b)+(a\cdot c)$ .

我們透過對 *c* 進行歸納來證明分配律

從基本情況開始

	$a\cdot (b+0)$
=	$a\cdot b$	[根據定義 1]
=	$a\cdot b+0$	[根據定義 1]
=	$a\cdot b+a\cdot 0$	[根據定義 3]

...並透過歸納法繼續

	$a\cdot (b+S(c))$
=	$a\cdot S(b+c)$	[根據定義 2]
=	$a\cdot (b+c)+a$	[根據定義 4]
=	$(a\cdot b+a\cdot c)+a$	[根據歸納假設]
=	$a\cdot b+(a\cdot c+a)$	[根據加法的結合律]
=	$a\cdot b+a\cdot S(c)$	[根據定義 4]

這就是要證明的結論。

練習

現在您已經看到了各種歸納論證技術的應用，您應該嘗試自己找出乘法的剩餘屬性。

嘗試逐行寫出這些屬性，並在等式的右側註明所用恆等式的來源，就像本頁中的佈局一樣。

為了幫助您，右側圖表顯示了屬性之間相互依賴關係的簡要概述。它還包括我們已經見過的屬性的推導，以及乘法和加法的定義。

祝你好運！

參考文獻

本頁中歸納證明的經典參考書是 Edmund Landau 的 *Foundations of Analysis*，Chelsea Pub Co. ISBN 0-8218-2693-X。您可以在其中找到大量進一步的屬性和練習，以及關於指數運算的介紹。

	(a + b) + S(c)
=	S((a + b) + c)	[根據定義 2]
=	S(a + (b + c))	[根據歸納假設]
=	a + S(b + c)	[根據定義 2]
=	a + (b + S(c))	[根據定義 2]