読者です 読者をやめる 読者になる 読者になる

ゆるゆる べんきょう

暇だから哲学・数学・物理学をゆるく勉強しているよ

トートロジーと論理的帰結

モデル・値付けw(wα=1)を充足関係 w|=α と捉えなおす。論理式φ∈Fはモデルによって充足したり、しなかったりするが、任意のモデルに対して充足する論理式があり、トートロジーと呼ぶ。任意のモデルに対して充足しない論理式があり、矛盾と呼ぶ。αを充足する任意のモデルに対してXが充足するとき、論理的帰結と呼び、 α|=X とかく。充足関係と論理的帰結に同じ記号を割り当てるが、特に混乱はないはず。

 

論理的帰結に関し、 X,α |= β ⇒ X |= α→β という演繹定理が成り立つため、これを帰納的に利用することで、任意の論理的帰結の妥当性は、ある種の論理式がトートロジーであるかどうかという問題に帰結し、決定可能である。

 

命題論理: 同値関係と標準形

n個の原子命題からなる論理式は、#Bn = 2^2^n 個あるf: 2^n → 2 なる関数と同一視できる。この同一視(意味論的同値関係)は、数学でいうところの同値関係(同一律、反射律、推移律を満たす)であるため、n個の原子命題からなる論理式全体からなる集合 Fn は意味論的同値関係によってパーティショニングすることができる。そして、各パーティションは、DNFもしくはCNFの形式の論理式で代表させることができる。別の言い方をすると、任意の論理式はDNFもしくはCNFと意味論的同値関係にある。

さらに、意味論的同値関係は、congruenceな関係でもある。それにより、論理式の一部を、意味論的同値関係にある別の論理式に置換してもよいという定理が得られる。

さらにさらに、δ: F→F を、帰納的に以下で定める。すなわち、 π→π, ¬α→¬δ(α), α∧β→δ(α)∨δ(β), α∨β→δ(α)∧δ(β)。このようなδで射影される二つの論理式 φ→ψを双対関係という。DNFとCNFは互いに双対関係であり、また、δδ=1である。

1階命題論理: 統語論と意味論

統語論に関するいくつかのメモ

命題論理の論理式は帰納的に定義できる/命題論理の式全体をFとする. π ∈ F で、 α,β ∈ F ⇒ ¬α , α∧β , α∨β ∈F 。部分集合 Sf も帰納的に定義できる Sf π = {π}, Sf ¬α = {¬α}∪Sf α, Sf α○β = {α○β}∪Sf α ∪ Sf β 

n個の変数からなる論理式Pが与えられたとき、Pが示す関数 f: 2^n → 2 ∈ Bn を一意に指定できる. なお、#Bn = 2^(2^n) である. n個の変数からなる論理式は加算無限個あるが、指示される関数全体の集合 Bn は要素を有限個しか持たない

括弧は読みやすさのために導入される。ポーランド記法など括弧を用いないように統語論を定めることもできるが、通常は括弧を含める。

真理値割り当て w: PV → 2 は、原子論理式全体から2への写像として理解されるが、これにより F→2 も一意に定まることから、 w: F → 2 ということもできるため、別の文字w' などを持ち出す必要はない

参考書

このブログで勉強した素材を一覧化し、寸評します。

 

古典論理

野矢: 論理学 ★★★★★

https://www.amazon.co.jp/dp/4130120530

3人の対話形式。前提知識不要。東大教授。最初の一歩に最適。

〇:対話形式なので素朴な疑問に答えてくれる

〇:前提知識不要なので、この1冊だけで完結して読める

〇:論理学の背後にある哲学思想がわかる

×:網羅的でない。特に完全性の説明はすっぽり抜けている

×:タブローや自然演繹などオブジェクトレベルの記述が少ない

 

北田:ゲーデル 不完全性定理発見への道 ★★★

https://www.amazon.co.jp/dp/4768703917/

