ボルツァーノ＝ワイエルシュトラスの定理の証明で学ぶ現代数学における無限の取り扱い

有界な数列は収束する部分列をもつというボルツァーノ＝ワイエルシュトラスの定理（以下BW定理）の証明を最初知ったときは本当にこんなことが可能なのか，という疑問が拭えず酷く消化不良をきたしたのを覚えています．主に無限の扱いについて引っかかりました．この定理の証明を「ちゃんと」理解したのは，微分積分を学んでから随分と後の方（学部2年生後期くらい？）でした．そして改めて書籍や数学系のブログなどを眺めていると，「この著者はちゃんと定理の証明を理解しているのかな」と思えるような証明がはびこっていることに気づきました．BW定理を $100\%$ 理解すれば，極限の概念を理解するだけでなく，現代数学でよく行われる証明の手法，主に無限の扱い方を身につけることができるので，題材としてはとても教育的だと私は思います．というわけで，くど過ぎるBW定理の証明の解説を行おうと思います．

この文書では，自然数に $0$ を含めることにし，自然数と実数全体の集合をそれぞれ $\mathbf{N},\mathbf{R}$ で表します．また，空でない閉区間 $I=[a,b]$ に対して， $a$ を $I$ の左端， $b$ を $I$ の右端と呼びます．また，高校数学では数列を $\{a_{n}\}$ などと表しますが， $\{\ \}$ は集合を表す記号と被るので， $(a_{n})_{n\in\mathbf{N}}$ もしくは単に $(a_{n})$ と表します．また， $a_{n}$ の $n$ のことを添字と呼びます．

1. よくある証明と疑問点

まずはよく見かけるBW定理の説明不足な証明を書いてみます．ちなみにBW定理には区間縮小法という定理を用いることが多いのですが，簡単に証明できることなので，あえて使いません．

(BW定理のそれらしい証明) 数列 $(a_{n})$ は有界なので，ある実数 $b_{0},c_{0}\in\mathbf{R}$ が存在し，任意の $n\in\mathbf{N}$ に対して $b_{0}\leqq a_{n}\leqq c_{0}$ を満たす． $I_{0}=[b_{0},c_{0}]$ とおいて， $I_{0}$ を真っ二つに分けた閉区間 $\begin{matrix} [b_{0}, (b_{0} + c_{0}) / 2], [(b_{0} + c_{0}) / 2, c_{0}] \end{matrix}$ のうち，数列 $(a_{n})$ の項が無限に存在する方を $I_{1}$ とし， $I_{1}$ の左端，右端をそれぞれ $b_{1},c_{1}$ とする．この定義より $\begin{matrix} b_{0} ≦ b_{1}, c_{1} ≦ c_{0}, c_{1} - b_{1} = \frac{c_{0} - b_{0}}{2} \end{matrix}$ が成り立つ．次に $I_{1}$ を真っ二つに分けた閉区間 $\begin{matrix} [b_{1}, (b_{1} + c_{1}) / 2], [(b_{1} + c_{1}) / 2, c_{1}] \end{matrix}$ のうち， $(a_{n})$ の項が無限に存在する方を $I_{2}$ とし，左端，右端をそれぞれ $b_{2},c_{2}$ とする．すると， $\begin{matrix} b_{1} ≦ b_{2}, c_{2} ≦ c_{1}, c_{2} - b_{2} = \frac{c_{1} - b_{1}}{2} \end{matrix}$ が成り立つ．以降，これを繰り返して，閉区間の列 $\begin{matrix} I_{0} \supset I_{1} \supset I_{2} \supset \dots \supset I_{n} \supset \dots \end{matrix}$ を構成する． $I_{n}=[b_{n},c_{n}]$ の定義より $\begin{matrix} b_{0} ≦ b_{1} ≦ b_{2} ≦ \dots ≦ b_{n} ≦ \dots \\ c_{0} ≧ c_{1} ≧ c_{2} ≧ \dots ≧ c_{n} ≧ \dots \end{matrix}$ および漸化式 $\begin{matrix} \forall n \in 𝐍 c_{n + 1} - b_{n + 1} = \frac{c_{n} - b_{n}}{2} \end{matrix}$ が成り立つ． $(b_{n})$ は有界な増加列， $(c_{n})$ は有界な減少列だから収束し， $\begin{matrix} c_{n} - b_{n} = \frac{c_{0} - b_{0}}{2^{n}} \to 0 (n \to \infty) \end{matrix}$ が成り立つので，同一の極限値 $\alpha$ が存在する．

次に $I_{0}$ に含まれる $(a_{n})$ の項を任意に選びそれを $a_{i(0)}$ とする．そして， $I_{1}$ には $(a_{n})$ の項が無限にあるから $a_{i(1)}\in I_{1}$ かつ $i(0)<i(1)$ となるような添字 $i(1)$ がとれる．次に， $I_{2}$ には $(a_{n})$ の項が無限にあるから $a_{i(2)}\in I_{2}$ かつ $i(1)<i(2)$ となるような添字 $i(2)$ がとれる．これを繰り返すと $\begin{matrix} i (0) < i (1) < i (2) < \dots < i (n) < \dots \end{matrix}$ が構成でき， $(a_{n})$ の部分列 $\begin{matrix} a_{i (0)}, a_{i (1)}, a_{i (2)}, \dots \end{matrix}$ がとれる．この部分列の構成法より任意の $n\in\mathbf{N}$ に対して $a_{i(n)}\in I_{n}$ が成り立つので $\begin{matrix} b_{n} ≦ a_{i (n)} ≦ c_{n} \end{matrix}$ が常に成り立つ． $(b_{n}),(c_{n})$ は $\alpha$ に収束するから，はさみうちの原理より $a_{i(n)}$ も $\alpha$ に収束する．以上で題意は示された． $\blacksquare$

以上の証明で，疑問点を挙げてみます．

