以前にもちらっと参考書として挙げていた本書であるが、冬休みを利用して最初から読みなおしてみた。 昔読んだときは肝心の後半部分を流して読んでいたのだが、『数学基礎論講義をこっそり読む』が第二不完全性定理にさしかかったのでその予習のつもりである…

第６講に入っていよいよ第一不完全性定理です。 お話っぽい説明が多くてサクサク進むのですが、行間を埋めつつ読み進めます。 まず p.87 の メタ定理 の証明。 （）証明のゲーデル数をとすると が成立している。(1)より、. はのモデルなので、 □ （) ならば …

まず p.77 定理5.6（および定理5.8）に関してです。『定理5.6 １）において表現可能な全域関数や関係は、すべて再帰的である。 ２）任意の再帰的全域関数、任意の再帰的関係は、上の適当な論理式、ならびに適当な論理式でにおいて表現される。』 おおっとい…

Part Bに入りました。いよいよ算術です。なぜか新井敏康著『数学基礎論』ではPAオンリーでロビンソンの算術Qは出てきません。 算術Qで不思議なのはやはり、p.69の でしょうか。公理A4でがあるので、これは加法の交換法則の特殊なもの すら成立していないこと…

またもや重箱の隅をつついて遊ぶ探究ではありますが、p.54 補題4.15で『 AがREならば [tex:\forall y が再帰的でないことの証明(ほとんどRiceの定理の証明)： 再帰的であると仮定して、その特性関数をとする。 また と定義すると は(定理4.19)をREとして特徴…

PART A 第４講に入りました。テキストのこの講はかなり駆け足というか猛ダッシュで、クリーネの標準型定理が説明だけなのは肩すかしをくらったような感がありますが、計算論のどの教科書にも載っている内容だからということなのかもしれません。私もちょこち…

今回は結構悩みました。p.38 辺りです。まずは系3.11のメモから。 『次の系は上の定理からただちに導かれる』とあるのですが、そこが第一の悩みポイントでした。分かってしまうとなーんだということになるのですが、系3.11の条件の下で、(は複数のxの略記と…

引き続きこっそり読んでいます。この本の冒頭に挙げられた問いの一つは 問1 ある形式体系Tにおいて、が証明できても、が証明できるような、あるが存在するとは限らない。その例を挙げよ。 で、直観には真っ向反していますが、こういうことが起こりうるのが形…

引き続きこっそり読んでいます。もうちょっとでPartA 第三講が終わります。 いくつか、コメントというかメモっぽいものを。p.31 定理3.2（演繹定理）の証明は読者に任されていますが、その証明中で唯一問題になりそうなのは の導出だと思います。ちょこちょ…

こっそり読んでいます。まだまだ最初の方の命題論理のコンパクト性のところなのですが、いきなり悩んでました... こちらのテキストでは、前提のある場合の命題論理の一般化された完全性定理『 』を先に証明して、そこからコンパクト性定理『 が充足可能 ⇔ 任…

先日たまたま大阪に出張する機会があり、帰りに梅田の旭屋を覗いてみると、な、なんと日本評論社の『数学基礎論講義』が復刊されて置いてあるではありませんか！ 数学基礎論講義―不完全性定理とその発展作者: 田中 一之,角田 法也,鹿島 亮,菊池 誠出版社/メ…

１章のハイライトのひとつ、定理1.4.14(コンパクト性定理）の証明についてコメントする。まず、P.30の初めにある『1階論理のトートロジー』の定義であるが、よく理解できなかったので、ちょっと調べてみるとその採用した体系によって若干異なる定義があり、…

こっちのネタ本の方もすこし読み進めてみた。気になったところをコメントする。 P.13の命題1.2.1の下のあたりに、『どんな閉論理式の有限集合をとっても、それが任意の可除アーベル群で正しければ、可除でないアーベル群でも正しくなってしまう』というステ…

とまあ、最初は有限群の勉強と思ってブログを始めたのだが、それからコロコロと興味が変わってしまい、更新もごぶさたであった。しかし…最近、私の趣味の数学魂を刺激する次の2つの書物がでてしまったのだ。数学基礎論作者: 新井敏康出版社/メーカー: 岩波書…

同じく高橋正子著 『計算論』 近代科学社のp.51から: 補題1.6.10をが個の引数を取る計算プログラムのコードとしたとき，その計算結果を返す関数とする(がプログラムのコードでなかったり，計算が止まらないときは未定義とする）. このとき任意の帰納的な全域…

原始帰納的関数でない帰納的関数の例としてよく知られているAckermann関数について，高橋正子著『計算論』近代科学社 のP.22の練習問題を解いてみた． ちょっと調べてみると1900年代の初期には計算可能な関数（今でいう帰納的関数）は全て原始帰納的関数であ…