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 aⁿ + bⁿ ≠ cⁿ.

is true but that

Bob can verify that for every a, b, c > 1, and n > 2, aⁿ + bⁿ ≠ cⁿ.

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 a² + b² = c².

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.

What Rosser did was the following: Let R be the statement “For every proof of R in T, there is a shorter proof of ~R.” Let’s see how this gets around the issue of ω-inconsistency.

First suppose that R is provable in T, say by a proof of length n. If there actually is a shorter proof of ~R in T, then T is inconsistent. Otherwise, we can actually verify case-by-case that there is no proof of ~R in T of length < n. But then we have proven ~R in T, making it again inconsistent.

Now suppose that ~R is provable in T, say by a proof of length n. If R is provable in T, then T is inconsistent, so suppose that R is not provable in T. Then, we can as before verify case-by-case in T that R is not provable in T by a proof of length ≤ n. But this means that we can prove in T that for any proof of R in T, there is a shorter proof of ~R: we can prove in T that there is no proof of R of length ≤ n and we may argue in T that for any longer proof of R we can take the proof of ~R of length n. But this is exactly what R says, so R is provable in T which is a contradiction.