Het werk van een wiskundige bestaat uit het bedenken van nieuwe stellingen en die stellingen vervolgens te bewijzen. Veel wiskundigen hebben er lol in om daarnaast – bij wijze van hobby – van oude stellingen nieuwe bewijzen te bedenken. De Griek Euclides, die 300 jaar voor Christus leefde, bewees al de stelling dat er oneindig veel priemgetallen bestaan. Naast het bewijs van Euclides bestaan er nog andere bewijzen van deze stelling. Aan de lijst van alternatieve bewijzen is er nog één toegevoegd: in het aprilnummer van het tijdschrift American Mathematical Monthly geeft de Canadese wiskundige Idris Mercer een nieuw, kort bewijs. Voor wie de middelbare schoolwiskunde niet al te moeilijk vindt en zich niet laat afschrikken door een paar wiskundige symbolen, is het bewijs van Mercer goed te snappen.
Mercer’s bewijs van de stelling: ‘er zijn oneindig veel priemgetallen’
Een priemgetal is een getal met precies twee delers. Het kleinste priemgetal is 2 en de rij gaat zo verder: 3, 5, 7, 11, 13, 17, … Om Mercer’s bewijs dat deze rij nooit ophoudt te snappen, is enig doorzettingsvermogen nodig. Maar wie het aandurft, krijgt een mooi voorbeeld te zien van een wiskundig bewijs. Deins niet terug voor de volgende wiskundige terminologie en notaties; het ziet er ingewikkelder uit dan het is.
In de wiskunde wordt met Z de verzameling gehele getallen aangeduid: {…, -2, -1, 0, 1, 2, …}. De verzameling even getallen {…, -4, -2, 0, 2, 4, …} kan kort worden genoteerd met 2Z, de verzameling drievouden met 3Z, enzovoorts. De verzameling van alle drievouden plus 2, dus {…, -4, -1, 2, 5, 8, …}, kan kort worden geschreven als 2 + 3Z, maar ook als bijvoorbeeld 5 + 3Z of -1 + 3Z. Zo’n verzameling a + bZ heet een aritmetische progressie.
De verzameling van alle gehele getallen die géén drievoud zijn, dus {…, -8, -7, -5, -4, -2, -1, 1, 2, 4, 5, 7, 8, …}, kan als vereniging van aritmetische progressies worden genoteerd, als volgt: (1 + 3Z) ∪ (2 + 3Z). Mercer noteert dit kort als NM (NM is de afkorting van non-multiples oftewel niet-veelvouden). En de verzameling van niet-vijfvouden: (1 + 5Z) ∪ (2 + 5Z) ∪ (3 + 5Z) ∪ (4 + 5Z); in Mercer’s korte notatie: NM.
Mercer gebruikt voor zijn bewijs van Euclides’ stelling twee hulpstellingen, lemma’s geheten.
Lemma 1: een eindige doorsnede van aritmetische progressies bevat óf nul elementen, óf oneindig veel.
Een voorbeeld maakt veel duidelijk. Neem de verzamelingen 2Z en 1 + 2Z, dus {…, -4, -2, 0, 2, 4, …} en {…, -3, -1, 1, 3, 5, …}. De doorsnede van deze twee verzamelingen bestaat uit alle getallen die in beide verzamelingen zitten: dat is er geen één! Een ander voorbeeld: neem de verzamelingen 3Z en 2 + 4Z, dus {…, -6, -3, 0, 3, 6, …} en {…, -10, -6, -2, 2, 6, 10, …}; hun doorsnede is de verzameling 6 + 12Z en die bevat oneindig veel elementen.
Het algemene bewijs voor lemma 1 (het artikel van Mercer staat hieronder bij de links) is niet moeilijk, al moet je even doorzetten om de wiskundige notatie te doorgronden.
Lemma 2: als S een collectie verzamelingen is, kan een eindige doorsnede van eindige verenigingen van verzamelingen uit S worden geschreven als een eindige vereniging van eindige doorsneden van verzamelingen uit S.
Lemma 2 klinkt misschien erg cryptisch, maar ook hier helpt een voorbeeld. Stel dat S bestaat uit zeven verzamelingen: A, B, C, D, E, F en G. Volgens een van de wetten van De Morgan geldt:
(A ∪ B ∪ C) ∩ (D ∪ E) ∩ (F ∪ G) = (A ∩ D ∩ F) ∪ (A ∩ D ∩ G) ∪ (A ∩ E ∩ F) ∪ (A ∩ E ∩ G) ∪ (B ∩ D ∩ F) ∪ (B ∩ D ∩ G) ∪ (B ∩ E ∩ F) ∪ (B ∩ E ∩ G) ∪ (C ∩ D ∩ F) ∪ (C ∩ D ∩ G) ∪ (C ∩ E ∩ F) ∪ (C ∩ E ∩ G).
We hebben nu voldoende gereedschap om te bewijzen dat de verzameling priemgetallen uit oneindig veel elementen bestaat. We doen dat uit het ongerijmde, dat wil zeggen: stel eens dat er slechts eindig veel priemgetallen zouden bestaan: p1, p2, …, pk. Bekijk nu de doorsnede van de verzamelingen NM, NM, …, NM:
( * ) NM ∩ NM ∩ … ∩ NM.
Dit is een eindige doorsnede van eindige verenigingen van aritmetische progressies en kan dus volgens lemma 2 worden geschreven als eindige vereniging van eindige doorsneden van aritmetische progressies en volgens lemma 1 bevat zo’n verzameling nul of oneindig veel elementen. Maar ( * ) bevat precies twee elementen, namelijk -1 en 1. Dit is een tegenspraak en daarom kunnen we concluderen dat de veronderstelling dat er slechts eindig veel priemgetallen bestaan, onjuist is. Dan rest er niets dan te concluderen dat er oneindig veel priemgetallen bestaan.
Helemaal nieuw?
De titel van Mercer’s artikel is ‘On Furstenberg’s Proof of the Infinitude of Primes’. Mercer verwijst hiermee naar een bewijs van de Israëlische wiskundige Harry Fürstenberg, die in 1955 met een verrassend bewijs van Euclides’ stelling kwam. Hij gebruikte de topologie, een tak van de wiskunde die je niet als vanzelfsprekend in verband brengt met de getaltheorie, om de stelling van Euclides te bewijzen. Het bewijs van Mercer is in feite een variant op het bewijs van Fürstenberg: het idee is hetzelfde, maar topologische taal wordt vermeden.
Zie ook:
Over verenigingen, doorsneden en de wetten van De Morgan De website van Idris Mercer Het artikel van Idris Mercer Oneindig veel priemgetallen (Kennislinkartikel) Priemgetallen (Kennislinkdossier) Waarom herbewijzen wiskundigen stellingen? Ulam-spiraal (Wikipedia, Eng.)