1. ３つの作業仮説
    1. 基礎論間の対応図式の成立
      2. 計算量を軸とした数学基礎論の対応図
      Logic 代入 &外延 &内包 &述語 　⊃(計算量)命題
      Arith. 書換系 &値域 &意味、関数 &算術公理 ⊃計算
      Comp. Algorism (のゆるす範囲＊）

      		NDTM [ Oracle の示すこと …　 ]
      Set&Model
      		[Set theoryで主に論じられたこと ]
      ＊（算術に楕円関数など外から見てのみ妥当では非純粋算術? ）
    2. ブール回路計算量 ブール関数を下の３つの立場から関数の性質を求める
      1. 大域的 ∨,∧-topやmonotoneなど全てのleavesに関係する概念
      2. 局所的 あるnodeから下のtree(=term)のなす構造
      3. 超局所的 個々のleafに固有の性質top,node,leafの間の距離などの、

        4. 直接は他に伝わらないもののみを使う
    3. ブール代数の基底とBdd.Arith.の選択公理を通じた結び付きが＃の真の姿と考える。

      4. ブール代数2ωの部分空間の基底の濃度をsharply boundedな数と考えたものを導入拡大すれば、
      ブール関数の不変式を通じて計算量にガロア理論の可解群に似たものが構成できる
  2. 純算術的問題
    1. ”算術的外延公理”をつくる
      1. 公理の階層　述語の型だけでなく互いの要素を対応させるのに必要な時間の関数の階層によって定義するには、どうするべきか。

        2. 少なくとも次数同型 =Oと多項式同型 =P,さらには原始帰納同型 =Pr,ω-重帰納同型=ωも。
      2. 公理の型　∀t(∀x∈t(Δ(x)⇔Γ(x))⇒Δ＝Γなどの制限の仕方やE-logic風など。
    2. ”算術述語の集合で強い算術PA2,HA2では素数を表現するpredcadeの集まりの外延性をIS2で証明できないものを示せ”

      3. これはD-述語とE-述語の外延が等しいかどうか、
      つまり任意の素数を表わす述語をP,P'としたときにIS2の保守拡大の４階理論で
      { IS2⇒∀x≦|t| (P(x)⇔P'(x)) }そのものを論じることで(素数述語の銀河系とでも)
      もしD(x)・E(x)を双PTC関数帰着可能きびしくは1対1のPTC関数で,
      すこしゆるめて∃Φ,Ψ∈(monoPTCfanction)(Φ:D→E&Φ:E→D)と解釈するなら
      ∀x≦|t| 型の外延公理(E-logicの公理∀x(Ex→(x=a∧x=b))⇒a=bを読み替えた)とCantor-Bernstein-Schr?derの定理のもとでExpが多項式時間でわかってしまう。
      あらゆる素数の表現述語を加法的,乗法的,ζ-的…を探す必要がある。
    3. 体系固有の問題　”＃2の解消”

      4. あきらかに＃n＜ωはこれに帰着される、
      ＡＣとの絡みがあり"sharply bounded census fanction"の存在
      つまり|t|で押えられる数から２への関数空間の存在と| |で置き換えることで、できると思ったが…。
      ωωの整列と関係しそうな気もする。
    4. ”代入”の階層的公理化

      5. どうして代入の定義はこんなに難しい。コード化なしに代入を扱うには分岐高階論理が必要と思う。
    5. Bdd.Arith.と高階算術”Sn+1はN階算術の部分体系と等価である”の証明。

      6. よく知られているようにS3と２階制限算術に等価な部分体系がある、
      これを一般化するのは＃2解消とRCA,WKL,ATR0等との関係,typeの問題や選択公理まですべてこのためである。これが出来たらP=NPもできるはず？
  3. 純論理的問題　古典の証明法を読み直す必要がある
    1. 帰納可算的に構成できるModelの性質は任意基数のModelから帰納可算的に抽出できる性質に全て受け継がれるか？それを語れる立場は
    2. コンパクト性定理の拡大(σ-compactで成立するか)
    3. 高階のCETを成立させるには何をあきらめるべきか。(特にnon-GMで構成的）CET0,CET1では 多項式での 証明不可能の 決定をそれぞれあきらめた。
    4. 単なる思いつき　複雑な順序系がいるのなら式を直にKard(¬AC)に対応させたら、おもしろそうだ。Z+AFA+DC,Z+ADなんかとでも。
  4. 集合と算術　

    5. 　Dedkind有限と可逆ゲートのIO数 がPHPに関連し
    またParikhの定理が置換公理(collection)そのものであるごとく、
    互いに重要な公理・定理の対応を整理し、より良い公理系を創造したい,
    AC (Census)はP=NPより重要とおもう。
    1. 基本的対応　S2ならclass,setにunbounded,sharplyboundedな数が対応
    2. 選択公理　　ひとつ加えるなら一般化された竹内の問題はGCHのようである
    3. 連続体仮説　Godelの連続体の濃度の仮説は算術にどのような影響をあたえるか

      4. sharply bounded (PA)→ω,S2→2ωとなるモデルがありそうな気がする
  5. ブール関数・ブール式　ここでは細かいアイデアを述べる。 ここで扱うブール関数とは変数も値も０,１の２値しかとらない。
    1. ∧-meet (p,q),[∨-meet(p,q)]

      2. これは準超局所化した∧-top,∧-meetの概念で
      formula Fのなかのterm t1,t2が∧-meet(p,q)するとは
      Fのsubformula F'がありF'=G1(t1)∧G2(t2)で
      それぞれt1,t2までp,qのdepthをもつ。
      必ずしも一意的でない欠点はtermの場所を固定することで可能とおもう。
    2. ブール回路での(コンピータのFPU・MMUのような)部品の組み込みで計算量はどう変わるか

      3. 部分回路の共用化・オラクル化にあたる。(0,1以外の既成の回路もはいるだけのこと)。
      この場合の回路の記述はn変数・m部分回路(外でfan-in,size,depthとも定義)の単調関数は
      <n,ωn+m+3…ωtとなる。(0と1を別に数えるので3から始まる)
    3. "restrictionの拡張" いまrestricution とは各変数から束3{0,a,1}への関数である。

      4. これを双対性が解りやすいブール束に変え,ゲートにも使えるようにしたい。
      現在は{xi,¬xi,∨,∧}のタイプの回路に４={0,a,-a,1}を使い定義できたのみだが
      n変数関数に対して t:xn→4n (xnに0→0,a→xn,-a→¬xn,1→1を代入）
      そして,t≦q⇔∀i∈n{t(xi)=0→q(xi)=0,t(xi)=a→q(xi)=¬a, t(xi)=-a→q(xi)=a,t(xi)=1→q(xi)=1}
      (要は裏返ってないこと)
      一方,ゲートに対してもn-in,1-outに一般化されても∨,∧のみならば４,3 がそのまま使える(0,１なら定数関数0,1を,aならそのまま,¬aならその双対) 、そして 2-in,1-outならゲート16個全てに４が同様に定義される。
    4. Khrapchenkoの定理に出てくる“擬同値記号”を拡張すればおもしろいことがきっとできる。
      Aを固定して“A,X,Y は n-bit の長さで, X,Yはm-bit Aと違う ”をdnmA(X,Y)と書くだけでもいいが
      m-bit以下の違いのものを全て加えたdn≦mA(X,Y)の方が使いやすそうだ(推移律をみたすひまわり)
      Ａを固定せずに単に1-bit違う関係d1X(X,Y)がKhrapchenkoのにあたる。
    5. 他の分野との対応、竹内氏のＳＳは代数幾何を思われてのことと思うが、特に微分形式に何が対応するか。
  6. 竹内の問題をめぐって
    1. 竹内の問題
      1. 竹内のBoole関数f,f'は2n変数で2分木の上から∧∨が交互に並ぶもの。

        2. 定義はfd,f'dは2d個の変数xiをもち
        f1(x1,x2)=x1∨x2, f'1(x1,x2)=x1∧x2　
        あとは帰納的にd≧2,n=2d-1に対して
        fd+1(x1≦i≦2n)=f'd(x1≦i≦n)∨f'd(xn+1≦i≦2n)
        同様にf'd+1(x1≦i≦2n)=fd(x1≦i≦n)∧fd(xn+1≦i≦2n)
        一般化してFr-shiftを定義するべきだがすっきりしないので、
        もとのかたちのF1のみ記しておく
        F1d=f'd-1(x1≦i≦n)∨f'd-1(x2≦i≦n+1)
        このFrdの計算量をもとめるのが問題である。　
    2. 立場　ここでは超局所の立場を具体的に述べる。竹内の問題の解決に迫った久馬氏は大域的手法、証明を完成した安本氏は局所的手法を取られた。やや厳しくは、ある関数を表現する木が与えられたとき、その木から出発して交互性を崩さない定数で押えられる葉の近くの簡約と、根と葉の距離全てを不変に保つ変換により少なくとも多項式のオーダーの差で回路計算量が求められる。（せめてdepthぐらいは）
    3. 非定値単調関数の簡約の可能性と証明のsize 　 　任意の非定値単調関数はある関数(竹内のf,f')の断面(xi=xjのように制限したもの)であるからその表現木(gateは全てfan-in2)から出発して様々な立場での簡約法(超局所的と言いたいが)計算量mL,dL...等を求める
      1. それは関数本来の計算量に等しいか？
      2. 証明のsizeを関数で表現する。
      3. ブール式・回路計算量と,その証明のsizeの階層の関係性を定式化
    4. 特殊問題　超局所的手法による竹内の問題(一般竹内問題)の証明 　次の制限された道具MLOで証明できるか、または何が足りないか？
      1. Simplcation a∨a⇒a,a∧a⇒a (aは literal)
      2. Commute A∨B⇔B∨A,A∧B⇔B∧A (A,Bは任意のterm=∞長の換)
      3. Local-simplcation (order-3) a∧(b∨c)と双対形のtermへのSimp. (a,b,cはliteral)
      4. Semi-Micro-local-optimize (order3) (Ａ∧(b∨c))∨(A∧(b∨c))⇒(A∧b)∨(A∧c)とその双対(Aは任意のterm. b,cはliteral)
    5. エルブランの定理の類似の予想　 さて6.4で挙げた方法MLOを用いて真単調ブール関数fの式表現の集合をFとし、M(G)を一般にGという表現式の集合からMLOの操作をほどこして得られる全ての式の集合とする。
  7. BB-space (Cantor空間の一般化以上のものとしてまだ未完成)
    1. 原形　ブール代数BがCard(B)=2α(α∈ω)のとき、tを任意のBdd.Arith.の tremとして自然な埋め込みB→P(ω)によりx≦|t|⇔x≦α
    2. 定義　cell...atomとみなすブール代数
    3. 置換群　m変数ブール関数のn個の式から2nへの関数の不変式　fn(xm)→2n
    4. 制限算術のモデルとして
    5. 収束
    6. 位相的ブール代数を通してのハイテイング代数の直観化
    7. トポスとのつながり
  8. 参考文献　
    1. 文中で言及したもの（日本語以外は当然、日本語のものもほとんど読んでない）
      1. 倉田令二朗　編集　河合数学探訪講座　90〜92　Ｐ＝ＮＰのテキスト・プリントなど、制限算術以外にも多くを教わった。
      2. 高瀬正仁　現代数学のあゆみの論文
      3. 竹内外史　直観主義的集合論、層・圏・トポス、線形代数と量子力学、Proof Theory(未読…)、Two Applications of Logic to Mathematics
      4. P.Clote,Krajicek ed.; Proof Thorey,and Computational Complxeity
      5. S.Buss ; Bounded Arithmetic (未読に等しい）
      6. M.S.Paterson ed ; Boolean Function Complexity,LMS,LN169
    2. その他参考にした書物　
      1. 論理学
        1. 竹内外史・八杉満利子　証明論入門
        2. 林晋　数理論理学
        3. Andrews,Peter B 数理論理学とタイプ理論
        4. Constructism in Mathmatics an Introduction (ながめただけ)
      2. 集合論
        1. 田中尚夫　公理的集合論、選択公理と数学
        2. 難波完爾　集合論
      3. 計算論
        1. 広瀬健　帰納的関数
        2. 小林孝次郎　計算の複雑さ
        3. 林晋・小林聡　構成的プログラミングの基礎（関数空間と巾を）
        4. P.Hajek,P.Pudlak Metamathematics of First-Order Arithmetic
      4. 圏論・束論　竹内外史のほか
        1. S.Koppelberg 現代のブール代数（いろいろ勉強した、おすすめ）
        2. 河田敬義　ホモロジー代数　(ながめただけ)
        3. 大熊正　圏論
      5. 解析関数論・代数幾何（すべてながめただけ）
        1. 飯高茂　代数幾何学
        2. 梶原壌二　複素関数論
      6. 組み合わせ論
        1. Frankl,Peter・秋山仁　現代組合せ論
      7. 現代数学のあゆみ1,2,3,4（古典の知識はすべてこれによる）
    3. 古典　実は原文で読んだことがひとつも無いのであるが３人は読みたい。　
      1. Cantor
      2. Gentzen
      3. Herbrand
      4. Godel
  9. 構想のもと（この節以下読み飛ばしてください）
    1. 対応図式について　初めてBussのS2を数セミで見た時にNBGと似ているなと思い。そのうちS3が２階算術に対応していることを知り、【竹内外史；層・圏・トポス】のＥの公理（外延公理とあとで知った）を自由に「ならば」と「射」に読み替えたことにある、そのうちsemi-termをおさえる何かがLKに不足している気分とOracleはどこに?という思いが代入の重要性を浮かばせたしtotallyの問題もあった。外から見ることと内でしていることの差を見たい。　
    2. ブール回路・関数計算量の３つの立場について　解析関数の３つの定義を流用したものでpositive literalと∨,∧とで構成できる、または0と1の両方を値としてとる単調関数が解析関数にあたると思うが竹内の関数に対する久馬栄道 安本雅洋両氏の仕事を倉田令二朗氏に教わること無しには決してたどり着けなかっただろう。
    3. Bdd.Arith.&AC　これはS2の#2を弱い選択公理と弱い関数空間の存在に分解して解消することを考えて浮かんだ、何よりPHP,census function,などDedekind finite,strong choiceに相当するものが数多くあったことにある。その後 量子群やガロア理論の解説を見て可解＝簡約の語呂合わせの様に進み“AC0が対称なら深さ一定で大変小さなサイズの計算回路がある”という [Ingo Wegener,Norbert Wurm,Sang-Zin Yi] に勇気が湧いた。
    4. 最後に哲学としての数学基礎論 　数学で哲学を語るには証明それ以外にない（奇蹟を伴わない預言者の様に）のだが、基礎論とは 単なるLogic,Theory,Modelの研究ではなく理論の拡大とそれにより表われる立場・構成・抽出による様々な矛盾点の分布の研究である(拡大やCONSともに階層があることに注意、解析接続に対応)言うまでもなく、これは高瀬正仁氏の解析関数論の見方の強い影響下にある。悪い予感としてCETが成立する体系がR,C よりも４元数や８元数の様な道をたどらないなら幸いであるそれでもvector,ring,moduleを生むのに必要だった。対策,non-GMの場合や特にCUTについてゆるぎない立場 基礎を20世紀の代数幾何のように見直してみること。
  10. 補足
みちくさにもどる
katzura1@mbox.kyoto-inet.or.jp