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

From Machinelearning
Jump to: navigation, search

semantic completeness

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".

  1. (for all sets of sentences \Gamma and all sentences \phi?) If \Gamma \models \phi, then \Gamma \vdash \phi
  2. "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

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