漸化式による数列の定義は認められる？

まずは再帰性定理を学ぶ意義について軽く解説します．例えば， $$\begin{array}{r}{a}_1=1,a_{n+1}=\sqrt{2+a_n}(n=1,2,3,\dots )\end{array}$$ で定義される数列 $(a_n)$ なんてものを平然と扱いますが，一般項が初等的に表せなくてもそのような数列を数学では扱うことができます．つまり，実際に計算せずとも，すべての自然数 $n$ に対して $a_n$ がただ一つ確定している，としてよいのです．このような漸化式によって数列が確定するという事実は，再帰性定理によるものなのです．中間値の定理や平均値の定理のように，具体的に幾つかは不明だけど，それを満足する実数は存在する，そんな感覚に似ています．

$n$ 回合成の定式化

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

モノイドを考えよう

二項演算やモノイドという言葉にピンと来る人は飛ばしてください．

前ページで，$a\in \mathbf{R}$ に対する $a^n$ の厳密に定義しました．この定義に基づけば $$\begin{array}{r}{a}^m{a}^n=a^{m+n},(a^m{)}^n=a^{mn}\end{array}$$ などの指数にまつわる性質を帰納法で初めて証明することができます（勿論 $\mathbf{N}$ の加法や乗法を定義してからですが）．ところで冪乗について，なにも実数に限定する必要はなく，$\alpha \in \mathbf{C}$ に対する ${\alpha }^n$ も同様に定義され，指数法則なども証明できます．

自然数の基本性質

$(\mathbf{N},0,\sigma )$ を自然数の体系とします．前ページで以下を証明しました．

さて，集合 $X$ に対し，写像 $f:X\to X$ 全体の集合 $\mathrm{map}(X,X)$ は，写像の合成に関して恒等写像 $1_X$ を単位元とするモノイドですので，$f$ の $n$ 回合成写像が $f^n$ 考えられ，上の命題も満たします．