2005/11/30 志村先生

# 原始帰納関数の話をするには、色々と準備が必要

[原始帰納関数の例]
	# 全部定義に戻ってやると大変なので、よく利用する原始帰納関数の作成方法をまとめておく

この後、次の事実をしばしば利用する。	# これがないと、後々、面倒くさい

	# 以前やった、「場合分け」による定義

		g_1 (x_1,..,x_n),..,g_k(x_1,..,x_n),g_{k+1}(x_1,..,x_n),
		h_1 (x_1,..,x_n),..,h_k(x_1,..,x_n)
	が原始帰納的ならば

				  g_1(x_1,..,x_n) ( h_1(x_1,..,x_n) = 0 の時 )
		f(x_1,..,x_n) = { g_2(x_1,..,x_n) ( h_1(x_1,..,x_n) \ne 0, h_2(x_1,..,x_n) = 0 の時 )
				   .....
				  g_k(x_1,..,x_n) ( h_i \ne 0 (i<k), h_k = 0 の時 )
				  g_{k+1}(x_1,..,x_n) ( h_i \ne 0 (i<=k) )

		# 前の条件が成立しなければ、次の場合を考える ( case 文に相当 )
		## 特に、h_i が同時に 0 にならない場合を良く考える

	# これまでやった関数で、上記の事実を利用したもの

		x+y
		xy
		pred(x)
			pred(0)=0
			pred(x')=x
		sg(x)
			sg(0)=0
			sg(x')=1
		\bar{sg}(x)
			\bar{sg}(0)=1
			\bar{sg}(x')=0
		f(y,x_1,..,x_n) が原始帰納的な時 ( 部分帰納法 )
			\sum{y<x} f(y,x_1,..,x_n)
			\prod{y<x} f(y,x_1,..,x_n)
		# この位しかしていない

		## +, ・があるので、-, / も考えたい
		## 我々は自然数しか扱っていないので、「本物」の -, / は定義できない
		### 限定した -, / を作る
			x \'- y = { x - y ( x >= y )
				  0     ( x < y )
			def
				x \'- 0 = x
				x \'- y = pred(x \'- y)
		# これを利用すると、大小関係が定義できる
			x > y <=> sg(x \'- y) = 1

			# このような関係で、大小関係を定義すると、例えば、推移律などは、帰納法を利用して、証明できる
			## x > y, y > z = x > z
			# 等号付の不等式は、「姑息な手」を使って次のように定義できる
				x >= y <=> sg(x'-1)
			## ここでの「姑息さ」は、「自然数しか扱わない」という立場から出る。( これは、今後もよく利用する )

		|x-y| = (x\'-y)+(y\'-x)
			# 一方が 0 になることに注意

		x = y <=> |x-y| = 0

		# 引き算ができたら次は、割り算

			x を y で割った商が q
			             余りが r
		の時
			x/y = q
			rem(x,y)=r
		とする。
			# 0 で割る場合を考える必要があることに注意
			## 0 は特別扱いしよう..

			rem(0,y)=0

					rem(x,y)+1	( rem(x,y) + 1 \ne y )
			rem(x',y)= {
					0		( rem(x,y) + 1 = y )

			0/y = 0

				 x/y	( rem(x,y)+1 \ne y )
			x'/y = {
				 x/y+1	( rem(x,y)+1 = y )

		# 本当は、これが、「割り算」や「余り」の性質を満すことを証明する必要があるが、それを始めると大変なので、ここではやらない。

		x|y ( x が y を割切れる ) <=> rem(y,x)=0

		prime(x) <=> x が素数
			 <=> \forall y < x [ y|x => y = 1 ] ∧ x > 1

		# 2 から x - 1 までの余りを全て掛け算して、その結果が 0 でないことを示せばよい。

		## もっと、一般に、上記の条件を考えれば、それから、原始帰納関数が作れる
		### [述語と関数の関係] ( 原始帰納的述語 )
		### not
		###	P(x_1,..,x_n) <=> f(x_1,..,x_n) = 0
		###	\not P(x_1,..,x_n) <=> \bar{sig}(f(x_1,..,x_n)) = 0
		### and
		###	( P <=> f = 0, Q <=> g = 0 ) => ( P and Q <=> f + g = 0 )
		### \forall
		###	\sum

		# 以上の議論から..

			prime(x) を原始帰納述語とするような関数 f が存在する

==
		# 「n 番目の素数」を求める関数 pr(n) を作ることを考える

			pr(n) = n 番目の素数
				pr(0) = 2
				pr(1) = 3
				pr(2) = 5
				..

		# これを定義するには、ちょっと準備 (n! の定義) が必要

				1		(x=0)
			x! = {
				x (x-1)!	(other)

		# 次のような素数に関する性質を利用する

		(Euclid)
			x と x! + 2 の間に素数が存在する
			# Euclid はこの性質を利用して、素数が無限にあることを証明

		proof)	
			x! + 1 は、x 以下の素数では割切れない
			従って x! + 1 の素因数 p は
				x < p かつ p <= x! + 1
			を満す。

		# これらの性質より、次のように pr が定義できる

		pr(0)=2
		pr(x') = \mu y          ( pr(x)<y ∧ prime(y) )
			y < pr(x)!+2

			# \mu y P(y) というのは、P(y) となるような y の中で最小なものを意味する。

			## \mu を実現するには、「テクニック」が必要

			f(x) を満す x の最小の x を知りたい
				g(x) = \PI_{y<x} f(x)
			を考えると
				f(n) = 0 => g(x) = 0 ( x>n )
					# n の所で 0 なので、それ以降は、0 になる
			となる。

			# これに工夫を加えて、次のような関数を考える

				h(x) = sg(g(x))

			これは、先頭から 1 が続き、f(x)=0 となる所から先は 0 になる
				よって、f(x)=0 となる場所を、1, 0 の並びで表現できる

			\mu' y (f(y)) = \sum{y<x} h(y)
			y<x

			x	0 1 2 3 4 5 6 7 8 9 
			h(x)	1 1 1 1 1 0 0 0 0 0 <= f(x) が x=5 の時初めて
			\mu' y	0 1 2 3 4 5 5 5 5 5
					  ^^^^^^^^^ <= 定常状態になったら求める数

			# 十分に、大きな x を与えれば、いつかは f(x)=0 となる、
			# すなわち、\mu y が見付かるということ意味する
			## 逆に、x が大きくないと、この \mu' では、「最小の数」とはいえない。
			## そこで、 \bar{sg}(h(x)) を追加する

			\mu y (f(y)) = \sum{y<x} h(y) ・ \bar{sg}(h(x))
			y<x

					 n ( n が y < x の範囲で f(y)=0 を満す最小の y の時 )
			\mu y (f(y)) = {
			y<x		 0 ( f(0)=0 か y < x の範囲では f(y)\ne 0 )

				# この \mu が限定最小作用素

		素数を求める pr で利用した \mu は実は、本質的な機能を持つ
			pr では、\mu の下にある y < pr(x)!+2 という条件が重要
				\mu は、直観的には
					「小さい方から順番に探す」
				という帰納法。
				ただし、ここで、上の制限は、
					「存在しない場合も、探すことが終る」
				ことを保証している。
					# 保証がなければ、0 が返る事になる
				素数の場合は、
					「上記の制限内に存在することが保証されている」
				ので、きちんと定義できる
					「存在が保証されれば \mu は強力」

	[Coding]
		自然趨の有限列の coding (次の対応を考える)
			1, 3, 2, 2 |--> 2^{1+1} 3^{3+1} 5^{2+1} 7^{2+1}
			2, 0, 1    |--> 2^{2+1} 3^{0+1} 5^{1+1}
			3          |--> 2^{3+1}
			空列        |--> 1

		この対応は、素因数分解の一意性により、右の数から左の有限列が復元できる
			この対応は、単写
			# ただし、全射ではない ( 例 2^4 5^2 は対応する列が存在しない )
			## ただし、特定の数が、このような数列の像になっているか ( つまり、数列を表現している数かどうか [ 素因数分解した時に、ギャップがなければよい ] ) は解る。

		像になっているための条件は、原始帰納的
			x の素因数に現れない最小の素数を考える
			g(x) =	\mu y ( \not y|x ∧ prime(y) ) 
				y<x!+2
		# 連続している場合、この y より大きな素数では x を割れない
		# 連続していない場合は、この y の後に、x を割ることができる素数がある

		f(x) =	\mu y (prime(y) ∧ y|x ∧ y > g(x))
			y<x+1			

		とすると、
			f(x) =  0 <=> 有限列の Code
			     >  0 <=> code でない

		# ここらへんは、全然、本質的ではない詳細な内容

		## 実際、自然数列の Coding の仕組は他にも色々あるがゲー
                ## デルは、数学者だったので、できるだけ数学的な性質だ
                ## けで定義しようとした。その結果として、詳細が奇妙に
                ## なっている

	自然数列 1, 0, 3 の code を ( 1, 0, 3 ) で表すことにする
	「自然数 x が有限列の code である」を seq(x) で表す

	lh(x) = \mu y    ( \not pr(y) | x )
		y < x+1

		x = ( 1, 0, 3 ) の時
		  = 2^2 3^1 5^4
		  = pr(0)^2 pr(1)^1 pr(2)^4

		よって、\not pr(3) | x つまり、lh(x)=3 となる。
			# これは、x が code の時には、その「自然数列の長さ」を表す

		lh(x) は x を code とするとき有限列の長さとなる
			# x が code ない時には、途中に穴があり、そこに落るので長さにならない

	(x)_n : x を素因数分解したときの pr(n) の巾 - 1

		(x)_n =	\mu k    \not pr(n)^{k+2} | x
			k < x+1

		とすれば、seq(x), n < lh(x) の時、(x)_n は code の有限列の n 番目の成分		

		# これによって、code を分解するための仕組が、原始帰納関数で可能になった


	# 最後に文字列の結合を考える
	## 列の結合は、簡単だが、それを、ゲーデルの coding を利用しようといする、大変なことになる。

	数列の結合

		2, 1, 4 * 3, 0 => 2, 1, 4, 3, 0

	を Coding の世界で考えると

		2^3 3^2 5^4 * 2^4 3^1 => 2^3 3^2 7^4 11^1

	計算する必要がある

		y = pr(0)^a_0 pr(1)^a_1 .. pr(k-1)^{a_{k-1}}
			↓
		y'= pr(0+lh(x))^a_0 pr(1+lh(x))^a_1 .. pr(k-1+lh(x))^{a_{k-1}}

		とするような y -> y' ができれば、 x * y = x y' となる

		y' = \PI        pr(k+lh(x))^{ (y)_k + 1 }
		     k < lh(y)

	# 自然列を自然数の中に埋め込むという作業をしている。
	# 埋め込み方が「素因数分解」という「奇妙な方法」を利用しているので、本来の「自然数列」という世界で、「自然な作業」が coding された先では「不自然な形」になってしまっている。
	## 「重要な点」は、「どうやったらできるか」ではなく ( どんな方法でも、構わないのだがとにかく ) その「埋め込みが可能」ということ