不可能性の証明

不可能性の証明で広く用いられている方法の一つに、背理法があります。この証明方法では、ある命題（例えば、特定の種類の方程式の解）が成り立つと仮定した場合、演繹によって、互いに矛盾する二つの事柄（例えば、ある数が偶数かつ奇数である、あるいは負の数かつ正の数であるなど）が成り立つことが示されます。矛盾は元の仮定から生じるため、仮定された前提は不可能であるに違いないということになります。

対照的に、非構成的な不可能性の証明は、考えられるすべての反例が無効であることは論理的に矛盾していることを示すことによって進められます。つまり、考えられる反例のリストにある項目のうち少なくとも1つは、実際に不可能性の予想に対する有効な反例でなければなりません。例えば、無理数のべき乗を無理数のべき乗にすると有理数になることは不可能であるという予想は、考えられる2つの反例のうち1つが有効な反例でなければならないことを示すことによって反証されましたが、どちらが有効な反例であるかは示されていません。

不可能な予想を否定する最も分かりやすい方法は、反例を一つ示すことである。例えば、オイラーは、 n個の異なるn^乗を足し合わせると、別のn^乗になるという予想を提唱した。この予想は 1966 年に否定され、わずか 4 種類の異なる 5 乗を足し合わせると別の 5 乗になるという反例が示された。

反例による証明は、主張を反証する対象物を示すという点で、構成的証明の一形態である。

社会選択理論において、アローの不可能性定理は、独裁的ではなく、かつ無関係な選択肢からの独立性と呼ばれる合理的行動の基本的要件を満たす順位選択投票システムを考案することは不可能であることを示している。

ギバードの定理は、2つ以上の結果を持つ戦略耐性のあるゲーム形式（つまり、支配戦略を持つゲーム形式）はすべて独裁的であることを示している。

ギバード＝サタースウェイトの定理は、他者の投票行動に関わらず、いかなる決定論的な投票システムも、あらゆる状況下で戦略的投票に対して完全に無敵であることはできないことを示す特殊なケースである。

啓示原理は、口語的な意味で、ギバードの定理の「反対」を示す不可能性定理と見なすことができる。つまり、戦略をメカニズムに組み込むことで、あらゆるゲームや投票システムを戦略に対して耐性のあるものにすることができる。したがって、真実のメカニズムによって得られる解よりも優れた解を持つメカニズムを設計することは不可能である。

紀元前500年頃のピタゴラス による証明は、数学に大きな影響を与えた。それは、2の平方根は2つの整数の比として表すことができないことを示した。この証明によって、「数」は有理数と無理数という、互いに重なり合わない2つのグループに分けられた。 

プラトンの『テアイテトス』には、テオドロス（プラトンの師）が、

${\displaystyle {\sqrt {3}},{\sqrt {5}},...,}$

個々のケースをすべて合計すると、17平方フィートになり ます ...。^{[ 6 ]}

より一般的な証明によれば、整数Nのm乗根は、Nが整数nのm乗でない限り無理数である。^{[ 7 ]}つまり、共通の素因数を持たない2 つの整数aとbの比a ⁄ bとして整数Nのm乗根を表すことは、 b = 1の場合を除いて不可能である。  

ギリシャ幾何学はコンパスと定規の使用に基づいていた（ただし、定規は厳密には必須ではない）。コンパスを使うことで、幾何学者は互いに等距離にある点を作図することができ、これはユークリッド空間では暗黙のうちに平方根の計算に相当する。作図方法について問う4つの有名な質問がある。

1. 与えられた角度を三等分する一対の直線。
2. 与えられた立方体の体積の2倍の体積を持つ立方体。
3. 与えられた円の面積と等しい面積を持つ正方形。
4. 辺の数が任意の正多角形。

2000年以上もの間、これらの問題を解決しようとする試みは失敗に終わり、ついに19世紀になって、コンパス以外の追加の道具を認めなければ、望ましい構造は数学的に不可能であることが証明されました。^{[ 8 ]}

これらはすべてユークリッド作図の問題であり、ユークリッド作図はユークリッド数のみを含む場合にのみ実行できます（後者の定義による）。^{[ 9 ]}無理数もユークリッド数になり得ます。良い例は、2の平方根（無理数）です。これは、長さが両方とも1単位の直角三角形の斜辺の長さであり、定規とコンパスで作図できます。しかし、ユークリッドの数世紀後に、ユークリッド数は加算、減算、乗算、除算、平方根の抽出以外の演算を一切含まないことが証明されました。

一般角を三等分することと立方数を2倍にすること はどちらも立方根を取る必要があるが、立方根は作図可能な数ではない。

${\displaystyle \pi }$これはユークリッド数ではないので、ユークリッドの方法では、直径が1の円の円周に等しい長さを構成することは不可能である。

なぜなら${\displaystyle \pi }$1882年に超越数であることが証明されたが、ユークリッド数ではない。したがって、長さの構成${\displaystyle \pi }$単位円から出すことは不可能である。^{[ 10 ] [ 11 ]}

