Sometimes it’s the case that in a first-order system T in which you can do number theory there is a property P(n) of natural numbers such that the following two seemingly contradictory statements hold:
For every n, T proves P(n)
and
T does not prove that for all n, P(n)
To see that these statements are not actually contradictory, replace T with a person Bob and observe that it’s certainly possible that
For every a, b, c > 1, and n > 2, Bob can verify that an + bn ≠ cn.
is true but that
Bob can verify that for every a, b, c > 1, and n > 2, an + bn ≠ cn.
is false, since for the first statement it suffices for Bob to be able to remember grade school arithmetic, whereas for the second statement to be true Bob must be able to prove Fermat’s Last Theorem.
If it’s the case that there is a property P(n) such that for all n, T proves P(n) but it is not the case that T proves for all n, P(n), then we could actually add “There exists an n such that ~P(n)” to T and still have a consistent theory. Thus, we might be in the even stranger situation where
For every n, T proves P(n).
but
T proves that there exists an n such that ~P(n)
even though T is consistent. Such a T is called ω-inconsistent. (T is called ω-consistent if it is not ω-inconsistent.)
On the other hand, note that it’s not really possible that
Bob cannot verify that there exists a, b, c > 1 such that a2 + b2 = c2.
given that there are such a, b, and c, since we could just tell Bob an example and have him use his knowledge of grade-school arithmetic to verify it.
Similarly, for all the theories T we will consider, if there exists an n such that T proves P(n), then T proves that there exists an n such that P(n).
Now consider the following argument, which is a rough version of Gödel’s original argument for the first incompleteness theorem:
Suppose that T is a complete theory (meaning that for every sentence S, either T proves S or T proves ~S.) Let G be the sentence “G is not provable in T” which it turns out we can interpret in the language of number theory. Suppose that G is provable in T. Then there exists a proof of G in T, so T can prove “There exists a proof of G in T.” But this is the same as ~G. So, since T can prove both G and ~G, it is inconsistent.
Now suppose that G is not provable in T. If T was ω-consistent, then since T is also complete, we would know that T proved “There is no proof of G in T.” But this is equivalent to G. So, since T can prove both G and ~G, it is inconsistent.
So, what we have proven is that if T is ω-consistent, then it is incomplete. But Gödel’s First Incompleteness Theorem is usually stated as: If T is consistent, then T is incomplete. This is a stronger and cleaner statement. (Note that in both statements we are assuming that number theory can be expressed in T.)
J. Barkley Rosser was able to prove this stronger statement with a very clever change in the self-referential statement G.
