Completeness and Incompleteness

Solution 1:

Consider the following three theorems:

Theorem (Soundness) Let $T$ be a first order theory in a given language $\mathcal L$ and let $\phi$ be a $\mathcal L$-formula. If there is a formal proof of $\phi$ from $T$ (in symbols $T \vdash \phi$), then for every model $\mathcal M$ of $T$ (i.e. $\mathcal M \models \psi$ for all $\psi \in T$) we have $\mathcal M \models \phi$.

In simpler words: If $\phi$ is provable from $T$, then it is true in every model of $T$.

Theorem (Completeness) Let $T$ be a first order theory in a given language $\mathcal L$ and let $\phi$ be a $\mathcal L$-formula. If for every model $\mathcal M$ of $T$ we have that $\mathcal M \models \phi$, then $T \vdash \phi$, i.e. there is a formal proof of $\phi$ from $T$.

In simpler words: If $\phi$ is true in every model of $T$, then there is a formal proof $T \vdash \phi$ witnessing this fact. (This is a special property of first order logic. There are other logics that don't satisfy completness.)

These two theorems combined are very promissing: In a sense Soundness says that everything provable is true. On the other hand Completeness says that everything universally true always has a formal proof. Great! However, there is one case not handled yet. What if $\phi$ is true in some models of $T$ and false in other models of $T$? Such a formula $\phi$ can't have a formal proof and also its negation $\neg \phi$ cannot be proved. It was hoped that this doesn't occur for nice theories $T$. For example, if $T$ is complete, this never occurs.

A (somewhat shocking - at least at that time -) result due to Gödel says that any natural theory $T$ has a formula $\phi$ such that $T \not \vdash \phi$ and $T \not \vdash \neg \phi$. In other words: If $T$ is consistent, then there are models $\mathcal M, \mathcal N$, such that $\mathcal M \models T \cup \{ \phi \}$ and $\mathcal N \models T \cup \{ \neg \phi \}$. More precisely:

Theorem (Incompleteness) Let $T$ be a recursive enumerable, consistent theory that can interpret Peano Arithmetics. Then there is a statement $\phi$ such that $T \not \vdash \phi$ and $T \not \vdash \neg \phi$.

In fact, this is true for $\phi \equiv \operatorname{Con}(T)$. Hence there is a true statement that $T$ cannot decide.

People often emphasize how bad this result is when it comes to Hilbert's program or the quest for a formal foundation of mathematics. While their concern is justified to some extend, I personally view the Incompleteness Theorem in another light: The proof of the Incompleteness Theorem boils down to a (very clever) fixed point argument that works, precisely because $T$ is recursively enumerable and can code formal proofs. Take either of those properties away and it doesn't work anymore. To me this says that consistent theories of a decent proof-theoretical complexity can't be coded as very simple subsets of $\mathbb N$. In other words: Any reasonable coding of such a theory has a nontrivial Turing degree. From a modern point of view this isn't surprising at all - it's to be expected.

Finally, let us compare these three theorems in light of your question. Soundness and Completeness tell us that our notion of formal proof is correct (both mathematically and philosophically). We can prove precisely those statements that $T$ implies (model theoretic) and that's exactly what we want.

Incompleteness, on the other hand, tells us, that all consistent, sufficiently complex (in terms of proof theory) theories that can be enumerated by a Turing machine have a (true) statement that they do not decide. Or - in other words - any consistent, sufficiently complex and complete theory cannot be enumerated by a Turing machine. This really says that any reasonable coding of such a theory must be pretty complex.

Solution 2:

The completeness theorem for first order logic is a general statement about first order languages and associated deductive rules that says if something is true in every model of a theory, then it's a provable consequence of that theory. That is, we do not end up with theories that are consistent but have no model, in which case we would be able to justifiably consider our notion of "model" to be inadequate to capture all of the theories we want to study. The key here is it's about a relation between first order languages and models of theories in those languages.

The second notion of completeness is a property of a theory, not of an entire deductive system, and we need not even talk about models to describe it. A theory $T$ is complete iff for every sentence $\varphi$, $T\vdash\varphi$ or $T\vdash\neg\varphi$. This is the sense of "complete" in Goedel's famous theorem.

Hopefully this should make it clear that these are different things; to say that first order logic is complete in the second sense would be gibberish because first order logic is not a first order theory. Likewise, to say that the theory of the real numbers is complete in the first sense is also gibberish, because the theory of real numbers is not a deductive system.

Solution 3:

To put it real short: Godel's completeness result is about (first-order) logic itself, and his incompleteness result is about arithmetic.

One way to put the results is: we can axiomatize all of (first-order) logic itself, but we cannot axiomatize all of arithmetic.