はてなブックマーク

『代数学は得意だけど，数学基礎論とかさっぱり分からない．論理とかマジイミフ』そんなアナタを対象に，ゲーデルの不完全性定理を解説してみよう！　のコーナーです．　　論理学と代数学（可換環論）との対応については，檜山さんによる素晴らしい記事があります：　古典論理は可換環論なんだよ - 檜山正幸のキマイラ飼育記　ただ，『論理学といえばまずコレ！』とも言うべき『ゲーデルの不完全性定理』の代数学的表現については書かれていないようなので，ちょっぴり魔が差して，ここでゲーデルの不完全性定理の代数学的な表現を与えることにしました．　だが，単にゲーデルの不完全性定理を代数学で表現するだけじゃあつまらない……倍プッシュだ……！というわけで，プラスアルファとして，その他色んな分野との関わりを含めて紹介します．　　0. 理論は対応する代数を持つよ！： リンデンバウム代数　まず，論理学と代数学を対応させる第一の架け橋

某所で再帰理論の最近の研究の流れの話が出たので、せっかくなのでブログに纏めておきます。　　数学基礎論の大きな分野のひとつとして、ゲーデルらの研究を発端として生まれた再帰理論。　では、ゲーデルの不完全性定理以後、数学基礎論の一分野である再帰理論は、どのような発展を遂げたのでしょうか。今回は、1950年代までの再帰理論の研究の歴史を辿ってみましょー。　　1930年代　1930年代。チャーチ、ゲーデル、チューリング、クリーネその他多くの研究者による研究、そしてゲーデルの不完全性定理を発端の一つとして、計算可能性と計算不可能性の研究が始まりました。1930年代の計算論の研究の始まりは歴史的に非常に重要ですが、詳しい文献がたくさんあるので、ここでは省略します。　このような1930年代の研究によって、計算という概念が数学的に定義され、コンピュータ開発もたぶん順調に進むことになったのでしょう。しかし何よ

集合論　一から強制法 (2007/01/05)二から強制法 (2007/01/07)三から強制法 (2007/01/21)連続体仮説の独立性証明 (2007/01/24)多値論理と強制法 (2007/05/24)　集合論における様々な命題の独立性証明を中心として、再帰関数論やモデル理論など、様々な分野で用いられている強制法 ( Forcing ) というテクニックの導入とその応用についてです。　その強制法の入り口である、集合論における Cohen Forcing の概念と、強制法の応用の最初の実例として、　「連続体仮説が証明も反証もできない」ということの証明までについての、大雑把なメモ書きです。　再帰理論（計算不可能性の理論）　再帰理論史 --ゲーデルの不完全性定理以後--（1930〜50年代） (2009/05/23)再帰理論史 --再帰理論的エルランゲン・プログラム-- (2009/0

強制法（ Forcing ）　「○○は証明も反証もできない」 「○○は××と（相対的に）無矛盾である」 　このようなものを証明するのに用いる常套手段が強制法（ Forcing ）です。　　基本アイデア　「○○は証明できない」 ということを証明するための基本アイデアは簡単です。 　たとえば、「理論 で文 が証明できない」ということを証明したいとします。　そのために、まず、理論 内の全ての法則を満たす宇宙（モデル）を仮定します。 　この宇宙を、さらに の全ての法則を満たすのみならず、文 の否定をも成り立たせるような宇宙に拡大させます。 　この拡大した宇宙は、理論 の全ての法則と、文 の否定を共存させてしまうのですが、 その一方、文 "" と " の否定" は決して共存し得ません。 　つまり、もし理論 から文 が導けると仮定すると矛盾してしまいます*1。 したがって、理論 から文 は絶対に証明で

やっぱ、前回の話、同じ集合論でやるのも芸が無いので、圏論を使った手法でやろうと思います。　いや、現時点では圏論的手法はほとんど知らないけど、多分そのうち分かるッ！　根拠は無いッ！　　ということで、今日は圏論へのイントロダクションということで、　「数学の基礎づけとして、集合論と圏論とはどう違うんだろ？　だろ？」　公理的集合論　公理的集合論にも、　 （ツェルメロ＆フレンケル）　 （ベルナイス＆ゲーデル）などの色んな体系があるのですが、　集合の論というくらいですから、その心は一つ！　　「モノを集めてモノを作るぜ！」　　たとえば、 の公理がどんなものかを大雑把に言うと、　対の公理　二つのモノがあったら、その二つを集めることができる。　　もっといい加減に描くと、こんな感じ。　　和の公理　集合の中のものを一つにまとめることができる。　　分出公理　集合のうち、指定した条件を満たすものだけを取り出すことが