決定不能命題の例
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/08/01 10:04 UTC 版)
「ゲーデルの不完全性定理」の記事における「決定不能命題の例」の解説
数学と計算機科学（コンピュータ科学）において、「決定不能」という言葉には二つの異なった意味がある。一つ目は証明論の文脈でゲーデルの定理に関連して使われる意味であり、特定の形式的体系の下で或る命題を証明も反証もできないことを言う。二つ目は計算可能性理論に関連した用法であり、命題ではなく決定問題に適用される。決定問題とは入力に対して答が真か偽のいずれかになるような問題である。ある問題を全ての入力に対して正しく解答するようなアルゴリズムが存在しないとき（すなわち特性関数が計算可能関数でないとき）、そうした問題は決定不能であると言う。 不完全性定理は、自然数論が一つ目の意味で決定不能であることを主張している。一方、述語論理の論理式が充足可能か否かを判定する充足可能性問題は決定問題にあたるが、不完全性定理によって、二番目の意味で決定不能である。つまり、述語論理の論理式が充足不能であれば、その論理式から矛盾を導く証明を見つけることができるが、充足可能であるときにその旨、回答を返すアルゴリズムは存在し得ない。 ゲーデルとポール・コーエンの仕事を合わせて、決定不能命題の確かな実例が得られた。連続体仮説はZFC（集合論における標準的な公理系）の下では証明も否定の証明もできない。また、選択公理もZF（ZFCに含まれる公理から選択公理を除いたもの）では証明も否定の証明もできない。これらの結果は不完全性定理を必要としない。1940年、ゲーデルはこれらの命題が何れも ZF または ZFC 集合論では否定を証明できないことを証明した。1960年代、コーエンはこれらがいずれも ZF から証明できず、また連続体仮説が ZFC から証明できないことを証明した。 マチャセビッチによるヒルベルトの第10問題の解決により、決定不能な命題の例が得られる。そのような例はディオファントス方程式の外側に存在量化子を幾つか並べた形として得られる。すなわち不完全性定理の前提条件を満たす形式的体系において、解の存在が証明も反証もできないようなディオファントス方程式が存在する。 1973年、群論におけるホワイトヘッドの問題（英語版）が標準的な集合論では決定不能であることが示された。 1977年、パリスとハーリントンは、ラムゼーの定理の一種であるパリス＝ハーリントンの定理が、一階算術の公理体系であるペアノ算術の下では決定不能だが、より大きな二階算術の体系では証明できることを証明した。カービーとパリスは後にグッドスタインの定理（自然数の数列に関する命題であり、パリス・ハーリントンの原理よりもいくらか易しい）がペアノ算術では決定不能であることを示した。 計算機科学で応用される Kruskal の木定理（英語版）はペアノ算術では決定不能だが集合論では証明できる。実際、Kruskalの木定理（またはその有限版）は、可述主義（英語版）と呼ばれる数学的哲学に基づいて構築されたもっと強い体系の下でも決定不能である。これに関連し、更に一般的な graph minors 定理（英語版）（2003年）は計算複雑性理論に影響する。 グレゴリー・チャイティンはアルゴリズム情報理論における決定不能命題を発見し、その状況下で新たな不完全性定理を得た。チャイティンの定理によると、十分な算術を表現可能ないかなる理論においても、どのような数であっても c {\displaystyle c} よりも大きなコルモゴロフ複雑性を有することがその理論上では証明できないような、上限 c {\displaystyle c} が存在する。ゲーデルの定理が嘘つきのパラドックスと関係しているのに対し、チャイティンの結果はベリーのパラドックスに関係している。
※この「決定不能命題の例」の解説は、「ゲーデルの不完全性定理」の解説の一部です。
「決定不能命題の例」を含む「ゲーデルの不完全性定理」の記事については、「ゲーデルの不完全性定理」の概要を参照ください。
- 決定不能命題の例のページへのリンク
