Infinite Objects And Deep Proofs
Are infinite objects needed to resolve important mathematical questions
Angus Macintyre is a top logician, especially in the area of model theory, and especially the model theory of fields. He is a Fellow of the Royal Society, and was awarded the Pólya Prize.
Today I want to talk about a relationship among Andrew Wiles’ proof of Fermat’s Last Theorem, Peano Arithmetic, and some of our open problems.
See an update at end of this post.
I have known Angus for many years, staring with my days at the Computer Science Department in Yale during the 1970′s. Angus, of course, was on the math faculty, and we became friends. He was very kind to me, a young theorist, who knew very little logic. I will always be grateful for his help and time to explain some of the then-new developments. In particular there was a time when I really understood the proof of the famous Paris-Harrington Theorem, thanks to Angus. I have discussed this before here.
An Inconsistent Number?
The Association of Symbolic Logic (ASL) now has three main publications: the Journal, the Bulletin, and the more philosophy-minded Review, all followed by “of Symbolic Logic” in their titles. Back then, however, there was only the Journal, and in a sense it had “everything.” I still recall looking at the Journal and reading an abstract with the title: “An Inconsistent Primitive Recursive Function.” The author claimed to have discovered a primitive recursive function that had two values at the same . This surprised me, no shocked me, since this clearly was “impossible.”
I asked Angus about this, and he explained how things worked at the ASL. He said that any member of the ASL could give a talk at one of their meetings, without any control or refereeing. A member also could publish a short abstract of the talk in the Journal. This led, as you might imagine, to some unusual publications. Later at an ASL meeting I attended a talk by the same researcher, who then had found what he called an inconsistent number.
Clearly there are some issues with allowing any member to publish anything, but it does have some merits. Perhaps today with the cost of adding papers to conferences being so low, it would be interesting to open up the entire publication system. Of course we will then get people who are earnest, believe that have something important to say, but whose ideas are not correct. I wonder what you think about this.
If you do not know the Paris-Harrington theorem, it is based on a “slight” variation on the famous Ramsey theorem. The variation is easily seen to be true, but cannot be proved in Peano Arithmetic (PA). More on PA in a moment, but the theorem is quite beautiful.
The standard Ramsey Theorem is:
Theorem: For any positive integers , there is an with the following property: no matter how we color each of the -element subsets of with one of colors, there exists a subset of with at least elements, such that all -element subsets of have the same color.
You may recognize this special case: color the edges of the complete graph red or green. Then there is always a triangle all of whose edges are the same color. This is the case where since we color edges (i.e., -element subsets), since we use two colors, since we seek a triangle, and .
Now consider a variant of Ramsey theorem, let’s call it the strong Ramsey theorem. It is almost the same, but insists that the set be large. Say a finite set of natural numbers is large provided the cardinality of is larger than the smallest element of . Thus is large, while is not large. The strong Ramsey theorem is:
Theorem: For any positive integers , there is an with the following property: no matter how we color each of the -element subsets of with one of colors, there exists a subset of with at least elements, such that all -element subsets of have the same color. Furthermore, the set is large.
Just the insistence that the monochromatic set must be large makes a huge difference. The strong Ramsey Theorem can easily be proved from the infinite version of the standard theorem, by much the same reasoning as the original, but it cannot be proved in PA. That was the brilliant insight by Jeff Paris and Leo Harrington. The Paris-Harrington theorem is the following:
Theorem: The strong Ramsey theorem cannot be proved in Peano Arithmetic.
There are several proofs known now of this result. The original proof was based on model theory, while Bob Solovay shortly thereafter found an alternative proof based on showing that grew too fast to be provably total in PA. See this for a complete proof and technical discussion of the various approaches to their result.
The famous solution by Andrew Wiles to Fermat’s Last Theorem is a long proof. It is broken into two papers, one joint with Richard Taylor. The main part due solely to Wiles is over one hundred pages, and it builds on papers that total easily hundreds of more pages. Length is not the only measure of the complexity of a piece of mathematics, perhaps not even the right measure for most proofs. Wiles’ proof is more than long, it is deep. This should be no surprise, after all the proof solved a problem that had been open for several hundred years. But it is deep in a precise technical sense: it is yet unknown if the proof can be expressed, even in principle, in PA.
This is the main question that I wish to discuss today: can Wiles’ proof be expressed in arithmetic? There is a very readable article by Colin McLarty in the Bulletin on this very question. The title of his paper is: “What does it take to prove Fermat’s Last Theorem?”
McLarty discusses whether or not there is even in principle a proof of FLT that can be expressed in Peano Arithmetic. The folklore belief is that any non-artificial problem that we do routinely in mathematics should be provable in PA. As with many maxims this is false, since there are “natural” combinatorial problems that are beyond PA. We have just presented one: the strong Ramsey Theorem of Paris-Harrington.
Being unprovable in PA seems less likely for a natural Diophantine statement like Fermat’s, but it remains to be seen. Recall Fermat’s Last Theorem is:
This is a statement in arithmetic, since each variable is restricted to be an integer.
McLarty points out that even though this is a simple universal sentence, it is unclear whether FLT can be proved in a theory as “weak” as PA. The issue is whether Wiles really needs certain infinite objects to prove this finite-sounding statement.
My understanding is that Angus is working on showing that Wiles’ proof can be done in PA. I believe this project is still ongoing, but should be available soon. The obvious question you might ask is: why bother? The current proof is understood by the experts, and even if there were a proof in PA, would it add any further insight?
I believe the answer is a two-fold yes. The main reason is the principle that understanding exactly what a proof requires gives us potentially new insight into what is proved. Thus Angus’ new approach will require nontrivial new insights. I quote McLarty:
Macintyre presents evidence but also shows how his claim remains to be verified by a great deal of further work in arithmetic, It will require serious new arithmetic.
The other reason is that the study of Wiles’ proof from this logical viewpoint could have substantial impact on number theory. New ideas or methods could be discovered in this way.
Go Big, Go Deep
I think there is a potentially interesting lesson here. Most—all?—of the results that we prove in complexity theory can easily be proved in Peano Arithmetic. There is nothing wrong about this, but it is an interesting indication that perhaps our field has dwelled too long in a set milieu. Perhaps the key to unlocking some of the great mysteries of questions like is to “go big, go deep.”
I wonder if there are proof techniques that involve ideas far beyond PA that we have not used, and which would help break open some of important problems. Should we be teaching our graduate students methods from areas of mathematics that lie beyond PA?
Here is an example of a solution to a famous conjecture of Emil Artin that was solved by James Ax and Simon Kochen who used infinite structures—ultraproducts in particular. The problem seems to be just about finding solutions to equations:
Does every homogeneous polynomial of degree over the -adic numbers in at least variables have a nontrivial zero?
They proved that the conjecture is “almost” correct: for each degree the conjecture holds for all primes large enough.
The reason I mention this example is the use of non-principal ultraproducts forces the proof to go beyond set theory. The standard set theory, ZF, is too weak to prove the existence of such infinite objects. Adding the classic Axiom of Choice is enough, actually it is too much. There is a more subtle issue which is that often proofs can be given that proof X and use powerful infinite structures such as ultraproducts, and later these objects can be removed from the proof. This still does not say that using powerful infinite objects was not useful in the discovery of the initial proof.
Do you think FLT can be proved in PA? What about our open problem? Do you think that more “infinitary” methods are needed to resolve our problems? If so, what will they look like?
Erratum/Addendum (2/6/11, by KWR)
Harvey Friedman has pointed out that we were wrong to impute that the Ax-Kochen theorem is unprovable in ZF set theory. It is true only that the infinite objects used in the particular proof require a fairly minimal form of the Axiom of Choice for their construction. Harvey drew our attention as noted here in Wikipedia’s Axiom_of_choice article that any theorem formalizable in the language of PA (and some more general systems) and provable in ZFC is provable already in ZF. In fact, the Ax-Kochen theorem is provable in Peano Arithmetic itself, and Harvey is inquiring whether it is provable in Elementary Function Arithmetic (EFA) (a relevant paper by J. Avigad is linked there).
Harvey also contends that the following by him is a more-natural “strong Ramsey-type theorem”: Say a function is “non-increasing” if for all .
THEOREM: For all and sufficiently large , for every nonincreasing function on , there exist distinct such that coordinate-wise.
As asserted here this is equivalent to the 1-consistency of PA; for some details see this draft paper. Finally, he notes that McLarty’s paper is available generally on the Web, for instance here. His conjecture regarding our “Open Problem” is that Fermat’s Last Theorem is provable not only in PA but even in EFA. We thank Harvey for the attention.