: 2022年5月10日

再帰性定理 II

: 基礎数学
: 自然数; 再帰性定理; 階乗; 和の記号
対象: 大学2.0年
前提知識: 集合の基礎; 写像; 直積集合

再帰性定理 I で扱えない関数

私は勝手に再帰性定理にバージョンを付けているのですが，初代再帰性定理は以下でした（加法が定義されたので $σ (n)$ は $n + 1$ とかけるようになりました）．

定理

再帰性定理 I

集合 $X$ とその元 $a \in X$ ，写像 $f : X \to X$ に対し，以下を満たす写像 $φ : N \to X$ が一意的に存在する：

$φ (0) = a$ ，
$\forall n \in N φ (n + 1) = f (φ (n))$ ．

例えば $2^{n}$ は，写像 $f (x) = 2 x$ に対し再帰性定理を用いて

$φ (0) = 1$
$\forall n \in N φ (n + 1) = f (φ (n)) = 2 p (n)$

を満たす写像 $p : N \to N$ を考え， $φ (n)$ を $2^{n}$ と書けばよかったのでした．再帰性定理は， $φ (0)$ を指定し， $φ (n)$ を用いて $φ (n + 1)$ を定義する方法を与える（写像 $f : X \to X$ ）ことによって，すべての $n \in N$ に対し $φ (n)$ を定める写像の定義法を提供します．ただし，この定理だけでは不便な点があります．例えば階乗のような， $n$ と $φ (n)$ を用いて $φ (n + 1)$ を定義するような写像は作れないのです．

例えば，再帰性定理 I だけでは

$F (0) = 1$
$\forall n \in N F (n + 1) = (n + 1) F (n)$

を満たすような写像 $F : N \to N$ を定めることができません．どうやっても $f : X \to X$ に該当する写像 $f$ を表現することができないからです． $F (n + 1)$ の定め方に，裸の $n$ を用いているのが原因です．後に $k = 0 \sum n a_{k}$ も定義しますが，これも再帰性定理 I では実現できません．

そこで，再帰性定理 II が登場します．

定理

再帰性定理 II

集合 $X$ とその元 $a \in X$ ，写像 $f : N \times X \to X$ に対し，以下を満たす写像 $φ : N \to X$ が一意的に存在する：

$φ (0) = a$ ，
$\forall n \in N φ (n + 1) = f (n, φ (n))$ ．

写像 $f$ を $N \times X \to X$ とすることで， $n$ と $φ (n)$ を用いて $φ (n + 1)$ を定義することができます．例えば $f : N \to X$ を $(n, x) \mapsto (n + 1) x$ で定義することにより，

$F (0) = 1$ ，
$\forall n \in N F (n + 1) = f (n, F (n)) = (n + 1) F (n)$

を満たす写像 $F : N \to N$ がただ一つ存在します． $F (n)$ を $n!$ ともかくことにするのです．

再帰性定理 II を用いると例えば， $a_{0} = 1, a_{n + 1} = 3 a_{n} + n (n = 0, 1, 2, \dots)$ などのような，裸の $n$ を含む漸化式によって定まる数列も初めて定義することができます．

証明のアイディア

再帰性定理 II の証明のアイディアを説明します．

$φ (0) = a$ ，
$\forall n \in N φ (n + 1) = f (n, φ (n))$ ．

という性質がそもそもどういう流れで $φ (n)$ を定義しているのかをゆっくりと見ていきます．

まず，最初の値は $a$ です： $a = : φ (0) ．$ 次に， $0$ と $φ (0)$ を $f$ に放り込んで $φ (1)$ を定めます： $(0, φ (0)) f φ (1) ．$ 次に， $1$ と $φ (1)$ を $f$ に放り込んで $φ (2)$ を定めます： $(1, φ (1)) f φ (2) ．$ 次に， $2$ と $φ (2)$ を $f$ に放り込んで $φ (3)$ を定めます： $(2, φ (2)) f φ (3) ．$ 以降，同様です．同じことを繰り返しているのは分かるのですが， $f$ の引数（インプット）が2つで，戻り値（アウトプット）が1つなのでなんかもやもやします．そこで，写像 $g : N \times X \to N \times X$ を $(n, x) g (n + 1, f (n, x))$ で定義します． $0, φ (0)$ を $g$ に放り込んで $(0, φ (0)) g (1, f (0, φ (0))) ．$ ここで， $f (0, φ (0)) = : φ (1)$ とします： $(0, φ (0)) g (1, φ (1)) ． (a)$ 次に $1, φ (1)$ を $g$ に放り込んで $(1, φ (1)) g (2, f (1, φ (1))) ．$ ここで， $f (1, φ (1)) = : φ (2)$ とします： $(1, φ (1)) g (2, φ (2)) ． (b)$ 同様に $2, φ (2)$ を $g$ に放り込んで $(2, φ (2)) g (3, φ (3)) (c)$ を得ます． $(a), (b), (c)$ を繋ぐと $(0, φ (0)) g (2, φ (2)) g (3, φ (3))$ を得ます．この工程を続ければ， $φ (n + 1) = f (n, φ (n))$ という関係を保ちながら $\dots g (n, φ (n)) g (n + 1, φ (n + 1)) g \dots$ という系列が続きます． $(0, φ (0))$ を $g$ で $n$ 回写すと $(n, φ (n))$ を得るので，右の成分を抽出すればよいという寸法です．

