This Statement Does Not Refer To Itself
The Rosser trick and other interesting statements
Barkley Rosser Sr. was an impressive mathematician who made seminal contributions to many diverse areas. There is a Rosser sentence in logic, a Rosser sieve in number theory, and a Rosser matrix in numerical analysis. There are not too many others who have made key contributions to such different areas.
Today I want to talk about “unusual” diagonal statements. One is mathematically important and two are just interesting, I hope.
I once spent the summer at University of Wisconsin, Madison as a guest of the Computer Science Department. Rich DeMillo was also there at the same time, and we shared an office—Rosser’s office. Rosser was away for the summer and we had the honor of using his office. There were great vibes that made us want to work on problems in logic, number theory, and numerical analysis. We actually only got to the former two, as we did not know enough to work on numerical analysis. The summer was great fun, and a great honor to use Rosser’s office, which came with a beautiful view of Lake Mendota.
I wish I could say the vibes helped us to prove some terrific theorem, but alas we did not. Well the short version is we did prove a pretty neat theorem in complexity theory. The issue was that we eventually discovered the theorem had been previously proved, and in exactly the same way that we did. Oh well.
Let’s turn now to diagonal statements (DS). The motivations are to try to get stronger results, to find more “relaxed” ways to employ diagonalization, and to recognize statements that are not diagonal after all. Note that we have previously talked about avoiding diagonalization here.
Examples of DS and Non-DS
I have listed them by who created them, or told them to me, or whom I wish to give credit.
Rosser: When Kurt Gödel proved his famous Incompleteness Theorem, in 1931, he needed to assume that Peano Arithmetic was more than consistent. He needed what is called -consistency, which is stronger than regular consistency. A theory is consistent if there is no sentence such that the theory proves both and . A theory like Peano is -inconsistent provided for some formula the theory can prove all these:
and it can also prove . It is -consistent if it is not -inconsistent.
I have seen summaries of Gödel’s Incompleteness Theorem that either ignore this point or misstate that Gödel could prove his theorem based only the assumption of consistency. But that is not true. Gödel’s achievement is monumental, but he did need more than consistency: he needed -consistency.
Suppose we try to prove Gödel’s theorem this way: we plan on using the fact that the Halting problem is undecidable to show that Peano Arithmetic cannot be complete and consistent. Consider a machine that we would like to discover whether or not it halts on the blank tape. We can clearly create an arithmetic sentence which means that halts in at most steps. We do the following in parallel:
- We start running for steps.
- We start searching for a proof of .
If we discover that the machine halts, then we are done. If we discover that we can prove , then we are also done. But what if the latter is false: there is no proof of this sentence. Then by completeness it must be the case that Peano proves . This is the same as . This is no contradiction with consistency, but is a contradiction with -consistency.
I find it quite interesting that the great Gödel could “only” prove:
If Peano Arithmetic is -consistent, then it is incomplete.
He could not prove the theorem that he really wanted:
If Peano Arithmetic is consistent, then it is incomplete.
There is a lesson here for all, I believe. Sometimes when you are stuck in proving some theorem, proving a slightly weaker theorem is fine. Gödel’s brilliant work was just as surprising with the stronger assumption of -consistency. Plus it allowed others the opportunity to improve his theorem. Which is precisely what Rosser did in 1936 when he improved Gödel’s Theorem so it needed only regular consistency. Recall Gödels theorem is based on this DS:
This sentence is not provable.
Rosser’s DS is a more complex sentence,
If this sentence is provable, there is a shorter proof of its negation.
This is often called Rosser’s Trick, which I think underplays the importance of his DS. But that is just my opinion.
Lipton: Not me, but my daughter Jen Lipton O’Connor. I have discussed it before here, but will include it again to save you from having to click. Another free service of GLL.
Jennifer may have invented, when she was about ten years old, a novel type of DS. On a sunny day in the month of May, I was driving her and her older sister, Andrea, to the mall. Andrea was twelve at the time. Jennifer asked if I could take her to Six Flags, a great amusement park, sometime over the summer. Andrea, who was about to go away to camp for the whole summer, immediately complained. Andrea said that it would not be fair if we went when she was away. Andrea loved roller-coasters, and still does, so she really wanted to go too. I answered something non-committal to both of them. But Andrea was clearly upset. Jennifer finally turned to Andrea and said,
Andrea, would it be okay if we went, but we did not tell you?
I almost lost control of the car laughing. Andrea, who was never at a loss for words, just looked at her sister.
Hasselblatt: In this March 2011 Math Monthly issue Boris Hasselblatt is a co-author with Keith Burns of an article on dynamical systems of the type I have just discussed. One of the neat features of this journal is authors give short bio’s at the end of their articles. Usually they list their home institution, their main math areas of research, and usually some fun thing about themselves. Hobbies are very popular. Hasselblatt ends his with this DS:
He dedicates this article to all those who do not dedicate their article to themselves.
Unknown: Ken Regan is unable to locate correspondence he remembers with Uwe Schöning that took place over twenty years ago in which a diagonal theme came up. It was a quotation by a German author, in German, along the lines of:
The only book that deserves to be banned is the index of all banned books.
This is not a DS—unlike the article-dedication example it can be resolved without contradiction or paradox. Namely, the Index can list itself as its only member. Then it deservedly bans itself.
Ken asks: can we prove Gödel’s Theorem using only consistency and avoid using Rosser’s trick? This is related to an earlier discussion about diagonal arguments here.
Are there some other favorite diagonal statements that you would like to share with the rest of us?