Q1.
$I_{1}$ の定義で $(a_{n})$ の項が無限に存在する方をとっているが，どうやって無限個あるのかを判定するのか？
Q2.
“これを繰り返して”という記述で $I_{0},I_{1},I_{2},\ldots$ という無限列を作り出しているが，無限回の操作は許されるのか？
Q3.
部分列の作り方に関して， $I_{1}$ は $(a_{n})$ の項を無限に含むからといって， $i(0)<i(1)$ となる $i(1)$ がみつかるらしいのだが，具体的にどうやってみつけるのか？　そして再び“これを繰り返して”という記述で無限列 $i(0),i(1),i(2),\ldots$ をとっているが，この無限回の操作も許されるのか？

いずれも無限がからんでいることに関する疑問です．対角線論法を否定的に解釈する人（数学者ではない）や，選択公理などを学んだ人は，無限回の操作を見ると慎重に考えてしまいます．Wikipediaからの引用ですが，クロネッカーの記事にも

構成的で，有限の操作しか行わないような証明でなければ疑わしく感じるようになった．従って，彼にはボルツァーノ＝ワイエルシュトラスの定理は認め難かった．

とあります．確かに，BW定理が正しくても，有界な数列 $(\sin n)$ から収束する部分列を具体的に構成することは，（少なくとも私には）困難です．となると，BW定理が正しいと分かったところでそれは机上の空論で，建設的な議論はできないのではないかと思いたくなります．しかし，それは現代数学が設定しているルールの問題（推論規則やZFC）にいきつくので，この文書では深く立ち入りしないことにします．あくまで，現代数学の立場でBW定理がちゃんとした定理であることを確認することを目標とします．

2. 無限個あることの判定について

数学において，ある対象が存在することとそれが具体的にどう表示されるのかは同じレベルの話ではありません．勿論後者がいえれば前者はいえますが，前者がいえたからといって後者がいえるとは限りません．高校で学ぶ平均値の定理などがまさにそれで， $\begin{matrix} \frac{f (b) - f (a)}{b - a} = f' (c), a < c < b \end{matrix}$ を満たす $c$ が存在することは分かっているけども，それが具体的に幾つかまでは言及しません．そして，その $c$ を用いて導かれる定理や結果は正しいものと認められるのです．となると，例えば，2つの集合 $A, B$ に対して，少なくとも一方が無限集合であることを示せれば，それを $C$ とでもおいて，以降の論理に用いることは認められることになります．特に $A\cup B$ が無限集合であることが分かれば， $A$ または $B$ は必ず無限集合になります．よって， $A, B$ のうち，無限集合である方を $C$ とするという議論は認められます．平均値の定理と同じことをやっている，ということをより理解するには，次のように存在記号を用いたステートメントで表すとよいでしょう． $\begin{matrix} \exists c \in 𝐑 \frac{f (b) - f (a)}{b - a} = f' (c), a < c < b \end{matrix}$ と $\begin{matrix} \exists C \in {A, B} C は無限集合 \end{matrix}$ を比較しましょう．平均値の定理によって $c$ を用いた議論を今後行えるのであれば， $A$ または $B$ を表す $C$ も今後用いることは可能なはずです．

次に，無限集合について少し触れます．無限集合の定義ですが，これは本によって異なるので面倒です．最も万人に受け入れられそうな「有限集合でない集合を無限集合と呼ぶ」をここでは採用します．すると，有限集合であることの定義も必要になります．

定義 1 (有限集合，無限集合の定義).

集合 $A$ が空集合であるか，ある正の整数 $n$ に対して全単射 $\begin{matrix} a : {1, 2, \dots, n} \to A \end{matrix}$ が存在するとき， $A$ は有限集合であるという．有限集合でない集合を無限集合という．

ここで， $\{1,2,\ldots,n\}$ は $\begin{matrix} {k \in 𝐍 ∣ 1 ≦ k ≦ n} \end{matrix}$ の略記だと思ってください．このような全単射 $a$ の存在より，任意の $A$ の元 $x$ に対して，ユニークな $1\leqq k\leqq n$ が存在して， $x=a(k)$ と表せます．これを $x=a_{k}$ と表すことが多いです．すると集合 $A$ は $\begin{matrix} A = {a_{k} ∣ 1 ≦ k ≦ n} \end{matrix}$ と表せます．これを直感的に $\begin{matrix} A = {a_{1}, a_{2}, \dots, a_{n}} \end{matrix}$ と表すことが多いです．

また，有限集合 $A$ に対するこの $n$ は全単射のとり方によらずユニークに定まります（証明が必要）．

定理 1 (有限集合の和集合).

$A, B$ が有限集合のとき， $A\cup B$ も有限集合である．

当たり前のことですが，じゃあ，証明してみろと言われると難しいのではと思います．ここら辺の厳密な話は，BW定理とはあまり関係ないので，またの機会に回します．さて，このステートメントの対偶をとれば， $A\cup B$ が無限集合ならば， $A$ または $B$ は無限集合であることになります．

さて，BW定理の証明を再考してみましょう． $(a_{n})$ は有界だからある実数 $b_{0},c_{0}$ が存在し，任意の $n$ に対して $b_{0}\leqq a_{n}\leqq c_{0}$ を満たします．そして， $I_{0}=[b_{0},c_{0}]$ とします．当然， $I_{0}$ には $(a_{n})$ の項が無限に存在します．ただ，これも言い方には注意が必要で，例えば $(a_{n})$ が $a_{n}=2$ という定数列だった場合， $(a_{n})$ の項は $2$ しかないのではないかと突っ込まれそうです．多くの本で書かれている $(a_{n})$ の項が無限個あるという述語を厳密にいうと， $I_{0}$ に属する $a_{n}$ の添字の集合が無限集合である，となります．

定義 2 (数列の項が無限に存在するとは).

空でない閉区間 $I$ に対して $\begin{matrix} {n \in 𝐍 ∣ a_{n} \in I} \end{matrix}$ が無限集合になることを，「 $I$ に $(a_{n})$ の項が無限に存在する」という．

