What is the difference between Gödel's Completeness and Incompleteness Theorems?

Same as title. What is the difference between Gödel's Completeness and Incompleteness Theorems?

-
They are about different kinds of "completeness". The Completeness theorem is about the correspondence between "truth" and provability in first order logic. The Incompleteness theorem is about there being either a proof of $P$ or of $\neg P$ for every sentence $P$ in the language. See Wikipedia's articles: en.wikipedia.org/wiki/G%C3%B6del%27s_completeness_theorem and en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorem – Arturo Magidin Dec 17 '10 at 19:36
It seems to me that the proof of Gödel incompleteness actually gives something stronger than "there is $\phi$ such that neither $\phi$ nor $\neg\phi$ is provable." The proof constructs using diagonalization a statement $S$ such that $S$ basically says "$S$ is not provable." Moreover, this statement is uniform: we can explicitly write it down, it would be the same in any model of the theory. But $S$ can't be false, because that would contradict consistency. Thus $S$ is true, and actually true in every model. But then $S$ provable by Gödel completeness, contradiction! – Holden Lee Jan 31 '14 at 10:25
What is wrong with this argument? – Holden Lee Jan 31 '14 at 10:25
The same argument appears to have been written about here math.stackexchange.com/questions/568819/…, although I still don't see why it doesn't work. – Holden Lee Jan 31 '14 at 10:38
@Holden: There is something wrong with your statement "S is true in any model of the theory". This is simply not the case, and the reason for this is the completeness theorem. Let $T$ be a theory to which the imcompleteness theorem applies. To be specific, let's say $T$ is ZFC. Of course, we assume that ZFC is consistent. Let $\varphi$ be a Gödel sentence for ZFC, i.e., a sentence such that both ZFC+$\varphi$ and ZFC+$\neg\varphi$ are consistent. Then by the completeness theorem, there are models of ZFC in which $\varphi$ is true and models where $\varphi$ is false. – Stefan Geschke Mar 25 '14 at 14:29

First, note that, in spite of their names, one is not a negation of the other.

The completeness theorem applies to any first order theory: If $T$ is such a theory, and $\phi$ is a sentence (in the same language) and any model of $T$ is a model of $\phi$, then there is a (first-order) proof of $\phi$ using the statements of $T$ as axioms. One sometimes says this as "anything true is provable."

The incompleteness theorem is more technical. It says that if $T$ is a first-order theory that is:

1. Recursively enumerable (i.e., there is a computer program that can list the axioms of $T$),
2. Consistent, and
3. Capable of interpreting some amount of Peano arithmetic (typically, one requires the fragment known as Robinson's Q),

then $T$ is not complete, i.e., there is at least one sentence $\phi$ in the same language as $T$ such that there is a model of $T$ and $\phi$, and there is also a model of $T$ and $\lnot\phi$. Equivalently (by the completeness theorem), $T$ cannot prove $\phi$ and also $T$ cannot prove $\lnot\phi$.

One usually says this as follows: If a theory is reasonable and at least modestly strong, then it is not complete.

The second incompleteness theorem is more striking. If we actually require that $T$ interprets Peano Arithmetic, then in fact $T$ cannot prove its own consistency. So: There is no way of proving the consistency of a reasonably strong mathematical theory, unless we are willing to assume an even stronger setting to carry out the proof. Or: If a reasonably strong theory can prove its own consistency, then it is in fact inconsistent. (Note that any inconsistent theory proves anything, in particular, if its language allows us to formulate this statement, then it can prove that it is consistent).

The requirement that $T$ is recursively enumerable is reasonable, I think. Formally, a theory is just a set of sentences, but we are mostly interested in theories that we can write down or, at least, for which we can recognize whether something is an axiom or not.

The interpretability requirement is usually presented in a more restrictive form, for example, asking that $T$ is a theory about numbers, and it contains Peano Arithmetic. But the version I mentioned applies in more situations; for example, to set theory, which is not strictly speaking a theory about numbers, but can easily interpret number theory. The requirement of interpreting Peano Arithmetic is two-fold. First, we look at theories that allows us (by coding) to carry out at least some amount of common mathematical practice, and number theory is singled out as the usual way of doing that. More significantly, we want some amount of "coding" within the theory to be possible, so we can talk about sentences, and proofs. Number theory allows us to do this easily, and this is way we can talk about "the theory is consistent", a statement about proofs, although our theory may really be about numbers and not about first order formulas.

-
hi, thanks a lot – varun Dec 17 '10 at 20:04
Is there actually a name for a first-order-theory that is recursively enumerable, consistent and capable of arithmetic? If not, why not? Wouldn't that be a useful terminological distinction? – mcb Jun 12 '15 at 13:30