: 2022年5月1日

再帰性定理

: 基礎数学
: 自然数; ペアノの公理系; 再帰性定理; 冪乗; 漸化式
対象: 大学2.0年
前提知識: 集合の基礎; 写像; 集合族の共通部分

$n$ 回合成の定式化

再帰性定理とは，集合 $X$ とその元 $a \in X$ ，写像 $f : X \to X$ に対し， $a$ を $f$ で $n$ 回写したものを $φ (n)$ とする写像 $φ : N \to X$ の存在およびその一意性を保証するものです．つまり，写像の「 $n$ 回合成」を定式化したものです．例えば， $a^{n}$ を $a^{n} = n 個 a \times \dots \times a$ として定義するのは厳密ではありません．「 $n$ 個の $a$ を掛け合わせたもの」をうまく論理式で表すことができないからです．そこで，再帰性定理を用い， $a$ をかける写像を $n$ 回合成することによって $a^{n}$ を定義するわけです．

$n$ 回合成の概念が扱えるようになると， $n = σ^{n} (0)$ が証明できるので，自然数 $n$ は $0$ を $σ$ で $n$ 回写したもの，という表現が可能になります．また， $m + n$ は， $σ^{n} (m)$ ，すなわち $m$ を $σ$ で $n$ 回写したもの，と定義すれば，和の定義が一丁あがりです． $mn$ は，合成写像 $σ^{m}$ を $n$ 回合成したもので $0$ を写せばよいのです．このように $n$ 回の合成はとてつもなく汎用性があり，種々の定義に説得力を与えます．

証明の前に，写像の集合としての定義について軽く補足しておきます．心得ている人は飛ばしてください．

集合 $A, B$ があり，任意の $a \in A$ に対し， $b \in B$ がただ一つ定まるとき，その対応を $A$ から $B$ への写像といい， $f$ などの記号を用いて $f : A \to B$ とかく，こんな説明が一般的だと思います．大学一年生くらいであればこれで問題ないのですが，自然数とはなんぞやと疑問に思う人であれば，「対応」とはなんぞやと思いたくなると思います．そこで，現代数学（集合論）では，便宜的に写像を次のように定めます．

定義

写像の集合論的定義

$A, B$ を集合， $f \subset A \times B$ とする．任意の $a \in A$ に対し， $(a, b) \in f$ を満たす $b \in B$ がただ一つ存在するとき， $f$ を $A$ から $B$ への写像といい， $f : A \to B$ とかく．また， $a \in A$ に対して $(a, b) \in f$ を満たすただ一つの $b \in B$ を $f (a)$ とかく．

$f (a) = b$ という等式は $(a, b) \in f$ の書き換えです．何でもかんでも集合として考えようという現代数学の立場です．別に「写像とは実は集合だった！」というほどのものではなく，あくまで便宜的なものです．ですので，写像は「対応」とか「規則」とか「機能」などの考え方は持ったままの方がいいと思います．

再帰性定理のステートメントおよび証明

定理

再帰性定理 I

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

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

とにかく証明が長いです．一旦飛ばして，再帰性定理の使い方を先に学んでその重要性を実感してから証明に戻ってくるのもいいでしょう．ちなみに I とあるのは，バージョンを表しています．というのも，再帰性定理 I だけでは扱えない関数（階乗など）が存在するので，後でバージョンアップすることになるのです．

証明

$N \times X$ の部分集合 $A$ で

$(0, a) \in A$
$(n, x) \in A ⟹ (σ (n), f (x)) \in A$

を満たすもの全体を $A$ とする（ $A$ は集合の集合）． $N \times X \in A$ だから， $A \neq = \emptyset$ ．ゆえに共通部分 $φ = ⋂ A$ がとれる．これは，(1) (2) を満たす $A$ のうち，包含関係に関して最小のものである．ここで，任意の $n \in N$ に対し $(n, x) \in φ$ を満たす $x$ がただ一つ存在することを帰納法で示す．

$(0, b) \in φ, a \neq = b$ とすると， $φ ∖ {(0, b)} \in A$ だが（(1) (2) を満たす）， $φ$ の最小性に矛盾．つまり $a = b$ ．よって， $(0, x) \in φ$ を満たす $x$ は $a$ に限る．

次に $(n, x) \in φ$ を満たす $x$ がただ一つあると仮定，それを $x_{0}$ とする．ここで， $(σ (n), y) \in φ, f (x_{0}) \neq = y$ を仮定．このとき $φ^{'} : = φ ∖ {(σ (n), y)} \in A$ が成り立つ．実際， $(σ (n), y) \neq = (0, a)$ より $(0, a) \in φ^{'}$ ． $(n, x) \in φ^{'}$ ならば， $φ^{'} \subset φ$ だから，帰納法の仮定よりこの $x$ は $x_{0}$ に限るので， $(σ (n), f (x)) = (σ (n), f (x_{0})) \in φ^{'} (∵ f (x_{0}) \neq = y)$ である．よって， $φ^{'} \in A$ となるが，やはり $φ$ の最小性に矛盾． $f (x_{0}) = y$ である．つまり， $(σ (n), y) \in φ$ を満たす $y$ は $f (x_{0})$ に限る．