$I_{0}=[a_{0},b_{0}]$ には $(a_{n})$ の項が無限に存在します．直感的にではなく，上の定義に基づいて説明しましょう． $\begin{matrix} L = {n \in 𝐍 ∣ a_{n} \in I_{0}} \end{matrix}$ と置き， $\mathbf{N}=L$ が実際に成り立つことを示せば， $\mathbf{N}$ は無限集合だから題意は示されます． $L\subset\mathbf{N}$ ですから $L\supset\mathbf{N}$ を示せばよいことが分かります． $I_{0}=[b_{0},c_{0}]$ の定義より，任意に $n\in\mathbf{N}$ をとると $b_{0}\leqq a_{n}\leqq c_{0}$ が成り立つので $a_{n}\in I_{0}$ が成り立つので， $n\in L$ です．よって $\mathbf{N}\subset L$ です．以上より， $\mathbf{N}=L$ だから， $I_{0}$ には $(a_{n})$ の項が無限に存在することが示せました．

次に $I_{0}=[a_{0},b_{0}]$ の中点 $(a_{0}+b_{0})/2$ をとり，左半分と右半分に区間を分けます．この記述は煩雑なので，新たな記号を導入しましょう．

定義 3 (閉区間の右半分と左半分).

空でない閉区間 $I=[a,b]$ に対して $\begin{matrix} left (I) = [a, (a + b) / 2], right (I) = [(a + b) / 2, b] \end{matrix}$ と定義する．

$I_{0}$ に $(a_{n})$ の項が無限に存在するとき， $\begin{matrix} left (I_{0}), right (I_{0}) \end{matrix}$ のどちらかには $(a_{n})$ の項が無限に存在します．すなわち $\begin{matrix} L = & {n \in 𝐍 ∣ a_{n} \in left (I_{0})} \\ R = & {n \in 𝐍 ∣ a_{n} \in right (I_{0})} \end{matrix}$ の少なくとも一方は無限集合になります．これは証明されなければなりません．仮にどちらも有限集合とすれば当然 $L\cup R$ は有限集合になりますが，実際 $\begin{matrix} a_{n} \in I_{0} \Leftrightarrow a_{n} \in left (I_{0}) \lor a_{n} \in right (I_{0}) \Leftrightarrow a_{n} \in L \lor a_{n} \in R \end{matrix}$ が成り立つので， $\begin{matrix} {n \in 𝐍 ∣ a_{n} \in I_{0}} = L \cup R \end{matrix}$ です．ここで左辺は無限集合なので矛盾します．よって $\operatorname{left}(I_{0})$ ， $\operatorname{right}(I_{0})$ のどちらかには $(a_{n})$ の項が無限に存在するので，そのどちらかを $I_{1}$ とすることができます．

3. 無限回の操作について

「これを繰り返して」，「以下同様にして」，少し気の利いた本であれば「帰納的に」という記述は数学では非常に多く登場します．いわゆる写像の帰納的な定義という手法です．BW定理をみると，無限回の操作をして $\begin{matrix} I_{0}, I_{1}, I_{2}, \dots, I_{n}, \dots \end{matrix}$ という無限列を作りだしているようにみえますが，スタートとなる $I_{0}$ を定義し，また， $I_{n}$ （と $n$ ）を用いてただ一つの $I_{n+1}$ を定義する手続きが定まっているのであればそのような無限列を扱ってもよい，という定理が数学にはあるのです．難しそうな話をしていますが，同様の議論は漸化式として高校生も体験しています． $a_{0}=1,\ a_{n+1}=a_{n}+2$ であれば $a_{n}=2n+1$ という風に一般項が具体的に求まるので，無限個の $\begin{matrix} a_{0}, a_{1}, a_{2}, \dots, a_{n}, \dots \end{matrix}$ を認知するのは簡単ですが， $\begin{matrix} a_{0} = 0, a_{n + 1} = \sqrt{1 + a_{n}} \end{matrix}$ といった漸化式で定義される数列は， $a_{n}$ を簡単に表示することはできません． $a_{1},a_{2},a_{3},\ldots$ が具体的にいくつかどうかは， $\begin{matrix} a_{1} = 1, a_{2} = \sqrt{2}, a_{3} = \sqrt{1 + \sqrt{2}}, a_{3} = \sqrt{1 + \sqrt{1 + \sqrt{2}}}, \dots \end{matrix}$ として逐次代入計算をし続けることで具体的な項が分かるだけです．この場合，一般の自然数 $n$ に対する第 $n$ 項 $a_{n}$ が不透明ではありますが，例えば $a_{10000}$ が存在するかどうかは分からないから考えることはできない，と言い張る人はいないでしょう． $10000$ 回の代入計算をすれば必ず求まるからです．同様にすれば，どんな（具体的な）自然数 $n$ に対しても $a_{n}$ は確かに存在する，そういう認識をすることは難しくないと思います．そしてそれは何故かというと， $\begin{matrix} a_{n + 1} = \sqrt{1 + a_{n}} \end{matrix}$ という， $a_{n}$ を用いて $a_{n+1}$ を得るための具体的な手続きが明確になっているからです．

ここまで，「認知する」とか，「認識をする」などの感覚的な言葉を用いてきましたが，もう少し厳密な話をしましょう．そもそも（実）数列とは自然数全体の集合 $\mathbf{N}$ から実数全体の集合 $\mathbf{R}$ への写像のことです．数列 $a:\mathbf{N}\to\mathbf{R}$ に対して，通常であれば $a(n)$ と書くところを $a_{n}$ としているわけです．また，定義より $a$ という記号単体で数列を表しますが，習慣的に $(a_{n})$ ， $(a_{n})_{n\in\mathbf{N}}$ などの記号を用います．つまるところ，数列に必要な要件は，任意の $n\in\mathbf{N}$ に対して $a_{n}$ がただ1つ定まっていることです． $a_{n}=2n-1$ のように，具体的な式表示があれば，任意の $n$ に対して $a_{n}$ はただ1つ定まっているといえますが，一般項がなく， $\begin{matrix} a_{n + 1} = \sqrt{1 + a_{n}} \end{matrix}$ という関係式だけで，本当に任意の $n$ に対して $a_{n}$ が一通りに定まっているのかが疑わしいのです． $a_{10},a_{11},a_{12}$ など，具体的な場合は有限の記号列（途中式）で確認できるでしょうが， $n$ が任意になってくると自信はなくなります．そこで活躍するのが「再帰性定理」です．

