良基归纳法

极小元与最小元

设 $(A,\leqslant)$ 是偏序集， $Q\subseteq A$ ， $y\in Q$ ，

如果 $\forall x\in Q$ ， $x\leqslant y\Rightarrow x=y$ ，

则称 $y$ 为 $Q$ 的极小元。

如果 $\forall x\in Q$ ， $y\leqslant x$ ，

则称 $y$ 为 $Q$ 的最小元。

注意极小元与最小元的区别，

最小元是集合中最小的元素，它与集合中其他元素都可比，

而极小元不一定与集合中其他元素都可比，

只要没有比它小的元素，它就是极小元。

对于有穷集合，极小元一定存在，但最小元不一定存在，

最小元如果存在一定是唯一的，但极小元可能有多个。

良基关系

设 $\prec$ 是集合 $A$ 上的二元关系，

如果不存在由 $A$ 中的元素构成的无穷下降链，

$\cdots\prec a_i\prec\cdots\prec a_1\prec a_0$ ，

则称 $\prec$ 为良基关系（well-founded relation）。

若 $a\prec b$ ，则称 $a$ 是 $b$ 的前趋。

良基关系一定是非自反的，也就是说 $a\prec a$ 不成立，

否则就会有一条无穷下降链， $\cdots\prec a\prec\cdots\prec a\prec a$ 。

一般我们用 $\preceq$ 来表示关系 $\prec$ 的自反闭包，即，

$a\preceq b$ ，当且仅当， $a=b$ 或 $a\prec b$ 。

良基关系 $\prec$ 的传递闭包 $\prec^+$ 是一个良基关系。

它的自反传递闭包 $\prec^*$ 是一个偏序关系。

良基性质

有时还可以用极小元的概念来定义良基关系。

设 $\prec$ 是集合 $A$ 上的二元关系，称关系 $\prec$ 是良基的，

当且仅当， $A$ 的所有非空子集 $Q$ 都含有一个极小元 $m\in Q$ ，

即， $\forall b\prec m$ ， $b\notin Q$ 。

（1）充分性

如果 $\prec$ 是集合 $A$ 上的良基关系，

则我们可以通过以下方法找出集合 $A$ 的任一子集 $Q$ 中的极小元。

取 $a_0$ 为 $Q$ 中的任一元素，

假设 $Q$ 中已经构造了一条链 $a_n\prec\cdots\prec a_0$ ，

则在 $Q$ 中，或者存在 $b\prec a_n$ ，或者不存在这样的 $b$ 。

如果 $Q$ 中不存在这样的 $b$ ，则停止链的构造， $a_n$ 就是 $Q$ 的极小元，

否则，取 $a_{n+1}=b$ ，由于 $\prec$ 是良基的，

所以，链 $\cdots\prec a_i\prec\cdots\prec a_1\prec a_0$ 的长度是有限的，

最左边的元素，就是 $Q$ 的极小元。

（2）必要性

如果集合 $A$ 的所有非空子集都有极小元，

那么必定不存在一条无穷下降链， $\cdots\prec a_i\prec\cdots\prec a_1\prec a_0$ ，

否则 $Q=\{a_i|i=0,1,\cdots\}$ ，就是集合 $A$ 的一个不含极小元的非空子集，与前提矛盾。

良基归纳法

设 $\prec$ 是集合 $A$ 上的良基关系， $P$ 是某一性质，

则 $\forall a\in A.\ P(a)$ ，当且仅当，

$\forall x\in A.\ ([\forall y\prec x.\ P(y)]\Rightarrow P(x))$ 。

良基归纳法说的是，

要证明集合上的所有元素都满足某一性质，只要证明，

对于任意元素 $x$ ，如果它的所有前趋该性质都成立，必有对 $x$ 来说该性质也成立。

（1）充分性

如果 $\forall a\in A.\ P(a)$ ，

则 $\forall x\in A.\ (\forall y\prec x.\ P(y))$ ，且 $\forall x\in A.\ P(x)$ ，

因此， $\forall x\in A.\ ([\forall y\prec x.\ P(y)]\Rightarrow P(x))$ 。

（2）必要性

假设 $\forall x\in A.\ ([\forall y\prec x.\ P(y)]\Rightarrow P(x))$ ，

但是 $\exists z\in A$ ，使得 $\neg P(z)$ 。

那么，我们就可以构造出一个集合 $Q=\{z\in A|\neg P(z)\}$ ，满足 $Q\subseteq A$ ， $Q\neq\varnothing$ ，

因此，根据良基关系的性质， $Q$ 必有极小元 $m$ ， $\neg P(m)$ 为真。

但是根据前提， $\forall x\in A.\ ([\forall y\prec x.\ P(y)]\Rightarrow P(x))$ ，

我们有， $(\forall y\prec m.\ P(y))\Rightarrow P(m)$ ，

由于 $\neg P(m)$ 为真，所以一定 $\exists y\prec m.\ \neg P(y)$ ， $y\in A$ ，

所以， $y\in Q$ ，且 $y\prec m$ ，这与 $m$ 为 $Q$ 的极小元矛盾。

因此，不存在 $z\in A$ ，使得 $\neg P(z)$ ，

即， $\forall a\in A.\ P(a)$ 。

参考