Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
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 at 10:25
    
What is wrong with this argument? –  Holden Lee Jan 31 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 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 at 14:29
show 1 more comment

2 Answers

up vote 22 down vote accepted

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.

share|improve this answer
    
hi, thanks a lot –  varun Dec 17 '10 at 20:04
add comment

If I can add some comments,

I think it is useful to state Godel's Completeness Theorem in this form : if a wff A of a first-order theory T is logically implied by the axioms of T, then it is provable in T, where "T logically implies A" means that A is true in every model of T. The problem is that most of first-order math theories have more than one model; in particular, this happens for PA and related systems (to which Godel's (First) Incompleteness Theorem applies). When we "see" (with insight) that the unprovable formula of Godel's Incompleteness Theorem is true, we refer to our "natural reading" of it in the intended interpretation of PA (the structure consisting of the natural number with addition and multiplication). So, there exist some "unintended interpretation" that is also a model of PA where the aforesaid formula is not true. This in turn implies that the unprovable formula isn't logically implied by the axioms of PA.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.