定理 2 (再帰性定理 I).

集合 $X$ に対して， $a\in X$ ， $f:X\to X$ のとき，

(i)
$\varphi(0)=a$
(ii)
$\forall n\in\mathbf{N}\ \varphi(n+1)=f(\varphi(n))$

を満たす写像 $\varphi:\mathbf{N}\to X$ が唯一つ存在する．

この定理において $X=\mathbf{R}$ ， $a=0$ ， $f(x)=\sqrt{1+x}$ とすれば

(i)
$\varphi(0)=0$
(ii)
$\forall n\in\mathbf{N}\ \varphi(n+1)=\sqrt{1+\varphi(n)}$

を満たす写像 $\varphi(n)$ が唯一つ存在します． $\varphi(n)$ を $a_{n}$ と表せば $\begin{matrix} a_{0} = 1, \forall n \in 𝐍 a_{n + 1} = \sqrt{1 + a_{n}} \end{matrix}$ と書けるので，どんな $n\in\mathbf{N}$ に対しても $a_{n}$ は確かに存在し，具体的な表示は分からないけども数学で扱うことが可能になるわけです．また，具体的な計算をしなくても $a_{10000}$ などが一通りに存在していることも分かります．

再帰性定理という呼び方は足立恒雄氏の『数とは何かそしてまた何であったか』のものを拝借していますが，同じ著者の『数体系と歴史』では回帰定理とあります．英語ではrecursion theoremというそうです．斎藤正彦氏の『数学の基礎』には数学的帰納法による写像の定義，という名前で紹介されています．ペアノの公理系から出発して自然数の話を展開した人ならば分かると思いますが，再帰性定理の汎用性は非常に高く，これまで曖昧に理解するしかなかった概念を，厳密なものとして取り入れることが可能になります．また，本文書で再帰性定理 Iとなっているのは，より汎用性のある再帰性定理 IIが存在するから，勝手にバージョンナンバーを付け足してます．

再帰性定理をもう少し深く見ていきましょう．(ii)の式に $n=1,2,\ldots$ を代入していけば分かりますが， $\begin{matrix} φ (1) & = f (φ (0)) = f (a) \\ φ (2) & = f (φ (1)) = f (f (a)) \\ φ (3) & = f (φ (2)) = f (f (f (a))) \end{matrix}$ となり，どうやら $\varphi(n)$ は $a$ を $f$ で $n$ 回写してできる元であることが確認できます．直感的には $\begin{matrix} a = φ (0) \overset{𝑓}{\mapsto} φ (1) \overset{𝑓}{\mapsto} φ (2) \overset{𝑓}{\mapsto} \dots \overset{𝑓}{\mapsto} φ (n) \overset{𝑓}{\mapsto} \dots \end{matrix}$ という図式のように， $a$ を初項として，逐次 $f$ で移してできる列を得るための定理が再帰性定理です．ようは任意の自然数 $n$ に対する写像の $n$ 回合成の存在を認める定理なのです．「写像で移す」ことを「手続き」という言葉に換言するならば，ある「手続き」を $n$ 回繰り返すことを，再帰性定理は定式化しているのです．例えば $a^{n}$ の定義として $\begin{matrix} a^{n} = \underset{n 個}{\underset{⏟}{a \times \dots \times a}} \end{matrix}$ とするのは，右辺が具体的にどういう式を意味しているかが不明です． $a^{n}$ は，（ $1$ に） $a$ を $n$ 回かけることで得られる実数のことです．同じ手続きを繰り返して得られるものを定義するのに再帰性定理が効果を発揮します． $a^{n}$ の厳密な定義は， $\begin{matrix} x \mapsto a x \end{matrix}$

として定義される写像 $f:\mathbf{R}\to\mathbf{R}$ を考え，再帰性定理より

(i)
$\varphi(0)=1$
(ii)
$\forall n\in\mathbf{N}\ \varphi(n+1)=f(\varphi(n))=a\varphi(n)$

として定まる写像 $\varphi$ に対する $\varphi(n)$ を $a^{n}$ と表す，というものです． $\varphi(\square)$ を $a^{\square}$ に置き換えて(i)と(ii)を改めると

(i)’
$a^{0}=1$
(ii)’
$\forall n\in\mathbf{N}\ a^{n+1}=a\cdot a^{n}$

となります．(ii)’において $n=1,2,3$ を代入してみると $\begin{matrix} a^{1} & = a \cdot a^{0} = a \cdot 1 = a \\ a^{2} & = a \cdot a^{1} = a \cdot a \\ a^{3} & = a \cdot a^{2} = a \cdot a \cdot a \end{matrix}$ だから，確かに私たちの直感と一致します．

多くの文献では， $a^{n}$ を定義するのに，(i)’と(ii)’，すなわち， $a^{n}$ の定義に $a^{\square}$ を使う，プログラミングでいう再帰のような書き方をするので，人によっては違和感を覚えることでしょう（私だけ？）．この手の写像の定義をする場合， $f$ がどういう写像なのかをちゃんと明記した上で，再帰性定理のステートメントに則ることで，今自分が本当に現代数学で考えることができる対象を扱っているのかを確認することでもやもやした部分を解消できます．

