User:IssaRice/Computability and logic/Entscheidungsproblem: Difference between revisions

Revision as of 00:39, 9 February 2019

Entscheidungsproblem, also called Hilbert's decision problem is a problem in mathematical logic.

Label	Statement	Notes
In terms of validity	Take as input a sentence of first-order logic, and decide whether it is valid (a.k.a. universally valid, true-in-every-interpretation).
In terms of provability	Take as input a sentence of first-order logic, and decide whether it is provable (using only logical axioms).	By Godel's completeness theorem, validity and provability are equivalent.
In terms of satisfiability	Take as input a sentence of first-order logic, and decide whether it is satisfiable.
In terms of semantic implication	Take as input a set of sentences $\Gamma$ and a sentence $\phi$ (both of first-order logic), and decide whether $\Gamma$ semantically implies (a.k.a. logically implies) $\phi$ .

@@ Line 10: / Line 10: @@
 |-
 | In terms of provability || Take as input a sentence of first-order logic, and decide whether it is provable (using only logical axioms). || By Godel's completeness theorem, validity and provability are equivalent.
+|-
+| In terms of satisfiability || Take as input a sentence of first-order logic, and decide whether it is satisfiable.
+|-
+| In terms of semantic implication || Take as input a set of sentences <math>\Gamma</math> and a sentence <math>\phi</math> (both of first-order logic), and decide whether <math>\Gamma</math> semantically implies (a.k.a. logically implies) <math>\phi</math>.
 |}