決定可能性
決定可能(けっていかのう、英: decidable)は、数理論理学または現代論理学において、論理式の集合のメンバーシップの決定をする実効的(effectiveな)方法が存在することを指す。決定可能性(けっていかのうせい、英: decidability)は、そのような属性を指す。命題論理のような形式体系は、論理的に妥当な論理式(または定理)の集合のメンバーシップを実効的に決定できるなら、決定可能である。ある決まった論理体系における理論(論理的帰結で閉じている論理式の集合)は、任意の論理式がその理論に含まれるか否かを決定する実効的方法があれば、決定可能である。そうでなければ、決定不能である。
理論は論理式の集合であり、論理的帰結の下で閉じているとする。理論の決定可能性を問うということは、その理論のシグネチャに含まれる任意の論理式を与えられたとき、その論理式がその理論の一部かどうかを決定する実効的手続きが存在するかどうかを問うことである。理論が公理の決まった集合からの論理的帰結の集合として定義されているとき、この問題は自然に生じる。決定可能な一階の理論の例として、実閉体の理論やプレスブルガー算術があり、決定不能な理論の例として、群の理論やロビンソン算術がある。
理論の決定可能性について、いくつかの基本的結論がある。矛盾を含む理論は決定可能である。その理論のシグネチャにある論理式はどれでもその理論の論理的帰結になりうるため、理論の一部となりうるからである。完全で帰納的可算な一階の理論は決定可能である。決定可能な理論を拡張したものは決定可能でない場合がある。例えば、命題論理には決定不能な理論もあるが、最小の理論である妥当性の集合は決定可能である。
無矛盾の理論で、全ての無矛盾な拡張が決定不能であるとき、本質的に決定不能であるという。実際、全ての矛盾のない拡張は本質的に決定不能である。体の理論は決定不能だが、本質的に決定不能ではない。ロビンソン算術は本質的に決定不能であることが知られており、ロビンソン算術を内包するか翻訳した全ての無矛盾な理論も(本質的に)決定不能である。