不可能の証明

数学において、不可能定理は、ある問題または一般的な一連の問題が解決不可能であることを実証する定理である。これらは、不可能性の証明、否定的証明、または否定的結果とも呼ばれる。不可能定理は、多くの場合、解決策が存在しないことを証明することによって、解決策を探すのに費やされた数十年または数世紀の作業を解決する。何かが不可能であることを証明することは、通常、逆のタスクよりもはるかに困難である。なぜなら、特定の例を示すだけでなく、一般に機能する証明を開発する必要があることが多いからである。^[1]不可能定理は通常、否定的な存在命題または論理学の 普遍命題として表現できる。

2の平方根の無理数は、最も古い不可能性証明の1つです。これは、2の平方根を2つの整数の比として表すことが不可能であることを示しています。もう1つの重要な不可能性証明は、1882年のフェルディナント・フォン・リンデマンの証明であり、円の^二乗問題は、 πが超越数（つまり、非代数的）であるため解くことができず、代数的数の部分集合のみがコンパスと定規で構成できることを示しました。他の2つの古典的な問題、一般角を3等分することと立方体を2倍にすることもまた、19世紀に不可能であることが証明され、これらすべての問題は、より複雑な数学的構造の研究を生み出しました。

20世紀に発見された不可能性に関する最も重要な証明のいくつかは決定不可能性に関するものであり、これは一般にいかなるアルゴリズムでも解決できない問題が存在することを示し、その中で最も有名なものの1つが停止問題である。ゲーデルの不完全性定理は、形式システムの証明可能性における根本的な限界を明らかにした他の例である。^[3]

計算複雑性理論では、相対化（神託の追加）などの手法により「弱い」不可能性証明が可能になり、相対化の影響を受けない証明手法ではP対NP問題を解決できない。^{[4]もう1つの手法は、}複雑性クラスの完全性の証明であり、問​​題がそのクラスの他の問題と同じくらい解決が難しいことを示すことで、問題の難しさの証拠を提供します。特に、そのクラスの問題の1つが解決不可能である場合、完全な問題は解決不可能です。

不可能性証明の広く使われているタイプの 1 つに、背理法による証明があります。このタイプの証明では、特定のクラスの方程式の解などの命題が成り立つと仮定すると、演繹によって、数が偶数でもあり奇数でもある、または負数でもあり正数でもあるなど、互いに矛盾する 2 つの事柄が成り立つことが示されます。この矛盾は元の仮定から生じるため、これは仮定された前提が不可能であることを意味します。

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

背理法による証明のもう1つのタイプは降下法による証明であり、これはまず、あるクラスの方程式に対する正の整数^{[5]解など、何かが可能であり、したがって最小の解が存在するはずであると仮定することから始まります（}整列原理により）。次に、想定される最小の解から、より小さな解が見つかることが示されますが、これは以前の解が可能な限り最小の解であるという前提と矛盾しており、解が存在するという当初の前提は誤りであることを示しています。

不可能予想を反証する明白な方法は、単一の反例を提供することです。たとえば、オイラーは、さらに別のn^乗を足し合わせるには、少なくともn^個の異なるn乗が必要であると提唱しました。この予想は 1966 年に、別の 5 乗を足し合わせるとさらに別の 5 乗になる 4 つの異なる 5 乗のみを含む反例によって反証されました。

27 ⁵ + 84 ⁵ + 110 ⁵ + 133 ⁵ = 144 ⁵。

反例による証明は、主張を反証する対象が示されるという点で、 構成的証明の一種です。

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

ギバードの定理は、 2 つ以上の結果を持つ戦略不可能な ゲーム形式(つまり、支配的な戦略を持つゲーム形式) は独裁的であることを示しています。

ギバード・サッタースウェイト定理は、他の人がどのように投票するかに関係なく、あらゆる状況で 戦略的投票に対して完全に無防備な決定論的投票システムはあり得ないことを示す特別なケースです。

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

紀元前 500 年頃のピタゴラス の証明は、数学に大きな影響を与えました。この証明は、 2 の平方根は 2 つの整数の比として表すことができないことを示しています。この証明により、「数」は有理数と無理数という2 つの重複しない集合に分割されました。

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

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

17平方フィートのルートまでのすべての個別のケースを検討します... ^[6]

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