帰納法により， $φ$ が写像 $N \to X$ を定めることが分かった．

さて， $(n, x) \in φ$ は写像の記法で $φ (n) = x$ と表せるので，

$(0, a) \in φ$ ，
$(n, x) \in φ ⟹ (σ (n), f (x)) \in φ$ ，

を写像の記法に直すと

$φ (0) = a$ ，
$φ (n) = x ⟹ φ (σ (n)) = f (x)$ ，すなわち $φ (σ (n)) = f (φ (n))$ ，

を得るので，写像 $φ$ はステートメントの (1) (2) を満たす．

最後に， $φ$ の一意性を証明する． $ψ$ がステートメントの (1) (2) を満たすとし， $\forall n \in N φ (n) = ψ (n)$ を帰納法で示せばよい． $φ (0) = a = ψ (0)$ だから， $n = 0$ のとき成立． $φ (n) = ψ (n)$ を仮定すると $f (φ (n)) = f (ψ (n)) i.e., φ (σ (n)) = ψ (σ (n))$ だから， $σ (n)$ のときも成立．題意は示された．

お疲れ様でした．

再帰性定理の使い方

実数全体 $R$ を先取りし，関数 $f : R \to R$ を $x \mapsto x^{2} + 1$ で定めます．再帰性定理より

$φ (0) = 1$
$φ (σ (n)) = f (φ (n)) = φ (n)^{2} + 1$

を満たす写像 $φ : N \to R$ がただ一つ存在します． $φ (n)$ を $φ_{n}$ に書き直してみると，

$φ_{0} = 1$
$\forall n \in N φ_{σ (n)} = φ_{n}^{2} + 1$

と表せます．これは，高校生が $a_{0} = 1, a_{n + 1} = a_{n}^{2} + 1 (n = 0, 1, 2, \dots)$ として数列 $(a_{n})$ を定める行為と同じことです．一般項は分かりませんが，任意の自然数 $n$ に対し， $a_{n}$ が定まっていることは再帰性定理により保証されます．

次に， $a \in R$ に対し，写像 $f : R \to R$ を $x \mapsto a x$ で定めます．再帰性定理より

$p_{a} (0) = 1$
$p_{a} (σ (n)) = f (p_{a} (n)) = a p_{a} (n)$

を満たす写像 $p_{a} : R \to R$ がただ一つ定まります．

$p_{a} (0) p_{a} (1) p_{a} (2) p_{a} (3) = 1 = p_{a} (σ (0)) = f (p_{a} (0)) = a 1 = a = p_{a} (σ (1)) = f (p_{a} (1)) = aa = p_{a} (σ (2)) = f (p_{a} (2)) = a (aa) = aaa ⋮$ となり，どうやら $p_{a} (n)$ は $a^{n}$ に等しいようです．もとい，記号 $p_{a} (n)$ で， $a^{n}$ を定義します．これが冪乗（累乗）のストリクトな定義です．再帰性定理を用いるにあたり，写像 $f$ をいちいち定義するのが面倒なので，以下のような記述で片付けてしまうことがあります：帰納的に写像 $p_{a} : N \to R$ を

$p_{a} (0) = 1$
$\forall n \in N p_{a} (σ (n)) = a p_{a} (n)$

で定義し， $p_{a} (n)$ を $a^{n}$ とかく．

あるいはもっと端折って，帰納的に $a^{n}$ を

$a^{0} = 1$
$a^{n + 1} = a a^{n} (n \in N)$

で定義する，なんて書き方もあります．ここまでくると，再帰性定理をどう使っているか見えにくい部分がありますが，無駄な記号を用いずに済むのでミニマルです．

微分積分学のボルツァーノ＝ワイエルシュトラスの定理の証明で面を食らった学生が多いと思います．閉区間 $I$ を二分割し， $(a_{n})$ の項が無限に存在する方（両方とも無限にある場合は左の方）を $I_{1}$ とし，次に $I_{1}$ を二分割し， $(a_{n})$ の項が無限に存在する方（両方とも無限にある場合は左の方）を $I_{2}$ とし，以下同様にして列 $(I_{n})$ を考える，みたいなやつです．これも再帰性定理を用いています．ここで，両方とも無限にある場合は左の方を強調しました．たまに，両方とも無限にある場合はどちらでもいいみたいな書き方をしてる証明を見受けられますが，その場合，再帰性定理を正しく使えてません．詳しくは機会があったらお話しましょう．

さて，このように， $a^{n}$ を厳密に定義しました．これで指数法則などの諸性質を初めて証明できます．

n 回合成の定式化

定義

写像の集合論的定義

再帰性定理のステートメントおよび証明

定理

再帰性定理 I

証明

再帰性定理の使い方

$n$ 回合成の定式化