3 questions about the completeness

122 Views Asked by At

I've got the following concrete questions I'm not completely sure in for a long time (sorry if it's a duplicate and for my cumbersome language). I think they are connected, though seem very like separate:

  1. Given a first-order theory $\kappa$ with its axioms $\Gamma$. Is it true that a sentence that is true in every model of $\kappa$ can be deduced from $\Gamma$, and every sentence that can be deduced from $\Gamma$ is true in every model of $\kappa$?

  2. Gödel-Rosser incompleteness theorem asserts that if the formal arithmetic with its axioms $S$ is consistent, then there is a sentence $F$ such that $F$ and $\neg F$ can not be deduced from $S$. If the answer to the previous question is positive, does it follow that if the formal arithmetic is consistent, then there is its model where some sentence $F$ is true, and another model where $\neg F$ is true? Thus, if the formal arithmetic is consistent, it must have at least two models.

  3. Can we adopt the second incompleteness theorem to the set theory $\sigma$ (since $S$ can be deduced there, though in another form), and then to say that the consistency of $\sigma$ (if it is consistent) can not be proved mathematically (since mathematics is based on $\sigma$ itself)?

1

There are 1 best solutions below

6
On BEST ANSWER
  1. Yes, that is the completeness theorem for first order logic.
  2. Yes, more precisely it says that any effectively axiomatizable, consistent, and sufficiently strong theory has such a sentence $F.$ Your argument that this means it has more than one model is correct. However, note that incompleteness is not the only reason for something to have more than one model. In fact, any first order theory that has infinite models, or even arbitrarily large finite models, has models of unboundedly large cardinality, hence many different models... this is a consequence of the compactness theorem for first order logic. (All the models just happen to agree on the truth of every first order sentence in the complete case.)
  3. Yes, the second incompleteness theorem applies to set theory as well, so e.g. assuming ZFC is consistent, we cannot prove ZFC is consistent in ZFC. So if we equate 'provable mathematically' with 'theorem of ZFC' then ZFC's consistency is not provable mathematically. However, it's not clear that we should equate these notions.