User:IssaRice/Computability and logic/Gödel's completeness theorem: Difference between revisions

Latest revision as of 20:09, 7 April 2019

Different formulations

There are two equivalent formulations of the completeness theorem. One phrases the theorem in terms of "logical consequence implies provable" and the other phrases it in terms of "consistent implies satisfiable".

(for all sets of sentences $\Gamma$ and all sentences $\phi$ ?) If $\Gamma \models \phi$ , then $\Gamma \vdash \phi$
"The completeness theorem says that, if a bunch of sentences is consistent in the sense of not entailing a contradiction [in a standard system of first-order logic] then it has a model."^[1] See also Enderton.^[2]

See https://machinelearning.subwiki.org/wiki/User:IssaRice/Computability_and_logic/Semantic_completeness#Alternative_formulation for a proof.

References

↑ https://math.stackexchange.com/a/436257/35525
↑ Enderton. A Mathematical Introduction to Logic. p. 135.

[1] ttps://math.stackexchange.com/a/436257/35525

[2] Enderton. A Mathematical Introduction to Logic. p. 135.

[1]

[2]

@@ Line 1: / Line 1: @@
 [[../Semantic completeness|semantic completeness]]
-I'm confused about the following framing: "The completeness theorem says that, if a bunch of sentences is consistent in the sense of not entailing a contradiction [in a standard system of first-order logic] then it has a model."<ref>https://math.stackexchange.com/a/436257/35525</ref>
+==Different formulations==
-if <math>\Gamma \models \phi</math> then <math>\Gamma \vdash \phi</math>
+There are two equivalent formulations of the completeness theorem. One phrases the theorem in terms of "logical consequence implies provable" and the other phrases it in terms of "consistent implies satisfiable".
+# (for all sets of sentences <math>\Gamma</math> and all sentences <math>\phi</math>?) If <math>\Gamma \models \phi</math>, then <math>\Gamma \vdash \phi</math>
+# "The completeness theorem says that, if a bunch of sentences is consistent in the sense of not entailing a contradiction [in a standard system of first-order logic] then it has a model."<ref>https://math.stackexchange.com/a/436257/35525</ref> See also Enderton.<ref>Enderton. A Mathematical Introduction to Logic. p. 135.</ref>
+See https://machinelearning.subwiki.org/wiki/User:IssaRice/Computability_and_logic/Semantic_completeness#Alternative_formulation for a proof.
 ==References==
 <references/>