归纳原理与递推定义

归纳原理 / 递推定义（Induction & Recursion）

thm.induction · 定理 · 归纳 · 递归

又称数学归纳法·induction·递推定义·recursion

陈述

设 $\omega$ 是最小归纳集（即 $\mathbb{N}$ ）。

(i) 归纳原理：若 $S \subseteq \omega$ 满足

\emptyset \in S, \qquad x \in S \implies x \cup \{x\} \in S

则 $S = \omega$ 。

(ii) 递推定义：给定集合 $A$ 、元素 $a_0 \in A$ 与函数 $F : A \to A$ ，存在唯一的函数 $g : \omega \to A$ 使

g(\emptyset) = a_0, \qquad g(x \cup \{x\}) = F(g(x)) \quad \forall x \in \omega

⭐ 归纳原理管证明，递推定义管构造 —— 两者是一件事的两面，都来自「 $\omega$ 是最小归纳集」这一条。

$\mathbb{N}$ 上的加法、乘法、序，以及后面 $\mathbb{Z}$ 、 $\mathbb{Q}$ 的运算，全都是用递推定义出来、再用归纳原理验证性质的。

⚠ 归纳原理只对 $\omega$ 成立；换成一般的良序集要做超限归纳 / 超限递归。 ⚠ 递推定义要用「函数 $F$ 」而不是「一句话」，否则会掉进「用未定义的东西定义自己」的坑。