漸化式の定義

変項\( y \)を含む論理式\( \Phi \)を次のように定義し、\( \forall n \in \mathbb{N}, \Phi(n) \)を示す：ただ１つのクラス関数\( (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) \)を次のように定義する：ただ１つの集合の組\( (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 \)の空列はただ１つであるので、\( \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 \)とする。仮定より、ただ１つのクラス関数\( (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) \)」を満たすただ１つのクラス関数クラス\( (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}} \)は２項間漸化式\( (c,f) \)を満たすような\( X \)の点列である。

\( X \)の点列\( (b_i)_{i \in \mathbb{N}} \)が２項間漸化式\( (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}} \)である。