QED

Sinds een tijdje ben ik geïnteresseerd in filosofische/metawiskundige vragen over zogenaamde “elementaire” bewijzen. Bij mijn weten is er niet echt een formele definitie van een elementair bewijs, maar in het algemeen gaat het over bewijzen die niet gebruik maken van concepten buiten het domein waarin de stelling gedefinieerd is. In de getaltheorie is een elementair bewijs bijvoorbeeld een bewijs dat in de Peano-rekenkunde kan uitgevoerd worden. Van zodra je in een bewijs van een getaltheoretische stelling gebruik maakt van bijvoorbeeld resultaten uit de complexe analyse, spreken we niet meer van een elementair bewijs.

“Elementair” betekent overigens niet dat deze bewijzen eenvoudig zijn, verre van. Zo zijn de meeste wiskundigen het erover eens dat de elementaire bewijzen van de priemgetalstelling veel moeilijker en minder inzichtelijk zijn dan de bewijzen die gebruik maken van complexe analyse. Zo zegt F.F. Bonsall (“A down-to-earth view of mathematics”, The American Mathematical Monthly, Vol. 89, No. 1 (1982), p. 10):

Our real live mathematician has only a limited knowledge of mathematics, so a proof should use economy of force. It should not invoke deep results if a little elementary calculus will do the trick. But on the other hand there is no merit in an elementary argument if it becomes long and boring. Our real live mathematician would prefer to master some difficult tool than to endure prolonged tedium. The Paul Erdős-Selberg elementary proof of the prime number theorem was a most remarkable tour de force, but no real live mathematician would use it in preference to the function theoretic proofs.

Ook Szemerédi’s elementair bewijs van de naar hem genoemde stelling is niet zo inzichtelijk. Ik laat Terence Tao aan het woord (“What is good mathematics?”, Bulletin of the American Mathematical Society, Vol. 44 (2007)):

While Szemerédi’s accomplishment is undoubtedly a highlight of this particular story, it was by no means the last word on the matter. Szemerédi’s proof of his theorem, while elementary, was remarkably intricate and not easily comprehended.

Vooral de lengte is bij elementaire bewijzen vaak een probleem dat inzichtelijkheid in de weg staat. Zo schrijft Jean-Paul Van Bendegem (“Thought experiments in mathematics: anything but proof”, Philosophica, Vol. 72 (2003), pp. 13-14):

Takeuti in Takeuti (1978) has shown that, if all definitions used are predicative, then a translation into elementary number theory is always possible. At first sight, it seems that all definitions used in Wiles’ and Taylor’s proofs are predicative. But, at the same time, it is quite clear that no one seems to be interested to actually write down that proof, as it would probably have a length beyond all comprehension.

Zowel Paul Erdős als Atle Selberg vonden in 1948 een elementair bewijs van de priemgetallenstelling. Voor velen was dit een schok, omdat de priemgetallenstelling als een “diep” resultaat in de getaltheorie werd gezien. Nu duidelijk was dat “elementaire” methodes voldoende waren om de stelling te bewijzen, bleek de stelling volgens velen ineens minder diep. In 1921 nog zei G.H. Hardy tijdens een lezing dat een elementair bewijs van de priemgetallenstelling hem onmogelijk leek door de ‘diepte’ van de stelling (Dorian Goldfeld, “The elementary proof of the Prime Number Theorem: an historical perspective”, p. 3):

No elementary proof of the prime number theorem is known, and one may ask whether it is reasonable to expect one. Now we know that the theorem is roughly equivalent to a theorem about an analytic function, the theorem that Riemann’s zeta function has no roots on a certain line. A proof of such a theorem, not fundamentally dependent on the theory of functions, seems to me extraordinarily unlikely. It is rash to assert that a mathematical theorem cannot be proved in a particular way; but one thing seems quite clear. We have certain views about the logic of the theory; we think that some theorems, as we say ‘lie deep’ and others nearer to the surface. If anyone produces an elementary proof of the prime number theorem, he will show that these views are wrong, that the subject does not hang together in the way we have supposed, and that it is time for the books to be cast aside and for the theory to be rewritten.

Maar eigenlijk moeten we het van een andere kant bekijken: de “elementaire” Peano-rekenkunde is veel krachtiger dan we tevoren misschien dachten. In 2001 bewees Olivier Sudac (“The prime number theorem is PRA-provable”, Theoretical Computer Science 257 (2001), pp. 185-239) zelfs dat de priemgetallenstelling kan bewezen worden in de primitieve recursieve rekenkunde, een veel zwakkere theorie dan de Peano-rekenkunde. Dit is een interessant resultaat voor het domein van reverse mathematics, waarover ik het eerder al had.

Waarom proberen wiskundigen nu elementaire bewijzen van stellingen te leveren? John Dawson heeft in zijn lijst van redenen om nieuwe bewijzen voor een al bewezen stelling te leveren enkele redenen staan die volgens mij zeker voor elementaire bewijzen opgaan:

• Gaten of onvolkomenheden in bestaande argumenten wegwerken. Een elementair bewijs kan bepaalde controversiële hypotheses vermijden.
• Een eenvoudiger redenering dan vroegere bewijzen opstellen. De lengte en ingewikkeldheid van de redenering wordt in een elementair bewijs meestal groter dan bij een niet-elementair bewijs, maar je gebruikt er dikwijls wel minder hypotheses of moet minder concepten vooronderstellen. Als het elementaire bewijs niet té lang is, kan het ook het meest didactische zijn voor studenten, die daarvoor niet eerst allerlei concepten hoeven te leren.
• De kracht van verschillende methodologieën aantonen. Het bewijs van Sudac maakt dit duidelijk. Dit toont aan dat primitieve recursieve rekenkunde toch een krachtige theorie is, als je er een ‘diepe’ stelling als de priemgetallenstelling mee kan bewijzen.
• Een nieuwe route naar een al bewezen resultaat vinden. Ook dit kan een motivatie zijn om een elementair bewijs te leveren: alleen al het feit dat je de stelling kan bewijzen zonder een “omweg” via complexe analyse.
• Methodologische puurheid. Dit lijkt me een belangrijke motivatie voor elementaire bewijzen. In zo’n bewijs gebruik je immers geen concepten die buiten de context van de vraagstelling liggen en dit is toch clean. Deze houding is bijvoorbeeld te zien bij de wiskundige Alfred Pringsheim die zijn elementaire bewijzen in de theorie van analytische functies ‘natuurlijker’ vindt dan Cauchy’s “sensational results of a mysterious mechanism” door niet-elementaire methodes. (Paolo Mancosu, “Mathematical explanation: problems and prospects”, Topoi, Vol. 20 (2001), pp. 111-112)
• Bevestiging van een al bewezen stelling door een nieuw bewijs. Dit kan je natuurlijk van elk bewijs zeggen, maar bij elementaire bewijzen geldt dit des te meer, omdat de correctheid ervan eenvoudiger en met minder vooronderstellingen lijkt na te gaan. Zo is Jeremy Avigad erin geslaagd om Selbergs elementair bewijs van de priemgetalstelling formeel te verifiëren in het bewijsprogramma Isabelle.