2
$\begingroup$

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.

  • 0
    Do you mean G\"odel's completeness theorem? You may want to be more specific so that people know how to help you. Also, there are videos available: http://www.youtube.com/results?search_query=godel%27s+incompleteness+theorem&oq=godel%27s+&gs_l=youtube.3.0.0l4.53.1524.0.3701.11.8.2.0.0.0.135.717.5j3.8.0...0.0.VfWjNL5ek9o2012-07-04
  • 0
    The essence of most (all?) completeness theorems is proving that there are "enough models". Usually one builds a model by syntactic considerations, but in the case of classical first order logic with set-models, some further tricks are required.2012-07-04
  • 0
    Take a look at Chang and Keisler _Model Theory_ Section 2.1. It is done by extending a theory to have witnesses and a Henkin construction of a model. It is somewhat technical, but very important. That section of Chang and Keisler also proves the compactness theory, upward, downward Lowenheim Skolem as consequences of these results.2012-07-04
  • 0
    How can a statement be true in one model and false in another? When you study number theory, do you focus on the standard model or do you keep in mind non-standard models also? I think non-standard models don't exist. Or at least you can't write a formula that's true in a non-standard model but false in the standard model in first-order logic.2012-07-04
  • 0
    When one studies number theory, one is usually working with second-order arithmetic or stronger. There are _no_ non-standard models of _those_. However there are non-standard models of first-order arithmetic, and necessarily so.2012-07-04
  • 1
    "How can a statement be true in one model and false in another?" By the definition of _model_, no statement can be true in one model and false in another. However, it can be true in one _structure_ and false in another. Think of the statement $\exists{x}\exists{y} (x \neq y)$. This is false in the structure $\left\{ 0 \right\}$, but true in the structure $\left\{ 0, 1 \right\}$.2012-07-04
  • 0
    But presumably you mean "How can a statement be true in one model _of a theory $T$_ and false in another?" In which case, the fact is that nonstandard models are a straightforward consequence of the compactness theorem.2012-07-04

2 Answers 2

5

You say you would welcome a book recommendation. The following have particularly clear presentations, I think:

  1. Ian Chiswell and Wilfrid Hodges Mathematical Logic (OUP), final chapter.
  2. Christopher C. Leary A Friendly Introduction to Mathematical Logic (Prentice Hall), Ch. 3.

(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.)

2

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.