关于利用归纳法证明有限集命题的原理疑问
关于利用归纳法证明有限集命题的原理疑问
嘿,这个问题问得太到位了——我当初刚学这种归纳技巧的时候也纠结过:明明数学归纳法是针对自然数的,怎么突然就跨界到有限集上了?其实这背后根本不是什么新原理,也没用到复杂定理,本质就是把有限集的问题转化成了它的基数(也就是大小)的自然数问题,还是在用你熟悉的那个数学归纳法。
先回顾下你提到的标准数学归纳法原理:
设 $G \subseteq \mathbb{N}$,如果满足:
- $1 \in G$;
- 若 $n \in G$,则 $n+1 \in G$;
那么 $G = \mathbb{N}$。
当我们要证明性质$P$对所有属于$\mathcal{X}$的有限集成立时,我们其实偷偷定义了一个自然数集合$G$:
$$G = { n \in \mathbb{N} \mid \text{所有属于}\mathcal{X}\text{且基数为}n\text{的有限集都满足}P }$$
接下来的步骤就完全贴合标准归纳法了:
- 第一步证明“所有基数为1的$\mathcal{X}$中的集满足$P$”,其实就是在证明$1 \in G$,对应归纳的基础步骤;
- 第二步证明“若所有基数为$n$的$\mathcal{X}$中的集满足$P$,则所有基数为$n+1$的也满足”,这就是在证明“如果$n \in G$,那么$n+1 \in G$”,对应归纳的递推步骤;
根据标准归纳法,$G$就是全体自然数$\mathbb{N}$——而任何有限集的基数都是某个自然数,所以自然所有$\mathcal{X}$里的有限集都满足$P$了。
你之前想到的“用归纳法代替有限步推理”其实是这个逻辑的直观感受,但它背后是有严格数学支撑的,不是什么非正式的偷懒手法。我们只是没把那个$G$明写出来而已,毕竟每次都定义一遍确实有点繁琐,但逻辑上它一直都在。
备注:内容来源于stack exchange,提问作者Scrappa




