計算機科學家邏輯/歸納法

歸納法

歸納法在本書中至少在兩個方面起著至關重要的作用。首先，它是數學中（當然也包括邏輯學中）主要的證明原理之一。特別是它可以用來研究無限集的性質。它經常被用作自然歸納法，即在自然數上。我們將把它作為一個更一般的原理在良基偏序集上引入，這被稱為結構歸納法。第二個方面是，它也可以用來定義無限結構，例如特定邏輯中良構公式的集合或二叉樹的集合。

我們從任意集合上的一個非常一般的結構開始，即偏序集。在 $A$ 上的關係 $R$ 是一個偏序當且僅當 $R$ 是自反的，傳遞的和反對稱的（即 $((x,y)\in R\land (y,x)\in R\Rightarrow x=y)$ )。偏序集（p.o. 集） $A$ 通常寫成 $(A,\leq )$ 。

定義 1

我們歸納原理所需的結構是一個偏序集，使得存在最小元素。給定一個p.o. 集 $(A,\leq )$ ，我們定義

$x<y$ 當且僅當 $x\leq y$ 且 $x\neq y$ 。
$(A,\leq )$ 被稱為良基的，如果不存在無限序列 $(x_{i})_{i\in N}$ 且 $x_{i+1}<x_{i},\forall i\geq 0$ 。
如果 $X\subseteq A$ ，則稱其為鏈，當且僅當 $\forall x,y\in X:x\leq y$ 或 $y\leq x$ 。
如果 $(A,\leq )$ 是一個全序，則 $A$ 是一個鏈。

引理 1

如果 $(A,\leq )$ 是良基的，則 $A$ 的每個非空子集都有一個極小元素。**證明**可以透過反證法完成，作為練習留給讀者。

我們終於有了引入完全歸納原理的工具。

定義 2（完全（結構）歸納）

給定一個良基偏序集 $(A,\leq )$ 和一個謂詞 $P$ ，即 $P:A\to \{true,false\}$ 。歸納原理由以下（二階）公式給出：
$\forall x\in A\;(\forall y\in A\;(y<x\Rightarrow P(y))\Rightarrow P(x))\Rightarrow \forall z\in A\;P(z)$

引理 2

歸納原理對每個良基集都成立。

**證明：**證明透過反證法給出：假設原理是錯誤的；即蘊涵是錯誤的，這意味著，我們必須假設前提為真

{\begin{matrix}\forall x\in A\;(\forall y\in A\;(y<x\Rightarrow P(y))\Rightarrow P(x))\equiv {true}(premise)\end{matrix}}

並將結論視為錯誤的

{\begin{matrix}\forall z\in A\;(P(z))\equiv =false=(conclusion)\end{matrix}}

因此，我們可以假設集合 $X=\{x\in A\mid P(x)=false\}$ 不為空。

由於 $X$ 是良基集的一個子集，它有一個最小元素，記為 $b$ 。根據假設（前提）我們可以得出結論

{\begin{matrix}(\forall y\in A\;(y<b\Rightarrow P(y))\Rightarrow P(b))\equiv {true}(inst)\end{matrix}}

現在我們可以區分兩種情況

$b$ 在 $A$ 中是最小的：因此不存在 $y\in A$ ，使得 $y<b$ 。因此，蘊含式(inst)中的前提 $\forall y\in A\;(y<b\Rightarrow P(y))$ 為真，這意味著結論 $P(b)$ 也為真。這與假設相矛盾，即
$b\in X$ !
b $b$ 在 A $A$ 中不是極小的：成立 $\forall y\in A\;(y<b)$ ，並且必須是 P(y) $P(y)$ 為真，因為否則的話，那就是 y $y\in X$ 並且 b $b$ 在 X $X$ 中不是極小的。因此，蘊含式 (inst) 中的前提 $\forall y\in A\;(y<b\Rightarrow P(y))$ $\forall y\in A\;(y<b\Rightarrow P(y))$ 為真，這意味著結論 P(b) $P(b)$ 為真。這與假設 b $b\in X$ 矛盾！

一個例子

在本小節中，我們將詳細進行一個歸納證明。為此，我們需要偏序集的擴充套件

定義 3（字典序）

偏序集 $(A,\leq )$ 誘導了一個在 $A\times A$ 上的排序 $\ll$ ： $\forall x,y,x\prime ,y\prime \in A:(x,y)\ll (x\prime ,y\prime )$ 當且僅當

$x=x\prime$ 且 $y=y\prime$ 或
$x<x\prime$ 或
如果 $x=x\prime$ 且 $y<y\prime$

