What is the difference between Gödel's completeness and incompleteness theorems?
What is the difference between Gödel's completeness and incompleteness theorems?
Solution 1:
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:
- Recursively enumerable (i.e., there is a computer program that can list the axioms of $T$),
- Consistent, and
- 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.
Solution 2:
I'll add some comments...
It is useful to state Gödel'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 mathematical theories have more than one model; in particular, this happens for $\mathsf {PA}$ and related systems (to which Gödel's (First) Incompleteness Theorem applies).
When we "see" (with insight) that the unprovable formula of Gödel's Incompleteness Theorem is true, we refer to our "natural reading" of it in the intended interpretation of $\mathsf {PA}$ (the structure consisting of the natural number with addition and multiplication).
So, there exist some "unintended interpretation" that is also a model of $\mathsf {PA}$ in which the aforesaid formula is not true. This in turn implies that the unprovable formula isn't logically implied by the axioms of $\mathsf {PA}$.