ギリシャの幾何学は、コンパスと定規の使用に基づいています(ただし、定規は厳密には必要ではありません)。コンパスを使用すると、幾何学者は互いに等距離にある点を構築できます。これは、ユークリッド空間では暗黙的に平方根を計算することと同じです。構築方法を問う 4 つの有名な質問があります。

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

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

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

一般的な角度を 3 等分する 場合も、立方体を 2 倍する場合も、立方根を取る必要がありますが、これは構成可能な数ではありません。

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

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

1837 年にガウス-ヴァンツェルの定理により、ほとんどのnの値に対して正n角形を構築することは不可能であることが示されました。

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

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

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

「任意のディオファントス方程式には整数解があるか？」という質問は決定不可能です。つまり、すべてのケースでこの質問に答えることは不可能です。

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

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

リチャードのパラドックスは...次のとおりです。有限個の 単語 [「単語」は記号です。強調のために太字で追加しました]によって定義できるすべての小数を考えます。Eをそのような小数のクラスとします。すると、Eには[無限個の]項があります。したがって、その要素は、1 番目、2 番目、3 番目、... と順序付けることができます。X を次のように定義される数とします[Whitehead と Russell は現在、カントールの対角線法を使用しています]。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 のメンバーであり、メンバーではありません。${\displaystyle \aleph_{0}}$

—  Principia Mathematica、第 2 版、1927 年、p. 61

クルト・ゲーデルは、彼の証明をリチャードのパラドックスの「類推」とみなし、それを「リチャードのアンチノミー」と呼んだ^[17]（下記参照）。

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

ネーゲルとニューマン (p. 68) の言葉を引用すると、「ゲーデルの論文は難しい。主要な結果に到達する前に、46 の予備的定義といくつかの重要な予備的定理を習得しなければならない」。実際、ネーゲルとニューマンは、証明の説明に 67 ページの序文を必要とした。しかし、読者が論文に取り組むだけの力があると感じるなら、マーティン デイビスは「この注目すべき論文は、知的な画期的なものであるだけでなく、読むのが楽しくなるような明快さと力強さで書かれている」と述べている (デイビス著「Undecidable」p. 4)。

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

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

ゲーデルは自身の証明を「リチャードの二律背反」と比較した（「二律背反」とは矛盾またはパラドックスのことである。詳細についてはリチャードのパラドックスを参照）。

「この結果とリチャードの二律背反との類似性はすぐに明らかである。また、嘘つきのパラドックス[14]とも密接な関係がある（ゲーデルの脚注14：あらゆる認識論的二律背反は、決定不可能性の同様の証明に使用できる）...したがって、私たちの前には、それ自体の証明不可能性を主張する命題がある[15]。（彼の脚注15：外見に反して、そのような命題は循環的ではない。なぜなら、まず、それは完全に明確な式の証明不可能性を主張しているからである）」^[17]

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

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

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

専門家以外の人に適した解説については、ベルトラミの 108 ページ以降を参照してください。また、フランゼンの第 8 章 137 ～ 148 ページとデイビスの 263 ～ 266 ページも参照してください。フランゼンの議論はベルトラミの議論よりはるかに複雑で、Ω (グレゴリー・チャイティンのいわゆる「停止確率」) について深く掘り下げています。デイビスの以前の扱いは、チューリング マシンの観点からこの問題にアプローチしています。チャイティンは、自身の取り組みと、それに伴う哲学的および数学的な影響について、多数の本を執筆しています。

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

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

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

自然科学では、不可能性定理は、確立された科学理論の範囲内で証明された数学的結果として導き出されます。この確固たる受け入れの根拠は、何かが起こらないという広範な証拠と、非常に予測に成功し、その仮定が論理的に何かが不可能であるという結論につながる基礎理論の組み合わせです。

物理学において広く受け入れられている不可能性の例としては、エネルギー保存の法則に反する永久機関と、特殊相対性理論の含意に反する光速を超えることの 2 つがある。もう1つは量子力学の不確定性原理で、粒子の位置と運動量を同時に知ることは不可能であると主張する。また、ベルの定理もある。つまり、局所的な隠れた変数の物理理論では、量子力学の予測をすべて再現することはできないということである。

自然科学における不可能性主張は絶対に証明することはできませんが、単一の反例を観察することで反証することができます。そのような反例は、不可能性を意味する理論の根底にある仮定を再検討することを要求するでしょう。

• 数学の未解決問題のリスト – これらの問題の解決策はまだ探されています。対照的に、上記の問題には解決策がないことが知られています。
• 集合論のパラドックス