Who can teach me completeness theorem? Thanks! Recommending a book is also welcome.
More specifically, it says that if a statement is true in all models of a theory, then it has a proof from this theory.
Who can teach me completeness theorem? Thanks! Recommending a book is also welcome.
More specifically, it says that if a statement is true in all models of a theory, then it has a proof from this theory.
You say you would welcome a book recommendation. The following have particularly clear presentations, I think:
(If you learnt elementary logic by trees, then my Introduction to Formal Logic has a clear completeness proof for the tree system for predicate logic.)
The key result in proving the completeness theorem is the statement that if a theory $T$ is consistent, then it's satisfiable. The statement that
$$\forall{M} (M \models T \rightarrow M \models \varphi) \rightarrow T \vdash \varphi$$
follows straightforwardly from this. Consequently, in order to prove completeness we must prove that every consistent theory is satisfiable. There are several steps in this proof, but the rough picture is as follows.
Let $T$ be a first order theory of signature $\sigma$. We first add new constants $c_\alpha$, expanding the signature to a new signature $\sigma^*$ so that each existentially quantified statement has a witness.
Now show that we can expand $T$ to a maximally consistent set of sentences $T^*$ in the language of $\sigma^*$. A maximally consistent set is negation complete: for all $\varphi$ in $L_{\sigma^*}$, either $\varphi \in T^*$ or $\neg\varphi \in T^*$. This is known as Lindenbaum's lemma.
Then we show that $T^*$ is satisfiable by constructing a term model from the terms of $L_{\sigma^*}$. This model must also be a model of $T$, thus proving the theorem.
There are many presentations of this proof; any good introductory logic textbook should include one. These days people follow Henkin's proof of the completeness theorem since it is much clearer than Gödel's original proof.