$a^{n}$ の定義をちゃんと行えば，任意の $m,n\in\mathbf{N}$ に対する $\begin{matrix} a^{m} a^{n} = a^{m + n} \end{matrix}$ などの基本的な公式の証明も厳密に証明することができます． $a^{n}$ の定義より上の(i)’と(ii)’が使えます． $m$ を任意の自然数として， $n$ についての帰納法で示してみましょう． $n=0$ のとき， $\begin{matrix} a^{m} a^{n} = a^{m} a^{0} = a^{m} 1 = a^{m} = a^{m + 0} = a^{m + n} \end{matrix}$ で確かに成り立ちます． $a^{m}a^{n}=a^{m+n}$ を仮定して $a^{m}a^{n+1}=a^{m+n+1}$ を証明しましょう．(ii)’より $\begin{matrix} a^{m} a^{n + 1} = a^{m} a \cdot a^{n} = a \cdot a^{m} a^{n} \end{matrix}$ 帰納法の仮定より $\begin{matrix} a \cdot a^{m} a^{n} = a \cdot a^{m + n} \end{matrix}$ (ii)’より $\begin{matrix} a \cdot a^{m + n} = a^{m + n + 1} \end{matrix}$ 以上で $a^{m}a^{n+1}=a^{m+n+1}$ が示せたので，任意の $m,n\in\mathbf{N}$ に対して $a^{m}a^{n}=a^{m+n}$ が示せました．他の指数法則なども証明できるので，自分で証明したことがない定理は使わないという主義の人や，暇な人は試してみてください．ちなみに， $\begin{matrix} \sum_{k = 0}^{n} a_{k}, \prod_{k = 0}^{n} a_{k} \end{matrix}$ などの記号も，再帰性定理を用いて初めて厳密に数学で扱える対象として定義されます（厳密には後述の再帰性定理 IIが必要）．もっと根元的な話をすると，自然数同士の加法や乗法も再帰性定理によります．自然数の定義から厳密に数学を展開すると，いかに再帰性定理が重要かが体感できます．

