リンク 家庭教師(数学)中沢
メール(中沢宛)ペアノ算術の辞書(1)(2021.4.11)(pdfファイル)
ペアノ算術の辞書5(2)(2021.3.31 記)(pdfファイル)
ペアノ算術の辞書と文の真偽参照4(2021.3.19 記)(pdfファイル)
概要;ΔはＰＡのΔ0文集合全体。Ｎを自然数の全体とする。この時,Ｎ→Δなる(再帰的)同型写像Ｃが存在する。(Ｎ→Ｎ)を自然数から自然数への関数全体とする。ここで扱う冠頭標準形とは例えば,無限命題関数∧ｖi(i=0〜∞)において各命題変数ｖiがΔの勝手な要素をとるとし,その要素の割り当てはf∈(Ｎ→Ｎ)ｖi=Ｃ(f(i))としたものを∀x(f(x))で表す。従って,対象とする冠頭標準形は連続無限個ある。一般にΠn,Σn文も同様に定義される。このように定義された文に対する真偽値を議論する。
§1.導入 ここでは,一般に集合Ａ,Ｂに対し(Ａ→Ｂ)によって集合ＡからＢへの関数全体を表す。集合(Ｎ→Ｎ)と実数の区間Ｉ={x|0＜x≦1}は,次のようにして同一視する。ｆ∈(Ｎ→Ｎ)に対し,ｇ(0)=f(0),g(n＋1)=g(n)＋f(n＋1)＋1とｇを定義する。更にｍ=g(n)を満たすｎ全体に対しｈ(ｍ)=1,それ以外のｋについてh(k)=0と無限2進数列を定義し,これを0.h(0)h(1)……と無限2進小数で表すとこれはＩに属する実数。この同型写像をＬ0;(Ｎ→Ｎ)→Ｉとする。(この同型写像は急増加関数が0の近榜に写される)逆写像をＲ0で表す。また(Ｎ→Ｉ)からＩへの同型写像をＬ,逆写像をＲで表す。但し,Ｌは次のように定義される。ｆ∈(Ｎ→Ｉ)とするとf(0)=0.d(0,0)d(0,1)……,f(n)=0.d(n,0)d(n,1)……,…と並べ,これに0.d(0,0)d(1,0)d(0,1),d(2,0)d(1,1)d(0,2)……なる無限2進小数を対応させる。(カントルの対関数の順序に従う)ｎ変数述語をＰ(Ｘ1,…,Ｘn)=Ｃ(f(P(Ｘ1,…,Ｘn)))と定義し,(ここにPは対関数)(f(Ｘ1,…,Ｘn))で表す。これらの述語はΠn,Σn文の真偽値を考える上で便利な範囲でしか用いない。 ｎ変数関数の2通りの扱い方について述べる。同型(Ｎ→(Ｎ→Ｎ))→(Ｎ×Ｎ→Ｎ)Pは同型Ｎ×Ｎ→Ｎを与えるから右辺の要素はｆ∈(Ｎ→Ｎ)を用いてｆ(P(x,y))と表せる。ｘ∈Ｎに対し,ｇ(x)=ｆ(P(x,y))とする。ｘを固定するとき,ｆ(P(x,y))らｙをｆ(P(x,y)に写す(Ｎ→Ｎ)の要素と見なすとｇ∈(Ｎ→(Ｎ→Ｎ))となる。逆に,ｇ∈(Ｎ→(Ｎ→Ｎ))に対し,ｇ(x)∈(Ｎ→Ｎ)よりｇ(x);ｙ→g(x)(y)なる関数を定義する。2変数関数g(x)(y)=f(P(x,y))があるｆ∈(Ｎ→Ｎ)に対して成り立つ。更に,同型(Ｎ→(Ｎ→Ｎ))=(Ｎ→Ｉ)=Ｉがあるから,ｒ∈Ｉに対してＲ(r)∈(Ｎ→Ｉ)。Ｒ(r)(x)∈Ｉ。Ｒ0(Ｒ(r)(x))∈(Ｎ→Ｎ)より2変数関数Ｒ0(Ｒ(r)(x))(y)を考えても良い。一般に同型(Ｎ×…×Ｎ→Ｎ)→(Ｎ×(Ｎ×(Ｎ×(…×…×(Ｎ×Ｎ)…))))→(Ｎ→(Ｎ→(Ｎ→…)))→(Ｎ→Ｉ)→Ｉ(最初の同型は対関数の反復の仕方を指示する)よりｎ変数関数は実数ｒ∈Ｉに対してｎ変数関数Ｒ0(…Ｒ(Ｒ(r)(Ｘ1))(Ｘ2))…(Ｘn−1))(Ｘn)を対応させるのが同型写像Ｉ→(Ｎ×…×Ｎ→Ｎ)である。我々の議論では帰納的に諸性質をＩの要素に帰着させる方向で進めるので同型(Ｎ×…×Ｎ→Ｎ)=(Ｎ→(Ｎ→(Ｎ→…)))=Ｉにおいて右辺を用いる。先ず,Π1文∀x(f(x))についての真偽値を考える。(ここにfは(Ｎ→Ｎ)のある要素。)ＴΔはΔの真なる要素全体,ＦΔはΔの偽なる要素全体とする。同型写像Ｃ;Ｎ→Δで,(Ｎの無限部分集合Ｎ0)→ＴΔなる同型写像をＣ0。(Ｎ−Ｎ0=無限部分集合Ｎ1)→ＦΔなる同型写像をとる。f∈(Ｎ→Ｎ)としてIｍｆ⊂Ｎ0なるものについてＬ0(f)全体をＩ(1,0),f∈(Ｎ→Ｎ)としてIｍｆ⊂Ｎ1なるものについてＬ0(f)全体をＩ(1,1),それら以外のf∈(Ｎ→Ｎ)についてＬ0(f)全体をＩ(1,2)とする。同型α;Ｎ→Ｎ0よりｆ∈(Ｎ→Ｎ)にαoｆ∈(Ｎ→Ｎ0)なる同型写像α;ｆ→αoｆが存在する。従って(Ｎ→Ｎ)→(Ｎ→Ｎ0)=Ｉ→Ｉ(1,0)なる同型写像α~が存在する。同様にＩ→(Ｎ→Ｎ1)=Ｉ→Ｉ(1,1)なる同型写像β~も存在する。r∈Ｉ(1,0)=Ｉ(1)についてｆ=Ｒ0(r)〓∀x(f(x))は真。r∈Ｉ(1,1)=ＲＪ(1)についてｆ=Ｒ0(r)〓∃x(f(x))は偽。ｒ∈Ｉ(1,0)∪Ｉ(1,2)=Ｊ(1)についてｆ=Ｒ0(r)〓∃x(f(x))は真。ｒ∈Ｉ(1,1)∪Ｉ(1,2)=ＲＩ(1)についてｆ=Ｒ0(r)〓∀x(f(x))は偽である。Ｊ(1)はＢ(1,k)をｘ＜kならf(x)∈Ｎ1,f(k)∈Ｎ0,ｘ＞ｋならf(x)∈Ｎなる関数全体であると定義すると各自然数ｋについて,ｆ∈(Ｎ→Ｎ)を自然数の可算無限順序数列,即ち(f(0),f(1),……)で表した時,これに(βof(0),…,βof(k−1),αof(k),f(k＋1),……)を対応させる変換をγ(k)とした時,Ｂ(1,k)はγ(k)oｆ∈(Ｎ→Ｎ)で得られる。ｒ∈Ｉに対してＲ(r)=ｆ(∈(Ｎ→Ｎ)(βof(0),…,βof(k−1),αof(k),f(k＋1),……))なる関数をＩに移す変換をΓ(k);r→γ(k)oＲ(r)とするとＩmΓ(k)=Γ(k)(Ｉ)=Ｌ0(Ｂ(1,k))。明らかにｋ≠ｍの時,Γ(k)(Ｉ)∩Γ(ｍ)(Ｉ)=φ。Ｊ(1)=Γ(0)(Ｉ)∪Γ(1)(Ｉ)∪…(直和)),各自然数ｋについて同型Ｉ→Γ(k)(Ｉ)が存在する。特に,Ｂ(1,∞)をｆ∈(Ｎ→Ｎ)に対してβoｆ全体と定義する。するとΓ(∞)(Ｉ)=Ｉ(1,1)。ゆえにＩ=∪Γ(k)(Ｉ)(ｋは0から∞まで)を得る。各ｆ∈(Ｎ→Ｎ)に対し,δ(k);γ(k)oｆ→γ(k＋1)oｆ,特に,δ(∞);βoｆ→γ(0)oｆと定義するとこれから同型Ｉ→Ｊ(1)を得る。ＲＩ(1)はＲＢ(1,k)をｘ＜kならf(x)∈Ｎ0,f(k)∈Ｎ1,ｘ＞ｋならf(x)∈Ｎなる関数全体,ＲＢ(1,∞)をｆ∈(Ｎ→Ｎ)に対して,αoｆ全体と定義するとＪ(1)と同様に同型Ｉ→ＲＩ(1)を得る。同型α;Ｎ→Ｎ0(=Ｉ(1))→Ｉ,Ｊ(1)→Ｉ,ＲＩ(1)→Ｉ,ＲＪ(1)→Ｉから同型写像Ｆ(1);Ｉ→Ｉ(1),Ｇ(1);Ｉ→Ｊ(1),ＲＦ(1);Ｉ→ＲＩ(1),ＲＧ(1);Ｉ→ＲＪ(1)とする。
【定理1】ｆ∈(Ｎ→Ｎ)の時,Ｌ0(f)=ｒ∈Ｉに対して,Ｆ(1)(x)=ｒ,Ｇ(1)(x)=ｒ,ＲＦ(1)(x)=ｒ,ＲＧ(1)(x)=ｒがｘ∈Ｉに解を持つか否かで∀x(f(x)),∃x(f(x))の真偽が定まる。別の言い方をすればｒにＦ(1),Ｇ(1),ＲＦ(1),ＲＧ(1)の逆写像を施したとき,どれでＩに戻るか分かれば,∀x(f(x)),∃x(f(x))の真偽が定まる。Π1文(Σ1文)はｆ∈(Ｎ→Ｎ)で決まるから,真なるΠ1文を定義するｆ全体をＴΠ1,偽なるΠ1文を定義するｆ全体をＦΠ1,真なるΣ1文を定義するｆ全体をＴΣ1,偽なるΣ1文を定義するｆ全体をＦΣ1と表す。これらはＬ0(ＴΠ1)=Ｉ(1),Ｌ0(ＴΣ1)=Ｉ(1,0)∪Ｉ(1,2)=Ｊ(1),Ｌ0(ＦΠ1)=Ｉ(1,1)∪Ｉ(1,2)=ＲＩ(1),Ｌ0(ＦΣ1)= Ｉ(1,2)=ＲＪ(1)で特徴づけられる。なお,ｒ∈Ｉは(Ｎ→Ｎ),(Ｎ→Ｉ)においていくつの変数の関数を表すか判然としないので以降ｎ変数関数の像である場合,(n,r)∈Ｎ×Ｉで表す事にする。次のセクションで,ｎ(≧2)変数に進む。
§2.一般の場合 上と同様の結果を帰納法で示すが,1変数の場合だけ関数ｆ∈(Ｎ→Ｎ)=Ｉだが2変数関数は同型(Ｎ→(Ｎ→Ｎ))→(Ｎ→Ｉ)を利用してｆ∈(Ｎ→Ｉ)で進める,一般にｎ(≧2)変数ではそうなる所が1変数の場合との相違点であるから2変数の場合を示せば,帰納法で一般の場合を示せる事は明らか。§1.での同型写像Ｌ;(Ｎ→Ｉ)→Ｉと逆の同型Ｒ;Ｉ→(Ｎ→Ｉ)。ｎ変数述語Ｐ(Ｘ1,…,Ｘn)はｎ変数関数ｆ(Ｘ1,…,Ｘn)によりＣ(ｆ(Ｘ1,…,Ｘn))と定義される。但し,ｎ変数関数ｆは上の実数(n,r)∈Ｎ×Ｉに対してｎ変数関数Ｒ0(…Ｒ(Ｒ(r)(Ｘ1))(Ｘ2))…(Ｘn−1))(Ｘn)を得る事を思い出しておく。 先ず,Π2文を定義する。(2,r)∈Ｎ×Ｉにより定義する。ｘに関する1変数Σ1述語∃yＣ(Ｒ0(Ｒ(r)(x))(y))よりΠ2文∀x∃yＣ(Ｒ0(Ｒ(r)(x))(y))を定義する。同様にΣ2文は∃x∀yＣ(Ｒ0(Ｒ(r)(x))(y))。 次にＴΠ2,ＦΠ2,ＴΣ2,ＦΣ2を定義する。 粗っぽく言えば,真なるΠ2文は各自然数ｘに対し,真なるΣ1文を(1,r(x))∈Ｎ×Ｉから関数Ｒ(r(x))∈(Ｎ→Ｎ)を経由して,各自然数ｘに対し,真なるΣ1文∃yＣ(Ｒ(r(x))(y))を対応させて得られるΣ1述語∃yＰ(x,y)から∀x∃yＰ(x,y)〓∀x∃yＣ(Ｒ(r(x))(y))で真なるΠ2文を定義する。 これを我々の定義に沿うように述べ直す。先ず(1,p)∈Ｎ×Ｉとし,∃yＣ(Ｒ0(p)(y))∈ＴΣ1。次に各ｘに対し,上のようなp∈Ｉを対応させる関数ｆ∈(Ｎ→Ｉ)を導く(2,r)∈Ｎ×Ｉを取る。Ｒ(r)=ｆ。定義より∀x∃yＣ(Ｒ0(Ｒ(r)(x))(y))は真なるΠ2文。ここでＲ(r)∈(Ｎ→Ｉ)。任意の自然数ｘについてＲ(r)(x)∈ＴΣ1(Ｃは省略している)。このようなｒ全体=Ｌ(ＴΠ2)=Ｉ(2)。Ｒ(r)∈Ｎ→ＴΣ1⊂Ｎ→(Ｎ→Ｎ)=Ｎ→Ｉ。Ｌ0(ＴΣ1)=Ｊ(1)。§1より,同型Ｇ(1);Ｉ→Ｊ(1)が存在するから,同型(Ｎ→Ｉ)→(Ｎ→Ｊ(1))が存在し,これから同型Ｆ(2);Ｉ→Ｉ(2)が存在し,(2,r)∈Ｎ×Ｉに対し,Ｆ(2)(x)=ｒが解ｘ∈Ｉが存在〓∀x∃yＲ0(Ｒ(r)(x))(y)は真。(Ｒ(r)=ｆ∈(Ｎ→(Ｎ→Ｎ))=(Ｎ×Ｎ→Ｎ)とすると∀x∃y(ｆ)が真)。 次に真なるΣ2文を定義する。(2,r)∈Ｎ×Ｉに対し,Ｒ(r)=ｆ∈(Ｎ→Ｉ)とする。§1同様Ｂ(2,k)をｘ＜kならf(x)∈ＦΠ1,,f(k)∈ＴΠ1,ｘ＞ｋならf(x)∈Ｉ→(Ｎ→Ｉ)なる関数全体,Ｂ(2,∞)を任意の自然数ｎに対してｆ(n)∈ＦΠ1と定義する。ｆをＩの要素の可算無限順序列,即ち(f(0),f(1),……)で表した時,これに(ＲＪ(1)of(0),…,ＲＪ(1)of(k−1),Ｆ(1)of(k),f(k＋1),……)を対応させる変換をδ(k)とした時,Ｂ(1,k)はδ(k)∈(Ｉ→Ｉ)で得られる。Ｉ→Ｌ(Ｂ(1,k))。また,δ(k)を(Ｎ→Ｉ)=Ｉから自身への同型写像と見なすと,明らかにｋ≠ｍの時,δ(k)Ｉ∩δ(ｍ)Ｉ=φ。Ｊ(2)=Γ(0)Ｉ∪Γ(1)Ｉ∪…(直和)),各自然数ｋについて同型Ｉ→δ(k)Ｉが存在する。§1.同様に,同型Ｇ(2);Ｉ→Ｊ(2)=Ｌ(ＴΣ2)を得る。同様にＲＦ(2);Ｉ→ＲＩ(2)=Ｌ(ＦΠ2),ＲＧ(2);Ｉ→ＲＪ(2)=Ｌ(ＦΣ2)が存在する。 同型写像Ｆ(2);Ｉ→Ｉ(2),Ｇ(2);Ｉ→Ｊ(2),ＲＦ(2);Ｉ→ＲＩ(2),ＲＧ(2);Ｉ→ＲＪ(2)が存在する。
【定理2】ｆ∈(Ｎ→Ｉ)の時,Ｌ(f)=ｒ∈Ｉ=(Ｎ→Ｉ)=(Ｎ→(Ｎ→Ｎ))=(Ｎ×Ｎ→Ｎ)に対して,Ｆ(2)(x)=ｒ,Ｇ(2)(x)=ｒ,ＲＦ(2)(x)=ｒ,ＲＧ(2)(x)=ｒがｘ∈Ｉに解を持つか否かで∀x∃y(f(x,y)),∃x∀y(f(x,y))の真偽が定まる。定理1,2より帰納法においてｎ−1を仮定し,ｎを示すことは容易。よって次の定理にまとめておく。
【定理3】ｎ≧2とする。ｎ=1の場合は定理1参照。 同型写像Ｆ(n);Ｉ→Ｉ(n),Ｇ(n);Ｉ→Ｊ(n),ＲＦ(n);Ｉ→ＲＩ(n),ＲＧ(n);Ｉ→ＲＪ(n)が存在する。 (n,r)∈Ｎ×Ｉの時,Ｆ(n)(x)=ｒ,Ｇ(n)(x)=ｒ,ＲＦ(n)(x)=ｒ,ＲＧ(n)(x)=ｒがｘ∈Ｉに解を持つか否かでｒから復元された母式(matrix)(f(x,…))を持つΠn文∀x…(f(x,…)),Σn文∃x…(f(x,…))の真偽が定まる。別の言い方をすれば,ｒにＦ(n),Ｇ(n),ＲＦ(n),ＲＧ(n)の逆写像を施したとき,どれでＩに戻るか調べれば,Πn文∀x…(f(x,…)),Σn文∃x…(f(x,…))の真偽が定まる。 また,真なるΠn文全体をＴΠn,偽なるΠn文を定義するｆ全体をＦΠn,真なるΣn文を定義するｆ全体をＴΣn,偽なるΣn文を定義するｆ全体をＦΣnと表す。これらはＬ(ＴΠn)=Ｉ(n),Ｌ(ＴΣn)=Ｊ(n),Ｌ(ＦΠn)=ＲＩ(n),Ｌ(ＦΣn)=ＲＪ(n)で特徴づけられる。
【系】ＰＡの冠頭標準形の述語は再帰的関数ｆで(f)と表され,上の標準形に含まれるから,上の定理はＰＡの冠頭標準形に対しても有効である。
【注意】上の議論は関数集合としてフルセット(Ｎ→Ｎ)=Ｉを取ったが関数集合として部分集合Ｎ→Ｎ=Ｎとして右辺から左辺への同型写像をＲとおくときＲ(Ｒ(i)(x))(y)=Ｒ(j)(P(x,y))が成立すればＩで行った議論がＮ及び(Ｎ→Ｎ)に移るだけで同様の結果が得られる。例えば,再帰的全域関数全体をインデックスする関数をＡ(n)とするときＡ(Ａ(i)(x))(y)=Ａ(j)(P(x,y))となるようなＡ(j)を無際限に加え続けて拡大したもの。Ａ再帰的全域関数の枚挙関数Ａ'さらにＡ'再帰的全域関数の枚挙関数…などである。
(議論)ｆ,ｇ∈(Ｎ→Ｎ)のときｆoｇ∈(Ｎ→Ｎ)でｆ,ｇ,特に,ｆoｇはＩの実数への同型写像で写されるが,Ｉでのfの像を(f)とおくと(ｆoｇ)は(f)(ｇ)なるＩの非可換な積を定義するが,何らかの積の性質を保存する射(Ｎ→Ｎ)→Ｉはあるか。同型Ｆ(n);Ｉ→Ｉ(n)において反復Ｆ(n)oＦ(n)o…(Ｉ(n))は不動点等を持つか。各同型Ｉ→Ｉ(n),Ｉ→Ｊ(n) を同相にする位相(Ｉからの誘導位相をＩ(n),Ｊ(n)ＲＩ(n),ＲＪ(n)に入れたとき)はどのようなものになるか。 多くの人々は特定の問題に関心を持つ。何かしら,結果を捻り出すには非計算不可能な仮定で集合論の主要な公理系と無矛盾なものから計算可能な結果を出すのだろうが,場合によっては,仮定そのものが記述不可能な場合もあり得る。
概要;ΔはＰＡのΔ0文集合全体。Ｎを自然数の全体とする。この時,Ｎ→Δなる(再帰的)同型写像Ｃが存在する。(Ｎ→Ｎ)を自然数から自然数への関数全体とする。ここで扱う冠頭標準形とは例えば,無限命題関数∧ｖi(i=0〜∞)において各命題変数ｖiがΔの勝手な要素をとるとし,その要素の割り当てはf∈(Ｎ→Ｎ)ｖi=Ｃ(f(i))としたものを∀x(f(x))で表す。一般にΠn,Σn文も同様に定義される。このように定義された文に対する真偽値を議論する。
§1.本文 ここでは,一般に集合Ａ,Ｂに対し(Ａ→Ｂ)によって集合ＡからＢへの関数全体を表す。集合(Ｎ→Ｎ)と実数の区間Ｉ={x|0＜x≦1}は,次のようにして同一視する。ｆ∈(Ｎ→Ｎ)に対し,ｇ(0)=f(0),g(n＋1)=g(n)＋f(n＋1)＋1とｇを定義する。更にｍ=g(n)を満たすｎ全体に対しｈ(ｍ)=1,それ以外のｋについてh(k)=0と無限2進数列を定義し,これを0.h(0)h(1)……と無限2進小数で表すとこれはＩに属する実数。ここで同型写像Ｌ0;(Ｎ→Ｎ)→Ｉ,逆写像をＲ0で表す。また(Ｎ→Ｉ)からＩへの同型写像をＬ,逆写像をＲで表す。Ｌはｆ∈(Ｎ→Ｉ)とするとf(0)=0.d(0,0)d(0,1)……,f(n)=0.d(n,0)d(n,1)……,…と並べ,これに0.d(0,0)d(0,1)d(1,0),d(0,2)d(1,1)d(2,0)……なる無限2進小数を対応させる。ｎ変数述語をＰ(Ｘ1,…,Ｘn)=Ｃ(f(P(Ｘ1,…,Ｘn)))と定義し,(ここにPは対関数)(f(Ｘ1,…,Ｘn))で表す。これらの述語はΠn,Σn文の真偽値を考える上で便利な範囲でしか用いない。 ｎ変数関数の2通りの扱い方について述べる。同型(Ｎ→(Ｎ→Ｎ))=(Ｎ×Ｎ→Ｎ)Pは同型Ｎ×Ｎ→Ｎを与えるから右辺の要素はｆ∈(Ｎ→Ｎ)を用いてｆ(P(x,y))と表せる。ｘ∈Ｎに対し,ｇ(x)=ｆ(P(x,y))とする。ｘを固定するとき,ｆ(P(x,y))らｙをｆ(P(x,y)に写す(Ｎ→Ｎ)の要素と見なすとｇ∈(Ｎ→(Ｎ→Ｎ))となる。逆に,ｇ∈(Ｎ→(Ｎ→Ｎ))に対し,ｇ(x)∈(Ｎ→Ｎ)よりｇ(x);ｙ→g(x)(y)なる関数を定義する。2変数関数g(x)(y)=f(P(x,y))があるｆ∈(Ｎ→Ｎ)に対して成り立つ。更に,同型(Ｎ→(Ｎ→Ｎ))=(Ｎ→Ｉ)=Ｉがあるから,ｒ∈Ｉに対してＲ(r)∈(Ｎ→Ｉ)。Ｒ(r)(x)∈Ｉ。Ｒ0(Ｒ(r)(x))∈(Ｎ→Ｎ)より2変数関数Ｒ0(Ｒ(r)(x))(y)を考えても良い。一般に同型(Ｎ×…×Ｎ→Ｎ)=(Ｎ→(Ｎ→(Ｎ→…)))=(Ｎ→Ｉ)=Ｉよりｎ変数関数は実数ｒ∈Ｉに対してｎ変数関数Ｒ0(…Ｒ(Ｒ(r)(Ｘn))(Ｘn−1))…(Ｘ2))(Ｘ1)を対応させるのが同型Ｉ=(Ｎ×…×Ｎ→Ｎ)である。我々の議論は帰納的に諸性質をＩの要素に帰着させる方向で進むので同型(Ｎ×…×Ｎ→Ｎ)=(Ｎ→(Ｎ→(Ｎ→…)))=Ｉを頻繁に用いる。先ず,Π1文∀x(f(x))についての真偽値を考える。(ここにfは(Ｎ→Ｎ)のある要素。)ＴΔはΔの真なる要素全体,ＦΔはΔの偽なる要素全体とする。同型写像Ｃ;Ｎ→Δで偶数全体Ｎ0がＴΔへの同型写像。奇数全体Ｎ1がＦΔへの同型写像となるものをとる。f∈(Ｎ→Ｎ)としてIｍｆ⊂Ｎ0なるものについてＬ0(f)全体をＩ(1,0),f∈(Ｎ→Ｎ)としてIｍｆ⊂Ｎ1なるものについてＬ0(f)全体をＩ(1,1),それら以外のf∈(Ｎ→Ｎ)についてＬ0(f)全体をＩ(1,2)とする。r∈Ｉ(1,0)=Ｉ(1)についてｆ=Ｒ0(r)〓∀x(f(x))は真。ｒ∈Ｉ(1,0)∪Ｉ(1,2)=Ｊ(1)についてｆ=Ｒ0(r)〓∃x(f(x))は真。である。Ｉ,Ｉ(1),Ｊ(1)はいずれも連続濃度。Ｉ(1)は明らか,Ｊ(1)はＢ(k)をｘ＜kならf(x)∈Ｎ1,f(k)∈Ｎ0,ｘ＞ｋならf(x)∈Ｎなる関数全体と定義すると各自然数ｋについてＢ(k)は連続濃度。Ｊ(1)はこれらＢ(k)全体の和集合だから連続濃度。ここでのＪ(1)=∪k＜ωＢ(k)はｎ≧2でもＪ(n)を同様に表せる。同型写像Ｆ(1);Ｉ→Ｉ(1),Ｇ(1);Ｉ→Ｊ(1)が存在する。ｒ∈Ｉに対して,Ｆ(1)(x)=ｒ,Ｇ(1)(x)=ｒがｘ∈Ｉに解を持つか否かで∀x(f(x)),∃x(f(x))の真偽が定まる。真なるΠ1文(Σ1文)はｆ∈(Ｎ→Ｎ)で決まるから,真なるΠ1文を定義するｆ全体をＴΠ1,真なるΣ1文を定義するｆ全体をＴΣ1と表す。これらはＬ0(ＴΠ1)=Ｉ(1),Ｌ0(ＴΣ1)=Ｉ(1;0)∪Ｉ(1;2)=Ｊ(1)で特徴づけられる。次に,ｎ(≧2)変数 に進む。帰納的に進めるからＬ(ＴΠn)=Ｉ(n)(⊂Ｉ),Ｌ(ＴΣn)=Ｊ(n)(⊂Ｉ)で特徴づけられ共に連続濃度と仮定する。但し,ｎ=1の時はＬはＬ0に置き換える。(Ｌは(Ｎ→Ｉ)からＩへの同型写像であった)ｎ変数述語Ｐ(Ｘ1,…,Ｘn)はｎ変数関数ｆ(Ｘ1,…,Ｘn)によりＣ(ｆ(Ｘ1,…,Ｘn))と定義される。但し,ｎ変数関数ｆは上の実数ｒ∈Ｉに対してｎ変数関数Ｒ0(…Ｒ(Ｒ(r)(Ｘn))(Ｘn−1))…(Ｘ2))(Ｘ1)で得る。Πn＋1文は勝手なｒ∈Ｉに対し,対応するＲ(r)=ｇ∈(Ｎ→Ｉ)からｒ(k)∈Ｉから得られるＲ(r(k))=ｆ(k)とおくときＸ0=ｋにΣn文∃Ｘ1ＱＸ2…ＱＸn(ｆ(k)(Ｘ1Ｘ2…Ｘn))(Ｑは∀または∃)を対応させるＸ0についてのΣn述語Ｐ(Ｘ0)=∃Ｘ1ＱＸ2…ＱＸn(ｆ(Ｘ0)(Ｘ1,Ｘ2,…,Ｘn))に対して∀Ｘ0Ｐ(Ｘ0)をΠn＋1文と定義する。Σｎ＋1文も同様に定義する。真なるΠn＋1文は各自然数Ｘ0について述語(ｆ(Ｘ0)(Ｘ1,Ｘ2,…,Ｘn))∈ＴΣnのとき,r∈Ｉ(n＋1;0)〓∀Ｘ(Ｒ(r)(Ｘ)∈Ｊ(n))。同様に真なるΣn＋1文はある自然数Ｘ0について述語(ｆ(Ｘ0)(Ｘ1,Ｘ2,…,Ｘn))∈ＴΠnのとき,即ち,r∈Ｊ(n＋1)〓∃Ｘ(Ｒ(r)(Ｘ)∈Ｉ(n)。Ｌ(ＴΠn＋1)=Ｉ(n＋1),Ｌ(ＴΣn＋1)=Ｊ(n＋1)は共に連続濃度。よって以上をまとめて次の定理を得る。
定理;Ｌ(ＴΠn)=Ｉ(n)(⊂Ｉ),Ｌ(ＴΣn)=Ｊ(n)(⊂Ｉ)で特徴づけられ共に連続濃度但し,ｎ=1の時はＬはＬ0に置き換える。(Ｌは(Ｎ→Ｉ)からＩへの同型写像,Ｌ0は(Ｎ→Ｎ)からＩへの同型写像)また濃度の対等から同型写像Ｆ(n);Ｉ→Ｉ(n),Ｇ(n);Ｉ→Ｊ(n)が存在し,ｒ∈Ｉに対して,Ｆ(n)(x)=ｒ(Ｇ(n)(x)=ｒ)がｘ∈Ｉに解を持つか否かでｆ(Ｘ1,…,Ｘn)=Ｒ0(…Ｒ(Ｒ(r)(Ｘn))(Ｘn−1))…(Ｘ2))(Ｘ1)とおくときΠn(Σn)文ＱＸ1…ＱＸn(f(Ｘ1,…,Ｘn))の真偽が定まる。
注意1;ＰＡの冠頭標準形の述語は再帰的関数ｆで(f)と表され,上の標準形に含まれるから,上の定理はＰＡの冠頭標準形に対しても有効である。
注意2;上の議論は関数集合としてフルセット(Ｎ→Ｎ)=Ｉを取ったが関数集合Ｎ→Ｎ=Ｎとして右辺から左辺への同型写像をＲとおくときＲ(Ｒ(i)(x))(y)=Ｒ(j)(P(x,y))が成立すればＩで行った議論がＮに移るだけで同様の結果が得られる。例えば,再帰的全域関数全体をインデックスする関数をＡ(n)とするときＡ(Ａ(i)(x))(y)=Ａ(j)(P(x,y))となるようなＡ(j)を無際限に加え続けて拡大したもの。もっと,端的に言えば,Ａ再帰的全域関数の枚挙関数Ａ'さらにＡ'再帰的全域関数の枚挙関数…などである。
(議論)上の定理の関数Ｆ,Ｇを連続関数に取れるか。
あるプログラムを実行したときいつか停止するか否か答えるルーチン(停止性判定ルーチン)があるとする。プログラムを入力し,YESかNOを返す。このルーチンがサブルーチンとして,普通のプログラムｅ(0)をパラメーターとしてＡ(0)(e(0))の形で呼び出して使えるプログラムｅ(1)を考える。このプログラムに対しても停止性判定ルーチンＡ(1)があり,Ａ(1)(e(1))で呼び出せるとする。 次にＡ(0),Ａ(1)をプログラムに含むプログラムｅ(2)に対する停止性判定ルーチンをＡ(2)(e(2))があるとする。同様に,一般にＡ(n)が有る計算システムのプログラムではＡ(k)タイプのサブルーチンがいつも呼び出せるとする。さて次に例えばＰＡ(ペアノ算術の公理的システム)の1変数の述語を考える。ＰＡの命題は原始再帰的述語Ｐ(x)が与えられたとき,有限時間で各自然数ｎに対してＰ(n)の真偽が普通のプログラムe(0)で分かる。しかし∀xＰ(x)(任意の自然数ｘに対してＰ(x)は真である)や∃xＰ(x)(ある自然数ｘについて真である)なる命題をチェックするには例えば∀xＰ(x)が真か偽か知りたければ,ある自然数ｎに対してＰ(n)が偽なら,そこで停止するプログラムを実行するとき,Ｐ(0),Ｐ(1),Ｐ(2),…とチェックして行く訳だがその実行がいつかは停止して∀xＰ(x)の反例が見つかり偽であると分かるが反例がない,つまり∀xＰ(x)が真なら,プログラムの実行は停止しないがいつまで待っていても停止するかどうかは分からない。そこで反例探索プログラムe(0)に対してサブルーチンＡ(0)(e(0))を用いると,停止性が判定できるから∀xＰ(x)や∃xＰ(x)の真偽が判定できる。∀x∃yＰ(x,y)(Π2文)や∃x∀yＰ(x,y)(Σ2文)だと前者なら,各自然数ｎに対して∃yＰ(n,y)をチェックして行き,これらが全て真なる事を知る必要があるからサブルーチンＡ(0)(e(0))を含むプログラムe(1)の実行の停止性判定が必要だからサブルーチンＡ(1)(e(1))を含むプログラムと実行が必要になる。∀x∃y∀zＰ(x,y,z)(Π3文)や∃x∀y∃zＰ(x,y,z)(Σ3文)ではさらにサブルーチンＡ(2)が必要。以下,同様。またＰ(0),Ｐ(1),…,Ｐ(n),…が全て証明可能なら∀xＰ(x)が証明されると言う無限論理の規則はω規則と呼ばれるが,無限の証明部分を関数で有限化したい。∀x∃yＰ(x,y)は驪に対してＰ(x,y)を真とする最小のｙを対応させると関数ｙ=f(x)が考えられるが逆に∀xＰ(x,f(x))が真となる関数が各自然数ｘに対するチェックを代行すると思ったのが関数をメインにＰＡの冠頭標準形(prenex forms)を分析しようとするきっかけでした。2012年1月の試論は上の停止性判定ルーチンによる真偽の判定とさほど変わらない強い仮定で関数による解析への拘りで書かれています。Πn文その他の用語に誤りがあります。ＰＡcompleteに関しては基礎論的には40年くらい前に決着したテーマです。この試論のＰＡシリーズはそう言った文献は無視して,誤りも気にせず,逐次近似的に自分が考え続けるために書いています。最近は,3ヶ月ほど前に自然数上の全域関数〓無限2進数列〓0,1区間の0を除く実数全体Ｉと言った簡単な対応に気づいて自然数上の全域関数集合の対角線論法による拡大やＩの点集合としての閉包をとる事による拡大。自然数上の関数合成に関して閉じた集合について関数ａ(ｂ(x))と関数a,bに対応するＩの実数の非可換な掛け算の定義とかを考えています。PDFファイルの意図はＰＡの述語をΔ0文の張り合わせの一種とみなしたとき単なるΔ0文(このΔ0も真偽が明確な文集合で置き換えてもよい)の張り合わせと一般的な自然数上の全域関数集合による張り合わせでできるprenex forms を対象とした解析をする事でした。関数集合Ｃは一般的に取り替え,先では実際の数論に応用できればと願っています。或いは直接的には非再帰的(可算)述語を描く事などです。PDFファイルは再帰的全域関数を枚挙する関数として非再帰的なｙ=Ａ(x)なる関数を仮定していますが変数の増加に従いＡ再帰的全域関数を枚挙する関数Ａ'。更に…とやり,ＴΠn(ＴΣn)の定義文の関数ｔはやはり,Ａ'再帰的全域関数,Ａ''再帰的全域関数…と段階的なものに置き換える事で修正されるとは思います。最初の普通のプログラムの実行での停止性判定ルーチンＡ(0)の添加,次にプログラムにＡ(0)サブルーチン呼び出しを含むプログラムの実行の停止性判定ルーチンＡ(1)の添加,…と同様だと思います。暫定的に再帰的全域関数の全体集合から始める事にしたのですがＰＡcompleteに絞ればはるかに精緻な結果があるためＣを取り替えて人工的な仮定が消去したり出来ないと既存の結果を薄めて,アプローチを変えただけになります。
他にも非再帰的関数でＰＡの命題で表せるものなどエラーの原因はあるでしょうが取り敢えずPDF ファイルの反省。何となくパラドキシカル？
エラーは2変数以上で起こりうる。 述語Ｐ(x,y)をΔ0へ分解するとＰ(m,n)(m,nは共に自然数全体)これを順序づけられたΔ0文の並び(順序づけが其なりに難しい)から再構成する。その1.Ｐ(0,0),Ｐ(0,1),Ｐ(1,0),Ｐ(0,2),Ｐ(1,1),Ｐ(2,0),……の順番でΔ0の中から探す。これはプログラムに従った操作だから再帰的。無限の過程が要るができるはず。よってある再帰的全域関数で収集可能に見える。(m,n)についてm＋nが小さいほど小さい。m＋nが同じならｍが小さいほど小さい。この順序で(x,y)は何番目かと言うと1からx＋yまでの和＋ｘ＋1番目。(x,y)にこの番号を対応させるのが対関数PでP;Ｎ×Ｎ→Ｎ,Pは逆関数を持つ。再帰的全域関数全体はＡ(m)で枚挙されて要するに再帰的全域関数(1変数しか考えないのは先の対関数で1変数の場合を考えれば十分だから)全体はｙ=Ａ(m)(x)(ｍは自然数全体)この順序で探すと。述語Ｐ(x,y)はある自然数ｋについてＰ(m,n)はＡ(k)(P(m,n))番目のΔ0文になっている。ＰＡの全ての述語はすべからくこのようにΔ0文全体から,再帰的に集められる。一方,ＰＡのprenex formsを考える場合,帰納法を使いたいからＰ(0,0),Ｐ(0,1),…、Ｐ(1,0),Ｐ(1,1),…,…Ｐ(m,0),Ｐ(m,1),…、…と収集する。Ｐ(m,0),Ｐ(m,1),… はΔ0文からＡ(f(m))(x)により,Ｐ(m,n)がＡ(f(m))(n)番目のΔ0文。ｙ=ｆ(x)は収集する のにパラメーターｍに依存してｙ=Ａ(f(m))(x)を選択する。ｍ毎にｆ(m)番目の再帰的全域関数Ａ()を選ぶと言う事だが,Δ0文のどれを選ぶかはプログラム可能だから再帰的だが同じ選択をする全域関数がｆ(m)番目と言うときには一応,どの再帰的全域関数が適当かはプログラム可能でよってf(m)なる関数も再帰的。自然数ｍ全体に渡りＡ(f(m))を収集する。ｙ=f(x)も再帰的全域関数だからじつはある1つの自然数ｋによりＡ(k)と同じ。だからＰ(m,0),Ｐ(m,1),…はｙ=Ａ(Ａk(m))(x)で収集される。 Ｐ(m,n)はＡ(Ａ(k)(m))(n)番目のΔ0文となる。一般にＰ(x,y)はＡ(Ａ(k)(x))(y)番目のΔ0文。さて最初の収集法だとＰ(x,y)はＡ(k)(P(x,y))番目のΔ0文、後の方ではＡ(Ａ(j)(x))(y)番目のΔ0文。ゆえにＡ(k)(P(x,y))=Ａ(Ａ(j)(x))(y)。Pも再帰的全域関数だから,両辺共に再帰的全域関数であろう。 ところでＡ(j)(x)=ｘだったとするとＡ(x)(y)は再帰的な2変数関数。ｙ=ｘとおくとｚ=Ａ(x)(x)＋1も再帰的全域関数のはずだがどのｎをとってもＡ(n)(x)=Ａ(x)(x)1はｘ=ｎで不成立。だから,Ａ(Ａ(j)(x))(y)は場合によっては非再帰的で,Ａ(k)(P(x,y))=Ａ(Ａ(j)(x))(y)を満たす左辺は存在しない場合がある。ところで,非再帰的な可能性のある右辺は,非再帰的な関数ｚ=Ａ(x)(y)は非再帰的全域関数だから(再帰的全域関数全体を枚挙する再帰的全域関数は存在しないから),Ａ再帰的と言うのはＡを初期関数に加えた再帰的関数システム(プログラムではサブルーチンとして使ってよいことにしたシステム)だからＡ(k)(P(x,y))=Ａ(Ａ(j)(x))(y)の右辺はＡ再帰的全域関数だから上の等式がいつも成り立つようにするにはＡ再帰的全域関数全体を枚挙する非再帰的関数を導入する必要がある。 でないとＥＡでの議論が破綻する。かくして変数が増加する度に新たなＡを導入する必要がある。他の部分が大丈夫ならこの反復的な新たな非再帰的関数の追加で所望の結果を得る。昨年1月の試論を見て頂くと用語や別解の関数定義文に誤りはあるが,確かに変数が増える度に新たなオラクルを追加している。真だが証明不可能な命題の真なる事を保証する計算の追加と言う存在論的で具体性を欠くオラクルではあるが。今後は寧ろＣ(PDFファイルのＲemark参照)として大きな関数集合を取る方向で,手始めにＣとして自然数から自然数への全域関数全体を取る場合で試みる。Δ0
概要;ここで考える拡大体系(ＥＡと呼ぶ)はＰＡに再帰的全域関数の関数定義文のゲーデル数全体を枚挙する非再帰的全域関数ｙ=Ａ(x)の存在を公理として加えたものである。再帰的全域関数が頻出するからここではrt関数と記す。またrt関数全体をＲtと記す。ＥＡでは非再帰的全域関数ｙ=Ａ(x)により,全てのrt関数はｙ=ｆn(x)(ｎ=0,1,…)と順序づけられる。rt関数ｆn毎に1つのＰＡの関数定義文∀x∃！yＰn(x,y)(〓ｙ=ｆn(x))を1つ選ぶ事にする。Ａ(n)=(ｙ=ｆn(x)の定義文∀x∃！yＰn(x,y)(〓ｙ=ｆn(x))のＰＡにおけるゲーデル数)によりrt関数は枚挙される。追加された命題は真なるΠ2文∀x∃！yＰ(x,y)の全体に含まれるから無矛盾性は保たれる。また真なるΠ2文∀x∃！yＰ(x,y)の全体を公理として採用しても良いがここでは上に述べたようにrt関数ｆn毎に1つの関数定義文を選ぶ事にする。rt関数全体はre集合ではないがＥＡではｙ=Ａ(x)の存在から(相対的に)re集合になる。更にrt関数を用いて拡張された冠頭標準形を定義する。ここではＥＡは公理化されてはいない。ＰＡにおいて最も基本的な部品はΔ0(=Π0=Σ0)文である。Δ0文全体,真なるΔ0文全体,偽なるΔ0文全体のゲーデル数は各々,再帰的可算集合であり各々ある関数ｄ,ｄ・ｔ,ｄ・ｆで枚挙される。ｄ,ｔ,ｆは全てrt関数。ＥＡにおいてはΠ1,Σ1文はΔ0文をrt関数で収集したものであり,真なるΠ1文は真なるΔ0文の収集で尽くされ,真なるΣ1文は少なくとも1つの真なるΔ0文を含むΔ0文の収集で尽くされる。Π2はΣ1文の収集,Σ2はΠ1文の収集,以下同様にＥＡでの冠頭標準形を定める。例えば上の関数ｄとrt関数ｇをとり,ｄ・ｇと収集したΠ1文の真偽は真なるΔ0文を枚挙する固定されたrt関数ｄ・ｔについてｄ(ｇ(x))=ｄ(ｔ(ｈ(x)))(恒等的)なるrt関数ｈが存在するか否かで決まる。rt関数全体はＥＡでは枚挙可能であるから上の等式を満たすrt関数ｈを順番に全て確認出来る。問題は同一のrt関数が多くのΠ2文で定義される事だがそれは以下で述べるようにｙ=0(恒等的)の関数定義文の定義で解決される。以上が本論でのＥＡの命題の真定義と与えられた命題の真偽の決定のシナリオである。自然数全体の再帰的部分集合全体を指定する事がこのシナリオの要点だから再帰的(全域とは限らない)関数の値域が無限集合であるもの全体を取っても同じようなシナリオで同じ結果を得る。しかし,再帰的全域関数全体を取る方がより単純であろう。
本文;(定義1)命題集合Ｓが再帰的可算として再帰的単射Ｇ;Ｓ→Ｎ(Ｎは自然数全体)があればａ∈Ｓのゲーデル数とはＧ(ａ)を指す。Ｇ(Ｓ)を枚挙するrt関数をｅ(Ｓ),Ｓの真命題全体をＴＳとするとき集合Ｎt={n|ｅ(Ｓ)(n)∈ＴＳ}を枚挙する関数をｔとおくとｅ(Ｓ)・ｔはＧ(ＴＳ)を枚挙するrt関数,Ｓの偽命題の全体をＦＳとおくとき集合Ｎf={n|ｅ(Ｓ)(n)∈ＦＳ}を枚挙する関数をｆとおくとｅ(Ｓ)・ｆはＧ(ＦＳ)を枚挙するrt関数。真命題がreならｔもrt関数,偽命題がreならｆもrt関数になる。またＰＡとＥＡのゲーデル数は異なるがどちらについても単に命題集合Ｓから自然数への再帰的単射として命題φに対してそのゲーデル数をＧ(φ)で表し,ゲーデル数gから元の式への復元をＲ(g)で表す。従ってｅ(Ｓ);Ｎ→Ｇ(Ｓ)(単射),Ｒ(Ｇ(Φ))=Φ。
(定理1)ＥＡにおいて冠頭標準形の真命題が定義され,与えられたＥＡの冠頭標準形の真偽は決定可能である。
(証明)結果はほとんどＥＡの定義に依存するから概要の細部を埋めれば十分であろう。冠頭標準形について先ずＥＡのΔ0(=Π0=Σ0)文はＰＡのそれと同じである。ＥＡにおけるｎ≧1に対するΠn,Σn文は,ｎに関して帰納的に定義するがΠn,Σn文全体を各々,Πn,Σnとおく。(定義1)のＳにΠn,Σnを各々おいて得られる定義はそのまま用いる。ＥＡのΠn,Σn文はＰＡのそれとは異なるが,命題集合Πnから自然数への再帰的単射Ｇが存在するから,(定義1)に従ってΠn文のＥＡにおけるゲーデル数全体をＧ(Πn),真なるΠn文のゲーデル数全体はＧ(ＴΠn),偽なるΠn文のゲーデル数全体はＧ(ＦΠn),Σnに関しても同様(ΠをΣに替える)に定義する。 Πj＋1(ｆm)≡∀xＲ(ｅ(Σj)・ｆm(x))とおくときΠj＋1={Πj＋1(ｆm)|ｆm∈Ｒt},Σj＋1(ｆm)≡∃xＲ(ｅ(Πj)・ｆm(x))とおくときΣj＋1={Σj＋1(ｆm)|ｆm∈Ｒt}と定義する。ＰＡのΠ1,Σ1文は適当なrt関数ｆmを取ればＥＡにおいてΠ1(ｆm),Σ1(ｆm)と解釈できる。ｎ≧2に対してもＰＡのΠn,ΣnはやはりＥＡでの解釈を持つ。ＴΠ1={Π(ｔ・ｆm)|ｆm∈Ｒt}と定義される。ｅ(Δ0)・tはＴΔ0のゲーデル数,即ち,Ｇ(ＴΔ0)の要素を枚挙するrt関数。一般に,各自然数ｎについてＢ(n,j)={ｆm∈Ｒt|ｅ(Πj)(ｆm(n))∈Ｇ(ＴΠj)かつｅ(Πj)(ｆm(n))∈Ｇ(ＦΠj)(k＜n)}とおくときＢj=∪n＜ωＢ(n,j)とＢjを定義するとＴΣj＋1={Σ(ｅ(Πj)・ｆm)|ｆm∈Ｂj},ＴΠj＋1={Π(ｅ(Σj)・ｔ・ｆm)|ｆm∈Ｒt}と定義する。ＦΣnはＴΠnの否定,ＦΠnはＴΣnの否定として得られる。従って,各々の集合は(公理ｙ=Ａ(x)の存在により)re集合。特にｆm∈Ｂ(0,0)なるＴΣ1の部分集合を枚挙するrt関数をｅ(Σ1)・ｔ0とする。真なるΠ2文は任意のrt関数ｆmに対してＴΠ2={Π(ｅ(Σ1)・ｔ・ｆm)|ｆm∈Ｒt},特に部分集合ＴΠ2(0)={Π(ｅ(Σ1)・ｔ0・ｆm)|ｆm∈Ｒt}と定義するとＴΠ2(0)は関数ｙ=0(恒等的)の関数定義文全体になる。ＥＡにおいて2つのrt関数P,ｑについて(P−ｑ＋|ｐ−ｑ|)/2もrt関数だがその関数定義文がＴΠ2(0)に含まれる場合,P=ｑ(恒等的)であり異なる関数定義文を持つ同一のrt関数が識別可能となる。以上でＥＡの真なる文は定義されるが,逆に与えられた文が真か偽か判定するには,例えば与えられたΠ1文Φに対してrt関数Jが定まりJ=ｔ・ｈを満たすrt関数ｈが存在するならΦは真,存在しなければ偽である。Σ1文ならrt関数JがＢに属すかやはりＢの関数との一致を示す問題になる。一般にＥＡでの証明の基礎となるΔ0文以外は2つのrt関数の同一性を示す問題になる。ＥＡではrt関数全体がre集合になるから(公理;関数ｙ=Ａ(x)の存在のため)真なら等式を満たすrt関数がいつか見つかり,偽なら否定文に対応する同様のrt関数がいつか見つかる。ＥＡでは真なるΠn,Σn文がre集合をなすから,上のΠn,ΣnからΣm,Πm(ｍ=ｎ＋1)への帰納法で示される。 (証了)
後記;筆者は停止問題の解決について次のような視点からの進歩に期待を持っている。計算機でプログラムを走らせる際,計算機自身はその物理工学的原理に従って動作するだけだから動作を規定する微分方程式等から時刻ｔでのメモリ値がＭ(t)とｔの関数として定まり,Ｍ(t)→α(ｔ→∞)(これが分かる事は計算時間が無限に速い事を意味する)から停止か否かが判明すること。ここで計算機はむしろ数学的に定義されたものでその固有の数学的性質から負わされた計算の停止問題に情報をもたらす状況を望む。
概要;本論の目的はＰＡ(ペアノ算術)のある拡大体系(ＥＡと呼ぶ)において真なる命題を定義し,与えられたＥＡの命題の真偽の判定の可能性を示す事にある。ＥＡは大雑把に言えばＰＡに再帰的全域関数の全体とΣn,Πn(ｎ≧1)に特別な解釈を加えたものである。
本文;(定理)ＥＡにおいてＰＡの真命題が定義され,ＥＡにおいてはそれらが証明を持つ。結果はほとんどいかに定義するかに依存するからそのアウトラインを以下に述べる。ＥＡは初期関数として全ての再帰的全域関数とその定義文を公理として持つ。より明確に言えばＥＡにおいて再帰的全域関数はｙ=ｆn(x)(ｎ=0,1,…)と順序づけられ各自然数ｎについてＡx(n)=ｆnの定義文のゲーデル数なる関数が存在する。ＥＡの述語としてｘはある再帰的全域関数の関数定義文のゲーデル数のときのみ真となる述語Ａ(x)の存在を要請する事はＥＡが再帰的全域関数全体を公理として持つ以上自然である。従ってＡ(x)の存在からｘに全ての命題のゲーデル数を代入して行き,真であるｘを順に取りだして行けばＥＡでは再帰的全域関数ｙ=Ａx(x)により再帰的全域関数定義文のゲーデル数を枚挙出来る。だから再帰的全域関数の全体は再帰的可算集合ではないが,ＥＡでは再帰的可算集合として扱える。再帰的全域関数ｙ=f(x)はＰＡにおいてはある再帰的述語φが存在してｙ=f(n)(数値毎に)はφ(n,y)が証明可能の形に表現可能であるがこのようなφ(x,y)を1つ選びこれを∀x∃！yφ(x,y)の形で公理として採用すると言うことである。全ての命題の中からこのようなΠ2文を公理として取り出して行く事で再帰的全域関数の関数定義文が枚挙出来ると言うのが上に述べた再帰的全域関数全体のＥＡでの再帰的可算集合化及び述語Ａ(x)の存在の根拠になる。これは各自然数ｎ毎の表現可能定理に対してω規則を適用したとも言える。但し,本論でのω規則の適用はこの形の適用に限定する。追加された命題は真なるΠ2文∀x∃！yφ(x,y)の全体に含まれるから無矛盾性は保たれる。また真なるΠ2文∀x∃！yφ(x,y)の全体を加えても良いがここでは再帰的全域関数ｆ毎に1つ選ぶ事にする。Δ0文はＰＡと同じものをもつがｎ≧1に対するΣn,Πn文はＥＡでは次のように定義される。先ずはΠ1,Σ1を定義する。自然数全体ＮからΔ0文のゲーデル数全体への単射をＧ,ゲーデル数から元の式への復元をＲとする。ＴΔ0={ｎ|Ｒ(Ｇ(n))が真},ＦΔ0={ｎ|Ｒ(Ｇ(n))が偽}とするとき,ＴΔ0,ＦΔ0の各要素を枚挙する関数をそれぞれｔ,fとする。Ｇ,ｔ,ｆは再帰的全域関数。Ｒ(Ｇ(x))も原始再帰的。真なるΔ0文のゲーデル数全体をＴとおくとＴの要素は関数ｙ=Ｇ(t(x))で枚挙され,偽なるΔ0文のゲーデル数全体をＦとするとＦの要素は関数ｙ=Ｇ(f(x))で枚挙される。任意の再帰的全域関数gについて,各自然数ｎについてＡ(n)〓Ｒ(Ｇ(g(n)))とするときＥＡのΠ1文,Σ1文はそれぞれΠg≡∀xＡ(x),Σg≡∃xＡ(x)と定義される。ＰＡのΠ1,Σ1文は適当な再帰的全域関数ｈを取ればＥＡにおいてΠh,Σhと解釈できる。再帰的全域関数全体をＲtとする。真なるΠ1文全体はＴΠ1={Π(ｔ・h)|ｈ∈Ｒt}と定義される。ｔ・hは2つの関数の合成関数を表す。以下でも同様に用いる。各自然数ｎについてＢ(n,0)={ｈ∈Ｒt|h(n)∈Ｔかつh(k)∈Ｆ(k＜n)}とおくときＢ0=∪n＜ωＢ(n)とＢ0を定義すると真なるΣ1文全体はＴΣ1={Σh|ｈ∈Ｂ0}と定義される。ＥＡは再帰的全域関数全体が具わっている事から真なるΠ1,Σ1文全体はそれぞれ再帰的可算化するから真なるΠ1文を枚挙する再帰的全域関数をａ,偽なるΠ1文(真なるΣ1文の否定文)を枚挙する再帰的全域関数をａ~とし,真なるΣ1文を枚挙する再帰的全域関数をｂ,偽なるΣ1文(真なるΠ1文の否定文)を枚挙する再帰的全域関数をｂ~,特にｈ∈Ｂ(0,0)なるＴΣ1の部分集合を枚挙する再帰的全域関数をｂ0とする。それらの値は自然数でコード化,復元する事になるから,値そのものはｈを再帰的全域関数としてΠh,Σhを直接的に取る事にする。真なるΠ2文は任意の再帰的全域関数ｈに対してＴΠ2={Π(ｂ・ｈ)|ｈ∈Ｒt},特に部分集合ＴΠ2(0)={Π(ｂ0・ｈ)|ｈ∈Ｒt}と定義するとＴΠ2(0)は関数ｙ=0(恒等的)の関数定義文全体になる。ＥＡにおいて2つの再帰的全域関数P,ｑについてP−ｑも再帰的全域関数だがその関数定義文がＴΠ2(0)に含まれる場合,P=ｑ(恒等的)であり異なる関数定義文を持つ同一の再帰的全域関数が識別可能となる。真なるΣ2文もΣ1の時と同様,各自然数ｎについてＢ(n,1)={Σα・h|α・ｈ(k)=ａ~(h(k))(k＜n)かつα・ｈ(n)=ａ(h(n))かつα・ｈ(k)=ｃ(h(k))(ｎ＜ｋ)}ここでｃはΠ1文を枚挙する再帰的全域関数。Ｂ1=∪n＜ωＢ(n,1)として真なるΣ2文全体はＴΣ2={Σ(α・ｈ)|ｈ∈Ｒt}と定義される。ｎ≧3に対してΠn,Σnの真なる文は同様に定義される。以上でＥＡの真なる文は定義されるが,逆に与えられた文が真か偽か判定するには,例えば与えられたΠ1文Φに対して再帰的全域関数Jが定まりJ=ｔ・ｈを満たす再帰的全域関数ｈが存在するならΦは真,存在しなければ偽である。Σ1文なら再帰的全域関数JがＢに属すかやはりＢの関数との一致を示す問題になる。一般にＥＡでの証明の基礎となるΔ0文以外は2つの再帰的全域関数の同一性を示す問題になる。ＥＡでは再帰的全域関数全体が再帰的可算化するから真なら等式を満たす再帰的全域関数がいつか見つかり,偽なら否定文に対応する同様の再帰的全域関数がいつか見つかる。ＥＡでは真なるΠn,Σn文が再帰的可算集合をなすから,Δ0をΠn,Σnに替えてΣm,Πm(ｍ=ｎ＋1)が帰納法で示される。 (了)
後記;筆者は停止問題の解決について次のような視点からの進歩に期待を持っている。計算機でプログラムを走らせる際,計算機自身はその物理工学的原理に従って動作するだけだから動作を規定する微分方程式等から時刻ｔでのメモリ値がＭ(t)とｔの関数として定まり,Ｍ(t)→α(ｔ→∞)(これが分かる事は計算時間が無限に速い事を意味する)から停止か否かが判明すること。ここで計算機はむしろ数学的に定義されたものでその固有の数学的性質から負わされた計算の停止問題に情報をもたらす状況を望む。
概要;本論の目的はＰＡ(ペアノ算術)に再帰的全域関数の全体を公理として加えた拡大体系(ＥＡと呼ぶ)においてＰＡのスタンダードモデルで真なる命題の完全な導出の可能性を示す事にある。
本文;ＥＡにおいてＰＡの真命題が定義され,ＥＡにおいてはそれらが証明を持つ。結果はほとんどいかに定義するかに依存するからそのアウトラインを以下に述べる。再帰的全域関数ｙ=f(x)はＰＡにおいてはある再帰的述語φが存在してｙ=f(n)(数値毎に)はφ(n,y)が証明可能の形に表現可能であるがこれを∀x∃！yφ(x,y)の形で公理として採用する。(真なるΠ2文∀x∃！yφ(x,y)の全体を公理に加えるとも言えるから無矛盾性は保たれる。また各自然数ｎ毎の表現可能定理に対してω規則を適用したとも言える。但し,本論でのω規則の適用はこの形の適用に限定する。)このＰＡの拡大体系をＥＡと呼ぶ事にする。再帰的全域関数全体は再帰的可算集合ではないが,各再帰的全域関数の公理への導入に従ってそれらのＰＡでの関数定義文∀x∃！yφ(x,y)の形のΠ2文全体を公理として加える事になるからそれらの命題のゲーデル数の小さいものからそれらのゲーデル数を枚挙する関数を考えるとＥＡにおいては再帰的全域関数全体が再帰的可算集合化する。(必要なら公理であるを意味する述語ＥＡ(x)を加え,ｘが全ての文の系列において追加したΠ2文のゲーデル数に対してのみ真,他の文のゲーデル数に対して偽をとるとする)真なるΣ1文の証明はΣ1文全体の再帰的可算性からそれらを∃xＳ(n,x)(ｎは自然数)と並べ(m,n)∈ω×ω〓ωの対応を与えるカントールの対関数の順序に従ってＳ(m,n)全体の真偽をチェックすると真なるΣ1文全体を順次得る。そのゲーデル数が真なるΔ0文ゲーデル数集合に含まれる事がＥＡでの証明になる。真なるΠ1文の定義とその導出は次に述べられるように異なる2つの定義を持つ再帰的全域関数の一致を示す事で遂行される。自然数全体からΔ0文のゲーデル数全体への単射をＧ,ゲーデル数から元の式への復元をＲとする。Ｇ(0),Ｇ(1),…から真なるもののｘを順にＴ(0),Ｔ(1),…とすると真なるΔ0文のゲーデル数はＧ(Ｔ(0)),Ｇ(Ｔ(1)),…と枚挙される。任意の再帰的全域関数gに対して各自然数ｎについてＡ(n)〓Ｒ(Ｇ(g(n)))としたときΠ1文,∀xＡ(x)に関数gを対応させる。Π1文にはそれぞれの再帰的全域関数が対応する。また真なるΠ1文には再帰的全域関数hが存在してＴohが対応する。gが対応するΠ1文が真であるための条件はg(x)=Ｔ(h(x))(恒等的)を満たす再帰的全域関数hが存在する事である事は定義から従う。ＥＡは再帰的全域関数全体が具わっている事から証明は以上の再帰的全域関数の条件をそのまま実行する事になる。以上でΠ1,Σ1の真の定義及びＥＡでの証明は完了する。ＥＡでは真なるΠn,Σn文が再帰的可算集合をなすから,Δ0をΠn,Σnに替えてΣm,Πm(ｍ=ｎ＋1)が帰納法で示される。 (了)
後記;筆者は停止問題の解決について次のような視点からの進歩に期待を持っている。計算機でプログラムを走らせる際,計算機自身はその物理工学的原理に従って動作するだけだから動作を規定する微分方程式等から時刻ｔでのメモリ値がＭ(t)とｔの関数として定まり,Ｍ(t)→α(ｔ→∞)(これが分かる事は計算時間が無限に速い事を意味する)から停止か否かが判明すること。ここで計算機はむしろ数学的に定義されたものでその固有の数学的性質から負わされた計算の停止問題に情報をもたらす状況を望む。
先ず,証明可能な文のうちのΠ0文(真なるΔ0文と可証なΔ0文は一致するから)の集合は再帰的可算だから,その無限部分集合の要素を指定する全域関数を考え,真なるΠ0文を集めて真なるΠ1文を尽す。ＰＡで表現可能な真なるΠ1文はこの収集で尽される筈である。また真なるΣ1文は証明可能だがこの集合も再帰的可算。この無限部分集合を上のように要素を指定する全域関数を用いて収集し,真なるΠ２文を尽す。真なるΠ1文のコレクションから真なるΣ２文全体が収集出来る。真なるΣ２文から全体から真なるΠ３文を,また真なるΠ２文全体から真なるΣ３文全体を収集する。この操作を帰納的にやればＰＡの真なる文全体が得られ,ＰＡは完全化する。かくして当初の目的は終わる。可証な集合全体から可証なΔ0文及びΣ1文のそれぞれの全体集合の再帰的部分集合の要素を収集するため,自然数全体の部分集合の要素を数え上げる再帰的全域関数を用いる。それらの再帰的全域関数(再帰的を超える部分集合が必要なら再帰的を超えて全域関数を収集する事も下記の対角線論法を超限無限回数を増やすだけだから可能だが再帰的で十分であろう)全体は対角線論法の超限帰納法的適用で収集する。にも拘わらず真なるΠ２文を収集する必要性は同一の再帰的全域関数を定義する2つのΠ２文の同値性が必ずしも可証ではないからである。
ＰＡの完全化には幾つもシナリオがあるようですが,結局,自分流に考えました。代数学の基本定理みたいな位置づけにある結果なんでとりあえず自身の証明が必要でした。チェックして概略正しければ次に進みたいと思っています。多少,基礎論を勉強したついでにも少しそちらのルートで進めたい所も有りますが,漸く,全く別のより個別的な問題へのアプローチが出来ればと思っています。
ＰＡでは任意のｘに対しＡ(x)が成り立つという形の命題は帰納法で証明出来ないとどのｎでＡ(n)が真でも証明不可能になる。あるｘでＡ(x)が成り立つのほうは真ならあるｎでＡ(n)が真と言えるはずだからこちらは(Σ1命題と呼ばれています)真なら証明可能。先の命題はΠ1文と呼ばれてますが真なるΠ1文全体をどうやって決めるかですが∀xＡ(x)が真ならＡ(0),Ａ(1),…それぞれは真命題として証明可能な命題としてある関数で他のＢ(k)とかと交じって並べられています。変数なしの∀や∃もなしの文はΔ0文と呼ばれてますがこの真なるΔ0文の無限部分集合をある関数で順番に並べて行くとｎ番目はＰnみたいに並べられますがＰnをＱ(n)にしてしまうと∀xＱ(x)(任意のｘでＱ(x)が真)が成り立つ。部分集合全部に対して上の形のΠ1文を作るともし∀xＡ(x)が真ならその中に含まれる。ここで部分集合全部じゃなく再帰的関数で要素が枚挙できる位の部分集合全部で真なるΠ1文は尽せる筈です。(要証明,このあたりを詰める作業が残ります)だからΠ1文∀xＡ(x)の真偽判定は難しいが真なるΠ1文∀xＡ(x)全体は決められるからこの中に与えられたΠ1文があるか探してもらうと原理的には見つかる筈で最初の可証命題の番号は自然数全体ですが部分集合を指定する全域関数が再帰的だと見つけるアルゴリズムが一応見つかるが再帰的全域関数全体は再帰的可算じゃないのでかなり運が良くないと見つからないです。次に再帰的全域関数全体を対角線論法で追加して行くときどこで反復拡大が止まるのかは超限帰納法でそのような関数全体を獲得するまで今の僕には不明ですが何なら実数無限の手前までやれば良いから再帰的全域関数全体を含む関数集合は獲得できるからどこまでやれば再帰的全域関数全体ピッタリになるか判れば良いとは思っていますから少しは考えないとダメな部分でチェックの対象に入ります。 後は,昨年1月に掲載したレポートの帰納法はスコーレム関数を用いてましたがそれが本当にに要るのかのチェックですね。昨年のは関数をフルに使いたいからΠ２,Π1みたいな不自然な流れが今回はＰＡ命題の扱いはΔ0,Σ1,Π1,Σ2,Π2,…と帰納法で流れ,部分集合の要素指定に用いる(先ずは真なるΠ1文の収集に使う)全域関数の集合定義は対角線論法の無限反復使用を超限帰納法で示すと言う形になります。ＰＡの有限部分に関する命題のYES,NOは本来一意的である事がＰＡに限定する理由の1つです。自然数のＰＡでの問題は幾つかの問題(平行線公理や連続体仮説など)みたいにどれも正当な複数解はなく証明可能性はともかく本来的には一意的な答えに行き着くだろうと言う直感ですね。さて,始まりのナカザワプログラムは停止性判定問題が計算を担うシステム側の構造で決められるのではないかと言う期待ですが,時刻をパラメーターとするメモリ値は計算論的には計算不可能。だから出発点となる概念は計算不可能なものが必要で初期概念から相対的に計算可能な形になると思います。個別的な問題では計算不可能な概念がどこかに潜む事になっているように思います。
《命題》Ｕ={1,2,…,Ｎ}(Ｎ=1978)とおく。Ｕを互いに共通部分のない6個の部分集合に分割し,Ｕ=Ａ(1)∪…∪Ａ(6)とするこのときあるＡ(k)は次の性質を持つ。(1)ａ,ｂをＡ(k)のある要素とするとき2×ａまたはａ+ｂはＡ(k)に含まれる。
《証明》結論を否定して矛盾を導く。Ａ(1),…,Ａ(6)のなかで要素数最大の集合の1つを必要なら番号を付け替えることによりＡ(6)={ａ1,…,ａn}とできる。ａ1＜…＜ａnとするとき鳩ノ巣原理よりｎ≧330。仮定よりi＜jならば．ａj−ａiはＡ(6)に含まれない。Ｂ(6)={ａj−ａ1}(2≦j≦ｎ)はｎ−1個の要素はＡ(6)以外の５個のＡ(k)のいずれかに含まれ,最も多くの要素を含むＡ(k)の1つを上と同様Ａ(５)とできるが,Ｂ(6)∩Ａ(５)=Ａ'(５)={ａ'1,…,ａ'm}(ａ'1＜…＜ａ'm)について鳩ノ巣原理よりm≧66。また仮定よりi＜jならば．ａ'j−ａ'iはＡ(6)∪Ａ(５)に含まれない。Ｂ(５)={ａ'j−ａ'1}(2≦j≦m)に対して同様の操作で,Ａ(6)∪Ａ(５)∪Ａ(4)に含まれない16個以上の要素を持つＢ(4)をＡ(6)∪Ａ(５)∪Ａ(4)∪Ａ(３)に含まれない５個以上の要素を持つＢ(３),そしてＡ(6)∪Ａ(５)∪Ａ(4)∪Ａ(３)∪Ａ(2)に含まれない2個以上の要素を持つＢ(2)を得る。Ｂ(2)から異なる2つの要素ａ,ｂをとると(ａ＞ｂ),ａ−ｂはどのＡ(k)にも含まれず矛盾。《証了》
《命題》Ｕ={1,2,…,Ｎ}(Ｎ=16)とおく。Ｕを互いに共通部分のない３個の部分集合に分割し,Ｕ=Ａ(1)∪Ａ(2)∪Ａ(３)とする。このときあるＡ(k)は次の性質を持つ。(1)ａ,ｂをＡ(k)のある要素とするとき2×ａまたはａ+ｂはＡ(k)に含まれる。
《証明》結論を否定して矛盾を導く。Ａ(1),Ａ(2),Ａ(３)のなかで要素数最大の集合の1つを必要なら番号を付け替えることによりＡ(1)={ａ1,…,ａn}とできる。ａ1＜…＜ａnとするとき鳩ノ巣原理よりｎ≧6だがｎ＞6なら6より先を捨ててｎ=6とする。仮定よりi＜jならば．ａj−ａiはＡ(1)に含まれない。Ｂ(1)={ａj−ａ1}(2≦j≦6)の５個の要素はＡ(1)以外の2個のＡ(k)のいずれかに含まれ,最も多くの要素を含むＡ(k)の1つを上と 同様Ａ(2)とできるが,Ｂ(1)∩Ａ(2)=Ａ'(2)={ａ'1,…,ａ'm}(ａ'1＜…＜ａ'm)について鳩ノ巣原理よりm≧３再びｍ=３とできる。また仮定よりi＜jならば．ａ'j−ａ'iはＡ(1)∪Ａ(2)に含まれないからＢ(2)={ａ'j−ａ'1}(2≦j≦３)の要素はＡ(３)に含まれる。Ｂ(2)は2個の要素を持つ。Ｂ(2)から異なる2つの要素ａ,ｂをとるとａ,ｂ,ａ−ｂはＡ(３)に含まれ,ｂ=(ａ−ｂ)+ｂから矛盾を得る。《証了》
《命題》Ｕ={1,2,…,５}とおく。Ｕを互いに共通部分のない2個の部分集合に分割し,Ｕ=Ａ(1)∪Ａ(2)とする。このときあるＡ(k)は次の性質を持つ。(1)ａ,ｂをＡ(k)のある要素とするとき2×ａまたはａ+ｂはＡ(k)に含まれる。
《証明》結論を否定して矛盾を導く。Ａ(1),Ａ(2)のなかで要素数最大の集合の1つを必要なら番号を付け替えることによりＡ(1)={ａ1,…,ａn}とできる。ａ1＜…＜ａnとするとき鳩ノ巣原理よりｎ≧3だがｎ＞3ならａ4以降を捨ててｎ=3とする。仮定よりi＜jならば．ａj−ａiはＡ(1)に含まれない。Ｂ(1)={ａj−ａ1}(j=2,３)の要素はＡ(1)以外のＡ(2)に含まれる。Ｂ(2)から異なる2つの要素ａ,ｂ(ａ＞ｂ)をとるとａ,ｂ,ａ−ｂは実際はａj−ａi(i＜j)の形に表せＡ(1)に含まれないからＡ(2)の要素であり,ｂ=(ａ−ｂ)+ｂから矛盾を得る。《証了》
ｎヶ国,ａ(n)人で同様の命題が成り立つためにはａ(1)＝2,ａ(n+1)=(n+1)ａ(n)+1を満たしていれば同じ論法で保証される。6ヶ国だと1957人いればよい。ａ(n)=n！×(2+1/2+1/(３！)+…+1/((n−1)！))≦ｎ！×ｅ。即ちＮ≧ｎ！×ｅであればｎヶ国,Ｎ人で同じ命題が成り立つ。この間の期待値に続いてまたｅ(自然対数の底)が出てきたのは面白い現象ですね。
問,最初は白玉1つ。次の規則に従い白または黒玉よりなる横一列の並びを作る。その際,全て白玉よりなる並びは3ｋまたは3ｋ＋1個の玉よりなるものに限る。規則1,既に置かれた隣接する玉の間に白玉を挿入すると左右の玉の色が逆になる。規則2;両端のいずれかに白玉を挿入する時,左端の左側に隣接して置く時は元の左端の玉の色のみ逆になる。右端の場合も同様。以上挿入する玉は白玉のみで元の隣接する玉の間または左端に隣接する左側,右端に隣接する右側のみに置ける。
解;黒玉がｎ−1個ある並びについて左側から見て最初の黒玉の左側の白玉の個数をmod3で考えたものをx1,最初の黒玉と次の黒玉の間の白玉の個数mod3をx2,…等々,そして最後の黒玉の右側の白玉の個数mod3をxnとし,上の玉を並べる規則をmod3に移して考える。即ちあるｘk＝0(mod3)ならｘkは0を含む3の倍数全ての場合があり得る。他も同様。その状態をＸ＝(x1,…,xn)で表し(ｎ＝1の時は黒玉なし),これに次の量Ｉ(Ｘ)≡ｘ1−ｘ2＋ｘ3−…＋ｘn(ｎが奇数),ｘ1−ｘ2＋ｘ3−…−ｘn−1(ｎが偶数)(いずれもmod3)を対応させる。Ｘ＝(0,1)または(1,0)から始め上の規則でＸ1からＸ2に変形した時Ｉ(Ｘ1)＝0,1mod3ならばＩ(Ｘ2)＝0,1mod3が成り立つ。ゆえに全て白玉にした時の最終形をＹで表すとＩ(Ｙ)＝0,1mod3となる。
追記;Ｉ(Ｘ)の定義は実際に黒玉を右側に寄せて白玉にする操作を黒玉が偶数,奇数の場合に考えると出てくる。例えば黒玉が偶数の時は左から2k−1番目の黒玉を2k番目の黒玉に寄せて2個並べた間に白玉を挿入する。黒玉が奇数の時は上の操作に加えて,一番右側の黒玉を右側いっぱいに寄せてその右に白玉を置いて白玉のみにする。それら白玉のみの総数をmod3で考えると上のＩ(Ｘ)の定義が出る。逆方向に黒玉を寄せて消すを考えるとＩ同様の量Ｊが得られるがｎ≧2だとＪ(Ｘ)＝1−Ｉ(Ｘ),但しｎ＝1のときはＪ(Ｘ)＝Ｉ(Ｘ),ｎ＝1(最後)だけ形が変わる。これがＩ(Ｘ)を優先する1つの理由。黒玉が残っているときの白玉の総数は一般にＩ(Ｘ)と一致しない(mod3で)が許された変形で取りうる値がmod3で0か1で2は取らない事が(言えるのではないかと思ったのがＩ(Ｘ)を考えた理由)比較的簡単に分かる。そして最終の白玉のみの場合には白玉の総数mod3がＩ(Ｘ)と一致して0,1mod3が分かる。
補足;実は,上のＩ(Ｘ)の取り方はＸを白玉のみに変形する手段を1つ決めておけば何でも良い。そのやり方で白及び黒玉の並びＸを白玉のみに変形した時の白玉の個数をＫ(Ｘ)とおくとＫ(Ｘ)＝0,1mod3になる筈。そこで変形規則のいずれかでＸをＹに変形したときＸをどのように変形しても白玉のみの最終形の白玉の個数＝0,1mod3となる筈だからＸからＹを経て,後は決まったやり方で白玉のみとやっても最終形の白玉の個数＝Ｋ(Ｙ)＝0,1mod3となる筈だから。その意味ではこの不変量的なものを考えるというアイデアの下では融通がきく易しい問題とも言えるでしょう。ただ上に取ったＩ(Ｘ)は簡明で交代和はホモロジーを連想させますがそれでなくとも上手く行く筈ですからトポロジーとは直接的な関係は無いかも知れません。勿論,トポロジカルな見立てが立てばグラフへの応用がありそうに思います。
概略;本論の目的はＰＡに可算個のＰＡの命題を満たす非再帰的全域関数全体を追加することにより,その拡大体系ＳにおいてＰＡの真命題が証明可能となる事を示す事にある。従って計算プログラムの停止問題もＳにおいては決定される。簡単な例から始める。ＰＡのΠ1文∀x∃yＰ(x,y)は関数ｙ=f(x)があり,∀xＰ(x,f(x))を示すことで証明される。ここでは上のようにＰＡの真命題を充たす関数全体を作ることによりＰＡの完全化を試みる。そのような関数について言及するシステムとしてここでは再帰的関数論をとる。以下,単に関数システムというと再帰的関数論のシステムのこととする。ある再帰的述語Ａ(x)に対して再帰的関数Ｆ(x)でＡ(n)が真ならＦ(n)=1,偽ならＦ(n)=0なるものが存在するからＦ(x)の定義域が自然数全体{0,1,2,…,n,…}でかつ常にＦ(x)=1であることは,Ｆ(x)(x=0,1,2,…,n,…)を計算するプログラムが停止しないことにより任意の自然数ｎについてＡ(n)が真なること即ち∀xＡ(x)が再帰的関数論のシステムで保証される。故に以下では関数システムにおいてまずは初期関数は標準的にとりＰＡの論理式を満たすが非再帰的全域関数をオラクルとして初期関数集合に加え続けることによりＰＡの真命題を証明可能にするという方針でＰＡを完全化する。本文;∀xＡ(x)をＡ(x)はｘのみを自由変数とするＰＡの量化子を含まない再帰的述語とする。即ちΠ1文∀x∃y1Ａ(x)だが述語Ａ(x)を充足する(x,y1)においてｙ1の値は任意である場合である。またＢ(x,y)をｘを入力としそのときＡ(x)が真なることを確認するプログラム(ゲーデル数ｅ)に従う計算過程(Ａ(x)が再帰的だから各自然数ｎに対してＡ(n)が真なら1,偽なら0をとる再帰的関数が存在するからそのような計算は明らかに存在する)のゲーデル数をｙとするときｙは出力として終点表示と変数y1=0を含むとする。(y1は任意だから最小の0をとるとする)このＴＭに対するクリーニの述語Ｔ1(e,x,y)をＰＡにおいて表現する述語とする。(ｅは無数にあるがその中の勝手な1つをとる) ∀xＡ(x)⇔∀x∃yＢ(x,y)…(★)は両辺がともに真かともに偽。よって公理として追加する。∀xＡ(x)がＰＡで証明されるならば∀x∃yＢ(x,y)はｙが一意的に決まることからＰＡにおいて1つの関数y=f(x),より詳細には(e,y,y1)=(e,y,0)=f(x)を定義する。また∀xＡ(x)が真だが証明不可能なら∀x∃yＢ(x,y)において与えられたｘに対しｙが一意的,故に関数(e,y,0)=f(x)(ｅはプログラムのゲーデル数,ｙはｅによる計算過程のゲーデル数)が存在するが∀x∃yＢ(x,y)はＰＡで証明不可能故に非再帰的であるがこれをＰＡの公理として追加する。同時に関数の初期関数集合にもオラクルとして加える。すると拡大されたＰＡでは∀xＡ(x)は証明可能となる。このような拡大を全てのｘのみを変数とする再帰的述語Ａ(x)全てに対して行うと∀xＡ(x)(Ａは再帰的で量化子を含まない)に関しては完全になる。よって∃xＡ(x)はその否定を考えればやはり真なら証明可能となっている。この操作を反復して次の定理を得る。
定理;ＰＡに可算個の非再帰的関数と同値形の公理(上の(★))を追加して拡大した体系においてＰＡは完全化する。
証明;ＰＡのΠ1文∀x1∃y1θ(x1,y1)(ここでθはx1,y1のみを変数として(y1はなくてもよい)持つ量化子を含まない述語)に対し,与えられたｘ1に対し,θ(ｘ1,ｙ)が真なるかをｙ=0,ｙ=1,…,ｙ=ｎ,…と調べθ(ｘ1,ｍ)が真なる最小のｙを見つけるとｙ1=ｍを終点表示とともに出力するＴＭについての計算過程のゲーデル数ｙの終点表示から最終的にｙ1を取り出す。(上のＡ(x1)のようにy1を含まない場合y1=0と設定される)クリーニの述語Ｔ1(e,ｘ1,y)を元に作る述語のＰＡでの表現をＢ(ｘ1,ｙ1)とすると上の同値式(★)と同様に∀ｘ1∃ｙ1θ(ｘ1,ｙ1)⇔∀x1∃y1Ｂ(x1,y1)を公理に追加する。右辺は真なら関数(e,y,y1)=f1(x1)を定義するが真だがＰＡで証明不可能のときこのような関数の存在を全て公理として追加してＰＡを拡大するとΠ1文に関しては完全になる。Σ1文に関しては否定がΠ1文だからΠ1文に関して完全ならΣ1文に関しても完全になる。ｎ＞1とし,ｎ−1のときΠ1からΠn−1文に関しては完全となるＰＡの拡大が既になされているとする。Πn−1文∀x1∃y1…∀xn−1∃yn−1θ(ｘ1,…ｘn−1,ｙ1…ｙn−1)(ここにθはｘ1,…ｘn−1,ｙ1…ｙn−1のみを自由変数に持ちかつ量化子を含まないいわゆる母式である)が真なる場合あるプログラムのゲーデル数ｅが存在し与えられた(ｘ1,…ｘn−1)に対しｘ1に依存してｙ1が,ｘ1,ｘ2に対してｙ2が,…,ｘ1,…ｘn−1に依存してｙn−1が存在して,即ちスコーレム関数f1(ｘ1)=(e,y,ｙ1),f2(ｘ1,ｘ2)=(e,y,ｙ2),…,fn−1(ｘ1,…ｘn−1)=(e,y,ｙn−1)が定義されるとし入力(ｘ1,…ｘn−1)に対し上の(ｙ1…ｙn−1)を出力するプログラムのゲーデル数ｅに従う計算過程のゲーデル数をｙとするとその計算のクリーニの述語をＴn(e,ｘ1,…ｘn−1,y)とする。ｙの終点表示から(ｙ1…ｙn−1)を取り出す述語をＢ(ｘ1,…ｘn−1,ｙ1…ｙn−1)とする。∀x1∃y1…∀xn−1∃y1…∃yn−1θ(ｘ1,…ｘn−1,ｙ1…ｙn−1)⇔∀ｘ1…∀ｘn−1∃ｙ1…∃yn−1Ｂ(ｘ1,…ｘn,ｙ1…ｙn−1)は公理として既に追加されている。左辺が偽なら右辺も偽となる。左辺が真のとき右辺に従い関数(e,y,y1,…,yn−1)=Ｆ(x1,…,xn−1)であるが特にスコーレム関数(e,y,y1)=f1(x1),…,(e,y,ｙ1…ｙn−1)=fn−1(ｘ1,…ｘn−1)も同時に定義されている。これらは帰納法の仮定よりＰＡに存在すると公理に追加されている。さてΠn文Φ≡∀x1∃y1…∀xn∃y1…∃ynθ(x1,…ｘn,y1,…ｙn)について(α,β)∈ω×ωとして可算無限個のΠn−1文Φ(α,β)≡∀x2∃y2…∀xn∃y1…∃ynθ(α,…ｘn,β,…ｙn)を考える。帰納法の仮定よりこれらの真偽は全て定まっている。そこでＴＭはそれらの真偽情報は全て利用できるものとする。即ち,Πnを考える際にはΠk,Σk(k＜ｎ)で導入した非再帰的関数はオラクルとして初期関数に加え使用可能と考える。Φが真ならばαを固定してΦ(α,0),…,Φ(α,n),…で真なる最小のｍをもつΦ(α,ｍ)を見いだすＴＭがある。αを入力したとき上と同様なΦ(α,ｍ)を計算するＴＭにΦ(α,ｍ)に対する上に述べたＴＭのプログラムを加えて与えられたx1,…ｘnに対しｎ−1と同様にy1,…ynを計算するＴＭのプログラムｅを作ることができる。以下ｎ−1の場合と同様にＢ(x1,…ｘn,y1,…yn)が存在しθが真なる事を確認するＴＭが存在する。(ｙ1はｘ1のスコーレム関数ｆ1でｙ1=ｆ1(ｘ1)の形で決まることになる)これに対するクリーニの述語Ｔn(e,ｘ1,…ｘn,y)(ｙは出力情報としてｙ1…ｙnを含む)を及び出力情報をＰＡにおいて表現する述語をＢ(ｘ1,…ｘn,ｙ1…ｙn)とする。∀x1∃y1…∀xn∃y1…∃ynθ(ｘ1,…ｘn,ｙ1…ｙn)⇔∀ｘ1…∀ｘn∃ｙ1…∃ynＢ(ｘ1,…ｘn,ｙ1…ｙn)を公理として追加すると左辺が真のとき右辺に従い関数(e,y,y1)=f1(x1),…,(e,y,ｙ1…ｙn)=fn(ｘ1,…ｘn)が定義される。これに対しても∀x1∃y1…∀xn∃ynθ(ｘ1,…ｘn,ｙ1…ｙn)が真でＰＡで証明不可能なら∀ｘ1…∀ｘn∃y1…∃ynＢ(ｘ1,…ｘn,y1,…,yn)を公理として追加する。即ちスコーレム関数(e,y,y1)=f1(x1),…,(e,y,ｙn−1)=fn−1(ｘ1,…ｘn−1)(e,y,ｙn)=ｆn(ｘ1,…ｘn)を公理として追加するとΦは証明可能となる。そしてΠn文に対しても完全となればΣn文も否定がΠn文故に完全となる。全ての自然数ｎでΠｎ文が完全となるまで拡大するとＰＡは完全となる。特にＰＡの真命題には真なることを保証する関数が全てＰＡに存在することになる。その拡大された体系においてＰＡの真命題は証明可能となる。(証了)
次のようにＰＡに存在しない非再帰的全域関数を次々に付加してＰＡ及び関数システムの拡大を超限無限回繰り返すことでも上と同様のシステムが得られる。 別証明;ＰＡの1変数再帰的関数全体(定義域が自然数全体でないものも含む)は再帰的可算であり,またある再帰的(部分)関数ｆのゲーデル数をｅとするときＫ={ｅ|f(e)が定義されている}もまた再帰的可算集合であり,更に再帰的全域単射関数Ｇの値域として表される。ｅ∈Ｋのときｅで定義される再帰的(部分)関数{ｅ}(x)のｘ=ｅでの値{ｅ}(e),Ｇを表現するＰＡの関数をやはりＧで,また値{ｅ}(e)のＰＡでの表現もやはり{ｅ}(e)で表す。まず任意の自然数ｘに対してｙ=0としておいてｘ=ｅ(∈Ｋ)のときｙをｙ≠{ｅ}(e)なる最小の自然数に置き換える手続きを全ての自然数ｘに対して行うとどの再帰的(部分)関数とも一致しない関数αが得られるが,この関数は次のＰＡの論理式∀x∃y(∃n((ｘ=Ｇ(n)→(y≠{Ｇ(n)}(Ｇ(n))∧(∀z＜ｙ¬(ｘ=Ｇ(n)→(z≠{Ｇ(n)}(Ｇ(n)))))∧∀n(ｘ≠Ｇ(n)→y=0))を充たすからこの論理式は真。αはこの論理式を充たす1つの自然数上の全域関数であるが定義からどの再帰的(部分)関数とも一致しないから非再帰的全域関数,故に上の論理式はＰＡで証明不可能。勿論,否定も証明不可能。ＰＡにこの命題(関数αを定義する)を公理として追加しＰＡを拡大する。また再帰的関数論にはαをオラクルとして初期関数に加える。同値式∀xＡ(x)⇔∀x∃yＢ(x,y)…(★)において右辺は左辺をα再帰的関数で保証する。αとして左辺がゲーデル文であるときの右辺から定まる関数を追加して拡大しても良いが関数追加の方針から上の関数を優先した)この拡大されたシステムをＰＡ(1)とするとαはここでは再帰的。また以降,再帰的と言うのはαをオラクルとして初期関数に加えたものを考える。従って以降のクリーニの述語はαを計算可能として加えたα計算の述語であり,α再帰的関数全体はαの追加に伴い可算無限個増加する。この手続きは以降の拡大でも同様に行う。だがこの型の拡大を超限無限回続けるとやがてある可算順序数ΩについてＰＡ(Ω)はこれ以上この型の拡大は不可能になる。(ＰＡの命題は可算個だから非可算無限回の拡大はできない)このとき真なるＰＡ命題を確認するための関数がすべて証明可能だからこのシステムＰＡ(Ω)は完全になる。もし真だが証明不可能な命題が在ればそれを確認する命題(上の(★)形式の同値式の右辺)からＰＡ(Ω)に含まれない1変数の全域的関数を定義する証明不可能な命題が作れて(多変数の場合,カントールの対関数の反復で1変数化する)ＰＡ(Ω)が更に同じ型の拡大可能となるから。(証了)
以上の結果を要約して次の系を得る。
系;ＰＡに非再帰的全域関数(上述したようにスコーレム関数の1つとなっている場合はそれらから取り出せる)でＰＡの命題(いずれ追加される関数を定義する部分を含み得る)を満たすものと関連する同値式(★)全てを追加したシステムＳでＰＡは完全である。
ＰＡを完全化したシステムでは再帰的可算な関係「ｅをプログラムのゲーデル数とする関数ｆについてｘ∈dom(f)」は表現可能であり,真なら証明可能だからｆにｘを入力したとき停止するか否かが定まる。 また同値式(★)の右辺を様々なシステムでの確認或いは証明を意味するものに取り替えて議論出来れば,新たな何かを得るかも知れない興味深いテーマと思われる。
本論の目的はＰＡに可算個の非再帰的関数を追加することにより,その拡大体系においてＰＡの真命題が証明可能となる事を示す事にある。∀xＡ(x)をＡ(x)はｘのみを自由変数とし量化子を含まないＰＡの述語とする。またＢ(x,y)をＡ(x)が真なる事を確認するＴＭに対するクリーニの標準形Ｔ1(e,x,y)をＰＡにおいて表現する述語とする。 ∀xＡ(x)⇔∀x∃yＢ(x,y)∧∀z＜y¬Ｂ(x,y)…(★)は両辺がともに真かともに偽。よって公理として追加する。∀xＡ(x)がＰＡで証明されるならば∀x∃yＢ(x,y)∧∀z＜y¬Ｂ(x,y)はＰＡにおいて1つの関数ｙ=f(x)を定義する。また∀xＡ(x)が真だが証明不可能なら∀x∃yＢ(x,y)∧∀z＜y¬Ｂ(x,y)即ち関数ｙ=f(x)をＰＡの公理として追加する。すると拡大されたＰＡでは∀xＡ(x)は証明可能となる。
定理;ＰＡに可算個の関数と同値形の公理(上の(★)の一般型)を追加して拡大した体系においてＰＡは完全化する。
証明;上に述べた事を一般化するだけである。ＰＡのΠn文∀x1∃ y1…∀xn∃ynθ(ここにθはｘ1,…ｘn,ｙ1…ｙnのみを自由変数に持ちかつ量化子を含まないいわゆる母式である)が真なる場合を考える。この場合も上と同様与えられたｘ1,…ｘnに対しθが真なる事を確認するＴＭに対するクリーニの標準形Ｔn(e,ｘ1,…ｘn,y)をＰＡにおいて表現する述語をＢ(ｘ1,…ｘn,y)とする。 ∀x1∃y1…∀xn∃ynθ⇔∀ｘ1…∀ｘn∃ｙＢ(ｘ1,…ｘn,y)∧∀z＜y¬Ｂ(ｘ1,…ｘn,y)がＰＡで証明可能でないなら公理として追加する。これに対しても∀x1∃y1…∀xn∃ynθがＰＡで証明不可能なら∀ｘ1…∀ｘn∃ｙＢ(ｘ1,…ｘn,y)∧∀z＜y¬Ｂ(ｘ1,…ｘn,y),即ち関数ｙ=ｆ(ｘ1,…ｘn)を公理として追加する。Σn文に対しても同様の操作をする。即ちＰＡの真命題にはその証となるはずの関数を全てＰＡに追加することによりその拡大された体系においてＰＡの真命題は証明可能となる。 (証了)
(別証明)ＰＡの1変数再帰的関数全体(定義域が自然数全体でないものも含む)は再帰的枚挙可能であり,またある再帰的関数ｆのゲーデル数をｅとするときＫ={ｅ|f(e)が定義されている}もまた再帰的枚挙可能集合で再帰的全域関数Ｇの値域として表されるとする。∀ｎ∀x∃y((ｘ=Ｇ(n)→(y≠{Ｇ(n)}(Ｇ(n))∧∀z＜ｙ¬(∀ｎ∀x∃z((ｘ=Ｇ(n)→(z≠{Ｇ(n)}(Ｇ(n))))∧(ｘ≠Ｇ(n)→y=0))は真ゆえにこれは1つのＰＡの全域関数を定義するが定義から非再帰的全域関数だからＰＡで証明不可能。ゆえにＰＡにこの命題を公理として追加しＰＡを拡大する。(ゲーデル文を確認する関数を追加して拡大しても良い)この拡大されたシステムをＰＡ(1)とする。この型の拡大を超限無限回続けるとやがてある可算順序数ΩについてＰＡ(Ω)はこれ以上はこの型の拡大は不可能になる。このとき真なるＰＡ命題を確認するための関数がすべて証明可能だからこのシステムＰＡ(Ω)は完全になる。もし真だが証明不可能な命題が在ればそれからＰＡ(Ω)に含まれない関数を定義する証明不可能な命題が作れてＰＡ(Ω)が更に同じ型の拡大可能となるから。(証了)
なお筆者には上のＰＡを完全化するシステムは少なくとも高階の集合論において実現できるように思える。
本論の目的はＰＡに可算個の非再帰的関数を追加することにより,その拡大体系においてＰＡの真命題が証明可能となる事を示す事にある。∀xＡ(x)をＡ(x)はｘのみを自由変数とし量化子を含まないＰＡの述語とする。またＢ(x,y)をＡ(x)が真なる事を確認するＴＭに対するクリーニの標準形Ｔ1(e,x,y)をＰＡにおいて表現する述語とする。 ∀xＡ(x)⇔∀x∃yＢ(x,y)∧∀z＜y¬Ｂ(x,y)…(★)は両辺がともに真かともに偽。よって公理として追加する。∀xＡ(x)がＰＡで証明されるならば∀x∃yＢ(x,y)∧∀z＜y¬Ｂ(x,y)はＰＡにおいて1つの関数ｙ=f(x)を定義する。また∀xＡ(x)が真だが証明不可能なら∀x∃yＢ(x,y)∧∀z＜y¬Ｂ(x,y)即ち関数ｙ=f(x)をＰＡの公理として追加する。すると拡大されたＰＡでは∀xＡ(x)は証明可能となる。この考えから次の定理を得る。
定理;ＰＡに可算個の関数と同値形の公理(上の(★)の一般型)を追加して拡大した体系においてＰＡは完全化する。
証明;上に述べた事を一般化するだけである。ＰＡのΠn文∀x1∃y1…∀xn∃ynθ(ここにθはｘ1,…ｘn,ｙ1…ｙnのみを自由変数に持ちかつ量化子を含まないいわゆる母式である)が真なる場合を考える。この場合も上と同様に与えられたｘ1,…ｘnに対しθが真なる事を確認するＴＭが存在する。(ｙ1はｘ1のスコーレム関数ｆ1でｙ1=ｆ1(ｘ1)の形で決まることになる)これに対するクリーニの標準形Ｔn(e,ｘ1,…ｘn,y)をＰＡにおいて表現する述語をＢ(ｘ1,…ｘn,y)とする。 ∀x1∃y1…∀xn∃ynθ⇔∀ｘ1…∀ｘn∃ｙＢ(ｘ1,…ｘn,y)∧∀z＜y¬Ｂ(ｘ1,…ｘn,y)ここに右辺はｎに関する帰納法により,ｙ1はｘ1のスコーレム関数ｆ1でｙ1=ｆ1(ｘ1),ｙ2=ｆ2(ｘ1,ｘ2),…,ｙn=ｆn(ｘ1,…ｘn)の形で決まることになるがｙ=ｈ(ｙ1,…ｙn)(ｈはωのｎ乗とωとの1対1対応)を意味する。この同値式をＰＡに公理として追加する。これに対しても∀x1∃y1…∀xn∃ynθが真でＰＡで証明不可能なら∀ｘ1…∀ｘn∃ｙＢ(ｘ1,…ｘn,y)∧∀z＜y¬Ｂ(ｘ1,…ｘn,y),即ち関数ｙ=ｆ(ｘ1,…ｘn)を公理として追加する。Σn文に対しても同様の操作をする。即ちＰＡの真命題には真なることを保証する関数が全てＰＡに存在することになる。その拡大された体系においてＰＡの真命題は証明可能となる。(証了)
(別証明) ＰＡの1変数再帰的関数全体(定義域が自然数全体でないものも含む)は再帰的枚挙可能であり,またある再帰的関数ｆのゲーデル数をｅとするときＫ={ｅ|f(e)が定義されている}もまた再帰的枚挙可能集合である再帰的全域単射関数Ｇの値域として表される。Ｇを表現するＰＡの関数をやはりＧで表す。∀ｎ∀x∃y((ｘ=Ｇ(n)→(y≠{Ｇ(n)}(Ｇ(n))∧∀z＜ｙ¬(∀ｎ∀x∃z((ｘ=Ｇ(n)→(z≠{Ｇ(n)}(Ｇ(n))))∧(ｘ≠Ｇ(n)→y=0))は真ゆえにこれは1つのＰＡの全域関数を定義するが定義から非再帰的全 域関数だからＰＡで証明不可能。ゆえにＰＡにこの命題を公理として追加しＰＡを拡大する。(ゲーデル文を確認する関数を追加して拡大しても良い)この拡大されたシステムをＰＡ(1)とする。この型の拡大を超限無限回続けるとやがてある可算順序数ΩについてＰＡ(Ω)はこれ以上はこの型の拡大は不可能になる。(ＰＡの命題は可算個だから非可算無限回の拡大はできない)このとき真なるＰＡ命題を確認するための関数がすべて証明可能だからこのシステムＰＡ(Ω)は完全になる。もし真だが証明不可能な命題が在ればそれからＰＡ(Ω)に含まれない関数を定義する証明不可能な命題が作れてＰＡ(Ω)が更に同じ型の拡大可能となるから。(証了)
なお上のＰＡを完全化するシステムは少なくとも高階の集合論において実現できるように思える。またプログラムに従う計算過程は計算で使用される作業用メモリも含めて出現する変数をまとめて1つの変数Ｘ,順次実行される部分を関数Ｆ(Ｘ)と表すと計算過程はＦを1つのサイクルとするループからなる。1サイクル分のメモリも含め停止する場合は最後に出力部分がくるものをやはりまとめてＹで表す。計算過程はＦ(1),Ｆ(2),…,Ｆ(n),…と継続し変数のある部分がループからの脱出条件である述語を充たすとループから脱出し,幾らかの処理の後計算過程は停止する。ＰＡ命題∀xＡ(x)の確認プログラムはＡ(0),Ａ(1),…と確認していくがＡ(n)の確認結果について真なら1,偽なら0の値をとる関数Ｆが任意のｎに対し1をとる関数であるとあるシステムで保証される場合(例えば∀n(Ｆ(n)=1)が 証明される場合)に∀xＡ(x)は確認できたと言えるし,反例探索の形で¬Ａ(m)であるものを追跡するプログラムに従う反例を求める計算過程Ｇが停止しないことがあるシステムで保証できる場合(例えば∀n(Ｇ(n)=0)または,ｍサイクル目で停止する場合Ｇ(m)=0,停止しない場合を1とすれば∀n∃x(ｎ＜x∧Ｇ(x)=1)証明される場合)に∀xＡ(x)は確認できたと言える。このような素朴な観察からある関数が存在してある条件を充たすことが ＰＡ命題の証明や計算過程の停止性判定では有効である。また述語の充足集合は関数のグラフの合併集合と見なせる。上記の非再帰的関数の追加によるシステムの拡大はこの素朴な観察に動機づけられたものである。
本論の目的はＰＡに可算個の非再帰的関数を追加することにより,その拡大体系においてＰＡの真命題が証明可能となる事を示す事にある。∀xＡ(x)をＡ(x)はｘのみを自由変数とするＰＡの原始再帰的述語とする。即ちΠ1文∀x∃y1Ａ(x)だが述語Ａ(x)を充足する(x,y1)においてｙ1の値は任意である場合である。またＢ(x,y)をｘを入力としそのときＡ(x)が真なることを確認するプログラム(ゲーデル数ｅ)に従う計算過程のゲーデル数をｙとするときｙは出力として終点表示と変数y1=0を含む。(y1は任意だから最小の0をとるとする)ＴＭに対するクリーニの標準形Ｔ1(e,x,y)をＰＡにおいて表現する述語とする。(ｅは無数にあるがその中の勝手な1つをとる) ∀xＡ(x)⇔∀x∃yＢ(x,y)…(★)は両辺がともに真かともに偽。よって公理として追加する。∀xＡ(x)がＰＡで証明されるならば∀x∃yＢ(x,y)はｙが一意的に決まることからＰＡにおいて1つの関数y=f(x),より詳細には(e,y,y1)=(e,y,0)=f(x)を定義する。また∀xＡ(x)が真だが証明不可能なら∀x∃yＢ(x,y)において与えられたｘに対しｙが一意的,故に関数(e,y,0)=f(x)(eはプログラムのゲーデル数,ｙはeによる計算過程のゲーデル数)が存在するが∀x∃yＢ(x,y)はＰＡで証明不可能故に非再帰的であるがこれをＰＡの公理として追加する。すると拡大されたＰＡでは∀xＡ(x)は証明可能となる。このような拡大を全てのｘのみを変数とする原始再帰的述語Ａ(x)全てに対して行うと∀xＡ(x)(Ａは原始再帰的)に関しては完全になる。よって∃xＡ(x)はその否定を考えればやはり真なら証明可能となっている。ここで特にｎはＰＡの命題のゲーデル数ｘはその命題の証明のゲーデル数であるとき真となる述語Ｐrf(n,x)をＡ(x)にとると原始再帰的述語であるから上の結果を用いると上の拡大されたシステムではＰＡの任意の真命題は証明可能,即ち上の拡大システムにおいてＰＡは完全になる。よって次の定理を得る。
定理;ＰＡに可算個の非再帰的関数と同値形の公理(上の(★)を追加して拡大した体系においてＰＡは完全化する。
(別証明1);上に述べた事を帰納法で行うだけである。ＰＡのΠ1文∀x1∃y1θ(x1,y1)(ここでθはx1,y1のみを変数として(y1はなくてもよい)持つ量化子を含まない述語)に対し,与えられたｘ1に対し,θ(ｘ1,ｙ)が真なるかをｙ=0,ｙ=1,…,ｙ=ｎ,…と調べθ(ｘ1,ｍ)が真なる最小のｙを見つけるとｙ1=ｍを終点表示とともに出力するＴＭについての計算過程のゲーデル数ｙの終点表示から最終的にｙ1を取り出す。(上のＡ(x1)のようにy1を含まない場合y1=0と設定される)クリーニの標準形Ｔ1(e,ｘ1,y)を元に作る述語のＰＡでの表現をＢ(ｘ1,ｙ1)とすると上の同値式(★)と同様に∀ｘ1∃ｙ1θ(ｘ1,ｙ1)⇔∀x1∃y1Ｂ(x1,y1)を公理に追加する。右辺は真なら関数(e,y,y1)=f1(x1)を定義するが真だがＰＡで証明不可能のときこのような関数の存在を全て公理として追加してＰＡを拡大するとΠ1文に関しては完全になる。Σ1文に関しては否定がΠ1文だからΠ1文に関して完全ならΣ1文に関しても完全になる。ｎ＞1とし,ｎ−1のときΠ1からΠn−1文に関しては完全となるＰＡの拡大が既になされているとする。Πn−1文∀x1∃y1…∀xn−1∃yn−1θ(ｘ1,…ｘn−1,ｙ1…ｙn−1)(ここにθはｘ1,…ｘn−1,ｙ1…ｙn−1のみを自由変数に持ちかつ量化子を含まないいわゆる母式である)が真なる場合あるプログラムのゲーデル数ｅが存在し与えられた(ｘ1,…ｘn−1)に対しｘ1に依存してｙ1が,ｘ1,ｘ2に対してｙ2が,…,ｘ1,…ｘn−1に依存してｙn−1が存在して,即ちスコーレム関数f1(ｘ1)=(e,y,ｙ1),f2(ｘ1,ｘ2)=(e,y,ｙ2),…,fn−1(ｘ1,…ｘn−1)=(e,y,ｙn−1)が定義されるとし入力(ｘ1,…ｘn−1)に対し上の(ｙ1…ｙn−1) を出力するプログラムのゲーデル数ｅに従う計算過程のゲーデル数をｙとするとその計算のクリーニの標準形をＴn(e,ｘ1,…ｘn−1,y)とする。ｙの終点表示から(ｙ1…ｙn−1)を取り出す述語をＢ(ｘ1,…ｘn−1,ｙ1…ｙn−1)とする。∀x1∃y1…∀xn−1∃y1…∃yn−1θ(ｘ1,…ｘn−1,ｙ1…ｙn−1)⇔∀ｘ1…∀ｘn−1∃ｙ1…∃yn−1Ｂ(ｘ1,…ｘn,ｙ1…ｙn−1)は公理として既に追加されている。左辺が偽なら右辺も偽となる。左辺が真のとき右辺に従い関数(e,y,y1,…,yn−1)=Ｆ(x1,…,xn−1)であるが特にスコーレム関数(e,y,y1)=f1(x1),…,(e,y,ｙ1…ｙn−1)=fn−1(ｘ1,…ｘn−1)も同時に定義されている。これらは帰納法の仮定よりＰＡに存在すると公理に追加されている。さてΠn文Φ≡∀x1∃y1…∀xn∃y1…∃ynθ(x1,…ｘn,y1,…ｙn)について(α,β)∈ω×ωとして可算無限個のΠn−1文Φ(α,β)≡∀x2∃y2…∀xn∃y1…∃ynθ(α,…ｘn,β,…ｙn)を考える。帰納法の仮定よりこれらの真偽は全て定まっている。そこでＴＭはそれらの真偽情報は全て利用できるものとする。即ち,Πnを考える際にはΠk,Σk(k＜ｎ)で導入した非再帰的関数はオラクルとして使用可能と考える。Φが真ならばαを固定してΦ(α,0),…,Φ(α,n),…で真なる最小のｍをもつΦ(α,ｍ)を見いだすＴＭがある。αを入力したとき上と同様なΦ(α,ｍ)を計算するＴＭにΦ(α,ｍ)に対する上に述べたＴＭのプログラムを加えて与えられたx1,…ｘnに対しｎ−1と同様にy1,…ynを計算するＴＭのプログラムｅを作ることができる。以下ｎ−1の場合と同様にＢ(x1,…ｘn,y1,…yn)が存在しθが真なる事を確認するＴＭが存在する。(ｙ1はｘ1のスコーレム関数ｆ1でｙ1=ｆ1(ｘ1)の形で決まることになる)これに対するクリーニの標準形Ｔn(e,ｘ1,…ｘn,y)をＰＡにおいて表現する述語をＢ(ｘ1,…ｘn,y)とする。∀x1∃y1…∀xn∃y1…∃ynθ(ｘ1,…ｘn,ｙ1…ｙn)⇔∀ｘ1…∀ｘn∃ｙ1…∃ynＢ(ｘ1,…ｘn,ｙ1…ｙn)を公理として追加すると左辺が真のとき右辺に従い関数(e,y,y1)=f1(x1),…,(e,y,ｙ1…ｙn)=fn(ｘ1,…ｘn)が定義される。これに対しても∀x1∃y1…∀xn∃ynθ(ｘ1,…ｘn,ｙ1…ｙn)が真でＰＡで証明不可能なら∀ｘ1…∀ｘnＢ(ｘ1,…ｘn,y1,…,yn)を公理として追加する。即ち関数(e,y,)ｙ=ｆ(ｘ1,…ｘn)を公理として追加するとΦは証明可能となる。そしてΠn文に対しても完全となればΣn文も否定がΠn文故に完全となる。全ての自然数ｎでΠｎ文が完全となるまで拡大するとＰＡは完全となる。特にＰＡの真命題には真なることを保証する関数が全てＰＡに存在することになる。その拡大された体系においてＰＡの真命題は証明可能となる。 (証了)
(別証明2);ＰＡの1変数再帰的関数全体(定義域が自然数全体でないものも含む)は再帰的枚挙可能であり,またある再帰的関数ｆのゲーデル数をｅとするときＫ={ｅ|f(e)が定義されている}もまた再帰的枚挙可能集合である再帰的全域単射関数Ｇの値域として表される。Ｇを表現するＰＡの関数をやはりＧで表す。∀ｎ∀x∃y((ｘ=Ｇ(n)→(y≠{Ｇ(n)}(Ｇ(n))∧∀z＜ｙ¬(∀ｎ∀x∃z((ｘ=Ｇ(n)→(z≠{Ｇ(n)}(Ｇ(n))))∧(ｘ≠Ｇ(n)→y=0))は真ゆえにこれは1つのＰＡの全域関数αを定義するが定義どの再帰的関数とも一致しないから非再帰的全域関数,故にＰＡで証明不可能。ＰＡにこの命題(関数αを定義する)を公理として追加しＰＡを拡大する。(ゲーデル文を確認する関数を追加して拡大しても良い)この拡大されたシステムをＰＡ(1)とするとαはここでは再帰的。また以降計算理論でも再帰的と言うのはαをオラクルとして再帰的と考える。従って以降のクリーニ標準形はαを計算可能として加えたα標準形。この手続きは以降の拡大でも同様に行う。だがこの型の拡大を超限無限回続けるとやがてある可算順序数ΩについてＰＡ(Ω)はこれ以上はこの型の拡大は不可能になる。(ＰＡの命題は可算個だから非可算無限回の拡大はできない)このとき真なるＰＡ命題を確認するための関数がすべて証明可能だからこのシステムＰＡ(Ω)は完全になる。もし真だが証明不可能な命題が在ればそれからＰＡ(Ω)に含まれない関数を定義する証明不可能な命題が作れてＰＡ(Ω)が更に同じ型の拡大可能となるから。(証了)なお上のＰＡを完全化するシステムはある条件を加えて高階の集合論において実現できるように思える。またプログラムに従う計算過程は計算で使用される作業用メモリも含めて出現する変数をまとめて1つの変数Ｘ,順次実行される部分を関数Ｆ(Ｘ)と表すと計算過程はＦを1つのサイクルとするループからなる。1サイクル分のメモリも含め停止する場合は最後に出力部分がくるものをやはりまとめてＹで表す。計算過程はＦ(1),Ｆ(2),…,Ｆ(n),…と継続し変数のある部分がループからの脱出条件である述語を充たすとループから脱出し,幾らかの処理の後計算過程は停止する。ＰＡ命題∀xＡ(x)の確認プログラムはＡ(0),Ａ(1),…と確認していくがＡ(n)の確認結果について真なら1,偽なら0の値をとる関数Ｆが任意のｎに対し1をとる関数であるとあるシステムで保証される場合(例えば∀n(Ｆ (n)=1)が証明される場合)に∀xＡ(x)は確認できたと言えるし,反例探索の形で¬Ａ(m)であるものを追跡するプログラムに従う反例を求める計算過程Ｇが停止しないことがあるシステムで保証できる場合(例えば∀n(Ｇ(n)=0)または,ｍサイクル目で停止する場合Ｇ(m)=0,停止しない場合を1とすれば∀n∃x(ｎ＜x∧Ｇ(x)=1)証明される場合)に∀xＡ(x)は確認できたと言える。このような素朴な観察からある関数が存在してある条件を充たすことがＰＡ命題の証明や計算過程の停止性判定では有効である。また述語の充足集合は関数のグラフの合併集合と見なせる。上記の非再帰的関数の追加によるシステムの拡大はこの素朴な観察に動機づけられたものである。
Ｂ(x,y)はＡ(x)を確認するプログラムの記述に沿って入力ｘの場合にそのプログラムを走らせた計算結果を考えるときプログラムの記述とそれに従って行われる計算の結果までの変数値全ての履,のゲーデル数がｙであるときのみ真なる値をとる述語でありＡ(x)が帰納法で証明されるときはＡ(x＋1)の確認はＡ(x)の確認操作と帰納法が示すパターンに従って計算されるだろう。Ａ(x)⇔∃yＢ(x,y)だから∀xＡ(x)⇔∀x∃yＢ(x,y)。∀xＡ(x)が真のとき各ｘに対しＢ(x,y)を真ならしめるｙ(確認プログラムや各変数の履歴から特にエンド文を実行するまでのステップ数をｙの値とした場合ｙの値は一意的に決まる)の最小値をｙ=f(x)で表す。そのときＰＡで∀x(ｙ=f(x)→Ｂ(x,f(x)))であり,ｙ=f(x)なる関数の導入により∀xＡ(x)が証明可能になる。∀xＡ(x)⇔∀x∃yＢ(x,y)より∀xＡ(x)がＰＡで証明可能ならば∀x∃yＢ(x,y)もＰＡで証明可能先ほどのようにプログラムを固定してステップ数をｙの値とするとｙの値は一意的だからこの論理式はＰＡでの関数を定義し故に再帰的になる。∀xＡ(x)が真だがＰＡで証明不可能なとき∀x∃！yＢ(x,y)→∀xＡ(x)が成り立つから∀x∃！yＢ(x,y)がＰＡで証明不可能。公理に追加すると新たな関数を導入したことになり拡大されたＰＡでは∀xＡ(x)も証明可能になる。ＰＡの任意のΠk命題φ(Σkは否定のΠk文をとり偽を定義することになる)に対しφの確認プログラム(全数検査)が存在し,それはＰＡに埋め込む事ができる。一般には集合論においてｎ変数の関数値が全てのＸ=(X1,…,Xn)に対し有限値である時,φを真と定義する。
ＰＡの証明に関して最重要な述語は2変数述語Ｐrf(x,y)である。ｘは命題のゲーデル数,ｙはその命題の証明のゲーデル数のときのみ真である述語。従ってＰＡのある命題φが証明可能か否かはφのゲーデル数がｎのとき∃yＰrf(n,y)が真か否かできまる。否定を取ると∀y¬Ｐrf(n,y)¬Ｐrf(n,y)をＡ(y)とおくと∀yＡ(y)の形になる。ｎをゲーデル文のゲーデル数とするとＡ(0),Ａ(1),…,Ａ(k),…が全て真でありながら∀yＡ(y)が導出できないため∀yＡ(y)は証明不可能。否定は偽だから証明不可能。一般に真だが証明不可能な∀yＡ(y)は真だからどのｋについてもＡ(k)は真,ところが∀yＡ(y)は証明不可能となる。そこでω規則が導入されるならなら真なるΠ1文∀yＡ(y)は証明可能となり真なる∀y¬Ｐrf(n,y)は全て証明可能となり,これが証明されるゲーデル数ｎを持つ命題を偽,そうでないものを真とすると実際,真なる命題φのゲーデル数は∀y¬Ｐrf(n,y)ではないから∃yＰrf(n,y)となりφはあるゲーデル数ｙを証明のゲーデル数にもつ。これがω規則の導入によるＰＡの完全化であると思う。すると万事問題なしだがＡ(0),Ａ(1),…,Ａ(k),…が全て真と言うのを如何にして確認するのか1つでも偽が出て来れば幸いだが出てこないからと言っても永遠にやれる訳ではない。次の問題は如何にしてＡ(0),Ａ(1),…,Ａ(k),…が全て真を示すのか,少なくともその可能性を示すことに問題は移る。そこで僕の提案は関数の導入で,実際にＰＡの命題φの決定がそのままできる訳ではないが無限回の拡大過程を飛び越えある関数に集合論的概念で指示されるにしか過ぎない関数に実効的に操作可能なまで辿り着けばＰＡの命題が証明可能となることを示すことを目指す。実は1変数述語に行き着いて取り扱いが分からず数日間考えたが典型的Π1文∀x∃yＰ(x,y)では上手く機能しそうな関数の導入による拡大の手が使えず母式(英語ではmatrix;要するに量化子を含まない原始的述語)を考えざるを得ないと言うことになったがそれは1変数の述語φ(y)にｙ=f(x)を代入した形になると結論した。φ(f(x))は述語φ(x)について集合Ａ={ｘ|φ(x)}を考えるとf(x)∈Ａと言うことになりさらにＡの特徴関数をｃ(x)とおくとｃ(f(x))=1(1は真を表すとする。0は偽を意味する)1変数述語Ｂ(x)=(ｃ(f(x))=1)となり関数ｃ(f(x))の出番が生じるが典型的Π1文で上手く機能した形は適応できないためさらに1変数述語Ａ(x)を2変数化することを考えたがあるプログラム(以前,全数検査プログラムむしろ全数検査関数と呼んでいた)によるｘがｋの場合のＡ(k)が真であるプロセスの履歴(現れる全ての変数の履歴をまとめたものを)例えばゲーデル数ｙで表すとｙは特別な意味を持ち∀xＡ(x)が真なる場合,各ｋに対しＡ(k)が真なることを確認するプロセスｙ(k)が存在する場合Ｂ(x,y)は真と定義すると∀xＡ(x)⇔∀x∃yＢ(x,y)であり,後者は如何にしてＡ(0),Ａ(1),…,Ａ(k),…が全て真を示すのかに対する次のような1つの処方箋を与える。即ち,Ｆをωからωへの関数全体としたとき∀xＡ(x)の真を∃f∈Ｆ∀x(y=f(x)→Ｂ(x,f(x)))が集合論で証明可能なときと定義する事である。上のＡ(x)からＢ(x,y)の移行は以前考えた全数検査の考えが自然に吸収されて満足する形になっている。1変数の場合を考えて間もなく比較的初期のアイデアだったがｘがゲーデル数でなくｙだけが異様に複雑なプロセスのコード化としてのゲーデル数で別の形を求めたが上述したφ(f(x))では典型的Π1文で上手く機能しそうなアイデアが活かせないのと全数検査過程が入っているのでＡ(x)からＢ(x,y)へ移行したがＰrf(x,y)にも似た形をしている。Ｐrf(x,y)からＢ(x,y)を思いついても良さそうなものだがＰrf(x,y)のｘ,ｙはゲーデル数と言うことが障害になってたようで直後に似てると思ってＢ(x,y)の妥当性を感じてＰrf(x,y)からの書き出しになったのです。これで¬∃yＰrf(n,y⇔∀y¬Ｐrf(n,y))を各ｎについて考える事ができるようになり考察の範囲をΠ1に収められる。全数検査過程を典型的Π1文に適用するとＰ(x,y)の成立を確認するプロセスのゲーデル数をｚとおくとＰ(x,y)⇔Ｑ(x,y,z)。∀x∃yＰ(xy)⇔∀x∃y∃zＱ(x,y,z)ですがω×ωからωへの1対1対応を用いると更に∀x∃y∃zＱ(x,y,z)⇔∀x∃wＲ(x,w)で殆ど変化はなしです。12月6日,21:44のメールにあるようにΠk(2≦ｋ)文の場合には4変数述語が基本ですが∃tに対応する変数ｔが述語に出現しなくても任意のｔについて同じと処理できるが関数ｆ,ｇの2種について処理するのはまだよくは考えてないが多少面倒です。典型的Π1と同じアイデアでＰＡ論理式で記述できる範囲の新たな関数の導入で証明可能な真なるＰＡのΠk文は得られるでしょうし,Π1の場合に完成しておいて次いでΠ2と帰納法を適用しても良いのですが(集合論に拡張したＰＡでは便利なコード化は順序数になる気もするがゲーデル数のようには行かない気もするのは非可算性による部分がそれなりにある。ＰＡの述語Ｐrf(x,y)の集合版が作れるとかなり楽ですが)制限された集合論でのＰＡの拡張でも非可算ながら完全化可能と思われるが論理式で表現可能な集合論でのＰＡはＰrf(x,y)に相当するものが見つからないうちは共に集合論では1変数述語から始まってΠ,…Πk,…へと帰納法での証明になるだろう。だから,無難なのは集合論でＰＡ命題の真偽を定義し,1変数述語,Π1文を片付け述語Ｐrf(x,y)に頼る証明になる。
本論の目的はＰＡの真命題が数学の何処かで決定(証明)可能である事を示す事にある。以下,主に定義とアウトラインを述べる。ＰＡのΠn文∀ｘ1∃ｙ1…∀ｘn∃ｙnＰ(ｘ1,ｙ1,…,ｘn,ｙn)(Ｐは量化子を含まない)が真であるための条件はＳＰ={((ｘ1,ｙ1),…,(ｘn,ｙn))|Ｐ(ｘ1,ｙ1,…,ｘn,ｙn)が真}(真理集合を1つの隣接する(x,y)成分毎に組にしてｎ個並べた形)が任意の自然数のｎ個の組(α1,…,αn)に対してある(ｙ1,…,ｙn)=(β1,…,βn)が存在して((α1,β1),…,(αn,βn))∈ＳＰを満たすことである。この時ＳＰは真集合と呼ぶ。真集合Ａの要素((α1,β1),…,(αn,βn))に(α1,β1)→…→(αn,βn)なる順序を入れるとＡは1つの木構造を持つ。(＊,＊)→(α,β)とし,(＊,＊)から(αn,βn)に至る全ての道を考える。道(＊,＊)→(α1,β1)→…→(αn−1,βn−1)を固定し,これから終点である自然数ｍについて(m,＊)なるものを全く持たないとき道(＊,＊)→(α1,β1)→…→(αn−1,βn−1)→(α,β)なる道全てを消す。残る道の(＊,＊)→(α1,β1)→…→(αn−1,βn−1)→(α,β)なるものでαが0,1,…,ｎ,…即ち自然数全体を終点に持つものが存在するこれを真理木構造Ｂとする。次に残った道のうち道(＊,＊)→(α1,β1)→…→(αn−2,βn−2)を固定し,これから(αn−2,βn−2)に続くものがある自然数ｍについて(m,＊)なるものを全く持たないとき道(＊,＊)→(α1,β1)→…→(αn−2,βn−2)→…なる道全てを消す。このような操作を最後まで遂行したとき真集合の木構造は(＊,＊)からの任意の道は自然数ｍについてｘn=ｍなる終点(ｘn,ｙn)へと繋がっている。また残る点(ｘk,ｙk)についてｘ成分のみを並べた(ｘ1,…,ｘn)全体は自然数のｎ組全体になる。そこで各自然数αについて(ｘ1,ｙ1)(ｘ1=α)から始まる道でｙ1が最小のものをｆ1(ｘ1)であらわす。このようにしてωからωへの関数ｆ1が定義される。更に各自然数αについて(α,ｆ1(α))に続く(ｘ2,ｙ2)でｘ2を固定したとき最小のｙ2を対応させる関数ｆ2(ｘ2)はαに依存して唯一決まるからこのｆ2をｆ2(α)で表す。同様にして任意の自然数のｋ組(α1,…,αk)に対して関数ωからωへの関数ｆk＋1(ｘk＋1)が1つ定まるがこの関数をｇ(α1,…,αk)(1≦k≦ｎ−1),ｇ(φ)=ｆ1 そして集合Ｂから得られた要素((α1,ｆ1(α1)),(α2,ｇ(α1)(α2)),…,(αn,ｇ(α1,…,αn−1)(αn)))((α1,…,αn)は自然数のｎ組全体)全体Ｃを集合Ａから得られた単純真集合と呼ぶ。ここで汎関数ｇはＡから定まるが逆に,任意に汎関数ｇを与えてＣを作ったとき任意のＡ(⊃Ｃ)は真集合である。集合論において自然数上のｎ項関係Ｒは単に集合ωのｎ乗の部分集合であるだけだが集合論におけるＰＡのΠn文∀ｘ1∃ｙ1…∀ｘn∃ｙnＲ(ｘ1,ｙ1,…,ｘn,ｙn)が真である条件をＲの真理集合が上述したある単純真集合Ｃを含むときと定義する。またΣn文に関しては否定がΠn文だから否定文がΠn文として偽のとき真であると暫定的に決めておく。Π文の場合に考えたような汎関数ｇを用いた単純真集合Ｃの類似物は後程定義するつもりである。この集合論におけるＰＡの拡大的理論ＳＡは汎関数ｇで定めるωからωへの関数及びそのｇによる定め方はその記述を計算可能なものに限るとか基準を弛めるかで変化するが先ずはＰＡの真理集合が真集合か否かを決定できるものを想定する。ＰＡのΠn文∀ｘ1∃ｙ1…∀ｘn∃ｙnＰ(ｘ1,ｙ1,…,ｘn,ｙn)(Ｐは量化子を含まない)についてＳＰ={((ｘ1,ｙ1),…,(ｘn,ｙn))|Ｐ(ｘ1,ｙ1,…,ｘn,ｙn)及びΣn文の真理集合が真集合であるような命題全体を考えΓとする。またその内ＰＡで証明可能な真集合を持つ命題全体をχとする。Γ−χの要素全体をＰＡに付加すればＰＡを完全にできる。また前回の記事にあるようなゲーデル文の一種の追加を超限無限に行えば,ＰＡ命題が可算無限個しかないから高々可算個のゲーデル文の追加でＰＡを完全化できる筈である。(但し,ゲーデル文の追加による拡大は単純に可算無限個の追加で終わる保証はなくω回の追加の後,更にω回の追加,さらに…と続行しなければならない。ωまでの無限個のゲーデル文の追加だとＰＡの公理系のＲＥ拡大だから完全化はできない。)いずれにしても計算不可能な拡大が必要である。ＰＡ命題の述語の真理集合は述語の特性を無視するような一般論では全数検査的に求めざるを得ず上で単純真集合Ｃを考える理由は例えばΠ1文∀x∃yＰ(x,y)を関数ｆにより同値な命題∀xＰ(x,f(x))を考える事が出来ればｘ→∞での全数検査の結果の追求を回避できる事にあった。後記;僕の元の計画は全数検査を実行するための媒体自身の性質により全数検査結果を知る事にあった。上でＣの汎関数ｇ及びｇで定まる関数を導入したのはそれらを色々動かして媒体自身の性質を作る目的がある。真理集合が真集合の場合証明可能な命題の真理集合で真集合を近似統する事,統計力学のイジング模型と見なして調べる事にも活路はあるかも知れない。
ゲーデル文として獲得される可能性のあるΠ1文ΦはＰＡで証明不可能故に通常の意味で全域的な再帰的関数を定義しないが真であるから実は述語部分は全域的な再帰的関数を定義する。このような事実からＰＡを扱う集合論で用意すべき関数は結局,全域的関数を定義する組(x,y)全体を定める論理式及びそれらを含む集合を真理集合とする述語部分を持つΠ1文を定義するだけで良い。
次回は全体像(一応の完成版)を掲載する予定です。
本論の目的はＰＡの真命題があるシステムで有限時間での決定(証明)可能性を示す事にある。Π1文の場合を検討しているうちに一般のΠnやΣn文の考察は不要であると言う結論に至った。Π1文∀x∃yＰ(x,y)が真ならｘを固定したときＰ(x,y)を満たす最小のｙをとれば付随する関数が定まり関数ｙ=f(x)から真なる命題∀x∃y(ｙ=f(x))あるいは∀xＰ(x,f(x))が真なら∀x∃yＰ(x,y)も真と決まり関数の存在から命題の真が定まる。実際,ＰＡの真なるΠ1文を完全に掌握できたとしよう。Ｐr(x,y)はゲーデル数ｙはゲーデル数ｘの命題の証明とする。自然数ｎに対しf(x)=ｎなる定数関数とする。∀x∃yＰr(f(x),y)は∃yＰr(n,y)と同値だから任意のΠ1文で十分である。このことは1変数述語Ａ(x)に対して∀Ａ(x)を考えれば十分であることに繋がる。ＰＡで証明可能なΠ1命題全体をχとする。ΓをＰＡの真なる命題全体,ＰＡで証明可能なΠ1命題全体をχとする。Γ−χの要素全体をＰＡに付加すればＰＡを完全にできる。しかしΓ−χのＰＡ命題αが1つあればＰＡの公理として追加しＰＡを拡大する。このような反復拡大はω回で完了する保証はないから順序数に沿った拡大をしなければならないにしてもＰＡ命題全体が可算無限個しかないから可算順序数までの拡大でΓは尽きる。以上のメタ議論が遂行可能なシステムでＰＡは完全性を持つ。従って追加する命題αの存在を示せば主張は完結する。
定理;α∈Γ−χなるＰＡ命題αが存在する。
証明可能なＰＡのΠ1文は再帰的可算であり命題のゲーデル数の大きさの順に出力するプログラムが存在する。ｎ番目の命題∀x∃yＰ(x,y)に対し,Ｐ(n,y)を満たす最小のｙに対し例えばｎでの値をｙ＋1とする出力するプログラムに対応するＰＡのΠ1文∀x∃！yＦ(x,y)は証明可能であり関数ｙ=Ｆ(x)を定める。(Ｆの存在はゲーデル数を用いてキチンとしなければならないにしてもχはより小さいものにできる。)結局Π1文だけで完全化可能だからｋ≧2についてのΠk,Σkは不要。ただし最後の定理は実際ＰＡに入ってないと拙い。
本論の目的はＰＡの真命題があるシステムで有限時間での決定(証明)可能性を持つことを示す事にある。Π1文の場合を検討しているうちに一般のΠnやΣn文の考察は不要であると言う結論に至った。Π1文∀x∃yＰ(x,y)が真ならｘを固定したときＰ(x,y)を満たす最小のｙをf(x)(ｙが出現しないときは0と定める)とすれば関数ｙ=f(x)から真なる命題∀x∃！y(Ｐ(x,y)∧∀z＜ｙ→¬Ｐ(x,z))が作れる。これを簡単に∀x∃y(ｙ=f(x))と表すとこれから∀x∃yＰ(x,y)が真なることは明らかで∀x∀y(Ｐ(x,y)∧ｙ=f(x)→Ｑ(x,y))ならば∀x∃yＱ(x,y)も成り立つ。関数の存在から命題の真が定まる。実際,ＰＡの真なるΠ1文を完全に掌握できたとしよう。Ｐr(x,y)においてゲーデル数ｙはゲーデル数ｘの命題の証明とする。自然数ｎに対しf(x)=ｎなる定数関数とする。∀x∃yＰr(f(x),y)は∃yＰr(n,y)だからゲーデル数ｎが証明可能かを問う述語も表現され,任意のΠ1文で十分であるこてが分かる。このことは勝手な命題のゲーデル数ｘ=ｎに対して1変数述語Ａ(x)=∃yＰr(x,y)に対して∀Ａ(x)を考えても十分であることに繋がるだろう。ΓをＰＡの真なる命題全体,χをＰＡで証明可能なΠ1命題の集合を表す。またＰＡ命題Φ∈χのとき¬Φ全体をμで表す。無論全体を表すこともある。上に述べたようにΓ−χの要素全体から各々定まるωからωへのＰＡで定義される関数すべてを加すればＰＡを完全にできる。これは自明な指摘であるがΓ−χのＰＡ命題αが1つあればＰＡの公理として追加しＰＡを拡大する。ここでχを小さくとり始めれば必ずしもＰＡの拡大にはならないがχは拡大する。このような反復拡大は最初の極限順序数ω回で完了する保証はないから順序数に沿った拡大をしなければならないにしてもＰＡ命題全体が可算無限個しかないから可算順序数までの拡大でΓは尽きる。以上のメタ議論が遂行可能なシステムでＰＡは完全性を持つ。従って追加する命題αの存在を示せば主張は完結する。我々はχとしてＡ(x)を特徴関数とするＰＡで証明可能なゲーデル数全体の再帰的可算集合全体から始める必要はない。有限集合から始めても良いのである。但しχの命題はゲーデル数の大きさ通りに番号づけられている(順序同型に)同様にμの命題も番号づけられているが各々,ゲーデル数の大きさに従うように番号づけられていて獲得された命題αのゲーデル数によって並べ直す。(順序づけ関数を変更する)操作が極限順序数段階に達しても拡大されたχの命題全体が全てΓ−χが空集合でなければ即ちχＵμの各要素がＰＡのゲーデル数全体でなければ同じ操作を続行する。無論それまでにΓが尽きていればその時点で終了する。操作に付与された段階を示す順序数は可算順序数なので段階番号(順序数)と命題番号(上の順序づけ関数による番号)は必ずしも一致しない。途中得られた獲得命題αはその時点でＰＡの公理に追加される。
定理;Γ−χが空集合でないならばα∈Γ−χなるＰＡ命題αが作れる。
(証明)χの命題のゲーデル数の大きさに従って再帰的に番号づけられているから番号ｎから該当のΠ1文は再帰的に 再構成される。それが∀x∃yａ(x,y)とすると,∃yａ(n,y)は証明可能命題だから上の命題を真とする最小のｙ=ｆn(x)が存在する。そのｎに対しｆn(n)＋1を対応させると組(n,fn(n)＋1)がχのゲーデル数の大きさの順に生成する再帰的手続きが存在し,それを表現するＰＡの命題∀x∃！yＰ(x,y)が存在する。これをαとすれば良い。(証了)
本論の目的はＰＡの真命題があるシステム(集合論の一部分)で有限時間での決定(証明)可能性を持つことを示す事にある。集合論にペアノの公理系で定義された自然数全体はωである。Π1文の述語は単にω×ωの部分集合,関数はωからωへの関数全体を考える。以下この算術体系もＰＡと呼ぶことにする。Π1文の調べているうちに一般のΠnやΣn文の考察は不要であると言う結論に至った。Π1文∀x∃yＰ(x,y)が真ならｘを固定したときＰ(x,y)を満たす最小のｙをf(x)(ｙが出現しないときは0と定める)とすれば関数ｙ=f(x)から真なる命題∀x∃！y(Ｐ(x,y)∧∀z＜ｙ→¬Ｐ(x,z))が作れる。これを簡単に∀x∃y(ｙ=f(x))と表すとこれから∀x∃yＰ(x,y)が真なることは明らかで∀x∀y(Ｐ(x,y)∧ｙ=f(x)→Ｑ(x,y))ならば∀x∃yＱ(x,y)も成り立つ。関数の存在から命題の真が定まる。実際,ＰＡの真なるΠ1文を完全に掌握できたとしよう。Ｐr(x,y)においてゲーデル数ｙはゲーデル数ｘの命題の証明とする。自然数ｎに対しf(x)=ｎなる定数関数とする。∀x∃yＰr(f(x),y)は∃yＰr(n,y)だからゲーデル数ｎが証明可能かを問う述語も表現され,任意のΠ1文で十分であるこてが分かる。このことは勝手な命題のゲーデル数ｘ=ｎに対して1変数述語Ａ(x)=∃yＰr(x,y)に対して∀Ａ(x)を考えても十分であることに繋がるだろう。ΓをＰＡの真なる命題全体,χをＰＡで証明可能なΠ1命題の集合を表す。またＰＡ命題Φ∈χのとき¬Φ全体をμで表す。無論全体を表すこともある。上に述べたようにΓ−χの要素全体から各々定まるωからωへのＰＡで定義される関数すべてを加えさえすればＰＡを完全にできる。Γ−χのＰＡ命題αが1つずつ加えΓ−χが空集合になるまで追加を続ける。追加した命題は公理としてＰＡのχを拡大する。ここでχを小さくとり始めれば必ずしもＰＡの拡大にはならないがχは拡大する。このような反復拡大を超限帰納法により完遂する。ＰＡのΠ1命題全体は非可算個存在する。先ず自然数ｎについてだけ1をとり他の自然数ｍに対しては0をとる関数をＦnで表すと任意の関数ＧはＧ=ΣXiＦiと表せる。ここに各Xiは自然数。(X1,…,Xn,…)に対して辞書式順序を入れると全体としてωのω乗の非可算無限順序集合。χは先ず空集合にしておく。(基本的な公理図式もここでは無視する。)また(i,Xi)(iは自然数全体)を要素とする述語をＰ(X1,…,Xn,…)(x,y)で表す。∀x∃！yＰ(X1,…,Xn,…)(x,y)は上の関数ｙ=Ｇ(x)を表すＰＡでの述語である。このような述語が上で述べたαであり,αがχに追加される度に命題∀x∃yＱ(x,y)でＱ(x,y)の真理集合がＰ(X1,…,Xn,…)(x,y)の真理集合を含むものもχに加えられる。かくしてΓのΠ1文は尽きる。それに上に述べたように∃yＰr(n,y)に関する完全な情報によりΠ1文以外の狭い意味でのＰＡの完全な情報を手にする。従って狭い意味でのＰＡの真命題全てを知ることになる。述語を集合論に取った場合,Π1,Σ1文以外の命題はΠ1同様に関数から決められるが,1つの関数だけでなく他の関数ｇ(序文と後記参照)が要る。以上のメタ議論が遂行可能なシステムでＰＡは完全性を持つ。
Ｆの要素はΣＸ(k)ｅk(x)(ｋは自然数全体をわたる)。これに順序数ΣＸ(k)(ωのk乗)(ｋは自然数全体をわたる)を対応させることにより順序数で指示できる。また集合論で述語Ｐ(f)(x,y)={(k,Ｘ(k))|ｋは自然数全体}により関数f(x)を充足する。この対応によりＦの関数はそれを充足する述語を持つ。さらにω×ωの部分集合である述語についてＰ(f)(x,y)⊂Ｐ(x,y)に対し∀x∃yＰ(x,y)は真であり,それらのみが真であると定義することにより集合論における自然数についてのΠ1文の真偽値が完全に決まることは既に述べたところである。しかしより小さいシステムでＰＡの完全性は保証できる。ΩをＰＡのΠ1文でＦのある関数を充足するもの全体とする。またＰＡで証明可能なΠ1文の全体をχ(0)とおく。Ω−χ(0)が空集合でなければそれからΠ1文を1つとりφ(0)とする。ＰＡにφ(0)を 公理として追加したＰＡをＰＡ(1)とし,定理全体をχ(1)とする。この操作を高々,可算無限回繰り返すとやがてΩは尽くされΩ=χ(κ)(κはある可算順序数)となる。そしてＰＡ(κ)はΠ1完全。ゲーデルの証明可能述語Ｐr(x,y)に対し,f(x)=ｎ(ｎはＰＡの命題のゲーデル数)∀x∃yＰr(f(x),y)=∃yＰr(n,y)がΩで真=証明可能か否かはＰＡ(κ)で決定可能。よってＰＡの任意の命題について決定可能。即ち,ＰＡ(κ)でＰＡは完全になる。φ(0)は具体的にどのように表されるかと言えばゲーデル文(f(x)=ｎ(ｎはＰＡの命題のゲーデル数))∀x∃yＰr(f(x),y)=∃yＰr(n,y)は既に述べたものより小さな可算な1つの具体例になる。
かなり前進しました！気掛かりな点がかなり分かった。しかし集合論ＺＦでＰＡの真命題が証明可能は撤回する事になりそうですが,ＺＦがＰＡのゲーデル文を全て生成出来れば話しは別で自然数の1階のＺＦの命題は真だがＺＦで証明不可能なものがある。ＰＡ命題をＺＦで扱った場合はまだよく分かりません。モデルについての部分が未だ不明なので。考えをΠ1文 φ=∀x∃yａ(x,y)に集中しようと今朝がた思ったんです。Πk文は帰納法でΠ1文に帰着されそうなんで。そこでａ(x,y)の真理集合をΚとする。さてφが真であるとしてＫの要素でｘ=αのものが唯一の場合を考えるとＫの要素(α,y)についてｙはαの関数値と見なせる。ｙ=ｆ(α),一般にＫの要素は(x,f(x))(ｘ=0,1,…,n,…)からなるとする。このようなｆは非可算個ある。全部でωのω乗。ところでＰＡで証明可能Π1文は高々可算個だからこのようなＰＡΠ1文の述語の真理集合に関して関数ｆが定義されそれらも可算個だからｆは一列に並べられる。それらをｆ1,ｆ2,…,ｆn,…とする。関数ｇ(x)=ｆx(x)＋1とおくと真理集合Κの要素が(x,ｇ(x))(ｘは自然数全体)である述語をＰＡで定義可能である。述語ｙ=ｇ(x)の真理集合はそうなっている。(ｆ1,ｆ2,…,ｆn,…に対応する再帰的関数の中でｇを作り,表現可能定理でＰＡに対応するものがあるがそれをやはりｇで表す。)すると∀x∃y(y=ｇ(x))は真だが証明不可能なＰＡのΠ1文になる。同様のことは集合論ＺＦでも言えるから集合論ＺＦで証明不可能なＰＡの命題の存在はあり得る。その場合ＰＡの命題φの述語の真理集合 Ｌからφが真であるものをＰＡの公理系に付加する操作を高々可算無限回実行する手続きを集合論ＺＦのメタ理論で実行するとＺＦのメタ理論ではＰＡの真命題は全て証明可能となる。 問題点;上のｇはＰＡの中で本当に取れるか。上の事情からＺＦのモデルで全数検査関数値は同じとは限らない。理論の中で全数検査関数値が正しく全て定まるようにするには非可算個の真理集合の各々について述語の真理集合から真が分かる全ての冠頭標準形のうちＰＡに属すものだけを真と判断出来れば良いだけだが正しく真理集合の全数検査が可能な関数を定義できて真理集合がそのような全数検査関数値が真である述語の真理集合を持つ全ての冠頭標準形を表現できるシステムにおいてはＰＡの真命題は勿論証明可能。1階なら述語をＺＦに しても真命題は証明可能になる。結局,集合論ＺＦなんか可算モデルを持つくらいだから理論の中に本物の,つまりどのモデルにおいても非可算個の要素を持つを公理としてくっつける。どのモデルでもＶ(φ)の値が同じになるシステムがあれば僕の前回のレポートが生きるんですが実数を丸ごと含む集合論はその候補かも知れない。,Ｖ(φ)=真,Ｖ(φ)=偽の一方のみが証明可能は公理として相応しくない。
ＰＡ命題の定理を全て出力するプログラムが存在する。但しｙ=定数の関数の代入で命題が証明されるものはｙ=0 の代入で証明されるとする。するとｘ番目に出力される命題のｘに対してｘ番目の命 題命題を真とする最小のｙ=fx(x)が計算できるからfx(x)の値をｘ番目に出力するプログラムがあり,ｘ番目にfx(x)＋1を出力するプログラムも存在する。そのプログラムは再帰的関数として表現されるから表現定理により対応するＰＡの論理式Ａ(x,y)とする。ここでｙはｘ番目の出力を表す。すると∀x∃！yＡ(x,y)(∃！は唯一存在を意味する)はＰＡ命題でｙ=fx(x)＋1を代入すると真となる命題である。この命題をＰＡの公理に加える。このようにしてＰＡを拡大するが,次のステップでは出力される定理の先頭になるように定理出力プログラムを変えて,以下同様にしてＰＡを拡大する。
ωからωへの関数全体をＷとおく。ｆ∈Ｗ に対してＰ(f)(x,f(x))が任意の自然数ｘに対して真となるような述語Ｐ(f)を全て付加した集合論Ｔを考え,ＰＡのΠ1文である命題φ=∀x∃yａ(x,y)に対してＶ(φ)の値をａ(x,f(x))(fはωからωへのある関数)が任意の自然数ｘに対して真であるとき,かつそのときのみ真と定義することが最も合理的である。このときＰＡの命題∀x∃yａ(x,y)が真なら∀x∃yａ(x,y)⇔∀x∃yＰ(f)(x,y)である。但しｆを計算可能な関数ばかりにできないからやはりＴの不完全性は残るだろう。それで証明可能なＰＡ命題φに対応するｆ全体を考えるとそれらは可算個だからｆ1,…,ｆn,…(Ｔの証明可能な命題全体は再帰的枚挙可能な可算無限集合だから,上の関数ｆ1,…,ｆn,…も再帰的枚挙可能な可算無限集合)のように一列に並べられる。そこでｇ(x)=ｆx(x)＋1と定義するとｇはωからωへの関数で∀x∃yＰ(g)(x,y)をＴに公理として追加する。(ｇもＰＡで表現可能でないとＰＡにＰ(g)(x,y)なる述語が存在しないから∀x∃yａ(x,y)⇔∀x∃yＰ(g)(x,y)を満たすＰＡの述語ａ(x,y)も存在せず,真だが証明不可能なＰＡ命題は増えない)ｇが表現可能ならこのような拡大を(次は関数をｇ,ｆ1,…,ｆn,…と並べる,以下同様にする)高々,可算無限回行うと(ＰＡ命題全体が可算無限個だから非可算無限回追加できない)そのシステムにおいてＰＡは完全になる。自然数全体ωについてωからωへの計算可能(例えば計算機で)な関数の再帰的枚挙可能な可算無限集合のときｇも計算可能であることが示せれば再帰的計算可能な関数はＰＡで表現可能,更に∀x∃yａ(x,y)がＴで証明可能ならば,あるｆについて∀ａ(x,f(x))がＴで証明可能が示せれば帰納法で一般化して完了します。結局,真だが証明不可能の原因は∃yａ(α,y)(αは具体的で固定された自然数)を確認する際,ｙに0,1,2,…,ｎ,…と代入して行くとき真ならいつかは真と確認できるが際限なく待たないとダメで偽なら果てしなく続く。だから真と分かるのは際限のない代入結果でなく理論的にｙの存在が分かるときとするとそのような最小のｙがｙ=ｆ(α)で,逆にωからωへの関数ｆ全体の代入を考え任意のｘについてａ(x,f(x))の成立が理論的に言えるときだと考えましたが一昨日の流れでＶ(φ)の定義域を対角線論法で延長することが念頭にあったからでしょう。対角線論法は1つ余分を獲得しますが全体的な相関関係が見えて来ないので避けたかったがＶ(φ)のどこかでの答えが予め期待できないようで仕方なく使いましたがｇがＰＡに含まれないとａ(x,g(x))⇔ｙ=ｇ(x)がＰＡの述語にならないから新たにＰＡの真だが証明不可能な命題を獲得したことにならない。しかしこう書いてみるとｇはＰＡに入ると拙い感じがします。しかし普通,自明に∀x∃y(ｙ=ｇ(x))は成立しそうですがｇ(x)をｘ番目の双子素数の小さい方でなければ0とすると双子素数が無限にあるか有限かも分かってないから現状だと真理集合が定まってない。
先ほどは失礼しました。車中すっかり寝込んでしまったようです。計算機のプログラムではＤＯ Ｗhile〜文にあたるのが計算の理論で最小化で得られる関数で∀x∃yａ(x,y)=0(ａ(x,y)は計算可能)なときｘ=αを与えるとａ(α,y)=0を満たす最小のyを返す関数です。実はこの形のＰＡ命題を調べたとき計算の理論の話しは全く頭にありませんでした関数ｇを対角線論法で定義したときｇがＰＡで表現可能か否かの議論で漸く気づきました。ＰＡで表現されなくても集合論では表現されるし,対角線論法なしで未定義要素を埋める命題が集合論でもＰＡでも存在するからドンドン埋めれば命題全体に真理関数が定義出来ます。対角線論法で作ったｇは具体的で分かり易いゲーデル文になってるはずです。だから基本的には完了したと思っています。ネットの2回分のレポートとメールでここ2回分,前進と完了か？を読んで貰えば同感して貰えると思っています。全数検査関数の扱いで元のものを一応定義するか今は真理関数と言った方が良さそうな∀x∃yａ(x,y)が真である事とωからωへの関数ｙ=f(x)が存在して∀xａ(x,f(x))が真であることが同値になるを押し出した真理関数の定義を並置するか,結論に関与する後者だけにするかどうまとめるか真であると証明可能のやや曖昧な区別を少し厳密にするかなどです。いずれにせよ厳密に書く必要はないと思いますから枚数も数ページにしかならないと思います。
変数係数の1階偏微分方程式の局所解は逆関数の定理で変数変換(しかもｕxの係数関数が0でなければヤコビ行列の第１列は関数でそれ以外の成分は下三角に取れると思います。上三角に取っても良いしかなり勝手に取れる)それで関数係数1階偏微分方程式は変数変換後はＵxかＵyの係数を零化できるからこれを解く。2階の場合(ａUx＋ｂUy)x＋(ｂUx＋ｃUy)y−(ａx＋ｂy)Ux−(ｂx＋ｃy)Uyが純2階になりますが1階偏微分の部分はｄUx＋ｅUy＋ｆU＋ｇに回して更に未知関数Ｇを入れて(ｄ−ａx−ｂy)Ux＋(ｅｂx−ｃy)Uy＋ｆU＋ｇ＋Ｇ=0 を先ず解いてUを(実際はUx,Uyを)Ｇで表す。(Ux,UyはＡＧ＋Ｂの形になると思います。)1階部分の解は(x,y)⇔ (Ｘ,Ｙ) なる変換でＸ,Ｙで先ずは表されていますが,x,y変数に戻す(実際に,式の形でx,yには表せないが),そして純2階のUx,UyをＡＸ＋Ｂの形のx,yの関 数で表し,今度は未知関数をＧとして解いて最初のUをＧで表した式に戻す。3階,3変数以上にも適用出来そうです。と言う事で関数係数偏微分方程式は境界条件を無視すれば局所解を持つ。(僕にしては思いがけないエラーがあって瓦解してしまうかも知れないが。)線形偏微分方程式以外は全て非線形偏微分方程式だから扱ったのは定数部分の関数が0なら解の和は解となります。係数に未知関数が含まれる非線形,例えば関数係数の5変数関数Ｆに対してＦ(x,y,Ux,Uy,U)=0 の解Uの解なんてUを固定されたある2つの関数ｆ(x,y)とｇ(x,y)に対して例えばｔ=0のときｆ,1のときｇとなるようなパラメーターｔを含むＦ(ｔ,x,y)で中間値の定理であるｔでＧ(Ｆ)=0 となるような方法をうんと複雑化した方法を考えるとか可微分多様体の微分同相局所座標みたいな感じですかね。ナビエ・ストークスみたいなものだと連立だから未知関数がU,V,Wあった気がしますが取り敢えずV,Wはパラメーター扱いして大きめにUの範囲を決めておいてｖ,ｗの条件を加味して行くのもありそうだがV,Wが食い込み激しく話しにならないのかも知れない。
2変数の場合に戻るともとの偏微分方程式はａＵx＋ｂＵy=ｃ,変数変換Ｘ=Ｘ(x,y),Ｙ=Ｙ(x,y)の後,偏微分方程式は(ａＸx＋ｂＸy)ＵＸ＋(ａＹx＋ｂＹy)ＵＹ=ｃとなる。それで1つ消去しようとするとａＸx＋ｂＸy=0 になるようにＸx,Ｘyを取る方向で考える。この式ではａ,ｂ,Ｘはすべて独立変数x,yの関数と考えられているが局所的にはx,yの方を独立変数Ｘ,Ｙの関数と考えられる。そう考えたときＸx,Ｘyとx,yをＸ,Ｙで偏微分した式で表す事に行き着く。幸いにも Ｊ=ＸxＹy−ＸyＹx とおくとＸx=Ｊδy/δＹ,Ｘy=−Ｊδx/δＹと計算出来るからａＸx＋ｂＸy=0 は ａδy/δＹ−ｂδx/δＹ=0となる。ここでＸ,Ｙで表した式をx,yに変数変換すると考えてａδy/δＹ−ｂδx/δＹ=0 を満たすように x,yを取り直すとδＵ/δＸの係数を0 に出来る。従って最初のx,yと最後のx,yは異なる。さ てこの方法では一般のｎでは厳しい。変数変換の結果,2変数だとａＸx＋ｂＸy=0 を満たすＸの存在をａδy/δＹ−ｂδx/δＹ=0 をみたすx,yの存在に置き換えたが3変数以上だとこんな計算ではすまない。(余因子行列はn=3でも面倒)直接ａＸx＋ｂＸy=0をみたすＸの存在を示す方向が望ましいが,次のようにやれば良い。Ｘy=1,即ちＸ=ｙ＋Ｗ(x)とおいてａＸx＋ｂ=0 でＷ(x)を決め,Ｙはヤコビアン≠0 になるように適当に取る。斯くして2変数を解くと3変数の場合,変数変換Ｘ=Ｘ(x,y,z),Ｙ=Ｙ(x,y,z)Ｚ=Ｚ(x,y,z)の後,偏微分方程式の係数の1つはａＸx＋ｂＸy＋ｃＸz=0,Ｘz=1,即ち,Ｘ=ｚ＋Ｗ(x,y)とおくとａＸx＋ｂＸy＋ｃ=0 ,zを定数扱いすると2変数の場合に帰着する。こうして1階の偏微分方程式は解の有無を論じ得る形になる。2階偏微分方程式に関しては未知関数Ｇを導入してａＵx＋ｂＵy＋Ｇ=ｃ,ＡＵxx＋ＢＵxy＋ＣＵzz−Ｇ=0とおき前者からＵをＧで表し,後者に代入すると未知関数Ｇに関する2階偏微分項のみからなる2階偏微分方程式が得られる。従って2階偏微分方程式の問題はＡＧxx＋ＢＧxy＋ＣＧ zz=Ｅ(ＥはＧを含み得る)を未知関数Ｇについて解くことが問題。
小近傍で係数を定数とみなして定数係数偏微分方程式の小近傍解を求められるとする。集積点を持つ位,可算無限個のデータが有れば解析関数なら一致の定理で集積点の近傍解が得られるはずですが無限回微分可能でも一意に関数は決まらないですよね。各点毎の積分定数の自由度は目指す非線形偏微分方程式に代入して決まるとして無限個データが有れば取り敢えず級数は決まりそうですが無数にデータを満たすものが存在する可能性があると言うことですね。無限回微分可能でも確定部分があるものはその近傍では解析的てことですかね。以前,灘の控え室でｙ'=3(xの−2/3乗)の解が至るところ分岐すると例示したことあると思いますがこの場合至るところ解析的解がないと言う事のようだから至るところ分岐する解析的でない解があり得るわけですね。データとしてどんな点を取るかによるのか も知れませんね。
携帯で2階非線形偏微分方程式を検索すると何故か1階非線形偏微分方程式が書かれていました。ハミルトン・ヤコビの正準方程式は1階非線形偏微分方程式だそうで解は完全積分で非常にきれいに表せるのだそうです。解析力学か何かその周辺ぽいですね。そもそも2階非線形偏微分方程式の一般論を考えて変数変換しても簡単になりそうになく偏微分方程式論は1階は変数変換で原理的には解けて,2階からが本当の始まりだとメールした後,以前,可能性として書きましたが気が進まない局所定数線形偏微分方程式の解の貼りあわせ位しか手はないかと考えあぐねて携帯検索すると意外なヒット！始まりと思ってた2階にしてもミレニアム問題の1つナビエ・ストークス方程式は2階非線形偏微分方程式だそうで解の存在問題が100万ドルらしいです。何か前回メールで解析関数と無限回微分可能関数の違 いに想いを馳せていたら基礎論の無限大近辺で分岐するモデルを連想しました。偏微分方程式論は僕が思ってたよりキツイみたいです。この分野は空き家だらけと思ったんですが頑丈な鍵つきかも知れませんね(笑)
《命題》ｄ次元空間において一般的な位置にｎ個の点からなる集合Ｓがあり,ｆ(Ｘ)=0がｄ−１次元の超平面を定めるとき,ｆ(Ｘ)＞0に含まれるＳの点全体をｆ(Ｘ)＞0で定まるＳの部分集合とする。このような部分集合の個数はｎ点の取り方によらず一意に定まる。この個数をＦ(ｄ,ｎ)で表すときＦ(d,n+１)−Ｆ(d,n)=Ｆ(d−１,ｎ)が成り立つ。 《証明》ｄ=１のとき明らか。ｄ＞１としｄ−１まで真とする。ｄ次元のときｎ=１,２,３のとき明らか。ｎ(≧３)まで真と仮定する。またＧ(ｄ,ｎ)をＧ(ｄ,ｎ)=Ｆ(ｄ,ｎ+１)−Ｆ(ｄ,ｎ),Ｈ(ｄ,ｎ)をＨ(ｄ,ｎ)=Ｇ(ｄ,ｎ+１)−Ｇ(ｄ,ｎ)と定義する。仮定よりＧ(ｄ,ｎ−１)およびＨ(ｄ,ｎ−２)は定まっている。Ｓがｎ+1点のときｎ+1個目の点Ｐをかってにとる。Ｐを除くｎ点のなす集合Ｖについてある超平面でＸとＹに分割されたとする。(その際,境界をなす超平面がＳの点を含むとき少し平行移動してＳの同じ部分集合を定めかつＳのどの点も含まないようにできるからＳのどの点も含まないものだけを考えれば十分)このときＶ=Ｘ∪Ｙなる分割を与える超平面全体のなす集合をＺとするとＺは開集合(分割を与える超平面はＶのどの点も含まないものだけを考えても良いから)。点ＰがＺに含まれるとき、Ｐを含めて考えるとＳ=Ｖ∪{Ｐ｝だからＳ=Ｘ'∪Ｙ=Ｘ∪Ｙ'、ただし Ｘ'=Ｘ∪{Ｐ｝、Ｙ'=Ｙ∪{Ｐ｝。よって新たにＸ'、Ｙ'の2つの部分集合を数えなければならないが、この2つは下に述べるように、常に点Ｐを含む部分集合の数え上げにおいて数えられる。また点ＰがＺに含まれないとき、Ｐを含めて考えるとＳ=Ｘ'∪ＹまたはＳ=Ｘ∪Ｙ'の一方だけが成り立ち部分集合の個数は増加しない。点Ｐは上に述べたものとし、Ｐを中心とする半径の十分小さい超球面に接する超平面全体で部分集合はＧ(d,n)個だけ増える(この段階では点の取り方に依存する)Ｖからかってに１点Ｑをとり,この点を除いて考えるとＰを中心とする半径の十分小さい超球面に接する超平面全体で部分集合はＧ(d,n−１)個だけ増える(仮定より点の取り方に依存しない)そこで上の議論をなぞるとＰ,Ｑを中心とする等しい半径の十分小さい超球面に同じ側で接する超平面全体で部分集合はＨ(d,n−１)個だけ増える(この段階では点の取り方に依存する)。ＰＱに垂直でＰを通るｄ−１次元のアフィン部分空間にｎ+１点すべてを正射影するとやはりその像であるｎ点の任意の近傍から一般的な位置にあるようなｎ点が取れるから考えている部分集合の個数を変えない範囲で像のｎ点が一般的な位置になるようにＶの点を取り直せるから,点Ｐの像(Ｑの像)を中心とする半径の十分小さい超球面に接する超平面全体で部分集合はＧ(d−１,n−１)個だけ増える。よってＨ(d,n−１)=Ｇ(d−１,n−１)。右辺は点の取り方に依存しないから左辺もそうであり,Ｇ(d,n)=Ｇ(d,n−１)+Ｈ(d,n−１)で右辺の2つの項は点の取り方に依存しないから左辺も点の取り方に依存しないで定まりＦ(d,n)+Ｇ(d,n)=Ｆ(d,n+１)よってｎ+１点の場合も真であることが示された。《証明終了》
ＰＡの命題は冠頭標準形と呼ばれるＱ1ｘ1,…,ＱnｘnＰ(ｘ1,…,ｘn)の形で表せる。(ここにＱ1,…,Ｑnは量化子,即ち∀または∃,ｘ1,…,ｘnは変数,Ｐはｎ変数の算術的述語(関係))ｎ組の自然数全体は自然数の1パラメーターｔで順序づけられる。ｔ番目のそれを(ｘ1(t),…,ｘn(t))で表す。命題の1つをφ=Ｑ1ｘ1,…,ＱnｘnＰ(ｘ1,…,ｘn)とおくとき,全数検査を実施する反例探索プログラムに従って計算機を走らせる。但しここでの計算は反例が見つかるか否かによらず永遠に行われるとする。Ｖを値集合としＶ={1}と初期設定する。ｔ回目の探索が偽であればＶをＶ∪{0}に変更し,見つからなければＶ∪{1}に変更する。(Ｖのまま)パラメーターｔに於けるプログラムの実行結果を踏まえて関数Ｆ(t)=Ｖ(t)とおくと,反例が見つかったとき Ｆ(j)=Ｖ(t)={0,1}だからＦ(k)=Ｆ(j)(k＞j)となる。そこでlimＦ(t)=∪Ｖ(t)(Ｖ(t)はｔ回目のＶ)(t＜ω)とおくとこれらの極限値は一意的に定まる。もし2つのモデルで異なる極限値を与えたとするとあるｔについて2つのモデルでφの述語部分Ｐ(ｘ1(t),…,ｘn(t))の真偽値が異なるがＰは自然数に於ける関係だからそのようなことは起こらない。(2つのモデルの自然数全体は標準モデルで同型だから)従って2つのモデルでの上の関数Ｆの極限値は一致する。ＰＡにこの極限計算関数(計算機で述べたが整数値をとる無限数列の和集合で表せるから)及び極限値を定義出来る集合論の一部分を加えた第１階形式体系をＳとおく。そこでＰＡのある1つの命題の真偽を確定する証明が存在しないとするとφが真でも偽でも無矛盾であるから。真とするモデルと偽とするモデルが作れるが, これはφの真偽値(実際は上の関数Ｆの極限値が0か1か)がモデルによらず一意的に定まる事に反する。よってφの真偽値(実際は上の関数Ｆの極限値)を判定する証明が存在する。
Ｖは前のように各段階で出力された結果の無限和集合とする。Ａを自然数についてのある性質で∃xＡ(x)(性質Ａを持つ自然数ｘが存在する)という命題を考えるがこの命題は偽でありしかも偽であることの証明はないとする。この時,性質Ａを持つ自然数ｃが存在するという主張を封じるためｘについての全数検査をする。いくら大きな自然数Ｎまで検査してもｃはそれよりもっと大きいと逃れられるがこれだとｃはどの自然数Ｎよりも大きい必要があり,そのような自然数ｃは存在せず全数検査の実行結果Ｖは偽を意味するものとなる。次に∀x∃yＢ(x,y)(任意のｘに対してあるｙが存在しＢが成り立つと言う命題)が偽であるとし,これにも全数検査を実施する。∃yＢ(0,y),…,∃yＢ(n,y),…のどれか1つは偽と言う反例を出せば良いが1つの反例を出力するにも先程の∃xＡ(x)のＶが偽を意味する出力をするのと同様,今度は反例1つ出力するにもｙについての無限回の検査が必要でしかも全体ではｘについても自然数全体に渡るチェックが必要だから全数検査でも1つの段階では反例は出せず集合論的にはω×ω回,上手く順序をつけ直してω={0,1,…,n,…}回の全数検査の結果,各段階での結果の無限和集合(この場合は結果をω×ω回の和集合に翻訳して表すのが適当でｔ回目のチェックが(α,β)回目に翻訳されるとしてＢ(d,e)の真偽が検査項目として偽ならＶ(α,β)={偽},真ならＶ(α,β)={真}としてＶ=∪Ｖ(α,β)((α,β)∈ω×ω))としてＶが定まる。困難であっても反例探索の全数検査によりＶは一意的に定まり高々2要素集合だから真偽まで決定するように思える。(集合論的にはそうだが実際には無限和集合の要素は分からない)ＰＡのある命題φが真であるとすると全数検査の結果として得られるＶもφが真なることを表すことになり,Ｓを1階の集合論としたとき,全数検査のプロセスをＶへの関数として書き直せばφのＳでの証明が得られる。(仮定よりＶが真を意味することが分かっているから)従ってこの間のメモは同語反復でありφが真ならＶも真を意味するはずと言うだけであり真で証明不可能なφはＶが一意的でない場合があることを導く。解析的には全数検査の各段階の結果を形式的には関数で表せる。Ｖのかわりに無限数列の和,或いは0から∞までの積分を用いる事が出来るが非常に簡単な場合でさえ殆ど実行不可能に見える。実際に命題φの証明はφの個性を反映した概念の採用が適当でしょう。正しいとして(余り自信は ありません)不完全性定理との関係は少し興味があります。
１.φをＰＡの命題,Ｔを真偽値の集合{真,偽}とすると集合論的関数ＦでＦ;{ＰＡの命題集合}→Ｔかつφが真ならＦ(φ)=真,φが偽ならＦ(φ)=偽を満たすＦが存在する事。
２.(示したかった事)ＰＡの命題φが真ならＳに於いてφの証明が存在する事。(証明が存在しなければφでも¬φでもＳで無矛盾だからＶが一意的でなく,(Ｖが2通りあるから)矛盾。故に証明は存在する。と書きはしたが,この辺りはＳのモデルの自然数部分が全数検査で真偽値を決めたモデルを共通に持つようにＳの公理系をとることが可能でないとダメだと思えます。
ＰＡで例えば∀xＰ(x)の真偽値をＶn={Ｐ(0),…,Ｐ(n−1)}として Ｖ=Ｕn＜ωＶnとおくとｍ＜ｎならばＶm⊂ＶnだからＶは一意的に定まりＶ={真}の場合にのみＶは真を意味して∀xＰ(x)は真であるべきと言うのがω規則なんで僕の定義した関数のＶと基本的に同じです。集合論の中の認識者にはＰＡの全命題についてＶの値が分かるはずですが外からは分からない。ＰＡの公理系と推論規則を保存するＶの値の割り振りはモデル理論によると無限個ある。だから1階の集合論の内部でＰＡの命題φに対して上のＶから定まる真偽値を定める関数をＦとするとＦ(φ)=Ｖが定める{真},{偽}(Ｆを1階で定義する為にはφをφのゲーデル数に置換する必要がある)なるＦとその値の一意性を定義する集合論の一部を公理として加えると集合論内部ではＶの値は真か偽か確定するのでＰＡの各命題φの真偽 値が一意的に定まりＰＡのモデルは一意的でありＶの値の割り振りは一意的とやってますが,ここは全く誤りで集合論の内部の認識者にはＰＡは完全に定まるが外部の我々から観ると結局正しいＶが分かればＰＡは完全になると言う自明な命題になってしまいます。そこで正しくＶの値を決めるには一種のゲーデル文Ｇ(ＰＡでは決定出来ないが真である)を追加しそのＶを真とし,それで推論規則に従って自然に定まるＰＡの一部分のＶが定まり,さらにＧ＋ＰＡの公理系で拡大されたＰＡ(ＧはＰＡの論理式だから拡大と言ってもＰＡの論理式は増加しない)に対して再びＧに相当する命題のＶを真としといった操作を可算無限回やるとＶは完全に定まる。定まらないＰＡの命題がいつまでも残っていれば公理系に付加するゲーデル文が非可算個あることになるから可算無限回でＶの真偽値の割り振りは完了する。それで付加したゲーデル文全体を公理系に加えるとＰＡは完全化します。だからある意味でＰＡは完全化して目標は達成された事になる。ゲーデル文に頼らないでこのＶの割り振りを実行するには次のようにやればよい。例えばＶの真偽値が既に割り振られた範囲外の命題が存在するとする。その中から仮に∀xＰ(x)を取る場合{Ｐ(0),…,Ｐ(n),…}がすべて真を与える命題を集合論内部では取り出せる。集合論ではそのような操作が許されると思います。自然数に対する命題∀xＰ(x)は真です。ＰＡの命題にこの命題を加えて但しこの∀xＰ(x)から演繹されるＰＡ命題φについ てのＶに真の割り振りをします。∀xＰ(x)→φは集合論での推論規則に従う事になります。そして∀xＰ(x)→φの形の論理式だけ公理系に加える。このような集合論にはあるはずの命題を付加する操作をＰＡの命題φのＶの真偽値の割り振りが完了するまで遂行する。この場合付加する集合論での命題Ｒは存在論的でＶの値を割り振る為のガイド情報として導入するだけです。残る集合論命題の真偽値の割り振りは存在します。そこで公理系は集合論で良い事になります。集合論はＰＡを完全化する。(真偽決定可能で真命題のみ集合論内部で証明可能,但し集合論の無矛盾性は仮定して,ゲーデル文の追加もＰＡの無矛盾性は仮定する)(本文終了)。
追記;上記が正しければ8月発表分もまとめてもう少し厳密な議論をしようと思っています。正しくてもいつまとめが完成するか明言出来ませんが。ゲーデル文の追加でフェファーマンがＰＡの完全化をしたと言う記事を読んで,多分北田氏の本で結果だけ見て,昔もそんな話しがあったなくらいでした。と言うのはゲーデル文は特殊な形の命題だからムリだろうと頭ごなしに決めつけてたのですが先日,穴埋めが必要な真なる証明不能命題はＰＡ命題が可算個しかないから非可算無限個はないのは明らかで穴埋め作業は可算回で完了せざるを得ないと気づきました。後者はＶが真の命題を付加する必要があるから集合論において真と分かる∀xＰ(x)集合論内部でＰＡ命題の片は付くと言う事から当初公理としては存在命題は避けたいと思いましたが他に適当な手段もなかったので。後で集合論に吸収されるから存在命題の特殊な公理系は消去できますし再登場が必要でも仕方ない。正しいなら誰かとっくにやっていそうな簡単さです。後者は一応集合論内部でＰＡ命題は決定可能であると言う僕の長年の課題でしたがやはり集合論内部では可能とした部分が問題ですがパーソナルレポートとして公表します。
以下Ｖは,8月のレポートにおけるものである。ＰＡの各命題φとその真偽値Ｖについて,1.先ずφに対してＶが集合論Ｔ(Ｔにおいて自然数全体はＰＡの公理系から定める。またＰＡの論理式,推論規則を含む。)において一意的に決まる。従ってＶ(φ)でその真偽値を表す。2.1.の関数Ｖ(φ)の関数値についてＰＡの公理式φについてＶ(φ)は真,またＶ(φ)の真偽値はＰＡの推論規則と両立する事を次のように定める。3.Ｗ={φ|φはＰＡの命題全体}とおく。Ｗの各要素の真偽値を次のように定めて行く。先ずφが公理式ならＶ(φ)は真,このようなものφ全体をＷ(0)とおく。次にＷ(0)の要素φからＰＡで演繹される命題ΦについてＶ(Φ)の真偽値を真とする。 このようなものΦ全体とＷ(0)の要素全体を併せたものをＷ(1)とする。Ｗ(1)に含まれる論理式に関するＶの値はＴでの値と一致する。 Ｗ−Ｗ(1)が空集合でない場合,この要素αで,ＴにおいてＶ(α)が真なるものが存在すればＰＡにαを公理に加えたものから演繹されるＰＡの論理式のＶの真偽値は真とする。この値がＴでの値と一致する事はＴにおけるＶの定義より言える。以下同様の操作を反復する。こうしてＰＡと付加されたＰＡの論理式α,…からＰＡの各命題βに対してＶ(β)の値はＴでのＶ(β)と一致する。ＴのＰＡ命題以外の命題γに対してＶの延長をとるとＴのモデルが定まるがＴの自然数全体とＰＡ命題に対する関数ＶがＰＡ命題上では一意的。故にＴにおいてＰＡの真命題は証明可能。
後者は,非構成的でいわゆるゲーデル文は有っても無くても構わない。要するに集合論Ｔで決まるＶ(φ)がＴ内部のＰＡ及び必要ならＴにおいて真であるがＰＡから演繹されないＰＡの命題α(実はＰＡ及びその拡大体系のゲーデル文)を次々に付加してＰＡを拡大して行くわけですがＰＡ及びその拡大体系におけるＶ(Φ)の値がＰＡ及びその拡大体系から演繹される命題Φは真であると言うことからＰＡ及びその拡大体系での真偽値と一致します。ＴにおいてＰＡのゲーデル文は定義可能であり,不完全性定理はＴでのＰＡに関する定理として発見可能なはずですからＴの内部で前者の議論は可能なはずで従ってＴにおいてＰＡの命題φについてのＶ(φ)の真偽値は求められるはずです。Ｔでゲーデルの議論を展開してみる事は大丈夫だと思いますが1階の集合論Ｔでやれるかが多少心配。従って,ＰＡの真命題φについて集合論Ｔ＋φのモデルの存在証明は可能なはずですが,Ｔ内部で実行できず(Ｔのモデルが在ると言うことはＴが無矛盾を意味するのでＴのモデルをＴで作れるとＴ内部でＴの無矛盾性を証明する事になり第2不完全性定理に反するから。)Ｔの拡大クラスで実行可能なはずです。
命題Ｐとその否定¬Ｐの理想的反例探索プログラムを同時に走らせたとします。ともに停止しないってことはともに真であるから矛盾。ともに停止するならやはり矛盾です。だから一方だけが停止して従って真であるのはＰであるのか否定の¬Ｐであるのか分かります。無論,普通の反例探索プログラムだとＰと否定の¬Ｐともに実行を停止しない場合があります。ゲーデル文Ｇは∀ｘＱ(x)の形だがその構成の仕方からＱ(0),Ｑ(1),…,Ｑ(n),…には永遠に反例が見つからずそのことからＰＡ(第1階ペアノ算術)にはＧの証明は存在せず従って証明不可能また普通の自然数のモデルで¬Ｇは偽だからＰＡで¬Ｇが証明されるとどのモデルでも¬Ｇは真であり上の事実に反するから勿論証明されない。自然数論の理論Ｔのある命題φがω全体で反例を持たないと実質的に翻訳できるＴで証明される命題が無ければ実際反例探索プログラムはω全体を掃過できないから停止せずφは真でもＴで証明されない。ω全体を掃過する理想的な反例探索プログラムの実行を代行するω上の関数の存在をＰＡに付加しても無矛盾なら数論の真偽は確定する。関数の実行結果が取り出せるものについては証明もできる。箱玉系についての竹野内氏のソリトン方程式を用いた結果はそのような例になっていると思えるがケースバイケースでしか結果は得られないにせよ取り敢えずω全体を掃過する理想的な反例探索プログラムの実行を代行するω上の関数を何らかの形で記述すること(以前述べたように例えば計算機のメモリ関数系)。其から少しずつ結果を出すことが組織的な探求には重要だと思っています。
プログラムを計算機において実行する計算過程を考えるとそれは決定論的物理過程でもあり,もしメモリ量などに制限を設けなければ各メモリ値は時刻ｔの(階段的)関数になる。そこで例えば計算機の電子回路網を支配する電子工学および物理的法則による微分方程式系などによりメモリ関数系を決定出来ないかと考えられる。それが可能でメモリ関数のｔ→∞での極限値が判るならプログラムの停止性判定ができる。勿論,プログラムを実行する道具は電子計算機である必要性はなく計算過程の媒体となりそこで実行される計算プログラムの内容とは独立に媒体において成立する独自の関係などにより,特にその計算過程の停止性判定が出来ればよい。数論の反例探索プログラムの停止性が判定出来れば数論の命題が決定出来る。だからここで提案しているのは数論の問題から関数の極限値の問題への移植である。既に提案されていても不思議でないし,私自身は見かけたことがないので上手く行かない決定的理由があるのかも知れないが敢えて提案する。計算論的な有限決定的枠組みで考えてはいない。例えばゲーデル文はプログラムを走らせても停止しないことは判明しないが高階の算術体系では判明する。論理的には集合論のフルセットで考える。また全ての場合に適用可能な方法であることは要求しない。