计算机科学家逻辑/归纳法

归纳法

归纳法在本书中至少在两个方面起着至关重要的作用。首先，它是数学中（当然也包括逻辑学中）主要的证明原理之一。特别是它可以用来研究无限集的性质。它经常被用作自然归纳法，即在自然数上。我们将把它作为一个更一般的原理在良基偏序集上引入，这被称为结构归纳法。第二个方面是，它也可以用来定义无限结构，例如特定逻辑中良构公式的集合或二叉树的集合。

我们从任意集合上的一个非常一般的结构开始，即偏序集。在 $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$