Decidability_(logic)
論理では、正しい答えを導き出すための効果的な方法が存在する場合、真偽の決定問題は決定可能です。0次論理（命題論理）は決定可能ですが、1次および高次論理は決定できません。論理的に有効な式 (または定理)のセットのメンバーシップが効果的に決定できる場合、論理システムは決定可能です。理論(論理的帰結の下で閉じられた一連の文)) 任意の式が理論に含まれているかどうかを判断するための有効な方法があれば、固定された論理システムで決定可能です。多くの重要な問題は決定不能です。つまり、メンバーシップを決定するための効果的な方法 (すべての場合において非常に長い可能性がありますが、有限の時間の後に正しい答えを返す) が存在しないことが証明されています。
コンテンツ
1 論理システムの決定可能性
2 理論の決定可能性
3 いくつかの決定的な理論
4 いくつかの決定不可能な理論
5 半決定可能性
6 完全性との関係
7 計算可能性との関係
8 ゲームの文脈で
9 こちらもご覧ください
10 参考文献
10.1 ノート 10.2 参考文献
論理システムの決定可能性
各論理システムには、特に証明可能性の概念を決定する構文コンポーネントと、論理的妥当性の概念を決定する意味コンポーネントの両方が付属しています。システムの論理的に有効な式は、システムの定理と呼ばれることがあり、特にゲーデルの完全性定理が意味的帰結と構文的帰結の同等性を確立する一次論理のコンテキストではそうです。線形論理などの他の設定では、構文上の結果 (確率) 関係を使用して、システムの定理を定義することができます。
任意の式が論理系の定理であるかどうかを判定する効果的な方法があれば、論理系は決定可能です。たとえば、命題論理は決定可能です。これは、真理値表法を使用して任意の命題式が論理的に有効かどうかを判断できるためです。
一般に、一階論理は決定可能ではありません。特に、等価性と、2 つ以上の引数を持つ少なくとも 1 つの他の述語を含む署名の論理的有効性のセットは決定できません。二階論理や型理論など、一階論理を拡張した論理系も決定不能である。
ただし、同一性を持つ単項述語計算の有効性は決定可能です。このシステムは、関数記号を持たず、等号以外の関係記号が複数の引数をとらない署名に限定された一階論理です。
一部の論理システムは、一連の定理だけでは適切に表現されません。（たとえば、クリーネの論理には定理がまったくありません。）そのような場合、論理システムの決定可能性の代替定義がよく使用されます。これは、式の妥当性だけでなく、より一般的なものを決定するための効果的な方法を求めます。たとえば、sequentsの有効性、または帰結関係{(Г， A ) | ロジックのГ⊧A }。
理論の決定可能性
理論とは一連の式であり、多くの場合、論理的帰結の下で閉じていると想定されます。理論の決定可能性は、理論の署名に任意の式が与えられた場合に、式が理論のメンバーであるかどうかを決定する効果的な手順があるかどうかに関係します。決定可能性の問題は、理論が公理の固定セットの論理的結果のセットとして定義される場合に自然に発生します。
理論の決定可能性に関するいくつかの基本的な結果が理論の署名に含まれるすべての式が理論の論理的帰結であり、理論のメンバーであるため、すべての (パラコンシステントではない) 矛盾した理論は決定可能です。すべての完全 な再帰的に列挙可能な一階理論は決定可能です。決定可能な理論の拡張は、決定可能ではないかもしれません。たとえば、命題論理には決定不可能な理論がありますが、有効性のセット (最小の理論) は決定可能です。
すべての一貫した拡張が決定不可能であるという性質を持つ一貫した理論は、本質的に決定不可能であると言われています。実際、すべての一貫した拡張は本質的に決定不可能です。体の理論は決定不能ですが、本質的に決定不能というわけではありません。ロビンソン算術は本質的に決定不能であることが知られているため、ロビンソン算術を含む、または解釈するすべての一貫した理論も (本質的に) 決定不能です。
決定可能な一次理論の例には、実閉体の理論、およびプレスバーガー算術が含まれますが、グループの理論とロビンソン算術は、決定不可能な理論の例です。
いくつかの決定的な理論
いくつかの決定可能な理論には次のものがあります (Monk 1976， p. 234):
1915 年にLeopold Löwenheimによって確立された、等価のみを持つ署名の 1 次の論理的有効性のセット。
1959 年に Ehrenfeucht によって確立された、等価性と 1 つの単項関数をもつ署名の 1 次論理有効性のセット。
プレスバーガー算術とも呼ばれる、等号と加算を伴う署名の自然数の一次理論。完全性は、1929 年にMojżesz Presburgerによって確立されました。
Skolem 算術とも呼ばれる、等号と乗算による署名の自然数の一次理論。
1940 年にAlfred Tarskiによって確立されたブール代数の一次理論(1940 年に発見され、1949 年に発表された)。
1949 年に Tarski によって確立された、特定の標数 の代数的に閉じた体の一次理論。
1949 年に Tarski によって確立された実閉順序体の一次理論 ( Tarski の指数関数問題も参照)。
1949 年に Tarski によって確立された、ユークリッド幾何学の一次理論。
1955 年に Szmielew によって確立されたアーベル群の一階理論。
1959 年に Schwabhauser によって確立された双曲幾何の一階理論。
1980年代から今日まで調査された集合論の特定の決定可能なサブ言語.(Cantone et al. ， 2001)
決定可能性を確立するために使用される方法には、量指定子の除去、モデルの完全性、およびŁoś-Vaught 検定が含まれます。
いくつかの決定不可能な理論(Monk 1976， p. 279):
1953 年にTrakhtenbrotによって確立された、アリティが 2 以上の関係シンボル、または 2 つの単項関数シンボル、またはアリティが 2 以上の 1 つの関数シンボルのいずれかを持つ、任意の一次署名の論理的有効性のセット。
1949 年にTarski とAndrzej Mostowskiによって確立された、足し算、掛け算、等号を伴う自然数の一階理論。
1949 年にJulia Robinsonによって確立された、足し算、掛け算、および等式を伴う有理数の 1 次理論。
1953 年にAlfred Tarskiによって確立された群の 1 次理論。有限群の。Mal’cev はまた、半群の理論と環の理論が決定不能であることを立証しました。ロビンソンは 1949 年に、体の理論は決定不能であることを確立しました。
1950 年にRaphael Robinsonによって確立されたように、ロビンソン算術(したがって、ペアノ算術などの一貫した拡張) は本質的に決定不可能です。
等号と 2 つの関数記号を使用した 1 次理論
解釈可能性法は、理論の決定不能性を確立するためによく使用されます。本質的に決定不可能な理論Tが一貫した理論Sで解釈可能である場合、Sも本質的に決定不可能です。これは、計算可能性理論における多一還元の概念と密接に関連しています。
半決定可能性
決定可能性よりも弱い理論または論理システムの特性は、半決定可能性です。任意の式が与えられた場合、その式が理論に含まれている場合は常に正確に伝えるが、式が理論に含まれていない場合は否定的な答えを返すか、まったく答えを返さない有効な方法がある場合、その理論は半決定可能です。すべての定理が最終的に生成されるような定理 (および定理のみ) を生成するための効果的な方法がある場合、論理システムは半決定可能です。これは決定可能性とは異なります。半決定可能システムでは、式が定理ではないことを確認する効果的な手順がない場合があるためです。
すべての決定可能な理論または論理システムは半決定可能ですが、一般にその逆は正しくありません。理論とその補数の両方が半決定可能である場合にのみ、理論は決定可能です。たとえば、一次論理の論理的妥当性のセットVは半決定可能ですが、決定可能ではありません。この場合、任意の式Aに対してAがVに含まれていないかどうかを判断する有効な方法がないためです。同様に、再帰的に列挙可能な一次公理のセットの論理的帰結のセットは半決定可能です。上記の決定不可能な一次理論の例の多くは、この形式です。
完全性との関係
決定可能性を完全性と混同しないでたとえば、代数的に閉じた体の理論は決定可能ですが不完全ですが、+ と × を含む言語の非負の整数に関するすべての真の 1 次ステートメントのセットは完全ですが決定不可能です。残念ながら、用語のあいまいさとして、「決定不能なステートメント」という用語は、独立したステートメントの同義語として使用されることが
計算可能性との関係
決定可能集合の概念と同様に、決定可能理論または論理システムの定義は、有効な方法または計算可能な関数のいずれかの観点から与えることができます。これらは一般に、教会のテーゼに従って同等であると考えられています。実際、論理システムまたは理論が決定不能であるという証明は、計算可能性の正式な定義を使用して、適切な集合が決定可能な集合ではないことを示し、チャーチのテーゼを呼び出して、理論または論理システムが有効な方法によって決定できないことを示します。メソッド (Enderton 2001， pp. 206 ff. )。
ゲームの文脈で
一部のゲームは、決定可能性に関して分類されています。
チェスは決定的です。 他のすべての完全情報有限 2 人ゲームについても同じことが言えます。
無限チェス(ルールとゲームピースに制限あり) のメイトインnは決定可能です。 ただし、強制的に勝利する位置 (有限個のピースを持つ) がありますが、任意の有限nに対して nで一致しません。
限られたボード上で不完全な情報を持つ (ただし、時間は無制限である) チーム ゲームの中には、決定不能なものも
こちらもご覧ください
哲学ポータル Entscheidungsproblem 存在の定量化
参考文献
ノート
^ Trakhtenbrot、1953年。
^ Monk， Donald (1976). 数学的論理。スプリンガー。ISBN 9780387901701.
^ タルスキ、A。モストフスキー、A。Robinson， R. (1953)， Undecidable Theories ， Studies in Logic and the Foundation of Mathematics， North-Holland， Amsterdam， ISBN 9780444533784
^ ユーリ・グレビッチ（1976）。「標準クラスの決定問題」 . Ｊ．Ｓｙｍｂ．ログ。41 (2): 460–464. CiteSeerX 10.1.1.360.1517 . ドイ: 10.1017/S0022481200051513 . S2CID 798307 .
^ スタック交換コンピュータ サイエンス. 「チェスゲームの動きTMは決定可能か？」 ^ 決められないチェスの問題？ ^ Mathoverflow.net/Decidability-of-chess-on-an-infinite-board Decidability-of-chess-on-an-infinite-board
^ Brumleve、ダン。ハムキンス、ジョエル・デビッド。シュリヒト、フィリップ （2012)。「無限チェスのメイトイン問題は決定可能」 . ヨーロッパにおける計算可能性に関する会議。コンピュータ サイエンスの講義ノート。巻。7318.スプリンガー。pp.78–88。arXiv : 1201.5597 . ドイ: 10.1007/978-3-642-30870-3_9 . ISBN 978-3-642-30870-3. S2CID 8998263 .
^ “”Lo.logic – $omega$ の動きでチェックメイト?”” .
^ プーネン、ビョルン （2014)。「10. 決定不能な問題: サンプラー: §14.1 抽象ゲーム」 . ケネディでは、ジュリエット（編）。ゲーデルの解釈：重要なエッセイ。ケンブリッジ大学出版局。211～241ページ参照 239.arXiv ：1204.0299。_ CiteSeerX 10.1.1.679.3322 . ISBN 9781107002661.}
参考文献
Barwise， Jon (1982)， “”Introduction to first-order logic””， in Barwise， Jon (ed.)， Handbook of Mathematical Logic ， Studies in Logic and the Foundations of Mathematics， Amsterdam: North-Holland， ISBN 978-0-444-86388-1
カントン、D.; オモデオ、EG; Policriti、A. （2013) 、コンピューティングの集合論。From Decision Procedures to Logic Programming with Sets ， Monographs in Computer Science， Springer， ISBN 9781475734522
チャグロフ、アレクサンダー。Zakharyashev、Michael (1997)、モーダル ロジック、Oxford Logic Guides、vol. 35、オックスフォード大学出版局、ISBN 978-0-19-853779-3、MR 1464942
Davis， Martin （2013) ， Computability and Unsolvability ， Dover， ISBN 9780486151069
Enderton， Herbert （2001)， A Mathematical Introduction to logic (2nd ed.)， Academic Press ， ISBN 978-0-12-238452-3
Keisler， HJ (1982)， “”Fundamentals of model theory”， in Barwise， Jon (ed.)， Handbook of Mathematical Logic ， Studies in Logic and the Foundations of Mathematics， Amsterdam: North-Holland， ISBN 978-0-444-86388-1
Monk， J. Donald （2012) ， Mathematical Logic ， Springer-Verlag ， ISBN 9781468494525″