##### 递归定义原理 - 递归定义原理 - **递归定义原理**表示在[[自然数]]基础上[[递归]]定义[[映射]]是有效存在且唯一的, 证明思路是证明思路是归纳法构造和唯一性验证. 设 $X$ 是一个集合, $a\in X$ 是一个元素, 且 $g:\mathbb{N}\times X\to X$ 是一个映射. 那么存在唯一的映射 $f:\mathbb{N}\to X$, 满足以下条件 - 初始条件, $f(0)=a$ - 递归关系, 对于任意 $n\in\mathbb{N}$, $f(n+1)=g(n,f(n))$, 即 $f(n+1)$ 的值是由映射 $g$ 根据 $n$ 和 $f(n)$ 的值来确定的。 >[!example]- 递归定义原理 > - $f(0)=a$ > - $f(1)=g(0,f(0))=g(0,a)$ > - $f(2)=g(1,f(1))=g(1,g(0,a))$ > - $f(3)=g(2,f(2))=g(2,g(1,g(0,a))$ > - $\cdots$