再帰性定理 II の証明

写像 $π_{0} : N \times X \to N$ を $(n, x) \mapsto n$ で， $π_{1} : N \times X \to X$ を $(n, x) \mapsto x$ で定義します．任意の $(n, x) \in N \times X$ に対し $(n, x) = (π_{0} (n), π_{1} (x)) (proj)$ が成り立ちます．このような写像を射影といいます． $x y$ 平面上にある点 $(a, b)$ から $x$ 軸に垂直な点線を引いて， $x$ 軸上に $a$ を書き込むあの作業のイメージでしょう，恐らく．

再帰性定理 II の証明

写像 $g : N \times X \to N \times X$ を $(n, x) \mapsto (n + 1, f (n, x))$ で定義し， $φ : N \to X$ を $n \mapsto π_{1} g^{n} (0, a)$ で定義すると， $φ$ はステートメントの (1) (2) を満たす．実際， $φ (0) = π_{1} g^{0} (0, a) = π_{1} (0, a) = a$ で (1) を満たす．(2) を示す前に， $\forall n \in N π_{0} g^{n} (0, a) = n (⋆)$ を帰納法で示す． $π_{0} g^{0} (0, a) = π_{0} 1_{N \times X} (0, a) = π_{0} (0, a) = 0$ だから $n = 0$ のとき成立． $π_{0} g^{n} (0, a) = n$ を仮定すると，ある $b \in X$ を用いて $g^{n} (0, a) = (n, b)$ と表せ， $g^{n + 1} (0, a) = g g^{n} (0, a) = g (n, b) = (n + 1, f (n, b))$ だから， $π_{0} g^{n + 1} (0, a) = n + 1$ ．以上で $(⋆)$ を示せた．さて， $φ (n + 1) = π_{1} g^{n + 1} (0, a) = π_{1} g g^{n} (0, a) = π_{1} g (π_{0} g^{n} (0, a), π_{1} g^{n} (0, a)) = π_{1} g (n, φ (n)) = π_{1} (n + 1, f (n, φ (n))) = f (n, φ (n)) (∵ 射影の性質) (∵ (⋆) と φ の定義)$ だから， $φ$ は (2) を満たす．一意性については (1) (2) を満たす $ψ$ に対し $\forall n \in N φ (n) = ψ (n)$ を帰納法で示せばよい．

和の記号を定義しよう

数列 $(a_{n} ∣ n \in N)$ に対し， $k = 0 \sum n a_{k} : = a_{0} + a_{1} + \dots + a_{n}$ という定義はストリクトではありません． $\dots$ を用いているからです．再帰性定理の出番です．

定義

モノイド $(M, +, 0)$ の元の列 $(a_{n} ∣ n \in N)$ に対し，再帰性定理 II より

$P (0) = a_{0}$ ，
$P (n + 1) = P (n) + a_{n + 1}$

を満たす写像 $N \to M$ が一意的に存在する． $P (n)$ を $k = 0 \sum n a_{k}$ ともかく．定義より以下が成り立つ：

$k = 0 \sum 0 a_{k} = a_{0}$ ，
$k = 0 \sum n + 1 a_{k} = k = 0 \sum n a_{k} + a_{n + 1}$ ．

命題

線形性

列 $(a_{n}), (b_{n})$ と $c \in M$ に対し以下が成り立つ．

$k = 0 \sum n (a_{k} + b_{k}) = k = 0 \sum n a_{k} + k = 0 \sum n b_{k}$ ，
$k = 0 \sum n c a_{k} = c k = 0 \sum n a_{k}$ ．

証明

(1) 帰納法． $k = 0 \sum 0 (a_{k} + b_{k}) = a_{0} + b_{0} = k = 0 \sum 0 a_{k} + k = 0 \sum 0 b_{k}$ だから $n = 0$ のとき成立． $n$ のとき成り立つと仮定すると， $k = 0 \sum n + 1 (a_{k} + b_{k}) = k = 0 \sum n (a_{k} + b_{k}) + (a_{n + 1} + b_{n + 1}) = k = 0 \sum n a_{k} + k = 0 \sum n b_{k} + a_{n + 1} + b_{n + 1} = k = 0 \sum n a_{k} + a_{n + 1} + k = 0 \sum n b_{k} + b_{n + 1} = k = 0 \sum n + 1 a_{k} + k = 0 \sum n + 1 b_{k} (∵ \sum の定義) (∵ 帰納法の仮定) (∵ 結合律) (∵ \sum の定義)$ だから $n + 1$ のときも成立．(2) は練習問題とする．

ちなみに，再帰性定理 II では，フィボナッチ数列などの3項間漸化式を扱うことはできません．まだまだ拡張の余地があります．