In order to illustrate Godel's Completeness Theorem, I'll give an example. Suppose that we work in a language that has the symbols 0,1,+,-, and *. In this language, we have the following axioms which I will collectively refer to as F:
1) 0+a = aIf you have some familiarity with Abstract Algebra abstract algebra, then you might recognize these as the field axioms. Now there are many mathematical frameworks in which the above axioms are true. For example, if we are working in the rational (fractional) numbers Q, then all of the above statements are true (when we interpret 0,1,+,-, and * in the usual way). Similarly, all of the above statements are true if we are working in the real numbers R or the complex numbers C. On the other hand, if we're working the integers Z, then statement 7) above is not true (there is no integer n such that 2*n = 1). Logicians call a mathematical framework (or mathematical universe) that satisfy these axioms a *model* of the axioms. Hence, each of Q, R, and C are models of F, but Z is not a model of F.
Now one would hope that if we could prove a statement from the axioms F, then that statement should be true in any model of F. That is, our proof system is "sound" in the sense that if we can prove a statement from F, then that statement should logically follow from F. This fact is true and is called the Soundness Theorem. For example, one can prove the statement "If a+a = a, then a = 0" from the above axioms F, and sure enough, this is true in each of Q, R, and C. The really interesting question is the converse, i.e. if a statement is true in every model of F, must it be the case that we can prove it from F?
For example, the statement S = "There exists an a with a*a = 2" is true in R, but false in Q since the square root of 2 is irrational. Similarly, the statement T = "There exists an a with a*a = -1" is true in C, but false in R (the imaginary unit i satisfies the statement in C). Hence, if you believe the Soundness Theorem, we should not expect to be able to prove either S or (not S) from F because there is one model of F in which S is true, and one where S is false. Similarly, we should not expect to be able to prove either T or (not T). Thus, our system F is incomplete, i.e. there are statements X such that we can neither prove X nor (not X). However, there are damn good reasons why it is incomplete because there are statements which can be either true or false depending on which model of F you are currently working.
The Completeness Theorem basically says that this is the only way a system can be incomplete. In other words, the above converse question is true, which implies that we can prove absolutely everything that is not ruled out for the above basic reason.
Now when you combine the Completeness and Incompleteness Theorems, you can get some really remarkable results. If you work with the axioms of number theory, call them N (which include many of the above axioms F along with axioms for < and axioms for mathematical induction), for example, we know by the Incompleteness Theorem that there is a statement X such that neither X nor (not X) is provable. Hence, by the Completeness Theorem, there is a model of N in which X is true and a model of N in which X is false. It follows that there are mathematical universes which look and act very much like the regular natural numbers, but do in fact have some subtle differences. One of the most fascinating results I've seen is that there is a model of number theory which "thinks" (in a precise sense) that the axioms N are inconsistent, even though they are not (roughly, the "proof" of an inconsistency that it "sees" is infinitely long, and so is not a real proof).