漸化式の定義

Last-modified: Fri, 28 Apr 2017 10:52:41 JST (1681d)
Top > 漸化式の定義
点列の定義へ戻る。

それでは一般の点列に対して漸化式という概念を考えましょう。

定義1(2項間漸化式の定義
\( X \)をクラスとする。\( X \)に値を取る2項間漸化式(binary recurrence relation)とは、元\( c \in X \)とクラス関数\( f \colon X \to X \)の組\( (c,f) \)のことである。\( X \)の点列\( (a_i)_{i \in \mathbb{N}} \)2項間漸化式\( (c,f) \)を満たすとは、以下が成り立つということである:
(1) \( a_0 = c \)
(2) 任意の\( i \in \mathbb{N} \)に対し\( a_{i \cup \{ i \}} = f(a_i) \)

抽象的な書き方をしましたが、要するに2項間漸化式とは初項\( a_0 \)\( a_i \)から\( a_{i \cup \{ i \}} \)を決める方法のデータのことであるということです。さて、漸化式が与えられた時に、直感的には\( a_0 \)から順に\( a_1 \)\( a_2 \)と決まっていくように感じると思います。それを実際に、公理的集合論において厳密に証明することが出来ます。

定理2(2項間漸化式の解の一意存在性)
\( X \)をクラスとする。\( X \)に値を取る任意の2項間漸化式\( (c,f) \)に対し、\( (c,f) \)を満たすような\( X \)の点列\( (a_i)_{i \in \mathbb{N}} \)がただ1つ存在する。

証明

変項\( y \)を含む論理式\( \Phi \)を次のように定義し、\( \forall n \in \mathbb{N}, \Phi(n) \)を示す:ただ1つのクラス関数\( (a_i)_{i \in y} \colon y \to X \)が存在し、条件「\( a_0 = c \)かつ任意の\( i \in y \)に対し\( i \cup \{ i \} \in y \)ならば\( a_{i \cup \{ i \}} = f(a_i) \)」を満たす。

また量化の有界な論理式\( \Psi(y) \)を次のように定義する:ただ1つの集合の組\( (S,a) \)が存在して、\( S \)\( X \)の部分集合かつ\( a \)は全射な写像\( (a_i)_{i \in y} \colon y \to S \)かつ条件「\( a_0 = c \)かつ任意の\( i \in y \)に対し\( i \cup \{ i \} \in y \)ならば\( a_{i \cup \{ i \}} = f(a_i) \)」を満たす*1

\( \Psi(y) \)における\( S \)\( a \)と包含写像の合成\( a \colon y \to S \)の像に他ならないので、\( \Psi \)\( \Phi \)と同値である。従って、\( \forall n \in \mathbb{N}, \Psi(n) \)を示すためには\( \forall n \in \mathbb{N}, \Psi(n) \)を示せば良い。数学的帰納法により、\( n \in \mathbb{N}, \Psi(n) \)が成り立つことと、\( \Psi(0) \)が成り立ちかつ任意の\( n \in \mathbb{N} \)に対し\( \Psi(n) \)が成り立つならば\( \Psi(n \cup \{ n \}) \)が成り立つことは同値である。更に、任意の\( n \in \mathbb{N} \)に対し、\( \Psi(n) \)\( \Phi(n) \)は同値である。以上より、\( \forall n \in \mathbb{N}, \Phi(n) \)を示すためには\( \Phi(0) \)が成り立つことと任意の\( n \in \mathbb{N} \)に対し\( \Phi(n) \)が成り立つならば\( \Phi(n \cup \{ n \}) \)が成り立つことを示せば良い*2

\( X \)の空列はただ1つであるので、\( \Phi(0) \)が成り立つ。任意の\( n \in \mathbb{N} \)に対し、\( \Phi(n) \)が成り立つならば\( \Phi(n \cup \{ n \}) \)が成り立つことを示す。まず\( n = 0 \)とする。条件「\( a_0 = c \)かつ任意の任意の\( i \in n \)に対し\( i \cup \{ i \} \in n \)ならば\( a_{i \cup \{ i \}} = f(a_i) \)」を満たすような\( (a_i)_{i \in 1} \)\( (c) \)に限るので、\( \Phi(1) \)すなわち\( \Phi(n \cup \{ n \}) \)が成り立つ。

次に\( n \neq 0 \)とする。仮定より、ただ1つのクラス関数\( (a_i)_{i \in n} \colon n \to X \)が存在し、条件「\( a_0 = c \)かつ任意の\( i \in n \)に対し\( i \cup \{ i \} \in n \)ならば\( a_{i \cup \{ i \}} = f(a_i) \)」を満たす。自然数の順序数としての特徴付けから、ある\( m \in \mathbb{N} \)を用いて\( n = m \cup \{ m \} \)と表せる。\( a_n := f(a_m) \)と置くことで得られる\( X \)の元を\( (n \cup \{ n \}) \)個並べたもの\( (a_i)_{i \in n \cup \{ n \}} \)は条件「\( a_0 = c \)かつ任意の任意の\( i \in n \cup \{ n \} \)に対し\( i \cup \{ i \} \in n \cup \{ n \} \)ならば\( a_{i \cup \{ i \}} = f(a_i) \)」を満たす。更に、\( X \)の元を\( (n \cup \{ n \}) \)個並べたもの\( (b_i)_{i \in n \cup \{ n \}} \)が条件「\( b_0 = c \)かつ任意の任意の\( i \in n \cup \{ n \} \)に対し\( i \cup \{ i \} \in n \cup \{ n \} \)ならば\( b_{i \cup \{ i \}} = f(b_i) \)」を満たすとする。\( (b_i)_{i \in n} \)は条件「\( b_0 = c \)かつ任意の任意の\( i \in n \)に対し\( i \cup \{ i \} \in n \)ならば\( b_{i \cup \{ i \}} = f(b_i) \)」を満たすので、\( n \in N \)の仮定より\( (b_i)_{i \in n} = (a_i)_{i \in n} \)である。従って\( b_n = b_{m \cup \{ m \}} = f(b_m) = f(a_m) = a_{m \cup \{ m \}} = a_n \)より、\( (b_i)_{i \in n \cup \{ n \}} = (a_i)_{i \in n \cup \{ n \}} \)である。以上より、\( \Phi(n \cup \{ n \}) \)が成り立つ。

上の議論により、\( \forall n \in \mathbb{N}, \Phi(n) \)が成り立つ。各\( n \in \mathbb{N} \)に対し、条件「\( a_0 = c \)かつ任意の\( i \in n \)に対し\( i \cup \{ i \} \in n \)ならば\( a_{i \cup \{ i \}} = f(a_i) \)」を満たすただ1つのクラス関数クラス\( (a_i)_{i \in n} \colon n \to X \)\( (a_{n,i})_{i \in n} \)と置く。その一意性を用いた定義から、任意の\( n \in \mathbb{N} \)と任意の\( m \in n \)に対し\( (a_{n,i})_{i \in m} = (a_{m,i})_{i \in m} \)が成り立つ。従って、\( (a_{i,i})_{i \in \mathbb{N}} \)\( (a_i)_{i \in \mathbb{N}} \)と置くと*3、任意の\( n \in \mathbb{N} \)に対し\( (a_i)_{i \in n} = (a_{n,i})_{i \in n} \)が成り立つ。特に、\( (a_i)_{i \in \mathbb{N}} \)は2項間漸化式\( (c,f) \)を満たすような\( X \)の点列である。

\( X \)の点列\( (b_i)_{i \in \mathbb{N}} \)が2項間漸化式\( (c,f) \)を満たすとする。任意の\( n \in \mathbb{N} \)に対し、\( (b_i)_{i \in n \cup \{ n \}} \)は条件「\( b_0 = c \)かつ任意の\( i \in n \cup \{ n \} \)に対し\( i \cup \{ i \} \in n \cup \{ n \} \)ならば\( b_{i \cup \{ i \}} = f(b_i) \)」を満たすので、\( \Phi(n \cup \{ n \}) \)が成り立つことにより\( (b_i)_{i \in n \cup \{ n \}} = (a_{n \cup \{ n \},i})_{i \in n \cup \{ n \}} = (a_i)_{i \in n \cup \{ n \}} \)となり、特に\( b_n = a_n \)である。従って、\( (b_i)_{i \in \mathbb{N}} = (a_i)_{i \in \mathbb{N}} \)である。

2項間漸化式の解の一意存在性が数学的帰納法で証明されることから、漸化式を用いた議論は全て数学的帰納法で置き換えることが出来ます。しかしながら、漸化式によって多くの証明が簡潔になります。漸化式の最も重要な応用の1つとして、自然数の四則演算を公理的集合論の中で再定式化したり、冪集合が元の集合より「大きい」ことを保証する「カントール・ベルンシュタインの定理」を証明したり出来ます。カントール・ベルンシュタインの定理については以下を参照して下さい。

それでは足し算から順に考えていきましょう。




*1 集合全体のなすクラスを&mathjax{V};と置いて論理式で書くと、&mathjax{\exists P \in V, \exists S \in V, \exists a \in S^y, ( (P = (S,a) ) \wedge (\forall x \in S, \exists i \in y, (i,x) \in a) ) \wedge ( ( (0,c) \in a) \wedge (\forall i \in y, \forall c' \in S, \forall c' ' \in S, ( ( (i,c') \in a) \wedge ( (i \cup \{ i \},c' ') \in a) ) \to ( (c',c' ') \in f) ) )};であり、確かに[[量化の有界な>述語論理#bounded]][[論理式>述語論理#substitution]]をなします。
*2 &mathjax{\Phi};に対して[[数学的帰納法>コラム 数学的帰納法#induction]]を使っただけではないか、と思うかもしれませんが、少なくとも[[Encyclopedia of &mathjax{P};-adic Numbers>FrontPage]]における[[数学的帰納法>コラム 数学的帰納法#induction]]に関してはその考えは誤りです。&mathjax{\Phi};を論理式で書くと&mathjax{\exists a, ( (a \subset y \times X) \wedge (\forall i \in y, \exists ! x \in X, (i,x) \in a) ) \wedge ( (\forall x \in S, \exists i \in y, (i,x) \in a) \wedge ( ( (0,c) \in a) \wedge (\forall i \in y, \forall c' \in S, \forall c' ' \in S, ( ( (i,c') \in a) \wedge ( (i \cup \{ i \},c' ') \in a) ) \to ( (c',c' ') \in f) ) ) )};となってしまい、これは&mathjax{a};に関する量化が有界ではありません。従って、この論理式に対しては[[数学的帰納法>コラム 数学的帰納法#induction]]を直接適用することが出来ません。だからこそ、一旦[[量化の有界な>述語論理#bounded]][[論理式>述語論理#substitution]]&mathjax{\Psi(y)};に置き換えるか、もしくはより広い状況で適用可能な別の「数学的帰納法」を証明する必要があります。
*3 このように点列の点列や写像に値を持つクラス関数を作り、2つの添字に同じ値を代入して1つの点列や写像を構成する操作を対角線論法と呼びます。[[ラッセルの背理>等号の定義#russell]]の証明もクラス関数を用いてほぼ等価な書き換えをすれば、同じ論法になります。