Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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: youtube.com/… –  math-visitor Jul 4 '12 at 5:11
    
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. –  Zhen Lin Jul 4 '12 at 5:26
    
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. –  William Jul 4 '12 at 5:34
    
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. –  Zirui Wang Jul 4 '12 at 12:36
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\}$. –  Benedict Eastaugh Jul 4 '12 at 14:17

2 Answers 2

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.