写像の再帰的定義がなぜ許されるのか｜漸化式を満たす写像の存在と一意性
再帰的定義を正当化する。
再帰的定義って本当にやっていいの？
集合 $A, B$ の直積 $A \times B$ の部分集合 $f$ が、各 $a \in A$ に対して条件
を満たすとき、$f$ を $A$ から $B$ への写像と呼ぶ。
再帰的に定義することってよくあるじゃん
$$\left\{ \begin{aligned} f(0) &= 1 \\ f(n + 1) &= f(n) + n \qquad (n \in \NN) \end{aligned} \right.$$
集合 $X$ と $x_0 \in X$ と写像 $R: \NN \times X \rightarrow X$ に対し、写像 $f: \NN \rightarrow X$ で $$\left\{ \begin{aligned} f(0) &= x_0 \\ f(s(n)) &= R(n, f(n)) \qquad (n \in \NN) \end{aligned} \right.$$ を満たすものが唯一つ存在する。
$\NN \times X$ の部分集合 $\varphi$ で、2条件 $$ \left\{ \begin{aligned} (0,x_0) &\in \varphi \\ \forall (n, x) \in \varphi, \ (s(n), R(n, x)) &\in \varphi \end{aligned} \right. $$ を満たすもの全体を $\mathcal{F}$ とする。$\mathcal{F} \neq \varnothing$ であることは $\NN \times X \in \mathcal{F}$ からわかる。$\NN \times X$ の部分集合 $f$ を $$f = \bigcap_{\varphi \in \mathcal{F}} \varphi$$ によって定める。$f \in \mathcal{F}$ となることに注意。
$f$ が写像であることを示すために、各 $k \in \NN$ に対して条件
「$(k, x) \in f$ なる $x \in X$ が唯一つ存在する」
が成り立つことを $k$ についての数学的帰納法で示す。
どの $\varphi \in \mathcal{F}$ に対しても $(0, x_0) \in \varphi$ なので $$(0, x_0) \in f$$ であり、存在性を得る。
一意性を得るために、$(0, x_1) \in f$ なる $x_1 \in X \setminus \cbr{x_0}$ が存在したと仮定して矛盾を導く。 $g = f \setminus \cbr{(0,x_1)}$ とすると $$(0, x_0) \in g$$ である。また $(n, x) \in g$ を任意に取ったとき、$(n, x) \in f$ なので $(s(n), R(n, x)) \in f$ だが、$(s(n), R(n, x)) \neq (0,x_1)$ なので $$(s(n), R(n, x)) \in g$$ である。したがって $g \in \mathcal{F}$ となるが、これは $g \subsetneq f$ と $f$ の定義より矛盾である。
帰納法の仮定より、$(k, x_k) \in f$ なる $x_k \in X$ がただ一つ存在する。$f \in \mathcal{F}$ なので $$(s(k), R(k, x_k)) \in f$$ であり、存在性を得る。
一意性を得るために、$(s(k), y) \in f$ なる $y \in X \setminus \cbr{R(k,x_k)}$ が存在したと仮定して矛盾を導く。 $g = f \setminus \cbr{(s(k),y)}$ とすると $$(0, x_0) \in g$$ である。また $(n, x) \in g$ を任意に取ったとき、$(n, x) \in f$ なので $(s(n), R(n, x)) \in f$ だが、
-
$n \neq k$ の場合、$s$ の単射性より $$(s(n), R(n, x)) \neq (s(k),y)$$である。
-
$n = k$ の場合、$(k, x_k), (k, x) \in f$ であるが、帰納法の仮定の一意性より $x = x_k$ となる。したがって $$(s(n), R(n, x)) = (s(k), R(k, x_k)) \neq (s(k),y)$$である。
いずれにしても $(s(n), R(n, x)) \in g$ を得る。したがって $g \in \mathcal{F}$ であるが、これは $g \subsetneq f$ と $f$ の定義より矛盾である。
$f$ が写像であることと $f \in \mathcal{F}$ から、この $f$ が求めるものであり、存在性を得た。
写像 $f, g: \NN \rightarrow X$ が $$\left\{ \begin{aligned} f(0) &= x_0 \\ g(0) &= x_0 \\ f(s(n)) &= R(n, f(n)) \qquad (n \in \NN) \\ g(s(n)) &= R(n, g(n)) \qquad (n \in \NN) \end{aligned} \right.$$ を満たすときに各 $k \in \NN$ に対して $f(k) = g(k)$ となることを $k$ についての数学的帰納法で示す。
$f(0) = x_0 = g(0)$ より従う。
$f(k) = g(k)$ ならば $$R(k, f(k)) = R(k, g(k))$$ なので $f(s(k)) = g(s(k))$ である。
こんな推論が隠れてたんだね
前にペアノの公理から加法を作るときに
再帰的定義使わなかった？
加法の存在性証明のときに使った再帰的定義は
$f: \NN \rightarrow \NN$ の形だったから
ちょっと証明が楽だった
加法の構成やっても良かったけど
こんな長い証明
いきなり読むのはしんどいでしょ
ペアノの公理の一意性
今日の目標 ペアノシステムの一意性を示す。 ペアノシステムの一意性 前にペアノシステムを 「集合」で ...
https://sorai-note.com/math/200419/
フィボナッチ数列って本当に存在するの？
$$\left\{ \begin{aligned} f(0) &= 1 \\ f(n + 1) &= f(n) + n \qquad (n \in \NN) \end{aligned} \right.$$
今回の定理使って存在がわかるけどさー
$$\left\{ \begin{aligned} f(0) &= 1 \\ f(1) &= 1 \\ f(n + 2) &= f(n) + f(n + 1) \qquad (n \in \NN) \end{aligned} \right.$$
どうすんの？
集合 $X$ と $x_0 \in X^2$ と写像 $R: \NN \times X^2 \rightarrow X^2$ に対し、写像 $f: \NN \rightarrow X^2$ で $$\left\{ \begin{aligned} f(0) &= x_0 \\ f(s(n)) &= R(n, f(n)) \qquad (n \in \NN) \end{aligned} \right.$$ を満たすものが唯一つ存在する。
$f = (f_1, f_2)$
$R = (R_1, R_2)$
で書きなおして……
集合 $X$ と $(x_1, x_2) \in X^2$ と写像 $R_1, R_2: \NN \times X^2 \rightarrow X$ に対し、写像 $f_1, f_2: \NN \rightarrow X$ で $$\left\{ \begin{aligned} f_1(0) &= x_1 \\ f_2(0) &= x_2 \\ f_1(s(n)) &= R_1(n, f_1(n), f_2(n)) \qquad (n \in \NN) \\ f_2(s(n)) &= R_2(n, f_1(n), f_2(n)) \qquad (n \in \NN) \end{aligned} \right.$$ を満たすものが唯一つ存在する。
集合 $X$ と $(x_1, x_2) \in X^2$ と写像 $R: \NN \times X^2 \rightarrow X$ に対し、写像 $f_1, f_2: \NN \rightarrow X$ で $$\left\{ \begin{aligned} f_1(0) &= x_1 \\ f_2(0) &= x_2 \\ f_1(s(n)) &= f_2(n) \qquad (n \in \NN) \\ f_2(s(n)) &= R(n, f_1(n), f_2(n)) \qquad (n \in \NN) \end{aligned} \right.$$ を満たすものが唯一つ存在する。
同値変形
集合 $X$ と $(x_1, x_2) \in X^2$ と写像 $R: \NN \times X^2 \rightarrow X$ に対し、写像 $f_1, f_2: \NN \rightarrow X$ で $$\left\{ \begin{aligned} f_1(0) &= x_1 \\ f_1(s(0)) &= x_2 \\ f_2(n) &= f_1(s(n)) \qquad (n \in \NN) \\ f_1(s(s(n))) &= R(n, f_1(n), f_1(s(n))) \qquad (n \in \NN) \end{aligned} \right.$$ を満たすものが唯一つ存在する。
唯一つだということが言える
$f_1 = g$ と $f_1 = h$ の二つがあったら
1～4式は
$f_1 = g_1, f_2 = g_1 \circ s$ としても成り立つし
$f_1 = h_1, f_2 = h_1 \circ s$ としても成り立つから
一意性より $g_1 = h_1$
集合 $X$ と $x_1, x_2 \in X$ と写像 $R: \NN \times X^2 \rightarrow X$ に対し、写像 $f: \NN \rightarrow X$ で $$\left\{ \begin{aligned} f(0) &= x_1 \\ f(s(0)) &= x_2 \\ f(s(s(n))) &= R(n, f(n), f(s(n))) \qquad (n \in \NN) \end{aligned} \right.$$ を満たすものが唯一つ存在する。