ユークリッドの『原論』の平行線公準は、直線と、その直線上にない点が与えられたとき、その点を通る直線に平行な線はただ1本しか引けないという命題と同等である。他の公準とは異なり、これは自明ではないと考えられていた。ネーゲルとニューマンは、これは公準が空間の「無限遠」領域に関係するためかもしれないと主張している。特に、平行線は漸近線とは対照的に、「無限遠」でも交わらないと定義されている。^{[ 12 ]}この自明性の欠如という認識から、他のユークリッドの公理や公準から証明できるかどうかという疑問が生じた。平行線公準を他の公準から演繹することは不可能であることがガウス、ボヤイ、ロバチェフスキー、リーマンの著作で示されたのは19世紀になってからのことだった。これらの著作は、さらに平行線公準は代替案に置き換えることができ、非ユークリッド幾何学につながることを示した。

ネーゲルとニューマンは、平行線公準によって提起された問題を「…おそらく、その後の数学的歴史に及ぼした長期的な影響の中で最も重要な発展」とみなしている。^{[ 12 ]}特に、彼らはその結果を「知的に最も重要なもの」とみなしており、それは「特定の命題（この場合は平行線公準）を与えられた体系（この場合はユークリッドの最初の4つの公準）内で証明することが不可能であることを証明できる」ことを示したからである。^{[ 13 ]}

フェルマーの最終定理は、1600年代にピエール・ド・フェルマーによって提唱されたもので、方程式の解を正の整数で見つけることは不可能であると述べている。${\displaystyle x^{n}+y^{n}=z^{n}}$と${\displaystyle n>2}$フェルマー自身は無限降下法を用いてn  = 4の場合の証明を与え、その後他の特殊なケースも証明されたが、一般のケースは1994年にアンドリュー・ワイルズによって証明されるまで証明されなかった。 

「任意のディオファントス方程式は整数解を持つか？」という問いは決定不能である。つまり、あらゆる場合についてこの問いに答えることは不可能である。

フランツェンは、ヒルベルトの第10問題とMRDP定理（マティヤセビッチ・ロビンソン・デイビス・パトナム定理）を紹介し、「ディオファントス方程式に解があるかどうかを判定できるアルゴリズムは存在しない」と述べています。MRDPはチューリングの決定不能性の証明を使用しています。「…解けるディオファントス方程式の集合は、計算可能列挙可能だが決定不可能な集合の例であり、解けないディオファントス方程式の集合は計算可能列挙不可能である」。^{[ 14 ]}

1905年にジュール・リシャールによって提示されたこの深遠なパラドックスは、^クルト・ゲーデル^{[ 15 ]}とアラン・チューリングの研究に影響を与えた。簡潔な定義はプリンキピア・マテマティカ[ ^{16 ]}にある。

リチャードのパラドックスは…次のとおりです。有限個の単語 （「単語」とは記号のことです。強調のために太字で示しています）で定義できるすべての小数を考えます。Eをそのような小数のクラスとします。すると、Eは次のようになります。$\displaystyle \aleph _{0}}$[無限の数の]項。したがって、その要素は 1 番目、2 番目、3 番目、... と順序付けることができる。Xを次のように定義される数とする[ホワイトヘッドとラッセルはカントール対角線法を採用している]。n 番目の小数のn番目の桁がpである場合、Xのn番目の桁をp + 1 (またはp = 9の場合は 0 )とする。すると、n がどのような有限値であっても、Xのn番目の桁はEを構成するn番目の小数のn番目の桁と異なり、したがってX はn番目の小数と異なるため、 XはEのすべての要素と異なる。しかしながら、我々はX を有限個の単語で定義した[つまり、上記の「単語」の定義そのもの]。したがって、X はEの要素であるべきである。したがって、X はE の要素であると同時に、そうではない。    

クルト・ゲーデルは、自身の証明をリチャードのパラドックスの「類推」と考え、それを「リチャードのアンチノミー」と呼んだ^{[ 17 ]}。

アラン・チューリングはこのパラドックスを機械で構築し、この機械が単純な質問に答えられないことを証明しました。その質問とは、この機械は（自身を含め）どの機械も非生産的な「無限ループ」（つまり、対角線の計算を継続できなくなる状態）に陥るかどうかを判断できるかどうか、というものです。

ネーゲルとニューマン（68ページ ）の言葉を借りれば、「ゲーデルの論文は難解である。主要な結果に到達する前に、46の予備的な定義といくつかの重要な予備的定理を習得しなければならない」。実際、ネーゲルとニューマンは証明の説明に67ページもの序論を必要とした。しかし、読者がこの論文に取り組むだけの力があると自覚するならば、マーティン・デイビスは「この注目すべき論文は、知的ランドマークであるだけでなく、明快さと力強さで書かれており、読む喜びを与えてくれる」と述べている（デイビス著『決定不能』 4ページ）。

ゲーデルは、自身の言葉で次のように証明した。