理系への数学の連載をまとめたもの。薄い。

〇:薄いのでさっと読める

〇:実際にゲーデル述語を構成している!

×:自己完結していない。勝手に未説明の用語を使う

×:章構成があまりうまくない。いったりきたり

 

戸次:数理論理学 ★★★★

https://www.amazon.co.jp/dp/4130629158/

お茶大教授。東大出版。かなりガチ。

〇:自己完結している

〇:古典論理に関しては完全に網羅している

〇:証明論がかなり詳しい

×:数学書のように定義・定理・証明の連続。無機質な説明。

×:演習の回答がない

 

Rautenberg:A Concise Introduction to Mathematical Logic ★★★★

https://www.amazon.co.jp/dp/1441912207/

かなりレベル高め。院レベル。英語(原書はドイ語)。

〇:1,2章が無料で読める。教授のページから。

 

集合論

Pinter: Set Theory ★★★★★

https://www.amazon.co.jp/dp/0486497089

Doverなので安い。前提知識不要。BNGな公理的集合論

〇:歴史的背景がしっかり書かれている

〇:自己完結。

〇:演習が豊富(回答はない)

×:強制法について書かれていないような気がする

×:やや冗長

 

志賀:無限への飛翔 ★★

https://www.amazon.co.jp/dp/4314010428

簡単。素朴集合論について。

〇:気楽に読める。ブルーブックスみたい

×:勉強向けの本ではない

 

 

論理学ちゃんと勉強

とりあえず、論理学の勉強として

あたりをやって、入門はできたと思う。一方、勘違いも多そうだし、あやふやなまま理解があるであろうことは考えられるので、ここで一つきちんとした教科書で勉強したいものだと思う。そこで、以下を今月の間に読もうと思う。

 

 

戸次は所有しているが、Rautenbergは高いので買っていない。1,2章は教授のページからダウンロードできるのでそれを利用しようと思う。

 

 

 

北田 発見への道 10章 (終)

10章 ゲーデル述語

前章からの続き。ロッサー文およびゲーデル文に出てくる述語を数値的に表現する。その際、自身のゲーデル数を自身に代入するという事情のため、ゲーデルナンバリング自体が数論的操作であることを示す必要があり、じっさいにそれを示す。

 

以上により、ゲーデル述語を実際に構成してみることにより、ロッサー文、およびゲーデル文で存在が予測されていた述語を帰納的に構成することができ、不完全性定理の証明が完成したことになる。

 

ゲーデル不完全性定理が完全に統語論的に導かれたとするならば、ヒルベルトプログラムを挫折させたといえるだろうが、その証明にはその意味論的操作が必要であったことは指摘したとおりである。意味論的な操作により、自己言及的な命題が記述可能になり、自己言及的な命題は様々な矛盾や困難を生み出すことになる。また、メタレベルにおいて対象の形式と同じ道具立てを利用しているというのも注目するべき点である。

 

最近ではメタな議論に選択公理集合論の公理を仮定することも珍しくなくなっている。

 

この章で大体ゲーデル不完全性定理の証明が終わったかな。結局対角化定理を使わないでロッサー型のゲーデル文を証明することで不完全性定理を証明したと。

 

残りの2章は哲学的なのでさらっと流すことにして、ブログでは、言及しないことにする。短い中でもなかなか示唆に富んだ良い本だったように思う。

 

 

北田 発見への道 9章

9章 証明の数値的表現

これまでの議論において、「xは公理である⇔Axiom(x)」や「xは証明列である⇔Proof(x)」といった、ゲーデル数を引数にとる述語を、自然数論の体系 N において再帰的に構成できると述べてきた。それを示している。

 

なお、「xは証明可能である⇔Pr(x)」、「xは反証可能である⇔Re(x)」もNにおいて表現できるが、それは再帰的ではない。

 

コンピュータ言語みたいっすなー。一つ一つはきちんと見ていないが実際にできるだろうということは納得がいく。