引理 3

如果 $(A,\leq )$ 是一個良基集，那麼 $(A\times A,\ll )$ 也是良基的。

定理 1

由以下遞迴定義的阿克曼函式 $ACK$ 是 $N\times N$ 上的全函式。

  ACK(x,y) = 
    if x=0  then y+1 else
                     if y=0 then ACK(x-1,1) 
                            else ACK(x-1,ACK(x, y-1))

證明：對於歸納基礎，我們取良基集的最小元素 $(0,0)$ ，
$(N\times N,\ll )$ ，其中 $\ll$ 是由 $(N,\leq )$ 誘導的字典序。因此，假設 $x=0,y=0$ 。根據
$ACK$ 的定義，我們得出結論 $ACK(0,0)=1$ ，因此它是定義的。假設對於任意 $(m,n)$ ，

ACK(m',n')

對所有

(m'.n')\ll (m,n)

都是定義的，如果

(m,n)\neq (m',n')

我們區分以下情況

$m=0$ ：即 $ACK(0,n)=n+1$ ，因此已定義。
$m\neq 0$ 且 $n=0$ ：我們知道 $(m-1,1)\ll (m,0)$ 且 $(m-1,1)\neq (m,0)$ 。根據歸納假設，我們知道 $ACK(m-1,1)$ 已定義，因此 $ACK(m,0)=ACK(m-1,1)$ 也已定義。
$m\neq 0$ $m\neq 0$ 且 $n\neq 0$ $n\neq 0$ ：根據 $ACK$ $ACK$ 的定義，我們需要考慮兩種情況。
- $(m,n-1)\ll (m,n)$ 且 $(m,n-1)\neq (m,n)$ ：根據歸納假設，我們立即得出結論， $ACK(m,n-1)$ 已定義。
- $(m-1,y)\ll (m,z)$ 且 $(m-1,y)\neq (m,z)$ ：與 $x$ 和 $y$ 的值無關。如果我們假設
  
  如果 $y'ACK(m,n-1)$ 且 $z=n$ ，我們根據假設再次得出結論， $ACK(m-1,ACK(m,n-1))$ 是定義的，因此 $ACK(m,n)$ 也是定義的。

總而言之，我們證明了，對於所有 $x,y\geq 0$ ， $ACK(x,y)$ 都是定義的。

問題

問題 1 (歸納法)

證明以下引理：如果 $(A,\leq )$ 是良基的，那麼 $(A\times A,\ll )$ 也是良基的。

注意：字典序 $(A\times A,\ll )$ 定義如下

(m,n)\ll (m',n')\iff {\big (}m<m'\lor (m=m'\land n\leq n'){\big )}

問題 2 (歸納法)

$n$ 條直線最多能有多少個交點？找到一個遞迴和顯式公式並證明。

問題 3 (歸納法)

證明一個數 $x$ 是偶數當且僅當 $x^{2}$ 是偶數。

問題 4 (歸納法)

用間接證明法證明不存在最大的素數！

問題 5 (歸納法)

以下序關係

$(\{A,\,B,\,C,\,0,\,1,\,2\},\leq )$ 需要滿足什麼前提條件才能成為

偏序關係
全序關係
良基關係？

問題 6 (歸納法)

一個良基集的例子是有限集 $M$ 上的冪集 $P(M)$ ，它關於子集關係 $\subseteq$ 是可比較的。如果 $M=\{1,\,2,\,3\}$ ，那麼例如 ${1}\subseteq \{1,\,2,\,3\}$ ，但 $\{1,\,2\}$ 和 $\{2,\,3\}$ 是不可比較的。請定義一個關係 $B$ ，使得 $(P(M),\,B)$ 是全序且良基的。

問題 7（歸納法）

檢查以下偏序中的哪些是全序，哪些是良基的！

$(2^{\mathbb {N} },\subseteq )$ ，其中 $2^{\mathbb {N} }$ 是自然數的冪集。
$(\mathbb {N} ,|)$ ，其中 $|$ 表示關係“是…的因子”。
考慮 $(\mathbb {N} \times \mathbb {N} ,\ll )$ ，其中 $(m,n)\ll (m',n')$ 當且僅當 $m<m'$ 或( $m=m'$ 且 $n\leq n'$ )。
考慮 $(\mathbb {N} ^{*},\preceq )$ ，其中 $\preceq$ 是字典序。
例如，對於 $\mathbb {N} ^{*}$ ，有 $1\prec 1.1\prec 3\prec 3.3.8$