「[プリンキピア・マテマティカとペアノの]公理は、与えられた体系で形式的に表現できるすべての数学的問題を決定するのに十分であるという推測を立てることは妥当である。しかし、以下では、そうではなく、むしろ、通常の整数の理論には、公理に基づいて決定できない比較的単純な問題が存在することを示す」（ゲーデル『決定不能』4ページ）。

ゲーデルは自身の証明を「リチャードのアンチノミー」（「アンチノミー」とは矛盾またはパラドックスのこと。詳しくはリチャードのパラドックスを参照）と比較した。

「この結果とリチャードのアンチノミーとの類似性はすぐに明らかです。また、嘘つきのパラドックスとも密接な関係があります（ゲーデルの脚注14：あらゆる認識論的アンチノミーは、同様の決定不能性の証明に利用できます）...したがって、我々は、自身の証明不能性を主張する命題に直面しています[15]。（彼の脚注15：見かけに反して、このような命題は循環的ではありません。なぜなら、まず、それは非常に明確な式の証明不能性を主張しているからです）」^{[ 17 ]}

• 決定問題（Entscheidungsproblem）は、1935年4月にチャーチによって初めて解決され、チューリングの論文が1936年5月に出版のために受理されたことから、チューリングより1年以上前に解決された。^{[ 18 ]}
• チューリングの証明は、必要な定義の数と、その微妙な性質のために難解です。詳細は、「チューリングマシン」および「チューリングの証明」を参照してください。
• チューリングの最初の証明（全3つのうち）は、リチャードのパラドックスの図式に従っています。チューリングの計算機は、「計算機」内の7文字の文字列で表されるアルゴリズムです。その「計算」は、すべての計算機（自身を含む）を「循環」の有無でテストし、循環しない、つまり「成功した」計算機の計算結果から対角線上の数を生成することです。この計算は、1から順番に、数値（8進数）を7文字の文字列に変換してテストすることで行われます。自身の数値に到達すると、自身の文字列を作成します。そして、それが成功した計算機の文字列であると判断しますが、この計算機（自身の）の計算を実行しようとすると、循環に陥り、先に進むことができなくなります。こうして、リチャードのパラドックスにたどり着きます。（もし理解できない場合は、チューリングの証明を参照してください。）

チューリングの証明の前後には、同様の決定不能性証明が数多く登場した。

1. 1935年4月：アロンゾ・チャーチの証明（「初等整数論の解けない問題」）。彼の証明は、「…有効計算可能性の定義を提案し…例を用いて、この種の問題すべてが解けるわけではないことを示す」ことであった（『決定不能』90ページ ）。
2. 1946年：ポスト通信問題（参考文献については、HopcroftとUllman ^{[ 19 ]} p.193ff  、p.407 を参照）
3. 1947年4月：エミール・ポストの証明（チューの問題の再帰的解不能性）（Undecidable p.  293）。これはその後「チューの単語問題」または「チューの単語問題」として知られるようになった（アクセル・チューはこの問題を1914年の論文で提唱した（Undecidable p. 303のポストの論文への参照を参照 ））。
4. ライスの定理：チューリングの第2定理の一般化された定式化（ホップクロフトとウルマン^{[ 19 ]} p.185ff参照 ）^{[ 20 ]}
5. グライバッハの定理：言語理論における決定不能性（ホップクロフトとウルマン^{[ 19 ]} p.205ff およびp.401の参照文献を参照 ：グライバッハ[1963]「最小線形文法の曖昧性問題の決定不能性」Information and Control 6:2、117–125、またp.402の参照文献 ：グライバッハ[1968]「形式言語の決定不能性に関する注記」Math Systems Theory 2:1、1–6。）
6. ペンローズタイルに関する質問。

専門家以外の方にも分かりやすい解説については、Beltrami の 108 ページ以降を参照してください。また、Franzen の第 8 章 137 ～ 148 ページ、および Davis の 263 ～ 266 ページも参照してください 。Franzén の議論は Beltrami のものよりかなり複雑で、Ω ― Gregory Chaitinのいわゆる「停止確率」― を掘り下げています。Davis の古い解説は、チューリング マシンの観点からこの問題にアプローチしています。Chaitin は、自身の研究と、それに伴う哲学的および数学的な影響について、数多くの著書を書いています。

文字列は、それより短いコンピュータプログラムから生成できない場合、（アルゴリズム的に）ランダムであると呼ばれます。ほとんどの文字列はランダムですが、有限個の短い文字列を除いて、特定の文字列がランダムであると証明することはできません。

「チャイティンの結果を言い換えると、十分に長い文字列がランダムであるという形式的な証明は不可能である…」^{[ 21 ]}

ベルトラーミは、「チャイティンの証明は、20世紀初頭にオックスフォード大学の図書館員G・ベリーが提起したパラドックスに関連している。そのパラドックスは、『1000文字未満の英語の文で定義できない最小の正の整数』を求めるものである。明らかに、この数の最短の定義は少なくとも1000文字でなければならない。しかし、引用符で囲まれた文は、それ自体が問題の整数の定義であり、長さは1000文字未満である！」と指摘している。^{[ 22 ]}