# Category Archives: Provability Logic

## 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.

1 Comment

Filed under Provability Logic, Self-Reference

## Löb’s Theorem: Santa Claus and Provability

Consider the following argument for the existence of Santa Claus (which is called Curry’s paradox):

Let S be the sentence

If S is true, then Santa Claus exists.

Lemma: S is true.

Proof. S is of the form “If P, then Q.” so to show S we just have to assume P and show Q. So, assume that S is true (with the goal of showing that Santa Claus exists). Since we’ve assumed that S is true, it follows that if S is true, then Santa Claus exists (since that’s exactly what S says). Then, since S is true, Santa Claus exists. $\square$

Corollary: Santa Claus exists.

Proof. Since S is true, it is the case that if S is true, then Santa Claus exists (since that’s exactly what S says). Therefore, since S is true, Santa Claus exists. $\square$

Since Santa Claus doesn’t exist, this argument seems to just prove that informal reasoning combined with self-reference can often lead you astray. Can we extract any interesting theorems out of this argument? It turns out that we can.

1 Comment

Filed under Provability Logic