User:IssaRice/Computability and logic/Entscheidungsproblem: Difference between revisions
| Line 5: | Line 5: | ||
{| class="wikitable" | {| class="wikitable" | ||
|- | |- | ||
! Label !! Statement !! Notes | ! Label !! Syntactic or semantic !! 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 validity || Semantic || 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 provability || Syntactic || 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 satisfiability || Semantic || 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>. | | In terms of semantic implication || Semantic || 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>. | ||
|} | |} | ||
Revision as of 00:40, 9 February 2019
Entscheidungsproblem, also called Hilbert's decision problem is a problem in mathematical logic.
Equivalent formulations
| Label | Syntactic or semantic | Statement | Notes |
|---|---|---|---|
| In terms of validity | Semantic | 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 | Syntactic | 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 | Semantic | Take as input a sentence of first-order logic, and decide whether it is satisfiable. | |
| In terms of semantic implication | Semantic | Take as input a set of sentences and a sentence (both of first-order logic), and decide whether semantically implies (a.k.a. logically implies) . |
