Recursive definition

这篇博客是关于递归定义的笔记。

命题

给定集合$X$, 和函数$f:X \rightarrow X$, 以及$a \in X$。 存在唯一的函数$u: \mathbb{N} \rightarrow X$满足:

1. $u(0) = a$
2. $u(n+1) = f(u(n))$

证明

首先证明$u$的唯一性。

假定$u, v$都是满足上述命题的函数，则有 $u(0)=v(0)$, $\forall n \in \mathbb{N}(u(n)=v(n) \Rightarrow u(n+1)=f(u(n))=f(v(n))=v(n+1))$由数学归纳法, $\forall n \in \mathbb{N}(u(n)=v(n))$, 于是$u=v$。

现在证明存在性。

我们定义

$C := \{ A \subseteq \mathbb{N} \times X \mid (0, a) \in A \wedge \forall (n,x) \in \mathbb{N} \times X ((n,x) \in A \Rightarrow (n+1, f(x)) \in A) \}$

$u:=\bigcap_{A \in C} A$

$D:=\{n\in \mathbb{N} \mid \exists! x \in X ((n,x) \in u)\}$

注意, C非空, 因为$\mathbb{N} \times X \in C$。此外，如果我们能证明$D = \mathbb{N}$, 那么$u$就是满足上述命题的函数。

我们通过数学归纳法证明$D = \mathbb{N}$。

首先证明$0 \in D$。

先证明$(0,a) \in u$。 这是显而易见的, 因为$C$非空, 且$C$中的$A$都满足$(0,a) \in A$。于是有$(0,a) \in u$。

然后证明$a$是唯一满足$x \in X, (0,x) \in u$的元素。不妨假定存在$b \neq a, (0,b) \in u$。令$A_1$为$C$中的一个元素, 令$\tilde{A}:=A_1 \backslash\{(0,b)\}$。 我们有 $(n,x) \in \tilde{A} \Rightarrow (n, x) \in A_1 \Rightarrow (n+1, f(x)) \in A_1 \Rightarrow (n+1, f(x)) \in \tilde{A} \Rightarrow \tilde{A} \in C$ 这是因为$n+1 \neq 0, (n+1, f(x)) \neq (0,b)$。于是$(0,b) \notin \tilde{A} \Rightarrow (0,b) \notin u$， 这是一个矛盾, 因此$a$是唯一满足$x \in X,(0,x) \in u$的元素, 于是$0 \in D$。

现在我们需要证明如果$n \in D$, 那么$n+1 \in D$。

在此之前, 我们可以先证明$u \in C$。

$(0,a) \in u$,这是前面证明过的。如果$(n,x) \in u \Rightarrow \forall A \in C((n,x) \in A) \Rightarrow \forall A \in C((n+1,f(x)) \in A)\Rightarrow (n+1,f(x)) \in u$。于是$u \in C$。

下面证明$n \in D \Rightarrow n+1 \in D$。

首先证明存在这样的$x$。

$n \in D \Rightarrow \exists x \in X ((n,x) \in u) \Rightarrow (n+1,f(x)) \in u$。 令$f(x)=y$,于是存在$y \in X$使得$(n+1,y) \in u$。

现在证明这样的x是唯一的。

不妨假定$y\prime \neq y$,且满足$(n+1,y\prime) \in u \wedge (n+1,y) \in u$。

令$\tilde{u}:=u \backslash \{(n+1,y\prime)\}$。 $(m,z) \in \tilde{u} \Rightarrow (m,z) \in u \Rightarrow (m+1,f(z)) \in u$ 我们希望证明

假定不是这样, 那么存在$(m_1, z_1) \in u$使得$(m_1+1, f(z_1)) = (n+1, y\prime)$。 于是$m_1 = n$,

$\exists! x \in X ((n,x) \in u) \Rightarrow (m_1,z_1) = (n,x) \in u \Rightarrow (m_1+1, f(z_1)) = (n+1, f(x))$

注意,$y=f(x)$, 于是$f(z_1)=y=y\prime$, 这是一个矛盾。

于是我们有(1)成立。 于是,$(m,z) \in \tilde{u} \Rightarrow (m,z) \in u \Rightarrow (m+1,f(z)) \in u$,由于$(m+1,f(z)) \neq (n+1, y\prime)$, 所以$(m+1,f(z)) \in \tilde{u} \Rightarrow \tilde{u} \in C$。这是一个矛盾, 因为$u$是$C$中的最小元素, $\tilde{u}$比$u$还要小。

于是$y$的唯一性得证, 于是$n+1 \in D$。 根据数学归纳法, 我们得到$D = \mathbb{N}$。

references:

[1]original answer on Mathematics Stack Exchange