このサイトは学部では早稲田で物理を, 修士では東大で数学を専攻し, 今も非アカデミックの立場で数学や物理と向き合っている一市民の奮闘の記録です. 運営者情報および運営理念についてはこちらをご覧ください.
理系のための総合語学・リベラルアーツの視点から数学・物理・プログラミング・語学 (特に英語) の情報を発信しています. コンテンツアーカイブに見やすくまとめているのでぜひご覧ください.
追記
やたべさんから次のようなご指摘を頂いたので
タイトルなど少し書き換えた.
なんか、終わりの方もう算術関係無くなってね?そもそも逆数学や記述集合論は算術じゃないだろ? QT @phasetr: http://t.co/hYBbRfa0O2 【算術士になるため算術の専門家である tri_iro さんに文献などをいろいろ聞いた記録】よくわからない数学
— ytb (@ytb_at_twt) 2014, 9月 23
追記終わり
算術士を目指したいので算術の専門家である
tri_iro さんにいろいろ聞いたらいろいろ教えてもらったのでその記録.
@tri_iro 何と言ったらいいのか分からないのですが【二階算術】とかつくような感じの【算術】の話を雰囲気を感じるところからはじめて勉強までしていくにはどんな感 じの本やらレビューやらを読んでいくといいでしょうか。多少の数学は知っていてもロジックや基礎論関係はザルな状態から開始で
— 相転移P(市民) (@phasetr) 2014, 9月 21
@phasetr その手の算術は、不完全性定理関連を勉強したいか、証明論寄りの順序数解析チックなことを知りたいか、逆数学みたいな感じのものを知りたいか、あるいは単純に算術的階層みたいな話を知りたいかで違うのですが、ほとんど予備知識がいらなさそうなものであれば、以下(続く)
— Takayuki Kihara (@tri_iro) 2014, 9月 22
@phasetr 和書であれば『数学基礎論講義』 http://t.co/EnHrkwdhph が不完全性定理の初歩から、ヘラクレスvsヒドラやグッドスタイン列、パリス-ハーリントンなどのPAの独立命題、算術の超準モデル論など幅広く解説してあり、おすすめです。
— Takayuki Kihara (@tri_iro) 2014, 9月 22
@phasetr 「ゲーデルと20世紀の論理学3巻:不完全性定理と算術の体系」も不完全性定理と逆数学に関してはもう少し詳しく書いてありますが、前述の書籍と比べると少し話題が狭いです。「数の体系と超準モデル」はそれ以外に算術の超準モデル論の雰囲気も感じられます。
— Takayuki Kihara (@tri_iro) 2014, 9月 22
@phasetr 未出版ですが、神戸の方の菊池誠先生(不完全性定理のプロの方です)の「不完全性定理」 http://t.co/OFOOOaY34w も目次を見る限り、テーマが不完全性定理なので、話題は不完全性定理まわりの算術に限っていますが、たぶんかなりの良書であると思われます。
— Takayuki Kihara (@tri_iro) 2014, 9月 22
@phasetr 洋書で良ければ、 “Metamathematics of First-Order Arithmetic” http://t.co/uilc3shGpN は算術のバイブルです。無料公開されており、Table of Contentsの所から無料でDLできます。
— Takayuki Kihara (@tri_iro) 2014, 9月 22
@phasetr 後の方で紹介したやつは、雰囲気を見るだけだとちょっとテクニカルすぎる本かもしれません。もっと啓蒙書っぽいものを紹介できればよかったのですが、算術の本でその手のやつを知らないもので……。
— Takayuki Kihara (@tri_iro) 2014, 9月 22
@tri_iro ありがとうございます。参考になります。急ぐ旅ではないのでゆるゆると勉強します
— 相転移P(市民) (@phasetr) 2014, 9月 22
まだもう少し続く.
相転移Pから算術の本に関しての質問を受けたのに乗っかって、ついでにプラスアルファでもうちょいテクニカルな算術の本も紹介してみよう。あ、なんかもうちょい入門書チックな算術の本をご存知な方がいましたら教えて下さい。
— Takayuki Kihara (@tri_iro) 2014, 9月 22
リプ欄でも紹介したけれど、 “Metamathematics of First-Order Arithmetic” http://t.co/uilc3shGpN 算術のかなり広範な話題を扱っている不朽の名著。ただし、算術の本の避けられない定めとして、序盤の超絶コーディングがつらみ
— Takayuki Kihara (@tri_iro) 2014, 9月 22
(承前)しかし、帰納法の無矛盾性のプロパーな階層、不完全性定理、ラムゼーの定理周辺の独立命題などの話題を非常に丁寧に扱っているうえ、出版社が無料公開中。あと地味に限定算術の話題までひとつのパートを割いて解説している。
— Takayuki Kihara (@tri_iro) 2014, 9月 22
(書評2) Models of Peano Arithmetic http://t.co/vz6v7C30F4 算術のモデル論の入門書。個人的に結構好きな本。前半はちょっとだるいけど、中盤以降が楽しい。自然数論の超準モデルってこんなんだったんかい!と目から鱗の落ちる一冊。
— Takayuki Kihara (@tri_iro) 2014, 9月 22
(承前) ちなみにパリス-ハーリントンの定理やカナモリ-マカルーンの定理のペアノ算術からの証明不可能性のインディケーターを使った証明も載っている。ヘラクレスvsヒドラやグッドスタイン列の証明不可能性は演習問題。
— Takayuki Kihara (@tri_iro) 2014, 9月 22
The Structure of Models of Peano Arithmetic http://t.co/b5CDSplXSW 前述のKaye本ではもう満足できなくなった人のための算術の超準モデル理論本。ペアノ算術の超準モデルを極めたい人向け。
— Takayuki Kihara (@tri_iro) 2014, 9月 22
(書評4) Proof Theory: The First Step into Impredicativity http://t.co/Fo6rDQoBe5 証明論寄りの算術というか、順序数解析の入門書。ε_0の整列性からのペアノ算術の無矛盾性証明に始まり、その先へ。
— Takayuki Kihara (@tri_iro) 2014, 9月 22
(書評5) Bounded Arithmetic, Propositional Logic and Complexity Theory http://t.co/7zRd0outZL 計算量に対応する算術の理論である限定算術などの話題を学べる入門書。限定算術パートは結構読みやすい。
— Takayuki Kihara (@tri_iro) 2014, 9月 22
(承前)あ、ただ、前述のKrajicek本はちょっと古いので、現代的には限定算術型でも、二階算術的な定式化をしているCook-Nguyen本 http://t.co/BgPTfOGBNj の方がいいのかも。Cook-Nguyen本はほとんど読んでないので、良い本か知らないけど。
— Takayuki Kihara (@tri_iro) 2014, 9月 22
最後に、Subsystems of Second Order Arithmetic http://t.co/MwKX69jxbw 言わずと知れた逆数学の入門書。言わずと知れているので、特に書評はありません。 というわけで、以上、突発的・算術の入門書紹介コーナーでした。
— Takayuki Kihara (@tri_iro) 2014, 9月 22
tri_iro さんが RT していた魔法少女.
Samuel R. Buss, Bounded Arithmetic の pdf が free だった気がする
— (@functional_yy) 2014, 9月 22
他の RT.
Handbook of Proof theoryのBussが書いている章も算術の証明論へのコンパクトな入門だと思います。
— yoriyuki (@yoriyuki) 2014, 9月 22
そしてやりたいのはこれだ.
このような算術の本を読んで、算術士の熟練度を上げることにより、レベル素数ホーリーなどの多彩な技を使えるようになります。
— Takayuki Kihara (@tri_iro) 2014, 9月 22
他にも RT.
これも割とおすすめ:Buchholz et al (eds). W. Iterated inductive definitions and sub-systems of analysis, Lecture Notes in Math. 897, Springer.
— Ryota Akiyoshi (@georg_logic) 2014, 9月 22
最初の方のFeferman, Siegが書いてある入門的章は基本的なことが書いてあって,後のBuchholz, Pohlers達の章も,結構丁寧に書いてある.使っているordinal notationsはちょっと古いので複雑だけれど.
— Ryota Akiyoshi (@georg_logic) 2014, 9月 22
ゼルプスト殿下の RT.
Oxford Logic Guide 11: R.Mansfield and G.Weitkamp «Recursive Aspects of Descriptive-Set Theory» が復刊しないものかと期待している http://t.co/Inq9yD2K1v
— ゼルプスト殿下 (@tenapyon) 2014, 9月 22
@tenapyon 集合論と計算論の初歩を修めた人向けに、補解析同値関係に関するシルヴァーの定理や0♯に関するハリントンの定理など当時まだ新しかった結果まで見通しよ く解説してくれる好著。しかし、これももう30年も前の本になるのか。このスタイルでいま書いたらどんな本になるかなあ。
— ゼルプスト殿下 (@tenapyon) 2014, 9月 22
Buchholz & Schutte本は院生時代に読もうとした結果、なんかよくわからない地獄の順序数計算によってトラウマになって、未だに立ち直れないのであった。いや、たぶんもうちょいちゃんと予備知識を習得してから読むべきだったんだろうけど。
— Takayuki Kihara (@tri_iro) 2014, 9月 22
あと別件だが再帰理論のも転載しておこう.
再帰理論をやろうと思っても、やっている人がまわり居なくてどうしていいかさっぱりわからないので、よかったら良い教科書か入門書を教えてください!
■和書:
初めに述べておくと、和書では個人的なオススメ本は一つもありませんが、一応、和書から紹介。■ マイケル・シプサ 『計算理論の基礎』
オススメ度:☆ 難易度:☆
もし、『計算可能性』について全く知らないのであれば、再帰理論を学び始める一歩手前に。■ 廣瀬 健 『計算論』
オススメ度:? 難易度:?
一応、和書なのでリストに挙げておきますが、内容知りません。■ 篠田 寿一 『帰納的関数と述語』
オススメ度:☆☆ 難易度:☆
再帰理論の和書としては、一番有名なのかな。
【利点】 一から丁寧に書かれているため、予備知識一切なしに読むことが出来る。
【欠点】 話題のチョイスが極めて独特でマニアックなので、標準的な教科書とは言い難い。再帰理論の標準的トピックが省略されて、抽象計算量など再帰理論と関係の薄い話題にページを割いている。■ 田中 一之 『逆数学と二階算術』
オススメ度:☆☆ 難易度:☆☆☆
再帰理論と逆数学をまとめて勉強したい人にオススメ。
【欠点】 薄い本なので、説明も薄く、ある程度予備知識を持ってる人じゃないと読むのはしんどいかも。■ 田中 尚夫 『選択公理と数学』
オススメ度:☆☆☆☆ 難易度:☆☆
再帰理論の本ではないんですが、再帰理論のアイデアやテクニックがかなり用いられているので、再帰理論の本と並行に読むと楽しいかも。選択公理ちゃんマジ公理。■ 新井 敏康 『数学基礎論』
オススメ度:☆☆☆☆ 難易度:☆☆
第2章と第6章が再帰理論の話題。再帰理論を含む、数学基礎論の色んな分野の古典をまとめて一気に勉強したい!という人にオススメ。
【利点】 再帰理論が誕生した当初の’40年代~’50年代の重要な定理には一通り触れてくれているので有難い。
【欠点】 逆に言うと、’40年代~’50年代よりも後の研究にはほとんど触れられていない。あくまで古典。■ 李 昂生 『可计算性理论』
オススメ度:☆ 難易度:☆☆☆
まともな再帰理論の教科書が一つも出版されていない日本とは異なり、中国語の再帰理論の教科書はそれなりにあります。「英語よりも中国語の方が得意だぜ!」という奇特な方へのオススメ本はコレ!
【利点】 再帰理論の基本的証明技法である優先法 (priority argument) について詳細に書かれており、 Lachlan’s nonbounding theorem などの monstrous injury priority argument を用いた証明も丁寧に解説されている。
【欠点】 言語の壁は厚い。■洋書
■ Cutland, “Computability: an introduction to recursive function theory” (1980)
オススメ度:☆ 難易度:☆
極めて普通の入門書。再帰理論の入門書というよりは、計算可能性の初歩に関するトピック。■ Martin Davis, “Computability and Unsolvability” (1958)
オススメ度:? 難易度:?
読んだことないけど、よく話を聞くので。■ Barry Cooper “Computability Theory” (2002, 2011)
オススメ度:☆☆☆☆☆ 難易度:☆
個人的に初学者へのオススメの一品はコレ。
【利点】 初歩から超丁寧に書かれていながら、結構深く広い話題に発展する理想的な教科書。
【欠点】 解析的階層や認容順序数などの再帰理論における主要なトピックの一部には全く触れられていない。■ Hartley Rogers, Jr., “The Theory of Recursive Functions and Effective Computability” (1967)
オススメ度:☆☆☆☆ 難易度:☆☆
古いけど色褪せない輝きを放つ、古典的な再帰理論の名著。
【利点】 1940年代~1950年代の再帰理論研究の集大成。
【欠点】 ちょっと古臭くて読みにくい。■ Manuel Lerman, “Degrees of Unsolvability: Local and Global Theory” (1983)
オススメ度:☆☆☆ 難易度:☆☆
次数の大域的構造が好きで好きでたまらない人へ贈る、職人の技術が詰め込まれた書籍。
【利点】 無料公開されました!
【欠点】 優先法の話題が全く載ってないのが致命的な欠点か。■ P. Odifreddi, “Classical Recursion Theory” (1989)
オススメ度:☆☆☆☆ 難易度:☆
再帰理論の古典について、幅広く網羅的に書かれたオススメの名著。
【利点】 やたら重くて硬いので、装備すると攻撃力がかなり上昇する。
【欠点】 個々の話題の取り扱いが非常に薄いため、証明技術などをこの書籍で身につけようとするのは困難。■ P. Odifreddi, “Classical Recursion Theory: Volume II” (1999)
オススメ度:☆☆☆ 難易度:☆☆
上記の本の続編。しかし、1巻に比べると話題のチョイスが若干迷走している感じ。
【利点】 話題の幅広さ。
【欠点】 3巻出る出る詐欺。■ Robert Soare, “Recursively Enumerable Sets and Degrees” (1987)
オススメ度:☆☆☆☆ 難易度:☆☆
再帰理論の基本的な証明技術を学ぶための教科書。一方で、話題が限定的なので、再帰理論の概観を眺めるという点では微妙。
【利点】 再帰理論の基本的技術を網羅的に取り扱っている。
【欠点】 再帰理論の研究トピックの極一部にしか触れていない。■ Gerald E. Sacks, “Higher Recursion Theory” (1990)
オススメ度:☆☆☆☆ 難易度:☆☆☆☆
解析的階層の理論から順序数上の再帰理論までを統一的に取り扱った名著。記述が若干古臭いのだけれど、それにも関わらず読みやすい気がします。
【利点】無料公開されました!
【欠点】記述が若干古臭い。■ Jens E. Fenstad, “General Recursion Theory: An Axiomatic Approach” (1980)
オススメ度:☆ 難易度:☆☆☆
用語が独特で若干読みにくい。意外と深い内容が書かれているんだけど、マニア層向け。■ M. C. Fitting, “Fundamentals of Generalized Recursion Theory” (1981)
オススメ度:☆ 難易度:☆☆☆
同上。マニア層向け。■ Peter G. Hinman, “Recursion-Theoretic Hierarchies” (1978)
オススメ度:☆☆☆ 難易度:☆☆☆
階層理論の話題が網羅されているのは嬉しい.この分野の入門書として最低限必要な話題である算術的階層・解析的階層・算術的強制法・基底定理の古典的結果は網羅されている。話題のチョイスが良い代わり、記述が古臭くて読みにくいのが残念。
【利点】 古典的な Δ^1_2 集合の理論のバイブル。
【欠点】 ちょっと論理論理しすぎてて読みづらいかも。■ Manuel Lerman, “A Framework for Priority Arguments” (2010)
オススメ度:☆☆ 難易度:☆☆☆☆☆
優先法マニア待望の、優先法に特化した教科書だよー!!
【利点】 優先法を理解している人が読むと、思考を整理できるかも。
【欠点】 優先法を既に理解している人じゃないと読める代物じゃない。■ Ash and Julia Night, “Computable Structures and the Hyperarithmetical Hierarchy” (2000)
オススメ度:☆☆☆☆ 難易度:☆☆☆
再帰モデル理論の基本的な教科書。個人的にはかなりオススメ。
【利点】 超算術的階層や解析的階層についても一緒に学べる。
【欠点】 特になし。■ Yuri L. Ershov and Sergei S. Goncharov, “Constructive Models” (2000)
オススメ度:☆☆ 難易度:☆☆
再帰モデル理論の基本的な教科書。こちらはかなりベーシックなモデル理論。
【利点】 上の本よりは初等的な内容から書かれているかも。
【欠点】 個人的にはちょっと読みづらく感じる。■ “Handbook of Computability Theory” (1999)
オススメ度:☆ 難易度:☆☆☆
標準的教科書に比べて勝ってる部分はあまり無いような……。■ “Handbook of Recursive Mathematics, Volume 1: Recursive Model Theory” (1998)
オススメ度:☆☆☆☆ 難易度:☆☆☆
再帰モデル理論に関する基本的話題を一通り知りたい人のためのハンドブック。■ “Handbook of Recursive Mathematics, Volume 2: Recursive Algebra, Analysis and Combinatorics” (1998)
オススメ度:☆☆☆ 難易度:☆☆☆
再帰数学、逆数学に関する基本的話題を一通り知りたい人のためのハンドブック。■ Andre Nies “Computability and Randomness” (2009)
オススメ度:☆☆☆ 難易度:☆☆
ランダムネスの基本的な教科書その1■ Hirschfeldt and Rod Downey “Algorithmic Randomness and Complexity” (2010)
オススメ度:☆☆☆☆ 難易度:☆☆
ランダムネスの基本的な教科書その2■ Marian B. Pour-El and J. Ian Richards, “Computability in Analysis and Physics” (1989)
オススメ度:☆☆☆ 難易度:☆
計算可能解析の古典的な良書。解析学や物理学と計算可能性の関係を知りたい方にはオススメ。■ K. Weihrauch, “Computable Analysis” (2000)
オススメ度:☆☆☆ 難易度:☆
計算可能解析の基本的な教科書。上の本よりはスッキリと書かれている。位相空間論と計算可能性の関係を知りたい方にはオススメ。■ Stephen G. Simpson “Subsystems of Second Order Arithmetic” (1999, 2009)
オススメ度:☆☆☆ 難易度:☆☆
逆数学の基本的な教科書。
後半の ω-モデルの章と β-モデルの章を読めば、再帰理論との関連性が明確になると思います。ただし、この本は再帰理論の専門的知識を使うトピックを可能な限り避けているので、前半部分は再帰理論っぽさは少ないかも。■ 近刊予定
■ Douglas Cenzer and Jeff Remmel, “Effectively closed sets”
近年、ランダムネスを初めとする様々な分野で重要性が認識されてきたΠ^0_1集合の理論に特化した教科書。期待の一品。■ Robert I. Soare, “Computability Theory and Applications I: The Art of Classical Computability”
再帰理論の新たなる教科書を目指して執筆中の教科書。Π^0_1集合の理論や再帰理論の微分幾何への応用などが重点的に書かれる予定らしい。■ Robert I. Soare, “Computability Theory and Applications II: Applications of Computability”
上の本の2巻。■ John Longley and Dag Normann, “Computability At Higher Types”
高階の計算可能性理論の教科書らしい。■ Damir D. Dzhafarov and Carl Mummert, “Reverse Mathematics”
Simpson本との棲み分けのために、おそらく再帰理論的な視点を重視してくると思われます。
逆数学のための再帰理論の技術や証明技法を解説した技術的教科書になると推測。■ 近隣分野の良書
■ Sanjay Jain, Daniel N. Osherson, James S. Royer, Arun Sharma, “Systems That Learn: An Introduction to Learning Theory” (1999)
オススメ度:☆ 難易度:☆
計算論的学習理論の中でも、特に帰納的推論について詳しく書かれた教科書。
初学者向けに非常に丁寧に書かれていて読みやすい。■ Jon Barwise “Admissible Sets and Structures: An Approach to Definability Theory” (1975)
オススメ度:☆☆☆☆ 難易度:☆☆☆☆
順序数上の再帰理論を展開するための認容集合の理論について書かれた教科書。
集合論と証明論の知識も多少持っていた方が読みやすい。■ Yiannis N. Moschovakis “Descriptive Set Theory” (1980, 2009)
オススメ度:☆☆☆☆☆ 難易度:☆☆☆☆
“Handbook of Mathematical Logic” では、記述集合論は再帰理論の項目に分類されていたので、これも再帰理論の教科書だと思います! 古典記述集合論のバイブルとも言うべき名著。個人的には超オススメです。■ Kechris “Classical Descriptive Set Theory” (1995)
オススメ度:☆☆☆ 難易度:☆☆☆
Moschovakis本とは方向性がかなり違うけれど、これも古典記述集合論のかなりの良書。
ロジック慣れしていない人にはこちらの方が読み易いかも。
とりあえず手許にあった再帰理論関連の教科書を一通りレビューしました。
結論として、個人的なオススメ教科書は:
■初めて再帰理論を学ぶ人:
Barry Cooper “Computability Theory”
P. Odifreddi, “Classical Recursion Theory”
Hartley Rogers, Jr., “The Theory of Recursive Functions and Effective Computability”■更に一段階進んで再帰理論を知りたい人:
Manuel Lerman, “Degrees of Unsolvability: Local and Global Theory”
Gerald E. Sacks, “Higher Recursion Theory”
Ash and Julia Night, “Computable Structures and the Hyperarithmetical Hierarchy”
Yiannis N. Moschovakis “Descriptive Set Theory”という感じかなあ、と思います。
追記 2
やたべ・tri_iro さん間でさらにやり取りがあったので追記する.
いろいろただで教えてもらえてこんなにありがたいことはない.
私も頑張ろう.
@phasetr @ytb_at_twt 記述集合論のあれは算術とは完全に無関係にぼくがRTしていたのが混ざったんだと思います。逆数学は、「【二階算術】とかつくような感じの【算術】」という要求だったので、元々二階算術の文献を探されていたのかと思って一応紹介しておいたというあれです
— Takayuki Kihara (@tri_iro) 2014, 9月 23
@ytb_at_twt @phasetr ところで、通常、「算術」って言った場合、どの程度の範囲を指すんでしょうか?
— Takayuki Kihara (@tri_iro) 2014, 9月 23
@ytb_at_twt @phasetr あ、さっきの「算術」はペアノ算術とか二階算術とかそういうロジックの意味で、です。
— Takayuki Kihara (@tri_iro) 2014, 9月 23
@tri_iro @phasetr そもそも「【二階算術】とかつくような感じの【算術】」というのがカテゴリーミステークだったんでしょうねぇ。二階算術は算術としての部分もある(自然数論の範疇性とかACA0がPAの保存拡大だとか)けど、シンプソン本は明らかに算術ではないような。
— ytb (@ytb_at_twt) 2014, 9月 23
@ytb_at_twt @phasetr シンプソン本は前半7割は逆数学ですが、後半3割(Part B)は純粋な二階算術のモデル論で、じつは保存拡大や体系の無矛盾性の階層の話などが結構詳しく書いてあって、後半部分は(証明論的な話は無いとはいえ)ギリギリ算術なのかなと思ってます
— Takayuki Kihara (@tri_iro) 2014, 9月 23
@tri_iro @phasetr 普通は「自然数論」の別名が算術ですよね。
— ytb (@ytb_at_twt) 2014, 9月 23
@ytb_at_twt @phasetr なるほど、そういう意味なら、純粋な二階算術の話でも、ほとんどは算術ではないということでしょうか。
— Takayuki Kihara (@tri_iro) 2014, 9月 23
@tri_iro @phasetr そうなんですか。僕の知っていたシンプソン本と違う! (そもそもタイプ打ちの草稿しか知らない)それは十分算術っぽいですね。
— ytb (@ytb_at_twt) 2014, 9月 23
この記事へのコメントはありません。