「選択公理で極大無矛盾な理論に拡張すれば不完全性定理と矛盾しないか?」¶

本文¶

こんさんと p 進大好き bot の基礎論というかロジック関係のトーク.

しかし「選択公理で極大無矛盾な理論に拡張すれば不完全性定理と矛盾しないか?」というのは一瞬悩んだしよい練習問題ではある.

@mr_konn 理論っていうものよく知らないんですけど, 理論全体のなす何かは集合として定式化できる感じですか? (そして選択公理ってここではメタ言語なんでしょうか. 選択公理が成り立つ集合理論の中で更に理論の全体を・・高階の論理や高階の圏論みたいで頭が痛くなりそうですね).

@non_archimedean 理論とは論理式の集合のことだと思えばよいです. 言語 L を固定すれば, 論理式の長さは有限ですから言語 L に含まれる記号の全体が集合なのなら L の論理式全体は集合をなし, ひいては L の理論の全体も集合になりますね.

@non_archimedean で, メタ理論云々の話ですが. この辺りは入り組んでいてパッと説明するのは難しいのですが ナイーブには選択公理が成り立つような集合論の中で論理式をエンコードして, それを自然数とかほかの数学的対象を集合論の中で扱うのと同じようにしていると思ってよいです.

@mr_konn なるほどー. この場合「理論」=「論理式の集合」は「原始命題系」で, それとは別に公理や演繹規則が既に固定されているという感じでしょうか? (それとも動くのは公理や演繹規則・・?)

@non_archimedean むしろ理論が公理系 (やそれに帰結を足したものでもよいですが) になっています. 論理的な公理や推論規則については, 基盤とする論理体系によって決まっていて, その上に理論を載せて数学をする感じです

@mr_konn 言語 L を集合と見るのはあくまで記号の問題ということでモデルをとっているわけではないと解釈すると, ここで公理系の「帰結」というのは「証明可能命題」よりむしろ「恒真命題」のことでしょうか. (その無矛盾公理系を充足するモデルが存在しない時どうなるのか分かりませんが).

@non_archimedean あぁ, たんに「理論に (集合として) 含まれる命題どうしが互いに独立でなくてもよい」くらいの意味です. ちなみに無矛盾な公理系には必ずモデルが存在し, 逆もまたしかりというのがゲーデルの「完全性」定理です.

@mr_konn 論理は 1 階なのですね・・

@non_archimedean はい. 集合論の内部なので一階で不自由ないですし, モデル理論はもっぱら一階の理論を扱います.

@mr_konn なるほど. しかし僕は論理弱者なようで結局 (排中律と自然数論を含んだ上で) どう矛盾が解消されるのか分かりませんでした・・. 答え (?) のようなものはございますでしょうか. ご教授していただけたら助かります.

@non_archimedean 不完全性定理の前提として, 理論が再帰的公理化可能であるという条件があります. つまり, 論理式が与えられた時に, それが公理であるかどうかをチューリングマシンなどで機械的に判定出来る必要があります. 選択公理で膨らませたら, 当然この条件は満たしません.

@non_archimedean 感覚としては「だったら実数に具体的な順序を入れて整列して見せてよ! 」「 W ・ O ・ T!W ・ O ・ T! 」とおなじ状況です

@mr_konn なるほど! そもそも不完全性定理を「自然数論を含む無矛盾な公理系」に対する主張だと思い込んで生きてきていました! 演習を解く舞台にも立てていませんでした・・. どうもありがとうございます.

この辺, 一度はきちんと勉強したいと思っているがなかなか機会がない. 数学ガールもラノベとしての楽しみ方しかしていなくてあまり数学を追っていない.

ラベル¶

数学, 数学基礎論, 数理論理