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