ゲーデルの不完全性定理を代数学を使って表現してみた - とりマセ
『代数学は得意だけど，数学基礎論とかさっぱり分からない．論理とかマジイミフ』そんなアナタを対象に，ゲーデルの不完全性定理を解説してみよう！ のコーナーです． 論理学と代数学（可換環論）との対応については，檜山さんによる素晴らしい記事があります： 古典論理は可換環論なんだよ - 檜山正幸のキマイラ飼育記 ただ，『論理学といえばまずコレ！』とも言うべき『ゲーデルの不完全性定理』の代数学的表現については書かれていないようなので，ちょっぴり魔が差して，ここでゲーデルの不完全性定理の代数学的な表現を与えることにしました． だが，単にゲーデルの不完全性定理を代数学で表現するだけじゃあつまらない……倍プッシュだ……！というわけで，プラスアルファとして，その他色んな分野との関わりを含めて紹介します． 0. 理論は対応する代数を持つよ！： リンデンバウム代数 まず，論理学と代数学を対応させる第一の架け橋
数学基礎論サマースクール2009 - とりマセ
東工大で開催された数学基礎論サマースクールに行ってきました。テーマは「非古典論理の代数的セマンティックス」 僕は非古典論理には超無知だったので、こんな楽しそうな研究があったのか！と感動です。中間論理のうちクレイグの補間性を見たす論理の数に関する定理なんて超驚きでした。いやー、部分構造論理の研究って面白そうですね！ いいですね！ しかし、参加者は非古典論理やその周辺分野を専門に研究なさってる人が多かったため、食事や懇親会でその辺の分野の専門的で技術的な話題が出ることが多かったのです。非古典論理に疎い僕には、彼らの話題に付いていくことが全くできなくて、ちょっと困りました。 「いやー、僕、部分構造論理とか様相論理とかみたいな非古典論理って全然勉強したことないんですよ」ぼそっとそう呟いたら、「へー、ロジック（論理学）全然やってない人なんだー」という反応が。 その発言にちょっと違和感を覚えたのです
ペアノの自然数論とZFC集合論は同型？ - とりマセ
しばらくドイツ出張でまたブログの更新が出来ないので、ちょこっと話題提供代わりにちょっとした記事を書き残していくことにします。 さて、論理学を学んでいる人には有名かもしれませんが、数学基礎論において、マリアン・プール-エルとソール・クリプキによる一見すると驚愕の定理があります。 それは、自然数論の理論であるはずのペアノ算術と、もっと遥かに巨大な理論であるはずのZFC集合論が、証明の形式を見る限りでは同型であるというものです。 プール-エルとクリプキの定理 (1967)実効的分離不可能理論たちの間には演繹を保つ計算可能な同型写像が存在する。したがって、特にペアノ算術とZFC集合論の間にも演繹を保つ計算可能な同型写像が存在する。 プール-エル＆クリプキ「自然数論と集合論は実は同型だったんだよ！！」Ω ΩΩ「な、なんだってー！！」 現代数学基礎論から見たプール-エルとクリプキの定理 この定理は、
再帰理論史<2> --再帰理論的エルランゲン・プログラム-- - とりマセ
数学基礎論の一分野として誕生した再帰理論。この分野は一体どのように発展してきたのでしょうか。 1930年代〜1950年代の研究の流れは前回の記事を参照してください。 再帰理論 --ゲーデルの不完全性定理以後--（1930〜50年代） - とりマセ というわけで、今回は、再帰理論の1960年代以降の歴史です！しかし、どんな数学理論も、時代を経るにつれ細分化してゆき、その研究の流れを直線的に解説するのは困難になります。再帰理論だって、その例外ではありませんでした。このため、1960年代以降は幾つかのトピックに分けて、その中での歴史を紹介していこうと思います。 エミール・ポストの問題を中心として大きな発展を遂げた次数の研究。再帰理論における次数の研究は、エミール・ポストの死後、何処へと向かっていったのでしょう。そのうちの一つが、「再帰理論的エルランゲン・プログラム」こと という構造の不変量の研究
再帰理論 --ゲーデルの不完全性定理以後--（1930〜50年代） - とりマセ
某所で再帰理論の最近の研究の流れの話が出たので、せっかくなのでブログに纏めておきます。 数学基礎論の大きな分野のひとつとして、ゲーデルらの研究を発端として生まれた再帰理論。 では、ゲーデルの不完全性定理以後、数学基礎論の一分野である再帰理論は、どのような発展を遂げたのでしょうか。今回は、1950年代までの再帰理論の研究の歴史を辿ってみましょー。 1930年代 1930年代。チャーチ、ゲーデル、チューリング、クリーネその他多くの研究者による研究、そしてゲーデルの不完全性定理を発端の一つとして、計算可能性と計算不可能性の研究が始まりました。1930年代の計算論の研究の始まりは歴史的に非常に重要ですが、詳しい文献がたくさんあるので、ここでは省略します。 このような1930年代の研究によって、計算という概念が数学的に定義され、コンピュータ開発もたぶん順調に進むことになったのでしょう。しかし何よ
チャイティンのオメガとランダム性 - とりマセ
今日は、アルゴリズム的情報理論から一つの話題です。 「チャイティンのオメガ」 それは、不完全性定理、ランダム性、様々な概念に関わる不思議な実数。 曰く。 チャイティンのオメガとは、擬似乱数とかそういうレベルではなく、本物の乱数である。 曰く。 チャイティンのオメガとは、それを知ればあらゆる物事が分かる、知識の湧き出す泉である。 曰く。 チャイティンのオメガさえ分かれば、ゴールドバッハ予想もリーマン予想も P=NP問題も、全ての数学の問題は解決してしまう！ このような噂がまことしやかに囁かれるチャイティンのオメガ、果たして、これらの話は全て真実なのでしょうか？ ……真相や如何に！？ オメガってなあに？ チャイティンのオメガとはプログラムの停止確率として定義されます。 プログラムが停止するというのは、 そのプログラムを実行したとき、 無限ループとかに陥ったりせずに正常に計算を実行し終える。と
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
ランダムネスの不思議な世界 - とりマセ
ランダム「無秩序の世界にようこそ！」 - とりマセ