Na de post over priemgetallen (1) verscheen een commentaar van lezer Lieven, die voorstelde eens te proberen het bewijs van Euclides, dat er oneindig veel priemgetallen zijn, na te bootsen.
Dat ging bij mij van "pfffff, amaï, zo moeilijk". Het is nochtans belangrijk. Nu ja, "belangrijk"... Maar toch. Als je bedenkt dat, naarmate je verder gaat in de getallen, er ook meer getallen komen waarmee je kan proberen de nog grotere getallen te delen, dan kan je je inbeelden dat er een moment komt waarop de getallen zo groot worden, dat ze allemaal wel deelbaar worden door iets.
Wel, dat is dus niet zo, en daar had Euclides, zo'n tweeëntwintig eeuwen geleden, een bewijs van. Ik herinner me het begin. Neem aan dat de verzameling priemgetallen niet oneindig is. Dan heb je dus een opsombare lijst van alle getallen die priemgetallen zijn. Wat zou er gebeuren als je die allemaal met elkaar vermenigvuldigde? Dus 2 X 3 X 5 X 7... enzovoort, tot al je priemgetallen gepasseerd zijn. Noem het getal dat je daarmee krijgt P. En tel daarbij het getal één op. Dus we hebben het over "P + 1"; het product van alle priemgetallen plus één.
Er zijn twee mogelijkheden: dat getal P + 1 is zelf een priemgetal, of het is geen priemgetal. Maar als het een priemgetal is, dan is het simpel: onze zogezegde verzameling van alle priemgetallen was niet de verzameling van alle priemgetallen, want P + 1 zat er niet in.
Dus het is géén priemgetal. En ik kwam daar terecht met een gevoel van "en wat dan nog?", en dat was het einde van een briljante mathematische redenering.
Maar deze nacht om vier uur werd ik wakker, en begon te piekeren over de verbouwingen hier. Piekeren is heel slecht, maar doe er maar iets aan. Dus begon ik maar weer aan de priemgetallen. P + 1 is dus géén priemgetal. Maar door welk getal gaan we het dan delen, vroeg ik me af? Het kan niet deelbaar zijn door een priemgetal, want P is al deelbaar door al die priemgetallen, dus bij deling van P + 1 door een priemgetal blijft er een rest één.
En dat is waar ik nu vastzit. Als P + 1 geen priemgetal is, maar ook niet deelbaar door een priemgetal, dan moet het deelbaar zijn door een getal dat geen priemgetal is. Dus als ik nu kon zeggen waarom het niet kan, dat een getal niet deelbaar is door een priemgetal, maar wel door een ander getal, dan zou ik dat bewijs van Euclides ongeveer bij elkaar hebben.
Of niet, soms?
UPDATE (de volgende ochtend)
Waar "een nachtje slapen" al niet goed voor is... Ik pas toch gewoon hetzelfde idee ("als P + 1 géén priemgetal is, waardoor gaan we het dan delen?") toe op de getallen waardoor ik net P + 1 gedeeld heb? Dus: ik had gisteren al (een) deler(s) van P + 1 dat geen priemgetal is: dus die heeft delers, en dat kunnen geen priemgetallen zijn. Immers, als er wel een priemgetal tussen zat, dan zat dat niet in de lijst met "alle" priemgetallen, vermits die juist delers van P zelf waren, zodat ze geen delers van P + 1 kunnen zijn. En in dat geval laat mijn "volledige" lijst priemgetallen toe nieuwe priemgetallen te vinden...
Maar dan zijn die delers op hun beurt en om dezelfde reden ook geen priemgetallen, en dus hebben ze delers, en die kunnen ook weer geen priemgetallen zijn, en dus hebben ze delers, etcetera. Je kan niet blijven delers vinden die geen priemgetallen zijn, want op een gegeven moment zit je bij twee en drie (of grotere priemgetallen, natuurlijk).
Op het eerste zicht reproduceert dat het bewijs van Euclides. Laat ik er vooral aan herinneren dat ik dat bewijs eens had gelezen in een boekje (dat ik hier niet heb) en er alleen de eerste stap van onthouden had. Maar toch, het verschil met Euclides is natuurlijk dat die niet eerst het bewijs van iemand anders had gelezen...
(Plus nog een hoop andere verschillen die iedereen wel zo zal geloven ook.)
Rest me de vraag waarom ik dacht dat ik moest kunnen bewijzen dat elk getal (dat geen priemgetal is) in een unieke set priemgetallen te ontbinden is. Heb ik toch nog iets over het hoofd gezien?
Aan het werk van Kantor, zoals een anonieme commentator suggereerde, zal ik me veiligheidshalve maar niet wagen. Nog vragen over evolutietheorie en creationisme, iemand?
---------------------------------
(1) http://speelsmaarserieus.blogspot.com/2007/04/priemgetallen-wat-is-kennis.html
20 opmerkingen:
Eigenlijk is dat toch wel een simpel bewijs.
En nu: Cantor's methode om te bewijzen dat Q en R een verschillende kardinaliteit hebben.
En eenmaal je de diagonaalmethode onder de knie hebt, kan je die ook gebruiken om de stelling van Godel te bewijzen.
Misschien dat de volgende tip je kan helpen Koen:
Elk getal is of zelf een priemgetal of te schrijven als een product van alleen maar priemgetallen. Nemen we als voorbeel 360, dan is dat te schrijven als 2 * 2 * 2 * 3 * 3 * 5
Haha, tips waren natuurlijk juist waar ik om vroeg. Maar juist op dit moment had ik een update aan mijn post toegevoegd, en nu ik er enkele seconden over nadenk lijk ik in de buurt, maar niet helemaal, te komen van wat jij schrijft. Zelf heb ik het gevoel dat ik hier iets over het hoofd aan het zien ben. Enig idee?
Bedankt,
Koen
Het is inderdaad simpeler als je eerst het volgende lemma bewijst: als Q>1 niet priem is, dan bestaat er minstens één priemgetal p dat Q deelt.
Het bewijs gaat dan:
Stel er zijn een eindig aantal (n>0) priemgetallen. met produkt P.
Dan is P+1 geen priemgetal. (want een produkt van natuurlijke getallen is GROTER dan elk van zijn factoren, i.e. P+1 kan niet voorkomen in onze lijst van n priemgetallen)
Maar als het geen priemgetal is dan moet er MINSTENS een priemgetal een deler van P+1 zijn.
Maar als we onze eindige list van priemgetallen afgaan, dan zeggen die allemaal "niet ik!", want ze zijn al een deler van P, en dus is de rest bij deling van P voor elk priemgetal 1.
En dus hebben we een contradictie: P+1 is zogezegd geen priemgetal, maar het is ondeelbaar door elk priemgetal.
En dus moet onze enige premisse, namelijk dat er slechts een eindig aantal priemgetallen bestaan; verkeerd zijn.
Ik haalde Cantor en Godel met een reden aan, omdat hun bewijzen verdacht gelijkaardig gaan:
Want Euclides zegt: stel dat het aantal priemgetallen enidig is: Bam! contradictie en dus niet waar.
Cantor zegt: stel dat de reële getallen enumereerbaar zijn. Bam ! contradictie en dus niet waar.
Het genie van Cantor zat hem dus in de manier waarop hij die contradictie creëerde. Maar achteraf gezien was dat eigenlijk niet zoveel verschillend van wat Euclides deed: een ééntje bijtellen.
Euclides telde een eentje bij het produkt van de priemgetallen. En als je al die priemgetallen vroeg: deel jij P+1 antwoordden die "niet ik!".
En dus telde Cantor ook overal een eentje bij, maar telkens op een andere plaats: de diagonaalmethode.
En Cantor vroeg aan alle geenumereerde reëele getallen: ben jij het getal op de diagonaal? En een voor een antwoordden die "niet ik!".
Bam ! contradictie!
"Anoniem" Ik zal hier een tikje langer moeten over nadenken...
Intussen, zou je meet dit soort reacties jezelf geen nickname aanmeten? Ik hoef heus je echte naam niet te weten, maar er zijn nu eenmaal veel "anoniemen", en de kwaliteit van allemaal is niet altijd even groot.
oops.
dat moet dus zijn:
want ze zijn al een deler van P, en dus is de rest bij deling van P+1 voor elk priemgetal 1.
Wel, ik begrijp intussen dat het bewijs beter zou zijn als ik dat punt (waar jullie het nu beiden over hebben) apart had bewezen. Maar ook daar zal ik nog eens een nachtje moeten over slapen.
Alleen... "mijn" bewijs waarbij ik altijd naar kleinere delers terugval, terwijl die nooit priemgetallen mogen zijn - is dat fout, of onvolledig, of gewoon te weinig strikt en teveel verhalend, of whatever?
Als terzijde, het hele verhaal over Kantor gaat me ver, ver boven mijn pet. Niet dat het niet mag, hoor, maar in mijn geval kan je je de moeite even goed besparen.
Een bewijs voor dat lemma is inderdaad de constructie die jij uitvoert: pak een factor en stop als het een priemgetal is, indien niet, factoriseer hem op zijn beurt enzoverder.
Als je eerst unieke factorisatie bewezen hebt, krijg je dat lemma natuurlijk onmiddellijk.
Overigens snap ik niet dat Cantor's diagonaalargument boven je petje zou gaan, zo moeilijk is dat nu ook weer niet.
Je bewijs is correct. Je hebt de unieke factorizatie niet nodig.
Hier is eigenlijk wel een leuk voorbeeld dat wiskunde nog lang niet is opgelost. De procedure in dit bewijs, levert net als je zeef in het vorig artikel een oneindige reeks priemgetallen op.
We beginnen met {2} als verzameling priemgetallen. De procedure uit het bewijs een keer toepassen levert 2+1=3 op als nieuw priemgetal dus nu hebben we {2,3}. Altijd maar verder gaand vinden we {2,3,7}, {2,3,7,43}. Deze laatste verzameling levert ons 1807=13x139 op. We vinden dus dat we ook kleinere priemgetallen ermee kunnen terugvinden.
De natuurlijke vraag is nu: Gaan we hiermee alle priemgetallen tevoorschijn toveren of zijn er die we nooit gaan vinden?
En in de huidige stand van de wiskundige kennis is dit een open vraag.
Canon: Je moet eens proberen je teksten over Kantor te lezen door de ogen van iemand die Grieks en Latijn heeft gedaan, en daar een lvende legende was wegens slecht in wiskunde. En die daarna rechten en filosofie heeft gestudeerd.
Als je er in slaagt je tekst door die ogen te lezen, dan zal je alleen maar namen als "Cantor" staan, en termen als "diagonaalargument", maar je zal geen flauw idee, werkelijk "not the slightest clue" hebben van waar die eigenlijk over gaan.
En dat is waar mijn eerste priemgetallenpost over ging. Ik kan het niet weten, maar ik zou serieuze weddenschappen afsluiten dat de papa van Jeroen ons allemaal om de oren kan slaan over Cantor en diagonaaldinges - en toch was het nonkel Koen die Jeroen uitlegde wat priemgetallen waren: "wat is kennis?"
Tja, ik nam aan dat je min of meer vertrouwd was met de grote lijnen van Cantor's bewijs.
Eigenlijk is dat toch een van de belangrijkste stellingen uit de verzamelingenleer.
Om te beginnen gaan we eerst iets zeggen over het begrip "kardinaliteit". Dat is gewoon een duur woord voor "hoe-grootheid" van een verzameling.
Twee verzamelingen hebben dezelfde kardinaliteit (definiëren we), als er een één-op-één relatie bestaat tussen deze twee verzamelingen.
Voor eindige verzamelingen is dat simpel, de kardinaliteit is dan eigenlijk niets anders dan het aantal elementen van die verzameling, en twee verzamelingen met hetzelfde aantal elementen hebben dezelfde kardinaliteit.
Dat lijkt allemaal simpel, en dat is het ook. je zou je afvragen waarom we eigenlijk het begrip kardinaliteit hebben gedefiniëerd. Wel, eigenlijk was dat om ook iets te kunnen zeggen over oneindige verzamelingen.
Eerst en vooral is er een simpele definitie voor een oneindige verzameling: een verzameling is oneindig als er een één-op-één relatie bestaat tussen die verzameling en een echte deelverzameling.
Bijvoorbeeld: als ik de natuurlijke getallen neem:
0 1 2 3 4 5 ...
en ik verdubbel ze allemaal
0 2 4 6 8 10 ...
dan heb ik een één-op-één relatie tussen de natuurlijke getallen en de even natuurlijke getallen. Dat lijkt een beetje "raar", omdat we intuitief niet verwachten dat als we de helft wegsmijten uit een verzameling, nog altijd "even veel" overhouden. Maar als we daar eens goed over nadenken, dan is het intuitief eigenlijk niet zo "raar" dat oneindige verzamelingen zich een beetje anders gedragen dan eindige verzamelingen. (En louter wiskundig is het helemaal niet raar, omdat we juist oneindige verzamelingen zo gedefinieerd hebben.)
En dan komen we eigenlijk bij de vragen die Cantor bezighield: hoeveel verschillende "soorten" oneindigheid zijn er, en in het geval dat er meer dan één is, kunnen we daar een beetje structuur inbrengen?
En het eerste stuk, is er meer dan één oneindigheid, leidt ons dan uiteindelijk tot Cantor's diagonaalargument.
Laat ons even stilstaan bij de problematiek. Stel, we hebben een oneindige verzameling C, waarvan we vermoeden dat ze van een andere kardinaliteit (i.e. een "grotere" oneindigheid) is dan die van de natuurlijke getallen.
Maar dan moeten we dus bewijzen dat er GEEN één-op-één relatie bestaat tussen die twee verzamelingen. En daar zou een mens wel eens de handdoek in de ring kunnen smijten, want hoe bewijs je nu in hemelsnaam een negatief gegeven?
Maar nee, we hbben dat al verschillende keren voorgehad in de les Wiskunde: we gaan gewoon veronderstellen dat zo'n één-op-één relatie bestaat, en dan moeten we gewoon daaruit een contradictie creëren, en pats boem, gedaan.
Neem nu dus dat C het interval [0, 1[ van de reële getallen is.
(En voor de pietluttigen onder ons, neem aan dat wij de reële getallen in een canonieke vorm kunnen schrijven, zodat we ofwel 0.0999999999... met allemaal 9s daarop volgend, ofwel 0.10000000... hebben, maar nooit de beide.)
en dus hebben we een zogezegde één-op-één relatie, bijvoorbeeld:
0 : 0.0000000...
1 : 0.5000000...
2 : 0.7071678...
3 : 0.2500000...
4 : 0.1415926...
...
En nu doet Cantor de truuk van Euclides, maar dan herhaaldelijk: hij telt overal eentje bij (modulo 10) op de diagonaal:
0 : 0.1 ...
1 : 0. 1 ...
2 : 0. 8 ...
3 : 0. 1 ...
4 : 0. 0 ...
En dan houdt hij daar (in dit geval) het getal 0.11810... aan over.
En nu zegt Cantor triomfantelijk: dat getal komt niet voor in de lijst!
Want het verschilt op de eerste decimale plaats van het éérste getal. En op de tweede decimale plaats van het tweede getal, en, generaliserend, op de n-de decimale plaats van het n-de getal voor elke n.
En dus hebben we een contradictie. (en voor de pietluttigen, ja soms zullen we een beetje moeten foefelen om te vermijden dat we 0.999999.. met allemaal 9s bekomen, maar dat kunnen we indien nodig.)
En dus heeft het interval [0, 1[ van de reële getallen een kardinaliteit verschillend van die van de natuurlijke getallen.
En eerlijk gezegd, zo moeilijk was dat nu toch niet?
Wel...
Het ziet er (ten eerste) zeer interessant uit...
En verder ziet het er ook uit alsof het inderdaad niet zo heel moeilijk is...
... als er niet het volgende kleine probleem was. Ik zie geen begin van een verband tussen je eerste tabel, waar je de natuurlijke getallen nogal willekeurig verbindt aan nogal willekeurig lijkende getallen tussen nul en één, en je tweede tabel. Ik zie het getal 0.11810 verschijnen, maar ik heb geen flauw idee waarom.
Hey, ik méénde dat van dat Latijn en dat Grieks, hé.
Maar toch, moet ik zeggen, hoop ik dat je de ontbrekende stukken (vanuit mijn perspectief dan) wil invullen. Het lijkt werkelijk nogal intrigerend, en tegelijk niet noodzakelijk zo heel moeilijk.
Ha, het is allemaal de schuld van html die min extra spaties heeft opgegeten!
de tabellen hadden er beter zo uitgezien
0 : 0.0000000...
1 : 0.5000000...
2 : 0.7071678...
3 : 0.2500000...
4 : 0.1415926...
...
0 : 0.1000000...
1 : 0.5100000...
2 : 0.7081678...
3 : 0.2501000...
4 : 0.1415026...
...
OK, met een volledige tabel voor ogen, even testen of ik het begrijp. Ik zie dus je getal 0.11810 (zonder puntjes), en ik zoek dat getal op de lijst. Maar als ik het vind, doen we gewoon verder met de "diagonale methode", en dat genereert 0.118101. En als ik dat opzoek, genereert het 0.1181011.
Iets dergelijks? De diagonale methode is een getallengenerator, en wel van getallen die niet op de lijst staan?
Nee, er wordt maar een enkel getal gegenereerd.
We berekenen ineens het volledige getal (hier dus met puntjes wegens plaatsgebrek) op de diagonaal, en wegens de constructie komt het niet voor in het lijstje.
Bon, ik zal hier allemaal eens heel rustig over moeten nadenken. Het heeft inderdaad allemaal wel iets erg intrigerends, maar ik denk dat je, vermits je er vertrouwd mee bent, onderschat hoe het allemaal gaat duizelen bij mensen die er nooit mee te maken hebben.
Misschien begin ik er nog wel eens opnieuw over. In afwachting dat het zover is, wel bedankt voor je input - dat zijn heel andere werelden die opengaan ... :-)
Wel ik ga ook eens een poging doen om het diagonaal bewijs van cantor uit te leggen. Aangezien Koen heeft aangegeven een redelijke leek te zijn zal ik proberen de zaak zo eenvoudig mogelijk te benaderen. Mijn verontschuldigingen aan iedereen die vind dat ik te traag ga.
Ik ga het hebben over natuurlijke getallen en hun verzamelingen. De natuurlijke getallen dat is eenvoudig dat begint met 0 en gaat verder met 1, 2 enz. Een verzameling is gewoon een aantal natuurlijke getallen bij elkaar genomen. Er zijn eindige verzamelingen zoals de verzameling bestande uit 5, 88 en 113 ook wel geschreven als {5, 88, 133} er zijn ook oneindige verzamelingen zoals alle drie vouden of alle priemgetallen of zelfs gewoon alle natuurlijke getallen en er is ook nog de lege verzameling: {} de verzameling waar geen enkel getal inzit. Bij een verzameling speelt de eventuele volgorde waarin de elemenet opgesomt worden geen rol. {7, 56, 843, 8} is de zelfde verzameling als {8, 7, 843, 56}. Nog een manier om verzamelingen te noteren is de volgende: {x | P(x)}. Dit betekent de verzameling van element waarvoor P(x) waar is. Als we b.v. de verzameling willen aanduiden van alle getallen groter dan 89 dan kunnen we dat als volgt schrijven {x| x > 89}.
De vraag is nu: zijn er meer verzamelingen dan getallen?
Iets duidelijker. We kunnen met elk getal een verzameling associeren. bv:
0: {}
1: {3, 8, 33}
2: {even getallen}
3: {9, 16, 25}
4: {alle kwadraten}
5: {x| x < 16}
...
Zo'n associatie kunnen we een naam geven b.v. F. F(a) is dan de verzameling waarmee het getal a wordt geassocieerd. In het bovenstaande geval hebben we dus:
F(0) = {}
F(3) = {9, 16, 25}
Nu in de meeste associaties die mogelijk zijn gaan er verzamelingen zijn die niet met een getal geassocieerd zijn. Nemen we het volgende voorbeeld:
0: {}
1: {0}
2: {0, 1}
3: {0, 1, 2}
Dus met elke getal associeren we de verzameling met getallen die kleiner zijn. Het is duidelijk dat in deze associatie de verzameling van even getallen met geen enkel getal geassocieerd is.
De vraag is nu of er een associatie bestaat waarbij elke mogelijke verzameling geassocieerd is met een getal.
We gaan ervan uit dat zo'n associatie bestaat, we noemen ze F, en zien wat er gebeurd.
Allereerst kunnen we aan de hand van de associatie de getallen in twee verzamelingen indelen. Namelijk a zit in F(a) of a zit niet in F(a). Gaan we even terug naar het eerste voorbeeld dan hebben we dat 2 in F(2) zit, want F(2) zijn de even getallen en 2 is een even getal. 3 zit daarentegen niet in F(3) want F(3) was {9, 16, 25} en 3 maakt daar geen deel van uit. Nu maken we de verzameling van die getallen die geen element zijn van de verzameling waarmee ze geassocieerd zijn:
S = {a | a niet in F(a)}
Nu was de aanname dat er voor elke verzameling een getal bestond waarmee de verzameling geassocieerd werd. Dus moeten we nu een getal hebben waarmee deze verzameling wordt geassocieerd. We noemen dat getal s. We hebben dus F(s) = S.
Nu komen we met de volgende vraag: zit s in S of niet.
Stel s in S. dat betekent s in F(s) maar S = {x | x niet in F(x)} dus s niet in F(s) we zitten hier met een tegenspraak
dus dit kan niet waar zijn.
Stel s niet in S. dus s niet in F(s) maar S = {x| x niet in F(s)} dus s in S
dus we zitten opnieuw met een tegenspraak.
Besluit als we aannemen dat er een associatie bestaat waarbij elke verzameling met een getal geassocieerd is, komen we uiteindelijk op een tegenspraak uit en dus is zo'n associatie onmogelijk.
Wel...
Ik ben er nog niet helemaal doorgekauwd, hoor.
Maar ik voel wel al ongeveer waar de wind vandaan komt. Ik zie wel dat het bewijs (*indien* ik het al helemaal begrepen had) hetzelfde *doet* als het bewijs van Cantor. Maar ik zie eigenlijk niet waarom je in het begin zegt dat het dat diagonaal bewijs *zelf* is. Ik zie eerlijk gezegd geen enkele diagonaal.
Overigens doet deze laatste post van Axxyanus me sterk denken aan een brief die de filosoof Bertrand Russell op een dag aan de logicus Gottlob Frege stuurde, met nogal explosieve gevolgen. Maar dat is alleen maar filosofische kennis, en zeker geen begrijp van de betrokken bewijzen zelf.
Waarschijnlijk zien we hier het verschil in actie, tussen "kennis" en "eruditie". Met hat laatste kan je altijd pronken, nietwaar?
:-)
Koen
"Ik zie eerlijk gezegd geen enkele diagonaal"
Beeld je een oneindige matrix in, met de getallen langs een as, en de verzamelingen langs de andere as, in de volgorde bepaald door F.
En op rij a kolom b zet je ofwel een eentje of een nulletje, naargelang a voorkomt in F(b) of niet.
Om te controleren of "a zit in F(a)" waar is, moet je dat dan gaan opzoeken op de diagonaal.
De verzameling S, zo die voorkomt in onze matrix, moet dan corresponderen met een kolom die we bekomen door alle eentjes en nulletjes op de diagonaal te verwisselen (en 45 graden te draaien).
Een reactie posten