Posted in May 2018
Het Compactheidsbeginsel
Twee recente artikelen op Kennislink hebben iets gemeen. Dat gemeenschappelijke is een belangrijk stuk gereedschap uit de Wiskunde dat bekend staat als het Compactheidsbeginsel.
In 2016 werd een kleuringsprobleem voor de natuurlijke getallen opgelost: is het mogelijk de natuurlijke getallen in tweeën te delen op zo’n manier dat beide delen geen enkel Pythagoreïsch drietal bevatten? Het antwoord is: “nee”. Zoals op Kennislink te lezen is is er iets meer ontdekt: bij elke verdeling van {1,2,3,…7825} in twee delen moet een van de delen een Pythagoreïsch drietal bevatten en er is een verdeling van {1,2,3,…,7824} waarbij geen van de beide delen een bevat.
Voor de goede orde: een Pythagoreïsch drietal is een drietal natuurlijke getallen (a,b,c) dat voldoet aan a2+b2=c2. Ook wordt het probleem vaak in termen van kleuringen geformuleerd: de verdeling wordt weergegeven door elk natuurlijk getal rood of blauw te kleuren.
Begin van deze maand werd vooruitgang geboekt bij een kleuringsprobleem in het platte vlak: in hoeveel verzamelingen moet je de punten in het vlak minimaal verdelen opdat geen enkel deel twee punten bevat die afstand 1 hebben. Er was lang bekend dat dat minimale aantal ten minste 4 en ten hoogste 7 is; nu is bekend dat het ten minste 5 moet zijn. Okk hier is al aan een eindige verzameling punten te zien dat bij elke verdeling in vier stukken er altijd een stuk is dat twee punten met afstand 1 bevat.
Waarom is dat? Het zou toch bij het eerste probleem zo kunnen zijn dat bij verschillende kleuringen de drietallen één kleur krijgen steeds hoger in de natuurlijke getallen moeten zitten. Maar kennelijk is het zo dat, ongeacht de kleuring er al een éénkleurig drietal is in {1,2,3,…,7825}.
Het geheim is een stelling van De Bruijn en Erdös; deze zegt dat bij elk kleurings probleem het volgende geldt: als elke eindige verzameling een `goede’ kleuring heeft dan is er een `goede’ kleuring voor de hele verzameling. Dat kun je ook als volgt contrapositief formuleren: als elke kleuring van de hele verzameling `slecht’ is dan is er een vaste eindige verzameling waarvoor elke kleuring `slecht’ is. In April 2014 is over deze stelling een artikel in Pythagoras verschenen.
Het voordeel van dit Compactheidsbeginsel is dat men voor positieve resultaten alleen naar eindige verzamelingen hoeft te kijken; dat kan de bewijzen aanzienlijk vereenvoudigen. Het nadeel is dat het niet constructief is: het geeft geen enkele informatie over de grootte van de vaste eindige verzameling waarvoor elke kleuring `slecht’ is. Dat laatste is te zien aan de resultaten waarover op Kennislink bericht werd; de zoektochten naar de eindige verzamelingen en de verificaties dat ze werkten kostten veel tijd en moeite.
Eindexamen Wiskunde B (vwo) (2018-05-14)
Ik heb gisteravond snel het examen gemaakt en becommentarieerd. Hier is een link naar mijn PDF. Ik had niet veel tijd dus ik kan fouten gemaakt hebben (laat het mij weten).
Ik vond het examen niet echt uitdagend. Er was niet veel context en die van de Sheffield Winter Garden leek er met de haren bijgesleept. Aan de andere kant waren de formuleringen wel erg uitgebreid en bleef er vaak niet meer over dan een (soms lastige) invuloefening.`
Het vlak kleuren
Vorige maand (april 2018) is er een stap gezet op weg naar de oplossing van het volgende probleem: “hoeveel kleuren heb je nodig om de punten van het vlak te kleuren en wel zo dat punten op afstand 1 verschillende kleuren krijgen. De titel van het artikel in de Volkskrant is misleidend want het probleem is nog niet opgelost; de titel van het stuk in NRC is correct.
Beide stukken waren niet zo duidelijk als men wellicht hoopte, getuige bijvoorbeeld de commentaren in de facebookgroep ‘Leraar Wiskunde’. De opmerkingen over de voorbeelden in de Volkskrant werden niet altijd begrepen en de pixelmetafoor in NRC leidde tot misverstanden over de aard van het probleem.
Wat bekend was over het probleem tot vorige maand was het volgende. Door middel van een betegeling van het vlak met behulp van regelmatige zeshoeken met diameter 1 kun je een kleuring met zeven kleuren maken. Hierbij moet je wel precies zijn: bij elke zeshoek neem je de randpunten van zes uur tot twaalf uur mee (inclusief zes uur exclusief twaalf uur) en laat je de andere randpunten weg. Elke tegel krijg namelijk een kleur en op deze manier vermijdt je dat randpunten op afstand 1 dezelfde kleur krijgen.
De voorbeelden in het NRC-artikel zijn duidelijk: als je de punten van het vlak met twee kleuren kleurt dan zijn er in een gelijkzijdige driehoek met zijden 1 al twee punten met dezelfde kleur. Daarnaast is er een configuratie van zeven punten te zien waarvoor bij elke kleuring met drie kleuren twee punten met afstand 1 zijn die dezelfde kleur krijgen.
Het nieuwe is een configuratie van 1581 punten, gevonden door Aubrey de Grey waarin hetzelfde geldt, maar nu voor vier kleuren; dus, hoe je die punten ook kleurt met vier kleuren er zullen er altijd twee zijn met afstand 1 en dezelfde kleur. Inmiddels is 1581 teruggebracht tot 633.
De pixelmetafoor uit NRC leidde tot een onderschatting van het probleem; dat kwam door een subtiel verschil tussen pixels en de punten van het vlak: in tegenstelling tot pixels hebben punten in het vlak geen directe buren en geen oppervlakte, ook zijn ze niet vierkant. De echte formulering van het probleem vraagt naar het kleinste natuurlijke getal n met de eigenschap dat er een functie van het vlak naar {1,2,…,n} is met de eigenschap dat als d(x,y)=1 dan f(x)≠f(y). Daar komt geen verf of kwast aan te pas en de vorm of oppervlakte van een punt is ook niet van belang.
Achter de voorbeelden die laten zien dat een bepaald aantal kleuren niet volstaat zit een stelling van De Bruijn en Erdös: als elke eindige deelverzameling van het vlak een goede kleuring met k kleuren toelaat dan laat het vlak ook een goede kleuring toe. Met andere woorden: om te laten zien dat er geen goede kleuring is moet je een eindige verzameling zonder goede kleuring vinden.
Overigens zou dit nog tot twee verschillende oplossingen van het probleem kunnen leiden: de stelling van De Bruijn en Erdös geldt onder aanname van het keuzeaxioma. In dit artikel van Shelah en Soifer is te lezen dat de aard van de gevraagde functie het antwoord kan beïnvloeden. Lang voor het werk van De Grey was bekend dat een Lebesgue-meetbare kleuring ten minste vijf kleuren zou vergen. NB de laatste stelling in het artikel van Shelah en Soifer is nu achterhaald.
Ten slotte: houd de Wikipediapagina over dit probleem in de gaten.
Toevoeging (2018-05-14): het hieronder in een reactie genoemde artikel op Kennislink is ook zeer informatief.
Did Thanos kill me?
Some of you may have seen Avengers: Infinity War already, some may have not. Via Geek Girl Authority I found this website: www.didthanoskill.me/. There you can check whether you will survive the carnage at the end of the movie.
As is to be expected the decision process is not very sophisticated:
if (randomNumber < 0.5) {
displayElement.textContent = "You were slain by Thanos,
for the good of the Universe.";
} else {
displayElement.textContent = "You were spared by Thanos.";
}
But, can you escape your fate by reloading the page? Actally, no.
The script first retrieves a cookie:
var randomNumber = getCookie("thanosNumber");
If that number exists it will be used in the decison process, so the random number is generated on your first visit and re-used on each next reload. My `thanosnumber’ is 0.3461087295578963, so I’m a goner.
I also checked whether the process is fair; it is on this page you can read that the random number is in the interval [0,1) (including 0, excluding 1). That means that, even accounting for the finite precision, half the numbers can be expected to be less than ½.
To see why excluding 1 mighyt matter think of a machine with a very low precision, say two binary digits. This means that the random numbers would be chosen from these four: .00, .01, .10, .11 (that is: 0, ¼, ½, ¾,). Clearly your probability of survival would be 2/4, i.e., one half. On the other hand, if 1 were als a possible outcome then your survival probability would be 3/5.
For the population of the Earth and with the precision suggested by my thanosnumber including 1 or not would not make much difference.
Since there are no more that 1010 people and the thanosnumbers have a precisioon of 16 digits the difference in the order of 10-6 person.
Wat is een verzameling? II
We zetten de zoektocht naar het begrip `verzameling’ voort.
In de vorige blogpost hebben we de definities die Bolzano en Cantor van `verzameling’ gaven geciteerd. Die kwamen eigenlijk neer op “een verzameling is een verzameling”. Nu is het nogal lastig om een definitie van verzameling in woorden op te schrijven zonder te vervallen in synomiemen maar het kan wel.
Rond de eeuwisseling (die van 1900) begon men ernstig over de aard van definities na te denken. De eerste stap was het vastleggen van de taal waarin die definities vastgelegd zouden worden. En met `taal’ bedoelde men niet zoiets als Grieks, Latijn, of Swahili maar een meer formele constructie. Deze gaat uit van een beperkt aantal symbolen. Sommige zijn algemeen, zoals ∧ (en), ∨ (of), ¬ (niet), ∀ (voor alle) ∃ (er is) enzovoort; en sommige zijn specifiek voor het onderhavige onderdeel van de wiskunde, in de verzamelingenleer kunnen we toe met ∈ (is element van) en = (is gelijk aan).
In deze taal kunnen we vrijwel alles beschrijven wat we willen. De taal is sterk genoeg om dingen als
- “x is een priemgetal”
- “x is een reëel getal”
- “x is een rechte lijn in het vlak”
en nog veel meer uit te drukken. Op deze manier kunnen we afspreken dat we iets alleen een verzameling noemen als het bestaat uit x-en met een eigenschap die in onze taal is uit te drukken. Dus
{x : x is een priemgetal}
is een verzameling (waarbij “x is een priemgetal” in de taal is geformuleerd). Dit komt vrij dicht in de buurt van Cantor’s definitie van verzameling: de accolades {} representeren de `Zusammenfassung zu einen Ganzen’, en we hebben `Annschauung’ en `Denken’ vervangen door `beschrijfbaar in de taal’.
De lege verzameling ∅ is uit te drukken door {x : x≠x} en telt dus mee als verzameling. Andere dingen leken iets dubieuzer, zoals {x : x=x}, de verzameling, V, van alle verzamelingen(?). Die gaf aanleiding tot een paradoxale toetand: Cantor had bewezen dat elke verzameling strikt minder elementen dan deelverzamelingen heeft (zie deze en de daarop volgende post voor de betekenis van meer en minder), maar voor deze V geldt dat niet, want elke deelverzameling is automatisch ook een element.
De oplossing, van Cantor, was onderscheid te maken tussen gewone en `oneigenlijke’ verzamelingen. En V was dus oneigenlijk; te groot om als gewone verzameling mee te tellen. Dat dit niet de schoonheidsprijs verdient lijkt me duidelijk want wie bepaald wat gewoon en oneigenlijk is?
Het kon nog erger: Bertrand Russell schreef de volgende verzameling, R, op: {x : x∉x}. Deze R leidt tot een wel heel eenvoudige paradox/tegenspraak, namelijk “$R∈R dan en slechts dan als R∉R”. Hier zijn geen diepe stellingen voor nodig; de afspraak hierboven was vanaf het begin al dubieus.
De uiteindelijke oplossing kwam van Ernst Zermelo. Deze formuleerde een een lijst axioma’s (spelregels) die we in acht moeten nemen als we met verzamelingen omgaan. Deze geven vooral aan hoe nieuwe verzamelingen uit oude gevormd kunnen/mogen worden. Die regels zijn redelijk natuurlijk; zo mogen we, gegeven twee verzamelingen x en y de verzameling {x,y} vormen.
Een van de belangrijkste regels is het Afscheidingsaxioma; dit zwakt onze eerste beschrijving wat af. Als x een gegeven verzameling is en φ is een formule in onze taal dat is {y:y∈x ∧ φ} weer een verzameling. Het verschil is dus dat we al een verzameling moeten hebben en daarbinnen elementen met een bepaalde eigenschap bijeen nemen.
Wat voor veel mensen in begin nog even wennen is is dat elk individu waar uitspraken over worden gedaan een verzameling is. Dus de elementen van verzamelingen zijn zelf ook weer verzamelingen enzovoort. Dat impliceert ook dat dingen als natuurlijke en reële getallen beschrijvingen krijgen die niet lijken op wat we gewend zijn maar dat went uiteindelijk wel.
Maar goed, dit leidt dan tot de volgnde definitie van verzameling: iets waarvan het bestaan uitgaande van de axioma’s te bewijzen is.
En wat dan allemaal uitgaande van die axioma’s mogelijk is kunt u in elk boek over Verzamelingenleer lezen en ook in het dictaat van de cursus Verzamelingenleer die ik zelf gegeven heb.
Recent Comments