ゲーデルの定理-4.2A- 対角化定理(嘘つき島から)

共通参考文献はこちら
前回からの続き

　スマリヤンの本では正しいことしか言わない騎士と嘘しか言わない奇人の住む島の住人の発言が問題として出題される形がよく使われます。邦訳では騎士と奇人ではなく正直者と嘘つきと意訳した方が読者にわかりやすいのではという話もありますが、私は、あえて真偽とは直結しない名称を使うのも意味があるのではと考えます。

　その話はまたの機会として、ここでは前回の閉論理式4.1-1が騎士と奇人の島ではどんな命題に該当するのかという話をします。すなわち以下の式4.1-1は命題4.2-1aまたは命題4.2-1bに該当します。

　【再掲】式4.1-1 Ａ⇔Ｒ(ａ)　ただしａ＝~Ａ~
　命題4.2-1a 騎士と奇人の島の住人が「私の発言はＲである」と言った。
　命題4.2-1b 騎士と奇人の島の住人が「私は、Ｒの性質の発言を、する者である」と言った。

　なぜそうなるのか。まずＡを「この住人の発言内容(を記述する式)」と解釈します。すると「私(この住人)の発言はＲである」という命題はＲ(ａ)で記述できます。すると命題4.2-1a,bについて、もし発言者が騎士ならば命題Ａは真であり、このときＲ(ａ)も真になります。逆にＲ(ａ)で記述されている命題は「この住人の発言内容」ですから、Ｒ(ａ)が真なら命題Ａも真であり発言は騎士です。すなわちこの状況は式4.1-1で記述されています。

　なお式4.1-1のＡは[Ref-s3)p11]で定義されているゲーデル文になります。文脈の都合上、原文とは記号を変えてゲーデル文の定義を示します。

定義4.2-1. 以下の条件が成り立つとき、自然数ｎの述語式Ａ(ｎ)をゲーデル文と呼ぶ。
　自然数集合{ｒ}、Ａ(ｎ)、Ａ(ｎ)のゲーデル数ａ_nとして、
　　Ａ(ｎ)が真、ならば ａ_n∈{ｒ}　かつ逆も成立
　となるような自然数集合{ｒ}が存在する。

　論理式Ａ(ｎ)が真というのは、ひとまずモデルでの対応する関係Ａ(ｎ)が真であることとしてください。ゆえに具体的な{ｒ}は、論理式Ａ(ｎ)のみならずモデルも決めないと決まりません。{ｒ}は式4.1-1の命題Ｒ(ｘ)を使えば「命題Ｒ(ｘ)を満たす自然数ｘの集合」つまり「命題Ｒ(ｘ)が真となる自然数ｘの集合」になります。別の言葉では「命題Ｒ(ｘ)は集合{ｒ}を内包的に定義している」ことになります。内包的定義と外延的定義については(2010/10/11)の記事[ある組織-5-内包公理]の注を御参照ください。

　注意しておくと、集合{ｒ}を内包的に定義する命題Ｒ(ｘ)を記述する論理式Ｒ(ｘ)が存在するとは限りません。まして論理式Ｒ(ｘ)が命題Ｒ(ｘ)を(むろん(2015/11/15)の記事[ゲーデルの定理-3.1-]で定義した意味で)表現するとは限りません。

　命題Ｒ(ｘ)を自然言語で記述すれば「ｘをゲーデル数とする論理式(が記述する命題)は、Ｒに対応する(論理式世界での)１項関係にある」ということになるでしょう。「ｘをゲーデル数とする論理式」といった対象は、例えばペアノ公理系なら表現可能であることは、ゲーデルが証明しました。が、Ｒ(ｘ)という命題が記述できるかどうかは、その定義によってくるでしょう。例えばＲ(ｘ)が「証明できる」という意味を持つならばペアノ公理系では構成できるが表現可能ではありませんでした。ではＲ(ｘ)が「ｘをゲーデル数とする論理式は真である」という意味を持つならばどうなるか？、という話が次回のテーマです。