ところで，BW定理で出てくる無限回の操作をして構成しているように見える $\begin{matrix} I_{0}, I_{1}, \dots, I_{n}, \dots \end{matrix}$ も，再帰性定理を用いれば数学的に認められた存在になります． $\mathfrak{I}$ を $\mathbf{R}$ の（空でない）閉区間全体の集合としましょう．前節で，閉区間 $I$ に対して数列 $(a_{n})$ の項が無限に存在することの定義はしてあります．また，閉区間 $I$ の左半分と右半分を表す記号 $\operatorname{left}(I),\operatorname{right}(I)$ を用います．さて，写像 $f:\mathfrak{I}\to\mathfrak{I}$ を $\begin{matrix} f (I) = {\begin{matrix} left (I) & (left (I) に (a_{n}) の項が無限に存在する) \\ right (I) & (それ以外) \end{matrix} \end{matrix}$ として定義します．こういった場合分けによる写像の定義は $\begin{matrix} | x | = {\begin{matrix} x & (x ≧ 0) \\ - x & (x < 0) \end{matrix} \end{matrix}$ などで，古くから用いられているので，それほど奇怪なものではありません．さて，写像 $f$ について次が成り立ちます．証明はどれも簡単です．

定理 3.

$I=[a,b]$ ， $f(I)=[a^{\prime},b^{\prime}]$ とする．

(1)
$I\supset f(I)$ ．
(2)
$a\leqq a^{\prime}$ ， $b^{\prime}\leqq b$ ．
(3)
$\displaystyle b^{\prime}-a^{\prime}={\,b-a\,\over\,2\,}$ ．
(4)
$I$ に $(a_{n})$ の項が無限に存在するならば， $f(I)$ にも $(a_{n})$ の項が無限に存在する．

有界な数列 $(a_{n})$ に対し，ある実数 $b, c$ が存在して任意の $n\in\mathbf{N}$ に対して $b\leqq a_{n}\leq c$ とできます．再帰性定理より

(i)
$I(0)=[b,c]$
(ii)
$I(n+1)=f(I(n))$

を満たす写像 $I:\mathbf{N}\to\mathfrak{I}$ が唯一つ存在します． $I(n)$ を $I_{n}$ と表すことにすると

(i)’
$I_{0}=[b,c]$
(ii)’
$I_{n+1}=f(I_{n})=\begin{cases}\operatorname{left}(I_{n})&(\text{$\operatorname% {left}(I_{n})$に$(a_{n})$の項が無限に存在する})\\ \operatorname{right}(I_{n})&(\text{それ以外})\end{cases}$

と書き換えられます．これで任意の自然数 $n$ に対する閉区間 $I_{n}$ が定まりました．そして， $\begin{matrix} b_{n} = \min I_{n}, c_{n} = \max I_{n} \end{matrix}$

として数列 $(b_{n}),(c_{n})$ を定義します． $f$ の性質より

(1)
$I_{n}\supset I_{n+1}$
(2)
$\forall n\in\mathbf{N}\ b_{n}\leqq b_{n+1},\ c_{n+1}\leqq c_{n}$
(3)
$\forall n\in\mathbf{N}\ \displaystyle c_{n+1}-b_{n+1}={\,c_{n}-b_{n}\,\over\,2\,}$
(4)
$I_{n}$ に $(a_{n})$ の項が無限に存在するならば， $f(I_{n})=I_{n+1}$ にも $(a_{n})$ の項が無限に存在する．

が成り立ちます．特に $I_{0}$ に $(a_{n})$ の項が無限に存在することと(4)より，任意の $I_{n}$ に $(a_{n})$ の項が無限に存在することが，帰納法により示されます．また，(3)の漸化式を解くことによって $\begin{matrix} c_{n} - b_{n} = \frac{b - c}{2^{n}} \to 0 (n \to \infty) \end{matrix}$ が成り立ちます．

ここで，BW定理の証明でよくある間違いを注意します．証明の最初， $I_{0}=[b_{0},c_{0}]$ から $I_{1}$ を定義する際，「 $\operatorname{left}(I_{0})$ が無限集合なら $I_{0}=\operatorname{left}(I_{0})$ ， $\operatorname{right}(I_{0})$ が無限集合なら $I_{1}=\operatorname{right}(I_{0})$ とする」という書き方をよく見かけますが，これは明らかに間違いです．この場合，写像 $f:\mathfrak{I}\to\mathfrak{I}$ を $\begin{matrix} f (I) = {\begin{matrix} left (I) & (left (I) に (a_{n}) の項が無限に存在する) \\ right (I) & (right (I) に (a_{n}) の項が無限に存在する) \end{matrix} \end{matrix}$ と定めて再帰性定理を用いようとしているのでしょうが，この $f$ は写像になっていません．なぜならば， $\operatorname{left}(I)$ にも $\operatorname{right}(I)$ にも $(a_{n})$ の項が無限に存在する場合， $f(I)$ は $\operatorname{left}(I)$ でも $\operatorname{right}(I)$ でもよくなってしまうので，写像の移り先として唯一つに定まらないからです．だから，ここは $\operatorname{left}(I)$ に $(a_{n})$ の項が無限に存在する場合と，それ以外で定義すべきです．また， $\operatorname{left}(I)$ にも $\operatorname{right}{I}$ にも $(a_{n})$ の項が無限に存在する場合はどちらでもよい，という記述もたまに見かけますが，これも危険です． $n$ が奇数だったら左半分，偶数だったら右半分，のように両方だった場合の明確な決め方を指定しているのならともかく，どちらでも良い，というように任意性を与えていると，やはりこれも $f:\mathfrak{I}\to\mathfrak{I}$ が写像として成立しないので，再帰性定理を正しく使えていません．

4. 再帰性定理の拡張

再帰性定理 Iだけでは

(i)
$a_{0}=1$
(ii)
$a_{n+1}=(n+1)a_{n}\quad(\forall n\in\mathbf{N})$

という形の漸化式で定まる数列を考えることはできません．この $a_{n}$ はいわゆる階乗 $n!$ です．再帰性定理 Iのステートメントでは， $\varphi(n)$ だけを用いて $\varphi(n+1)$ を定義させるような手続きがあれば……という形態なので， $\varphi(n)$ と $n$ を用いて $\varphi(n+1)$ を定義するような状況では使えません．これを解決するには次の再帰性定理 IIを用います．

定理 4 (再帰性定理 II).

集合 $X$ に対して， $a\in X$ ， $f:\mathbf{N}\times X\to X$ のとき，

(i)
$\varphi(0)=a$
(ii)
$\forall n\in\mathbf{N}\ \varphi(n+1)=f(n,\varphi(n))$

を満たす写像 $\varphi:\mathbf{N}\to X$ がただ1つ存在する

再帰性定理 Iとの違いは， $f(\varphi(n))$ の部分が $f(n,\varphi(n))$ になっているところです．これによってより多くの写像を扱うことができます．例えば， $X=\mathbf{R}$ ， $a=1$ ， $f(n,x)=(n+1)x$ とすれば

(i)
$\varphi(0)=0$
(ii)
$\forall n\in\mathbf{N}\ \varphi(n+1)=(n+1)\varphi(n)$

を満たす $\varphi$ がただ1つ存在します． $\varphi(n)$ を $n!$ と表せば，階乗の出来上がりです．

再帰性定理 IIは再帰性定理 Iの応用として簡単に証明できますが，一見複雑に見えるので，先に概略を説明します．そもそも再帰性定理 Iとは，直感的には $\begin{matrix} a = φ (0) \overset{𝑓}{\mapsto} φ (1) \overset{𝑓}{\mapsto} φ (2) \overset{𝑓}{\mapsto} \dots \overset{𝑓}{\mapsto} φ (n) \overset{𝑓}{\mapsto} \dots \end{matrix}$ という図式のように， $a$ を初項として，逐次 $f$ で移してできる列を得るための定理でした．ここで $f$ は集合 $X$ から $X$ への写像です．それが直積集合でも構いません．だから， $X=\mathbf{N}\times\mathbf{N}$ として $\begin{matrix} g (n, x) = (n + 1, (n + 1) x) \end{matrix}$ と定義し， $b=(0,1)$ として， $g$ で逐次移していけば $\begin{matrix} (0, 1) & \overset{𝑔}{\mapsto} (1, 1 \cdot 1) = (1, 1) \\ \overset{𝑔}{\mapsto} (2, 2 \cdot 1) = (1, 2) \\ \overset{𝑔}{\mapsto} (3, 3 \cdot 2) = (3, 6) \\ \overset{𝑔}{\mapsto} (4, 4 \cdot 6) = (4, 24) \end{matrix}$ となり， $n$ 回目に移したものが， $(n,n!)$ になっているので，この第2成分を $\varphi(n)$ とすればよいのです．この説明を一般の場合に，ちゃんとした言葉でこてこてにしたものが次です．

(再帰性定理 IIの証明) 写像 $g:\mathbf{N}\times X\to\mathbf{N}\times X$ を $\begin{matrix} g (n, x) = (n + 1, f (n, x)) \end{matrix}$

と定義します．再帰性定理 Iより

(i)
$\psi(0)=(0,a)$
(ii)
$\psi(n+1)=g(\psi(n))$

を満たす $\psi:\mathbf{N}\to\mathbf{N}\times X$ がただ1つ存在します．ここで， $\psi(n)$ は $\mathbf{N}\times X$ の元なので，第1成分を $\iota(n)$ ，第2成分を $\varphi(n)$ と表すことにすると， $\psi(n)=(\iota(n),\varphi(n))$ と表せます．この記法で(i)と(ii)を書き直すと

(i)
$(\iota(0),\varphi(0))=(0,a)$
(ii)
$\forall n\in\mathbf{N}\ (\iota(n+1),\varphi(n+1))=g(\iota(n),\varphi(n))=(% \iota(n)+1,f(\iota(n),\varphi(n)))$

となります．かなり面倒くさそうな展開になってきましたが，第1成分だけに着目すると $\begin{matrix} ι (0) = 0, \forall n \in 𝐍 ι (n + 1) = ι (n) + 1 \end{matrix}$

ですから， $\iota(n)=n$ です．よって(i)と(ii)は更に

(i)
$(0,\varphi(0))=(0,a)$
(ii)
$(n+1,\varphi(n+1))=(n+1,f(n,\varphi(n)))$

と書き換わります．第2成分だけを抽出すると

(i)
$\varphi(0)=a$
(ii)
$\varphi(n+1)=f(n,\varphi(n))$

となっています．これで $\varphi$ の存在はいえました．一意性は帰納法で簡単に証明できます．

5. 部分列の構成

再帰性定理によって，閉区間の列 $\begin{matrix} I_{0} \supset I_{1} \supset \dots \supset I_{n} \supset \dots \end{matrix}$ は各 $I_{n}=[b_{n},c_{n}]$ に $(a_{n})$ の項が無限に存在するように構成することができました．このあと，適切に各 $I_{n}$ から $(a_{n})$ の項をとりだし，収束する部分列を構成します．しかし，個人のブログなどに多いのですが，取り出し方の詳細が書かれておらず， $I_{n}$ に $(a_{n})$ の項が無数に存在するから，任意に1つずつ取り出して $(a_{n})$ の部分列を構成すればいい，といった記述が見られます．これは部分列の定義を無視した大きな間違いです（さすがに書籍化されているものにはほとんど見受けられません）．また， $I_{n}$ に属する $a_{n}$ から，最も番号が若いものを $a_{i(n)}$ とする，という惜しい説明も見かけます．しかし，いずれにしろ部分列の定義を無視しているので間違いです．この部分列の構成において，部分列の定義と，項を取り出す方法，2つの項目を見直す必要があります．

まず部分列の定義からです．素朴に言えば，数列 $\begin{matrix} a_{0}, a_{1}, a_{2}, \dots \end{matrix}$ において，左から項を適当に選んでできる数列のことを $(a_{n})$ の部分列といいます．例えば，偶数項だけ取り出した $\begin{matrix} a_{0}, a_{2}, a_{4}, \dots \end{matrix}$ 素数の項だけ取り出した $\begin{matrix} a_{2}, a_{3}, a_{5}, \dots \end{matrix}$ などです．ここで大事なのは，「左から」という表現があるので，部分列において， $a_{n}$ の添字が途中で小さくなったりするものは考えません．例えば $\begin{matrix} a_{3}, a_{2}, a_{1}, a_{11}, a_{12}, \dots \end{matrix}$ といったものは部分列とは呼びません．よって，部分列を構成する上で， $a_{n}$ の添字が単調に増加するような取り方に限定されます．厳密には次のように定義します．

定義 4 (部分列の定義).

写像 $i:\mathbf{N}\to\mathbf{N}$ を狭義増加関数とする．すなわち， $\begin{matrix} \forall n \in 𝐍 i (n) < i (n + 1) \end{matrix}$ が成り立つとする．このとき，数列 $(a_{n})$ に対して，第 $n$ 項を $a_{i(n)}$ として定義される数列 $\begin{matrix} a_{i (0)}, a_{i (1)}, \dots, a_{i (n)}, \dots \end{matrix}$ を $(a_{n})$ の部分列という．

例えば， $i(n)=2n$ として定義すれば， $\begin{matrix} i (0) = 0, i (1) = 2, i (2) = 4, \dots \end{matrix}$ で，単調増加ですから $\begin{matrix} a_{0}, a_{2}, a_{4}, \dots, a_{2 n}, \dots \end{matrix}$ となり，偶数項だけを取り出した部分列が出来上がります．部分列 $\begin{matrix} a_{i (0)}, a_{i (1)}, \dots, a_{i (n)}, \dots \end{matrix}$ を構成する上で重要なのは $i(n)<i(n+1)$ が成り立っていなければならないということです．BW定理の証明において，各 $I_{n}$ から $(a_{n})$ の項を任意に1つとって，それを $a_{i(n)}$ としてしまうと， $i(n)<i(n+1)$ かどうかの保証がありません．もっと言えば選択公理を用いています．そもそも $I_{n}$ から任意に1つとってくれば良いだけなのなら， $(a_{n})$ の項が無限に存在するように $I_{n}$ を定義した意味がありません．

次に項の取り出し方についてです．ここまでで選択公理がどうたらこうたらという話をちょくちょく持ち出しています．選択公理を認めると，例えば，空でない $\mathbf{R}$ の部分集合の列 $\begin{matrix} A_{0}, A_{1}, A_{2}, \dots, A_{n}, \dots \end{matrix}$ から， $a_{n}\in A_{n}$ を満たすような数列 $\begin{matrix} a_{0}, a_{1}, a_{2}, \dots, a_{n}, \dots \end{matrix}$ をとることができます．当たり前と思うか，そうでないと思うかは人それぞれです．クロネッカーのような立場の人は， $a_{n}$ は具体的にどう表されるのか，という点を突っ込むのかもしれません．一方で，空でない $\mathbf{N}$ の部分集合の列 $\begin{matrix} W_{0}, W_{1}, W_{2}, \dots, W_{n}, \dots \end{matrix}$ から， $w_{n}\in W_{n}$ を満たすような数列 $\begin{matrix} w_{0}, w_{1}, w_{2}, \dots, w_{n}, \dots \end{matrix}$ は，選択公理を仮定しなくてもとることができます．なぜならば， $\mathbf{N}$ の空でない任意の部分集合は最小元をもつことが数学的帰納法で証明できるので， $\begin{matrix} w_{n} = \min W_{n} \end{matrix}$ とすれば，数列 $(w_{n})$ が直接的に定義できるからです．空でない実数の部分集合 $A$ には，そのようなある確定した値を指定することができないために選択公理が必要なのです．

空でない $\mathbf{N}$ の部分集合が最小元をもつという性質は $\mathbf{N}$ の整列性と呼ばれるもので，色々な分野で使われています．例えば，整数 $a, b$ に対してその最大公約数を $d$ とするとき， $\begin{matrix} a x + b y = d \end{matrix}$ を満たす整数 $x, y$ が存在することを示すには， $\begin{matrix} {a x + b y ∣ x, y \in 𝐙} \end{matrix}$ は空でないから，その最小元を $d$ とし，その $d$ が， $a, b$ の最大公約数であることを示す，という流れで証明します．また，群 $G$ の元 $a$ に対して，ある自然数 $n$ が存在して $a^{n}=1$ を満たすとき，そのような $n$ で最小のものを $a$ の位数といいます．ここでも整列性を用いています．線型代数や体論で登場する最小多項式の存在もやはり整列性によっています． $\mathbf{N}$ の整列性はあらゆる所で使われていますが，それは数学的帰納法が正しい議論であることと同値です．つまり，現代数学のあらゆる所で帰納法を用いていることになります．

定理 5 ( $\mathbf{N}$ の整列性).

次は同値である．

(i)
$\mathbf{N}$ の任意の空でない部分集合は最小元をもつ．
(ii)
$p(n)$ を論理式とする．以下が示せれば $\forall n\in\mathbf{N}\ p(n)$ ：
1. (I)
  $p(0)$ ．
2. (II)
  $\forall n\in\mathbf{N}\ p(n)\Rightarrow p(n+1)$ ．

では， $\mathbf{N}$ の整列性を用いて， $(a_{n})$ の部分列を構成しましょう．写像 $g:\mathbf{N}\times\mathbf{N}\to\mathbf{N}$ を $\begin{matrix} g (n, x) = \min {k \in 𝐍 ∣ a_{k} \in I_{n + 1} \land x < k} \end{matrix}$ で定義します．これは各 $I_{n}$ には $(a_{n})$ の項が無限に存在するという性質より， $\min\{k\in\mathbf{N}\mid a_{k}\in I_{n}\wedge m<k\}$ が空でないので， $\mathbf{N}$ の整列性により必ず最小元が存在する事実から，写像 $g$ が確定します．最小元の定義から当然 $\begin{matrix} g (n, x) \in {k \in 𝐍 ∣ a_{k} \in I_{n + 1} \land x < k} \end{matrix}$ が成り立つので， $\begin{matrix} a_{g (n, x)} \in I_{n + 1}, x < g (n, x) \end{matrix}$

が任意の $n\in\mathbf{N}$ で成り立つことに注意してください．再帰性定理 IIより

(i)
$i(0)=\min\{k\in\mathbf{N}\mid a_{k}\in I_{0}\}$
(ii)
$\forall n\in\mathbf{N}\ i(n+1)=g(n,i(n))$

を満たす写像 $i:\mathbf{N}\to\mathbf{N}$ が唯一つ存在します． $g$ の性質 $\begin{matrix} a_{g (n, x)} \in I_{n + 1}, x < g (n, x) \end{matrix}$ において， $x=i(n)$ とすれば $\begin{matrix} a_{g (n, i (n))} \in I_{n + 1}, x < g (n, i (n)) \end{matrix}$ すなわち $\begin{matrix} a_{i (n + 1)} \in I_{n + 1}, i (n) < i (n + 1) \end{matrix}$ が任意の $n\in\mathbf{N}$ で成り立ちます． $a_{i(0)}\in I_{0}$ は， $i(0)$ の定義より成り立つので，任意の $n\in\mathbf{N}$ に対して $a_{i(n)}\in I_{n}$ が成り立ちます．

6. 誤解のない証明

では最後に，無限回の操作をしていると思わせない，ちゃんとした証明をして締めくくります．

(BW定理の証明) 数列 $(a_{n})$ は有界なので，ある $b,c\in\mathbf{R}$ が存在して任意の $n\in\mathbf{N}$ に対して $b\leqq a_{n}\leqq c$ を満たす．空でない閉区間全体の集合を $\mathfrak{I}$ として，写像 $f:\mathfrak{I}\to\mathfrak{I}$ を $\begin{matrix} f (I) = {\begin{matrix} left (I) & (left (I) に (a_{n}) の項が無限に存在する) \\ right (I) & (それ以外) \end{matrix} \end{matrix}$ で定義する．再帰性定理より $\begin{matrix} I_{0} = [b, c], I_{n + 1} = f (I_{n}) \end{matrix}$

を満たす $\mathfrak{I}$ の列 $(I_{n})$ が唯一つ存在する． $f$ の性質より，以下の性質が示せる．

(1)
$I_{n}\supset I_{n+1}$
(2)
$\forall n\in\mathbf{N}\ b_{n}\leqq b_{n+1},\ c_{n+1}\leqq c_{n}$
(3)
$\forall n\in\mathbf{N}\ \displaystyle c_{n+1}-b_{n+1}={\,c_{n}-b_{n}\,\over\,2\,}$
(4)
$\forall n\in\mathbf{N}\ I_{n}$ に $(a_{n})$ の項が無限に存在する．

(2)より， $(b_{n}),(c_{n})$ は単調かつ有界な数列であることが分かり，(3)によって $\begin{matrix} c_{n + 1} - b_{n + 1} = \frac{c - b}{2^{n}} \to 0 (n \to \infty) \end{matrix}$ が成り立つので，同一の極限値 $\alpha$ に収束する．また，(4)と $\mathbf{N}$ の整列性より，写像 $g:\mathbf{N}\times\mathbf{N}\to\mathbf{N}$ を $\begin{matrix} g (n, x) = \min {k \in 𝐍 ∣ a_{k} \in I_{n + 1} \land x < k} \end{matrix}$ で定義できる．最小元の定義から当然 $\begin{matrix} g (n, x) \in {k \in 𝐍 ∣ a_{k} \in I_{n + 1} \land x < k} \end{matrix}$ が成り立つので， $\begin{matrix} a_{g (n, x)} \in I_{n + 1}, x < g (n, x) \end{matrix}$

が任意の $n\in\mathbf{N}$ で成り立つ．再帰性定理 IIより

(i)
$i(0)=\min\{k\in\mathbf{N}\mid a_{k}\in I_{0}\}$
(ii)
$\forall n\in\mathbf{N}\ i(n+1)=g(n,i(n))$

を満たす写像 $i:\mathbf{N}\to\mathbf{N}$ が唯一つ存在する． $g$ の性質より $\begin{matrix} a_{g (n, i (n))} \in I_{n + 1}, x < g (n, i (n)) \end{matrix}$ すなわち $\begin{matrix} a_{i (n + 1)} \in I_{n + 1}, i (n) < i (n + 1) \end{matrix}$ が任意の $n\in\mathbf{N}$ で成り立つ．任意の $n\in\mathbf{N}$ に対して $a_{i(n)}\in I_{n}$ が，すなわち $\begin{matrix} b_{n} ≦ a_{i (n)} ≦ c_{n} \end{matrix}$ が成り立つ．はさみうちの原理より $a_{i(n)}$ も $\alpha$ に収束する．以上で題意は示された．