アリストテレス以来の天才と激賞され、天才フォン・ノイマンから尊敬され、アインシュタインが唯一の友と考えたゲーデル先生ですが、我々凡人にはなかなか理解されません。
ただその影響力は甚大ですし、そのインパクトを単なる歴史的な知識ではなく、身体に入れておきたい感覚ではあります。
その感覚とは不完全性定理の肝である「自己言及のパラドックス」です（自己言及のパラドックスが不完全性定理の定理の肝であると言うと、専門家の先生方からは苦言を呈されることは確実なのでしょうが(；・∀・)）
寺子屋ではまず新約聖書のあまりに有名な一節からスタートしました。引用とリンクはいつもながらWikisourceです。
（引用開始）
クレテ人のうちのある預言者が「クレテ人は、いつもうそつき、たちの悪いけもの、なまけ者の食いしんぼう」と言っているが、この非難はあたっている。
（引用終了）
テトスへの手紙１章１２節～１３節途中
これの何が有名かと言えば、抽出して考えれば、『クレテ人が「クレテ人はいつもうそつき」と言った』ということになるからです。
新約聖書では、クレテ人となっていますが、我々は慣れたクレタ人として表記します。
クレタ人が「クレタ人をうそつき」と呼ぶのが何が問題かと言えば（自国民の悪口とかそういう政治的な話ではなく）、これが深刻な自己言及のパラドックスを引き起こすからです。
寺子屋では、このどこが自己言及のパラドックスかのワークを厳密にやりました。
頭ではわかっていても、実際に出力すると（口に出そうとすると）意外と戸惑います。
我々の通常の自然言語処理ではこのような言及は問題とされないからです。
普通に考えれば分かりますが、「おれ、実はうそつきでさ～」と言ったとして、「その発言の真偽値は決定不能だね」などと返答されることはまずありません。
しかし我々の友人であるAI（人工知能）くんは少なくとも困るかもしれません。
ちなみにニュートンの友人は真理だそうです（マリではありません、シンリです。冗談です）。
Amicus Plato— amicus Aristoteles— magis amica veritas.
「プラトンもお友達、アリストテレスもお友達、しかし本当の友達は真理！」
余談はさておき、AI君の気持ちになるためにも、ゲーデルの不完全性定理の感触を味わうためにもこの自己言及のパラドックスは身体にいれておきましょう。
何が問題なのでしょう？
ちなみに、このようなパラドックスを考えるときは、ノートかホワイトボードか黒板かパピルスに書き記すほうがいいです。脳の最大の機能は「使っている振りをすること」です。脳は勝手に考えたふりをして、分かったふりをしますので、それを避けるためにも出力したほうがいいです（これは何かを考えているときも同様です。ある程度、発酵してきたら出力したほうがいいです）。
「クレタ人はうそつき」という命題が真だと考えます。
そうするとクレタ人＝うそつきということになります。
うそつきという属性を持つクレタ人は嘘しか言いません。逆に言えば、その逆を取れば真理命題ということになります。
さてうそつきのクレタ人がこう言いました。「クレタ人はうそつきだ」と。
とすると、この命題は明らかに偽となります。なぜなら命題の中身にかかわらず、話者がうそつきだからです。
すると、「クレタ人はうそつき」という命題は嘘となります。
すると、クレタ人はうそつきの反対で、クレタ人は正直者というのが真となります。
すなわち、クレタ人は正直者です。嘘つきなのに正直者という矛盾がまずここで生じます。
しかし、正直者であるとして、話を薦めます。すると、その正直者のクレタ人がこう言いました「クレタ人はうそつき」だ、と。
すると正直者が言っている以上は、その命題はいつも真です。いつも正しいことしか言いません。
ということは正直者が言っている以上は、その言っていることは正しいということになり、この「クレタ人はうそつき」だという命題も正しいということになります。
それゆえ、クレタ人は嘘つきということになります。正直者のクレタ人なのに嘘つきという矛盾がまた生じます。すると、嘘つきのクレタ人が「クレタ人はうそつきだ」と言ったということになり、スタートに戻ります。何度も繰り返して、終わりません。無限ループします。命題の真偽値はは決定不能です。
命題の真偽値はクレタ人が嘘つきか正直者かの定義によってくるくる変わります。クレタ人が嘘つきか正直者かもくるくる変わります。
このくるくる変わるという感覚を持つことが重要です。これを実際に手を動かして論理ステップを踏みながら、体感することが大切かと考えます（単なる知識として知っていることと、手を動かして体験したことでは自ずとそのアルゴリズムは異なります。生きた知識とするためには、最小の労力でも良いので作業することです）。このパタンパタンと変わっていく様と、終わりが頭につながるという無限ループは、あたかもエッシャーの「上昇と下降」の無限階段のようです。
M. C. Escher "Ascending and Descending"
１つ自己言及のパラドックスが分かれば、他のパラドックスもそのカラクリが見えます。
たとえば、『「張り紙するな」という張り紙』、「自分で髭を剃らない人のための理髪師のひげは誰が剃るのか」という床屋（理髪師）のパラドックス、ラッセルのパラドックスなども理解可能です（多分）。
対角線論法もシンプルに理解して（今回の寺子屋ではあえて外したので、秋の復習講座でやりましょう）。自己言及と対角線論法から、ゲーデルに切り込みましょう。
ちなみに、ゲーデルの原論文への切り込みは寺子屋では避けています。言及したのは前書きと終わりの部分のみです。なぜかと言えば．．．難しいからです。
たとえば、プリンキピアを理解するには、F=maという運動方程式を微積分で扱えばよく、ニュートンがやってみせたように（本人は流率法として微積分を使いながら）幾何学を用いて学ぶことに意味はありません。文献学としては意味があるでしょうが、同じアルゴリズムならば易しい方を選びます。
ローマ数字よりもアラビア数字を用いるのと同じです。同じ数のアルゴリズムならば表記が易しく合理的な方を選びます。
その点について、チャイティンはこう言います。
（引用開始）
手短に言うと、ゲーデルは不完全性を、チューリングは計算不可能性を、私はランダム性を発見しました。
（略）
私のアプローチは、ゲーデルやチューリングの方式同様に複雑ですが、その複雑さが異なります。ゲーデルの場合は、それは公理系の内部構造、原始帰納定義スキーマ、および、彼のゲーデル数の番号付けが複雑なのでした。チューリングの場合は、彼の1936年の論文で説明された、万能チューリングマシンのインタープリタープログラムが複雑でした。私の場合には、（チューリングの複雑な万能マシンに相当する）LISPインタープリターが複雑です。これはみなさんには見えません。
（引用終了）
これは寺子屋のレジュメでも用いましたが、ポイントは用いているアルゴリズムが異なるという話です。
ゲーデルの複雑さは「公理系の内部構造、原始帰納定義スキーマ、および、彼のゲーデル数の番号付け」であり、チューリングは「万能チューリングマシンのインタープリタープログラム」そして、自身のチャイティンは「（チューリングの複雑な万能マシンに相当する）LISPインタープリター」が複雑です。
計算尺で宇宙へ行くか、新しいコンピュータで行くかの違いです。速度は異なるでしょうが、やっている演算は同じです。
とすると、Lispで理解するのが最もエレガントということになります。
ただチャイティンの証明を見ても、何かを証明した感じがしません（我々の抽象度がまだ及ばないので）そのときは、地を這うようなゲーデルの計算をチラッと覗き見るのも面白いかもしれません。
ゲーデルについて引用したのはこちら。
彼の頭の中が少し垣間見ることができます。
誤解されがちですが、特殊相対性理論という論文がないように、不完全性定理という論文もありません。「『プリンキピア・マテマティカ』およびその関連体系における形式的に決定不能な命題についてⅠ」というのがタイトルです。
（引用開始）
どんな形式体系も、論理式は外見上、原子記号（変項、論理記号、括弧、句読点）の有限列であり、どの記号列が意味ある論理式であるか否かを正確に記述することは容易である。同様に、証明は、形式上（ある特定の性質をもつ）論理式の有限列に他ならない。もちろん、メタ数学的な考察においては、原始記号そのものがどんなものかは重要ではなく、われわれはこの用途に自然数を割り当てることにする。
すると、論理式は自然数の有限列、証明は自然数の有限列の有限列となる。こうしてメタ数学的概念（や命題）は、自然数や自然数の列についての概念（や命題）になる。（略）さて、以下では、体系PMで決定不能な命題、つまりAもnot-Aも証明できない命題Aを構成する。（略）以上の議論がリーシャルのパラドックスと類似していることが注目される。「うそつきのパラドックス」とも密接に関わっている。（脚注１４どんな認識論的パラドックスも、決定不能命題の存在論の同様な証明に使える）
『プリンキピア・マテマティカ』およびその関連体系における形式的に決定不能な命題についてⅠ
（引用終了）
『すると、論理式は自然数の有限列、証明は自然数の有限列の有限列となる。こうしてメタ数学的概念（や命題）は、自然数や自然数の列についての概念（や命題）になる。』という記述がポイントかと思います。
論理式と証明が、あっさりと（いや大変な困難を伴いますが）、自然数や自然数の列になってしまったということです。
「論理式は自然数の有限列、証明は自然数の有限列の有限列」になったということです。
このための準備を膨大に行った後で、非常にシンプルな以下の証明に入ります。すなわち、「体系PMで決定不能な命題、つまりAもnot-Aも証明できない命題Aを構成する。」いわゆるGです。ゲーデル文であり、決定不能な命題です。これが不完全性定理の肝となります。
ゲーデル自身はこの議論を自身の手で発展させたかったのでしょうが（だからこそ論文にはⅠとあります）すかさずチューリングがチューリングマシンの計算不可能性によって援護射撃をします。
それについてゲーデル先生は論文の附記でこう書きます。
（引用開始）
附記
（略）その後の発展の結果、とくにA.M.チューリングの仕事のお陰で、いまや形式体系の一般概念について厳密で、疑いなく妥当な定義が得られるようになり、それにより定理ⅥとⅪの完全に一般的な表現が可能になった。すなわち、つぎのことが厳密に証明される。ある程度の有限的算術を含むどんな無矛盾な形式体系にも決定不能な算術命題が存在し、さらにそのような体系の無矛盾性はその体系において証明できない。
（引用終了）
とは言え、今回は自己言及のパラドックスのイントロダクションではなく、１１月の寺子屋でもとうとう登場するクリプキ様のこんな自己言及パラドックスを紹介したいと思っていました。
長くなりましたが、簡単に紹介します。
いわゆるウォータゲートのパラドックスです。某所でのセミナーにて紹介しました。
（引用開始）
（１）ウォーターゲート事件に関してニクソンが言ったことの半分以上は偽である。
（２）ウォーターゲート事件に関してジョーンズが言ったあらゆることは真である。
（引用中断）
特に、パラドックスも自己言及も出てこなさそうな普通の命題です。
両方共、真であっても問題はありません。そのような状況はありえます。
しかし、これに続けて、
（引用再開）
（１）を言ったのはジョーンズであった。そしてそれがジョーンズがウォーターゲート事件に関してなした唯一の発言だった。
一方、（２）を言ったのはニクソンであった。そして、この発言以外にウォーターゲート事件に関してニクソンが言ったことはちょうど真・偽が半分ずつであった。
（引用終了）（以上、pp.90-91 論理学をつくる）
とあると、途端にパラドックスが生まれます。
パラフレーズしてみましょう。
（２）のニクソンの発言が真だと仮定します。
すると、「ウォーターゲート事件に関してジョーンズが言ったあらゆることは真である。」は真であるとなります。
すると（１）を言ったのはジョーンズです。そしてそれが唯一の発言であることから、
「ウォーターゲート事件に関してニクソンが言ったことの半分以上は偽である。」という命題は真となります。
しかしここで問題が生じます。「この発言以外にウォーターゲート事件に関してニクソンが言ったことはちょうど真・偽が半分ずつであった。」という制約がある以上は、「ウォーターゲート事件に関してニクソンが言ったことの半分以上は偽である」ことから、ニクソンのこの発言は偽となります。
とすると、ニクソンの「ウォーターゲート事件に関してジョーンズが言ったあらゆることは真である。」が偽であるとなれば、「ウォーターゲート事件に関してジョーンズが言ったあらゆることは偽である」ということになります。
とすると、ジョーンズの言った「ウォーターゲート事件に関してニクソンが言ったことの半分以上は偽である。」は偽ということになります。とすると、「ウォーターゲート事件に関してニクソンが言ったことの半分以上は真である」ということになり、「この発言以外にウォーターゲート事件に関してニクソンが言ったことはちょうど真・偽が半分ずつであった。」という制約がある以上は、「ウォーターゲート事件に関してニクソンが言ったことの半分以上は真である」ことから、ニクソンのこの発言は真となります。とするとまた仮定と矛盾し、ふたたび無限ループに陥ります。
まあここから見出される結論は、パラドックスを生むかどうかは、文がどのような状況で使われるかに依存する、そしてパラドックスの責任は文それ自体ではなく、文とそれが使われる状況による。また自己言及を含んでいるような文でもパラドックスが生じないように使うことは可能ということです（たとえば、「この文は日本語の文です」は自己言及を含むがパラドックスは含まない）。
というわけで長々と書きましたが、ゲーデルの不完全性定理の肝としての自己言及のパラドックスの風景は脳の不思議な部分を使う感覚があります。ぜひ使っておきましょう！
１１月の寺子屋はクリプキ様の登場です。
１１月の寺子屋も寺子屋・秋の集中講座もお楽しみに。
【書籍紹介】
論理学でも紹介した書籍ですが、上記で引用したので、再度紹介します。
ゲーデル数化などについても、３６５ページに非常に簡潔に紹介されています。
素因数分解の一意性とすべての論理式が枚挙可能であることがどうしてもつながらない人はぜひ読んでみると良いかと思います。
ゲーデルの論文を引用したものと、チャイティンの著作はいま手もとに見当たらないので（寺子屋のレジュメから引き写しました）、見つかり次第紹介します。
論理学をつくる/名古屋大学出版会
￥3,990
Amazon.co.jp
名指しと必然性―様相の形而上学と心身問題/産業図書
￥2,835
Amazon.co.jp