Explanation about completeness and incompleteness theorems in logic

Question

There must be some fundamental notion that I don't understand, because I have these doubts about Godel's completeness and incopleteness theorems in first order logic. The completeness theorem states that in a first order theory everything that is true is provable; the incompleteness theorem states that in the Robinson arithmetic (for example) there is a formula $A$ such that both $A$ and $\lnot A$ are not provable. Since one of $A$ and $\lnot A$ must be true, why it isn't true anymore that everything true is provable? Thanks in advance for your patience

Answer 1

The problem is with the use of the word "true".

• The completeness theorem says that $T$ proves $\varphi$ if and only if $\varphi$ is true in all the models of $T$.

• The incompleteness theorem says that there is $\varphi$ that is true in a specific model, usually taken to be $\Bbb N$, which is not provable from Robinson arithmetic.

Truth is always relative to a structure, but in the case of arithmetic, when we say "true" without qualifying it, we mean in the standard model: the natural numbers. But there are other models, and in those $\varphi$ will be false. Exactly because it is not provable from Robinson arithmetic.

Answer 2

"The completeness theorem states that in a first order theory everything that is true is provable." No it doesn't.

To say standard first order logic is complete is to say that if some premisses $\Gamma$ semantically entail a conclusion $\varphi$, then there is a formal proof from the premisses $\Gamma$ to the conclusion $\varphi$.

To say that a first order theory with axioms $\Gamma$ is (negation) incomplete is to say that there is some $\varphi$ such that $\Gamma$ entails neither $\varphi$ nor $\neg\varphi$.

It is obvious you can have an incomplete theory with a complete first-order logic (just omit some needed axioms from the theory).

What is not obvious, of course, but which we get from Gödel, is that some first order theories are in a good sense incompletable.

Any introductory text should explain this. Try for example my Gödel Without (Too Many) Tears which you can freely download from https://www.logicmatters.net/igt -- see page 6.

Answer 3

Here is a description of the incompleteness theorems for a layman:

Four words: provable, there exists a proof that an proposition is true; refutable, there exists a proof that an proposition is false; decidable, is said of a proposition that is either provable or refutable; undecidable, is said of a proposition that is neither provable nor refutable.

Incompleteness theorem 1: by formulating the following theorem "G: the theorem called G is not provable within the theory T", Gödel shows that G is necessarily undecidable, because G being provable leads to a contradiction and G being refutable leads to a contradiction.

Incompleteness theorem 2: a proof for the coherence of theory T is a proof that no proposition in T is both True and False. However, the existence of theorem G inside T makes this exercise of "knowing if it is not both True and False at the same time" impossible for G. Thus, there does not exist a proof of coherence for T; otherwise through this proof of coherence, one could know the truth value of G.