Thread: Completeness and Incompleteness theorems

Hi Folks, I was wondering if someone would be kind enough to explain the differences in the above theorems in as simple terms as possible. I've been reading various sites but I'm just getting more and more confused!

My understanding is the the completeness theorem follows on from Russell and Whitehead's Principa Mathematica and states that any formal system that is robust enough to axiomatize arithmetic must have statements that are true but not provable. (I couldn't find any examples of this so if anyone has one....)

BUT I can't see the difference between the above and in the incompleteness theorem.

Any help greatly appreciated. Thanks.


Dave.

A completeness theorem is a statement that some theory or logic is complete. Now, there are two kinds of completeness: a syntactic completeness and a semantic one. A theory T (i.e., a set of formulas) is syntactically complete (with respect to some logic, i.e., axioms and inference rules) if T is consistent, i.e., T does not derive a contradiction, but if any formula is added to T, it becomes inconsistent. Note that this definition does not refer to models, interpretations, or truth; it only refers to derivability. On the other hand, a logic L is semantically complete if for any formula P, if P is valid (i.e., true in every interpretation), then P is derivable in L. There is also strong semantic completeness for a logic L, which says that if a theory T logically implies P, (i.e., if all formulas in T are true in some interpretation, then P is also true in that interpretation), then T derives P in L. The (weak) completeness is obtained when T is empty. The converse to semantic completeness is soundness.

Thus, there is Gödel's completeness theorem, which says that classical first-order logic is semantically complete. It has nothing to do with arithmetic. On the other hand, Gödel's incompleteness theorem says that arithmetic (which is a theory) and all theories that contain it are syntactically incomplete. The fact that there exists a formula that is true in the standard model of natural numbers but is not derivable in arithmetic is an easy corollary: Suppose that neither A not ~A is derivable; one of them has to be true. Gödel's second incompleteness theorem gives a specific example of a formula such that it, as well as its negation, are not derivable in arithmetic: this is the formula that expresses the consistency of arithmetic.

I believe that the Completeness Theorem says that any consistent set of sentences has a model. This is quite different from the incompleteness theorem.

I believe that the Completeness Theorem says that any consistent set of sentences has a model.

This is a closely related statement that is often used as a key lemma in proving that T |= P implies T |- P, my version of (strong semantic) completeness.

Proposition. Suppose that every consistent set has a model. Then T |= P implies T |- P.
Proof. Suppose that but . Then is consistent. Therefore, there is a model M such that , but , which contradicts .

Originally Posted by emakarov

It has nothing to do with arithmetic.

Thanks for such a helpful reply - I really appreciate it. I'm still struggling to fully understand it though. I've copied something I was reading on one of (the many) sites I've been reading. Presumably, the writer is discussing Godel's Incompleteness theorem?


KURT GODEL
"But it soon became clear that naive use of sets could lead to contradictions (such as the set of all sets that aren't members of themselves). Set theory itself would have to be axiomatized. In their massive 3-volume Principia Mathematica, Russell and Whitehead built the foundations of mathematics on a set of axioms for set theory; they needed hundreds of preliminary results before proving that 1 + 1 = 2.

There remained the problem of analyzing the axioms of set theory. Mathematicians hoped that their axioms could be proved consistent (free from contradictions) and complete (strong enough to provide proofs of all true statements). Gödel showed these hopes were overly naive. He proved that any consistent formal system strong enough to axiomatize arithmetic must be incomplete; that is, there are statements that are true but not provable. Also, one can't hope to prove the consistency of such a system using the axioms themselves. The basic idea of Gödel's proof, indirect self-reference, is strikingly simple, but tricky to grasp."

Yes, this is talking about the incompleteness theorem. Gödel showed that there is a formula A independent from arithmetic, i.e., neither A not ~A is provable from arithmetic axioms. Since one of these formulas must be true in the standard model, arithmetic is not "strong enough to provide proofs of all true statements".

Originally Posted by emakarov

A theory T is syntactically complete if T is consistent, but if any formula is added to T, it becomes inconsistent.

To make it more precise, if any formula that is not derivable from T is added to T, it becomes inconsistent.

I glossed over the following fact. Suppose and . Why does this mean that T is incomplete according to the definition above? Because is consistent. Indeed, if , then (how this is shown depends on the details of the logic).

That's a great help. Thanks very much emakarov.

Still reading up on this and it's seems to be becoming clearer, thanks to the help here.

Would this be a correct and simple summation for the completeness theorem: "for a logical consequence of a set of axioms, there is a proof of the consequence using the axioms and logical rules of reasoning."?

Would this be a correct and simple summation for the completeness theorem: "for a logical consequence of a set of axioms, there is a proof of the consequence using the axioms and logical rules of reasoning."?

Basically, yes. Usually we don't say that a formula P is a logical consequence of the set of axioms. Calling it this way means that for any interpretation I, if all axioms are true in I, then P is true in I. However, when we are talking about interpretations of a logic, they are already supposed to make all axioms true. It's not like we consider interpretations of classical logic, and only some of them make all axioms true; the truth of axioms is built in the concept of an interpretation. Formulas that are true in all interpretations are called valid. So: "All valid formulas have a proof using the axioms and logical rules of reasoning." In any case, this is a minor point.

emakarov, thanks very much for your help (and patience!), I really appreciate it. It's made a lot of help reading and understanding the information that I've collected.

You are welcome.