Rosser’s Clever Improvement to Gödel’s Original First Incompleteness Theorem

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 + bncn.

is true but that

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

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.

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.

About these ads

1 Comment

Filed under Provability Logic, Self-Reference

One response to “Rosser’s Clever Improvement to Gödel’s Original First Incompleteness Theorem

  1. Pingback: About decidability… « Dijkstrabühl

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s