KP Hart
De Gulden Onzin
Hier is weer wat flauwekul over de Gulden Snede.
Boekenplanken voor gevorderden
In dit vervolg op deze blogpost ga ik het hebben over het ordenen van boeken.
Bij de twitterdiscussie over of er verschil is, of niet, tussen boeken en getallen kwam ook de mogelijkheid getallen en boeken te ordenen ter sprake. Hierbij werd met `getal’ stilzwijgend `natuurlijk getal’ bedoeld. Nu komen natuurlijke getallen met een natuurlijke ordening, waarin elk getal een directe opvolger heeft en elk getal, behalve het eerste, een directe voorganger.
Hoe zit het met de boeken? Als je het met Marc eens bent dat een boek van vijf miljard pagina’s meer dan genoeg is zijn we gauw klaar.
Nee, ik denk dat het redelijk is om te zeggen dat een boek een bepaalde maximale omvang heeft: iets van vijf miljard pagina's is niet langer een boek, maar een serie boeken.
— Marc van Oostendorp (@fonolog) October 15, 2019
Als we het aantal bladzijden begrenzen en niet raar doen met onhandelbaar grote pagina’s en ook niet al te kleine letters gebruiken dan is, in een vaste alfabet, het aantal boeken eindig. Als we de letters, spaties, interpunctie etc van een vaste ordening voorzien kunnen we elk boek als een rij symbolen beschouwen en gewoon lexicografisch ordenen: als rij/boek A een echt beginstuk van rij/boek B is dan komt boek A voor boek B; anders kijken we naar de eerste plek waar A en B verschillen en gebruiken de ordening van de tekens om te beslissen welke van de twee eerst komt. Het resultaat is een rij boeken met een eerste en een laatste, waarin elk boek behalve het eerste een directe opvolger heeft, en elk boek behalve het laatste een directe voorganger.
En dit laat inderdaad een praktisch verschil zien tussen getallen en boeken: van de laatste zijn er maar eindig veel.
Oneindig veel boeken
Echter, …, de hele discussie begon met een artikel van Paul Postal, waarin het begrip boek wat ruimer werd opgevat: elke eindige rij symbolen is een potentieel boek.
Dan wordt het ordenen van de boeken een minder eenvoudige klus. Er was een heel specifieke vraag van Marc:
Maar boeken kun je toch ook ordenen? Bijvoorbeeld alfabetisch (op de hele tekst)? Dus na een boek dat eindigt op 'vrede op aardbei' komt een boek dat verder identiek is, maar eindigt op 'vrede op aarde'?
— Marc van Oostendorp (@fonolog) October 15, 2019
Het antwoord daarop is niet geheel flauw.
Lexicografisch
Je kunt je (potentiële) boeken nog steeds als hierboven lexicografisch ordenen. Dan is in ieder geval duidelijk dat het antwoord op de vraag van Marc bevestigend luidt: zijn twee boeken zijn geen beginstukken van elkaar en ze verschillen als eerste bij de positie van de b en de d, en de b komt voor de d. Er zitten natuurlijk nog zat boeken tussen die twee: aardbei komt voor aardbeienjam en dat komt voor aardappel hetwelk zelf weer voor aarde komt.
Het interessante, zeker voor wiskundigen, is dat tussen elk tweetal boeken oneindig veel (potentiële) boeken staan.
Tussen de nogal flauwe boeken (a) en (b) staan (ab), (aab), (aaab), (aaaab), … (een dalende rij boeken); tussen (ab) en (aab) kun je ook zoiets maken: (aba), (abab), (abaab), …
Dit is voor makers van boekeplanken nogal vervelend: de planken moeten overal oneindig lang zijn om al die oneindig veel tussenliggende boeken kwijt te kunnen.
Iets praktischer
Het kan praktischer (ook al door Marc opgemerkt in een commentaar op neerlandistiek.nl: sorteer de boeken eerst op lengte en orden ze bij vaste lengte weer gewoon lexicografisch. Dan heb je een eerste boek en elk ander boek heeft net als bij de natuurlijke getallen een directe voorganger en een directe opvolger. Dit is wel zo praktisch voor de timmerlieden: terwijl jij de planken vult kunnen zij gewoon vooruit werken.
Het verschil met hierboven is wel dat het aarde-boek van Marc vóóor het aardbei-boek komt: het eerste is één karakter korter dan het tweede.
Kleene-Brouwer
Tijdens de discussie noemde ik nog de Kleene-Brouwerorde; die lijkt op de lexicografische met dit verschil dat indien A een echt beginstuk van B is A juist achter B geplaatst wordt. Het tweede deel van de definitie blijft ongewijzigd. Dus (a) komt nog steeds voor (b), maar (aaa) komt voor (aa) en die weer voor (a).
Ook dit is een nachtmerrie voor boekenkastmakers: tussen elk tweetal boeken hebben we weer oneindig veel boeken. Het is zelfs een dubbele nachtmerrie: lexicografisch is er tenminste een eerste boek, bij Kleene-Brouwer hebben we dat niet eens; de timmerlieden moeten nu twee kanten op planken ophangen die overal oneindig veel boeken moeten kunnen hebben.
Voor mensen die werken in Beschrijvende Verzamelingenleer en in de Recursietheorie is de Kleene-Brouwerordening heel nuttig. Maar dat is weer een heel ander verhaal.
Boeken, getallen, stellingen
Vorige week ontspon zich een kleine discussie op Twitter over boeken en getallen; Marc van Oostendorp schreef Neerlandistiek.nl over een artikel van Paul Postal waarin de laatste over de aard, de ontologie, van boeken schrijft.
Boeken zijn als getallen. https://t.co/UPA1zENKqx
— Marc van Oostendorp (@fonolog) October 15, 2019
Ietwat kort door de bocht is de these van Postal dat een boek (hij gebruikte Pride and Prejudice als voorbeeld, Marc nam De Kleine Johannes als voorbeeld) als abstract object altijd al bestaan heeft, het is namelijk een rij symbolen (letters, spaties, interpunctie, …) en iemand heeft die rij een keer voor het eerst opgeschreven. Net als het getal gerepresenteerd door 7.987.923.892.274 (gezien de ene hit bij Google waarschijnlijk door Marc als eerste opgeschreven).
Voor het geval de ingebedde tweet hierboven niet goed werkt is hier een korte samenvatting van de discussie.
Mogelijke tegenwerping (Ionica Smeets): elk natuurlijk getal heeft een natuurlijke opvolger, hoe zit dat met boeken? Lijken boeken en stellingen niet meer op elkaar?
Antwoord (Marc): orden ze alfabetisch.
Ander argument (ik): dat werkt niet helemaal, als je alfabetisch wilt werken is Kleene-Brouwerorde beter, maar dan staan tussen elk tweetal boeken weer oneindig veel boeken (ik zag elke rij symbolen als een potentieel boek). Dit geldt overigens ook voor de normale Lexicografische orde van eindige rijen symbolen.
Antwoord (Marc): een boek van vijf miljard pagina’s is lang genoeg. Zou het verschil dan niet zijn dat er maar eindig veel boeken (kunnen) zijn?
Het laatste argument schuurt dan weer met de inhoud van het artikel van Postal (pagina 12): die laat willekeurig lange zinnen toe en concludeert dan dat er niet alleen oneindig veel boeken zijn maar zelfs overaftelbaar veel. Sterker nog: de boeken in een gegeven taal vormen niet eens een verzameling (volgens mij is dat laatste lariekoek maar daar hebben we het later nog wel eens over).
Is er wel verschil?
Je kunt op diverse niveau’s naar deze vraag kijken.
Representaties: rijen symbolen
Als het om opgeschreven verhalen en opgeschreven getallen gaat dan is er inderdaad geen echt verschil: beide bestaan uit rijen symbolen die hun betekenis prijsgeven als je volgens bepaalde regels (in dit geval op school aangeleerd) decodeert.
Bestonden die rijen symbolen ook al voor ze werden opgeschreven? En zo ja, hoe lang al?
Dat is een lastige vraag en waarschijnlijk voer voor lange filosofische discussies. Mijn mening: eigenlijk wel. In ieder geval sinds halverwege de negentiende eeuw (dat maakt het voor Pride and Prejudice wat onzeker): toen begon men namelijk functies als objecten te beschouwen en niet als `formules’ of `regels’. En Cantor nam, gegeven twee verzamelingen X en Y, de verzameling van alle functies van X naar Y ter hand om machtsverheffen van kardinaalgetallen te definiëren.
Als we dus voor een groot genoeg natuurlijk getal N alle functies nemen van {1,2,…,N} naar ons alfabet, aangevuld met spaties en interpunctiesymbolen, dan zit daar het verhaal van De Kleine Johannes (1884) dus ook in. In de tijd van Pride and Prejudice was de wiskunde nog niet zo ver en ik laat het aan de meer filosofisch ingestelden onder ons om te overdenken of dat boek er (ver) voor 1811 ook al was.
Het boek zelf; het getal zelf
Tot nu toe hebben we boek en getal vereenzelvigd met hun representaties. Bij een boek is dat bijna noodzakelijk. We kunnen het boek anders representeren, denk aan een lange rij nullen en enen in een e-reader, maar we hebben bij het lezen toch de oorspronkelijke rij symbolen nodig (tenzij iemand zich heeft aangeleerd de binaire code uit het hoofd te vertalen maar dat lijkt me vergezocht).
Bij een getal is dat niet zo. Neem het getal gegeven in decimale representatie als 1729 (decimale representatie) of als 6C1 (hexadecimaal) of als 11011000001 (binair). Deze representeren alledrie exact dezelfde hoeveelheid stippen, of hoop kogeltjes. En die hoop kogeltjes is de kleinste die op twee verschillende manieren in drie hoopjes verdeeld kan worden die dan elk als kubus gestapeld kunnen worden.
En Stellingen?
Ik was het in eerste instantie met Ionica eens maar nu twijfel ik. Ik vind achteraf dat stellingen dichter bij getallen liggen dan ik dacht. Een stelling heeft vele representaties maar de uiteindelijke betekenis is altijd dezelfde, net als elke representatie van een getal tot dezelfde hoeveelheid stippen, strepen, dropjes zal leiden.
Er is meer
In de tweets hadden we het ook over de mogelijkheid boeken en getallen te ordenen en het al dan niet bestaan van getallen.
Daar zal ik het in een latere post een keer over hebben.
KP checkt: Hartslag en de Gulden Snede
In deze blogpost beschreef ik een artikel waarin metingen aan mensenschedels moesten aantonen dat een aantal maten zich volgens de Gulden Snede zouden verhouden. De conclusies waren nogal discutabel maar ook al waren de getallen niet echt dicht bij de Gulden Snede ze leken tenminste te kloppen. In de referenties van het artikel vond ik veel verwijzingen naar andere voorkomens van de Gulden Snede. Twee daarvan heb ik nader bekeken: Golden Ratio is beating in our heart en Does systolic and diastolic blood pressure follow Golden Ratio. Daar kloppen de getallen iets minder goed.
Kloppende getallen
Wat bedoel ik met `kloppende getallen’? Welnu, als je een lengte, zeg A, in twee stukken verdeeld, zeg B en C, dan geldt natuurlijk A=B+C. Als je op jacht bent naar de Gulden Snede neem je de grootste van de twee stukken, zeg C, en dan bekijk je de verhoudingen A/C en C/B. Je hoopt dat die verhoudingen gelijk zijn want dan heb je de Gulden Snede te pakken.
Tussen die twee verhoudingen bestaat een relatie: deel de gelijkheid maar door C dan krijg je A/C=B/C+1, of iets ingewikkelder opgeschreven: A/C=1/(C/B)+1. Als we onze twee verhoudingen even afkorten, A/C=y en C/B=x, dan staat hier y=1/x+1.
Anders gezegd: het punt met coordinaten (C/B,A/C) ligt op de grafiek van y=1/x+1.
In het artikel Mammalian Skull Dimensions and the Golden Ratio worden de volgende gemiddelden van de verhoudingen gerapporteerd: A/C=1.64 ± 0.04) en C/B=1.57 ± 0.10 (de letters zijn anders, maar het gaat om de getallen).
Niet alleen het punt (1.57,1.64) ligt op de grafiek van y=1/x+1 maar ook de punten (1.47,1.68) en (1.67,1.60); deze worden bepaald door de randpunten van de intervallen (1.60,1.68) (voor A/C) en (1.47,1.67) (voor (C/B). Zie het plaatje hieronder.
Dit bedoel ik met kloppende getallen: de resultaten horen in ieder geval bij de stituatie waar A=B+C.
Overigens laat ik het aan de lezer om te beoordelen, gezien dit plaatje, in hoeverre deze conclusie gerechtvaardigd is:
In humans, the ratio of the nasioiniac arc over the parieto-occipital arc (NI/BI = 1.64 ± 0.04) and the ratio of the parieto-occipital arc over the frontal arc (BI/NB = 1.57 ± 0.10) are essentially identical and closely approximate Φ (1.618) within 1 standard deviation.
Het snijpunt van de twee grafieken (y=1/x+1 en y=x) is het punt (Φ,Φ), en daar ligt (1.57,1.64) toch nog wel ver vandaan.
Hartslag en bloeddruk
In de referenties van het schedelartikel vond ik de artikelen die hierboven genoemd werden.
Hartslag
Om te beginnen: in Golden Ratio is beating in our heart wordt de Gulden Snede ontdekt in verhoudingen van tijdsintervallen in de hartslag. Een mooi plaatje met een uitleg van alle termen staat op de wikipedia-pagina over het QRS-complex:
De drie grootheden waar het hier om gaat zijn: (A) het R-R-interval (tussen twee opeenvolgende R-en), (B) de systole (samentrekfase), en (C) de diastole (ontspanningfase).
De letters komen overeen met onze eerste paragraaf en met de verhoudingen waar het artikel over gaat.
De resultaten zijn
- A=866 ± 73
- B=333 ± 22
- C=536 ± 66
- C/B=1.611
- A/C=1.618
Deze getallen zijn problematisch.
Ten eerste tellen de gemiddelde waarden niet goed op: A=866 en B+C=869. Dat zou wel moeten als alle metingen goed waren dan geldt A=B+C voor elke meting en dan ook voor de gemiddelden.
Ten tweede: als een van de verhoudingen gelijk is aan Φ dan is de andere dat ook, hier is dat niet zo.
Ten derde: als je, net als in het schedelmetingartikel, de verhoudingen van de gemiddelden neemt kom je op andere getallen uit: 866/536=1.61567 en 536/333=1.6096.
Het zou kunnen zijn dat de gerapporteerde verhoudingen gemiddelden zijn van de verhoudingen per meting maar dan hadden de auteurs dat wel even mogen vermelden.
Voorlopig geloof ik niets van de conclusies van het artikel.
Het lijkt er op dat de individuele verhoudingen wel zijn uitgerekend want het artikel bevat nog een niet-ter-zake-doende grafiek waarin de verhouding C/B is uitgezet tegen de hartslag.
Daar is in ieder geval te zien dat de verhouding C/B behoorlijk variabel is.
Bloeddruk
In het artikel Does systolic and diastolic blood pressure follow Golden Ratio gaat het om de bloeddruk. De grootheden zijn nu: (A) de systolische druk (bovendruk), (C) de diastolische druk (onderdruk), en (B) hun verschil; alle in mm Hg.
| A | C | B | A/C=y | C/B=x | |
|---|---|---|---|---|---|
| etmaal | 137 ± 16 | 86 ± 12 | 51 | 1.59 | 1.69 |
| dag | 140 ± 17 | 89 ± 12 | 51 | 1.57 | 1.75 |
| nacht | 131 ± 18 | 80 ± 13 | 51 | 1.64 | 1.62 |
Wat hier opvalt is dat er voor het verschil geen interval is opgegeven; alsof het bij alle metingen precies 51 mm Hg was (dat geloof ik dus niet). De verhoudingen komen hier wel voort uit de gemiddelden behalve de verhouding C/B in de nacht: 80/51=1.56862. Laat die foute 1.62 nou net de verhoding zijn die het dichtst bij de Gulden Snede ligt.
Ik heb de punten vergeleken met de grafiek van y=1/x+1.
De twee punten rechts horen bij de verhoudingen voor een etmaal en overdag. Het meest linkse punt hoort bij de echte nachtelijke verhoudingen. Het punt dat ruim boven de grafiek ligt hoort bij de gerapporteerde nachtelijke verhoudingen. Ik heb geen idee hoe dat gebeurd kan zijn.
Daar is-tie weer: de Gulden Snede
Niet uit te roeien, die Gulden Snede: via een stukje op Science Alert kwam ik hier: Mammalian Skull Dimensions and the Golden Ratio.
Wat staat er in dat artikel?
Welnu over je schedel loopt een lijn, van het Nasion (N) naar het Inion (I); op die lijn ligt een punt het Bregma (B) geheten. Op honderd mensenschedels zijn de lengten NI, NB en BI gemeten (niet letterlijk, er is gemeten aan hoge-resolutiescans van schedels). Nu geldt, natuurlijk, NB+BI=NI en verder is het deel BI wat groter dan het deel NB.
Op zoek naar de Gulden Snede hebben de auteurs van elke schedel de verhoudingen NI/BI en BI/NB bepaald. Als B de lijn NI inderdaad volgens uiterste en middelste reden verdeelt, dan verwachten we dat NI/BI gelijk is aan BI/NB.
Na middelen en standaard-deviatie nemen komen de auteurs uit op NI/BI = 1.64 ± 0.04 en BI/NB = 1.57 ± 0.10. In de woorden van de auteurs:
In humans, the ratio of the nasioiniac arc over the parieto-occipital arc (NI/BI = 1.64 ± 0.04) and the ratio of the parieto-occipital arc over the frontal arc (BI/NB = 1.57 ± 0.10) are essentially identical and closely approximate Φ (1.618) within 1 standard deviation.
Ik weet niet wat de lezer denkt maar in vind dat een krasse uitspraak. De gemiddelden liggen nogal ver uit elkaar. Of je nu vanuit 1.64 of vanuit 1.57 rekent, het verschil is relatief meer dan 4%. Dat lijkt me niet `essentially identical’. Ik denk dat de wens hier toch de vader van de gedachte is geweest.
Overigens zijn de opgegeven waarden wel consistent met de betrekking die tussen de verhoudingen moet gelden: door de gelijkheid NB+BI=NI door BI te delen ontstaat de gelijkheid NI/BI = 1/(BI/NB)+1. Om dit iets overzichtelijker te maken noemen we NI/BI even y en BI/NB even x, de gelijkheid wordt dan y=1+1/x. De punten (1.57,1.64), (1.47,1.68) en (1.67,1.60) liggen op een haar na op de grafiek van deze vergelijking.
Deze betrekking verklaart ook de volgende observatie van de auteurs:
Interestingly, the reciprocal of Φ (1/Φ or 1/1.61803…) is 1 integer less than Φ (0.61803…) and has the same decimal extension as Φ, and the square of Φ (Φ² or 1.61803…2) is 1 integer more than Φ (2.61803…) and also has the same decimal extension.
Uhm, ja, nogal wiedes; de verdeling in uiterste en middelste reden dicteert dat Φ aan de gelijkheid Φ=1+1/Φ moet voldoen, en dus ook aan Φ²=Φ+1. Iedere middelbare-scholier die kwadratische functies heeft gezien kan je dit uitleggen.
Ten slotte
Het artikel beslaat negen kolommen; daarvan zijn er vier gevuld met een verslag van de metingen; er is ook aan zes andere zoogdiersoorten gemeten en het lijkt er op dat bij toenemende `complexiteit’ van de soort de verhouding NI/BI daalt en BI/BN dus daalt. De (speculatieve) uitleg is dat gaande de evolutie de schedel op deze manier bij bepaalde kwabben is gaan passen.
Als de auteurs zich nu maar bij deze conclusie hadden gehouden dan was er weing mis geweest met dit artikel. De overige vijf kolommen zijn echter gevuld met niet ter zake doende beschrijvingen van de Gulden Snede, de relatie met de rij van Fibonacci, en het vermeende optreden van dit getal bij allerlei fysiologische en morphologische verschijnselen.
Allerlei al lang onderuit gehaalde mythes over de Gulden Snede worden weer van stal gehaald en als belangwekkende feiten gepresenteerd.
In het fraaie boek De Ontstelling van Pythagoras heeft Albert van der Schoot vrijwel niets heel gelaten van alle flauwekul die over de Gulden Snede verteld wordt. De recensie in NRC noemt er al een paar. En lees ook het artikel Het is niet alles goud wat er snijdt van Van der Schoot in het Nieuw Archief voor Wiskunde.
Ook deze column van Keith Devlin is het lezen meer dan waard.
Metaforen? Liever definities.
Bij uitleg van niet-triviale wiskundige resultaten grijpt men nogal vaak naar een of andere metafoor, waarschijnlijk omdat de echte context te moeilijk voor de lezer wordt gevonden. Dat leidt vrijwel altijd tot onbegrip of erger nog tot slecht begrip. Een extreem voorbeeld was onlangs te vinden in NewScientist.
In bovenvermeld stuk werd melding gemaakt van een, ook voor de gemiddelde wiskundige, niet-triviaal resultaat — de formulering was in de vorm van een metafoor over een oneindige versie van de lotto. Die was zo onduidelijk dat ik aan het eind van het stuk nog steeds niet wist niet wat het wiskundige resultaat was (of zelfs waar het over ging); pas na doorklikken naar het echte artikel herkende ik het als iets dat ik in april al voorbij had zien komen. De reacties onder het stuk laten zien dat er meer lezers waren die niet begrepen hadden waar het over ging.
Nadat ik mijn blogposts (deze en deze) op facebook had gezet schreef een collega dat de opsteller van het oorspronkelijke probleem (Adrian Mathias) zelf de lotto-metafoor had verzonnen.
Het probleem van het stuk in NewScientist (en het het origineel) was ook nog dat de uitleg niet volledig was: het was niet duidelijk hoe de lottoformulieren in te vullen en er werd al helemaal niet vermeld hoe je zou kunnen winnen.
Ik heb zelf maar een lotto verzonnen en aan twitter gevraagd welke uitleg beter was: zakelijk of metaforisch.
Welke uitleg is beter
— (((K P Hart))) (@hartkp) September 20, 2019
De uitslag was overweldigend: 100% vond de zakelijke uitleg beter. Ik geef toe: drie stemmen is niet veel, maar er moest dan ook wel veel gelezen worden.
Het wiskundige resultaat ging over families oneindige deelverzamelingen van de verzamelingen der natuurlijke getallen. In deze blogpost staat meer informatie; het kost waarschijnlijk enige moeite alles te verstouwen maar ik heb de illusie dat heze uitleg beter is dan een gekunstelt verhaal over de lotto.
Het oneindige fascineert velen, dat is zelfs te zien geweest in de Nationale Wetenschapsagenda. Veel vragen gingen eigenlijk over de metaforen die gebruikt zijn om `oneindig’ uit te leggen en hadden dus eigenlijk in het geheel geen wiskundige inhoud. En dat vind ik dus jammer. De wiskunde van het oneindige is te mooi om in verhullende verhalen te verstoppen. Wie mij over oneindig wil laten praten krijgt de definities om de oren (en het helpt als je vantevoren deze wikipediapagina goed bestudeert.
U bent gewaarschuwd.
Strictly between
This is the third in a short series of blog posts intended to explain the terms in red in the following sentence, that succinctly describes the Continuum Hypothesis.
There is no set whose cardinality is strictly between that of the integers and the real numbers.
These are, in the words of John Lloyd, the bits that he does not understand.
Thus far we have dealt with set in this post and this one, and with the notion of cardinality in this one.
To recap our findings: we first came to the disappointing realisation that the definitions proposed by Georg Cantor, very strictly speaking, did not deliver on their promises. There is a way out of this via the development of Axiomatic Set Theory but that would take us too far afield.
In the spirit of Cantor we can define a set to be a well-defined collection of objects as long as we furnish a good description/definition of that collection.
As to cardinality: we consider it a property that every set has and that leads to two derived properties of pairs of sets that are defined unambiguously.
Two sets, X and Y, are said to have the same cardinality if “it is possible to put them, by some law, in such a relation to one another that to every element of each one of them corresponds one and only one element of the other” (Cantor, translation by Jourdain). We simply abbreviate this as |X|=|Y|. Additionally we can define what |X|≤|Y| (“the cardinality of X is less than or equal to that of Y”) means that there is a subset Z of Y such that |X|=|Z| (“X has the same cardinality as some subset of Y”).
In this post there are some examples of sets with the same cardinality (provinces of the Netherlands, and months of the year) and with different cardinalities (two teaspoons of chocolate sprinkles).
It is now actually quite straightforward to come to the definition of strictly between. First we define `strictly less’; then `strictly between’ is a combination of twice `strictly less’.
In the example of the chocolate sprinkles the cardinality of the sprinkles in the left hand spoon was strictly less that the cardinality on the right hand side. I paired off the sprinkles on the left with a subset of the sprinkles on the right and it was at once clear that there was no way to pair off both sets with each other. In short, we saw that |L|≤|R| and that |L|≠|R|. And this will be our definition of “the cardinality of X is strictly less than that of Y”, in symbols |X|<|Y|: it is the conjuction of |X|≤|Y| and |X|≠|Y|.
Cantor’s seminal theorem from 1873 can be summarized as |N|<|R|, where N and R denote the sets of natural and real numbers respectively (more on the definition of these in later posts).
Since N is a subset of R it is clear that |N|≤|R|; the hard part of Cantor’s proof was to show that |N|≠|R|, i.e., that there is no way to pair off the natural numbers and the real numbers with each other.
So “the cardinality of Y is strictly between the cardinalities of X and Z” is the conjuction of |X|<|Y| and |Y|<|Z| and ultimately comes down to the following four statements:
- X can be put into one-to-one correspondentce with a subset of Y,
- Y can be put into one-to-one correspondentce with a subset of Z,
- X cannot be put into one-to-one correspondentce with Y, and
- Y cannot be put into one-to-one correspondentce with Z
For explicitly given sets it is often not too difficult to establish whether this state of affairs holds or not; certainly not with all the tools that Cantor and his followers have developed.
In the case of the Continuum Hypothesis matters lie differently: two of the three sets are there; one should produce the third in the middle, or show that no third exists. At the beginning of the 20th century either possibility probably seemed like an insurmountable task, although Cantor strongly believed in the second alternative.
Loterijen? Eerder de Lotto.
Gisteren, in het stuk over bijna-disjuncte families, heb ik het niet over de loterijen gehad waar het in stuk in NewScientist over ging. Sommige mensen waren benieuwd naar die metafoor voor het resultaat in het artikel van David Schrittesser en Asger Törnquist. Ik doe hier een poging zo’n loterij te beschrijven. Ik laat het aan de lezer om te beoordelen welke uitleg beter is: de feitelijke in de vorige post of de metaforische hieronder.
Om te beginnen: `loterij’ is eigenlijk een verkeerde vertaling van het Amerikaanse `lottery’. Bij een loterij koop je een lot en weet je niet wat je lotnummer zal zijn. In een lottery kies je zelf de getallen op je kaartje. Het is dus eerder te vergelijken met onze Lotto. De beschrijving van de `loterij’ in NewScientist is ook eerder die van een variant op de Lotto dan op de Staatsloterij.
Een oneindige variant op de Lotto
In plaats van 6 uit 45 kiezen we getallen uit N. Met de betekenis van het woord `bijna’ van gisteren in gedachten leggen we vast dat we niet `bijna niets’ en ook niet `bijna alles’ mogen kiezen: we moeten er oneindig veel kiezen (aankruisen) en we moeten er oneindig veel niet aankruisen.
Een `formulier’ heeft dus oneindig lange kolommen (net zo lang als N) en oneindig veel kolommen. Je mag dus, kennelijk, oneindig veel kolommen invullen. Wat in het stuk niet duidelijk vermeld wordt is hoe je een prijs kunt winnen.
Maar met het artikel in de hand kunnen we wel wat regels opstellen. Het artikel bewijst namelijk dat oneindige maximale bijna-disjuncte families niet bestaan (dat `oneindige’ heb ik gisteren voor het gemak weggelaten maar dat wordt nu belangrijk); het stukje zegt dat er geen winnende formulieren bestaan. Conclusie: een (zeker) winnend formulier heeft in de kolommen een oneindige maximale bijna-disjuncte familie.
Daaruit concluderen we dan dat een winnende kolom een oneindige doorsnede heeft met de getrokken deelverzameling van N.
We halen hier ook nog wat voorwaarden uit waaraan een geldig formulier aan moet voldoen: niet alleen mag je in één kolom niet bijna alle getallen aankruisen, ook mag je er niet voor zorgen dat je over een eindig aantal kolommen bijna alle getallen aankruist. Als je bijvoorbeeld over tien kolommen achtereenvolgens de tienvouden, tienvouden-plus-1, … tienvouden-plus-9 aankruist win je ook zeker; die tien verzamelingen vormen een eindige maximale bijna-disjuncte familie.
Samengevat: op je formulier kruis je in een aantal kolommen telkens oneindig veel getallen aan. Dat aantal kolommen mag eindig zijn maar hoe dan ook: in elke eindige greep kolommen mag je nooit samen bijna alle getallen aankruisen. Je wint als je in ten minste één kolom oneindig veel getrokken getallen hebt aangekruist.
Door je kolommen bijna-disjunct in te vullen spreid je je inzet het zuinigst; twee kolommen met een oneindige doorsnede hebben een grote overlap aan mogelijkheden. Ten slotte: als je kolommen een maximale bijna-disjuncte familie vormen dan bevat je formulier, per definitie, een winnende kolom.
Het bestaan van (zuinige) winnende formulieren
Het stuk in NewScientist vertelt niet de hele waarheid. De suggestie wordt gewekt dat winnende formulieren niet bestaan. Dat is slechts voor de helft waar. Je kunt bewijzen dat zeker winnende en zuinige formulieren bestaan, met behulp van het Lemma van Zorn (een equivalent van het Keuzeaxioma).
Sommige wiskundigen vragen zich in dit soort situaties af of het Lemma van Zorn wel nodig is bij zo’n concrete vraag; dat Lemma levert namelijk nogal zwaar geschut. En dat is nu wat David Schrittesser en Asger Törnquist hebben vastgesteld: je hebt zwaar geschut nodig; er is bestaat een situatie waarin dat zware geschut niet voorhanden is en waarin geen enkele maximale bijna-disjuncte familie bestaat.
Loterijen? Nou, nee.
Vanochtend (2019-09-19) vond ik via twitter dit artikel uit NewScientist (een vrij letterlijke vertaling van dit stuk. Nadat ik het verhaal over niet-bestaande oneindige loterijen had gelezen was ik nog niets wijzer geworden. Na doorklikken naar het originele artikel zag ik dat ik het al eerder had gezien in april, op ArXiV.org en dat het niets met loterijen te maken had.
Maar waar gaat het artikel dan wel over? Over bijna-disjuncte families. En wat zijn dat nu weer?
Eén van mijn favoriete objecten in de verzamelingenleer is de familie van alle deelverzamelingen van de verzameling N der natuurlijke getallen. Dit is een nimmer opdrogende bron van vragen en resultaten die in veel delen van de wiskunde gebruikt worden maar die gewoon ook leuk zijn om aan te werken.
Hierbij is het bijwoord `bijna’ bijna niet te vermijden. In het artikel waar we het hier over hebben past men `bijna’ dus toe op `disjunct’. Nu noemen we twee verzamelingen A en B `disjunct’ als hun doorsnede leeg is, A∩B=∅, als er geen x is die zowel in A als in B zit.
Het woord `bijna’ kort eigenlijk het wat uitgebreidere `op eindig veel na’ af: twee verzamelingen zijn bijna disjunct als hun doorsnede eindig is — `hun doorsnede is op eindig veel elementen na leeg’. Hierbij eisen we wel dat de verzamelingen zelf oneindig zijn want anders is bijna-disjunctheid niet zo spannend.
De twee verzamelingen E en O van respectievelijk de even en oneven getallen zijn disjunct; er is geen natuurlijk getal van tegelijk even en oneven is.
Hier is een mooie truc, van Sierpinski uit 1928: voor elk positief irrationaal getal x en voor elk natuurlijk getal n doen we het volgende: bepaal n×x, neem het gehele deel [n×x] (gooi alles achter de komma weg) en deel dat weer door n.
Bij vaste x krijg je zo een rij rationale getallen: [x], [2x]/2, [3x]/3, [4x]/4, … Bij π bijvoorbeeld krijgen we zo 3, 3, 3, 3, 3, 3, 3, 25/8, 28/9, 31/10, 34/11, 37/12, …
Uit de definitie van de rij volgt dat 0<x-[n×x]/n<1/n voor alle n en dit betekent iets voor de bijbehorende verzamelingen termen. Bij elke x stoppen we de termen van de rij in de verzameling Sx, dus Sπ={3, 25/8, 28/9, 31/10, 34/11, 37/12, …}.
Neem nu eens twee irrationale getallen x en y met x<y; dan geldt voor n>1/(y-x) dat [n×y]/n>y-1/n>x, en dus zit [n×y]/n niet in Sx. We concluderen dat de verzamelingen Sx en Sy bijna disjunct zijn.
De verzamelingen Sx vormen het soort familie waar het artikel over gaat: een bijna-disjuncte familie, elk tweetal elementen is bijna disjunct (en elke Sx heeft oneindig veel elementen).
Het voorbeeld van Sierpinski laat zien dat er een groot verschil is tussen `disjunct’ en `bijna disjunct’. Als een familie disjunct is dan zit elk punt in ten hoogste één element van de familie. De bijna-disjuncte familie van Sierpinski bestaat uit verzamelingen rationale getallen, daar zijn er evenveel van als natuurlijke getallen. De familie zelf heeft evenveel elementen als er positieve irrationale getallen en dat zijn er veel en veel meer als er natuurlijke getallen zijn (en dat is allemaal precies te maken). Dat zorgt er voor dat veel van de rationale getallen in meer dan één verzameling Sx zitten.
Maar goed, terug naar het artikel. Het hoofdresultaat zegt iets over de aard van bijna-disjuncte families deelverzamelingen van N: onder bepaalde omstandigheden is er geen maximale bijna-disjuncte familie. Als je zo’n familie hebt kun je er een oneindige deelverzameling van N bij doen zó dat de grotere familie ook bijna-disjunct is (en nog één, en nog één, …).
Wat dit nou met loterijen te maken heeft? Ik zou willen zeggen dat ik geen idee heb maar dat heb ik wel. Ik vind de vergelijking echter zó vergezocht dat ik de lezer er niet mee lastig wil vallen. En ik denk eigenlijk dat de uitleg van die vergelijking lastiger is dan die van het resultaat zelf.
Birthday Paradox on steroids.
Most of us are familiar with the so-called Birthday Paradox: the probability in a group of 23 people there are (at least) two who share a birthday is larger than 50%. If you are not familiar with this result then you could peek at the calculation on the Wikipedia page or try it for yourself (big hint calculate the probability that no two people in the group share a birthday).
In Act One of Episode 630 of This American Life we see another take on this phenomenon. It occurs in the context of voter fraud, in particular double voting. In this case, a bit simplified, one looks at the probability that in the group of American Voters two of them would have the same name and the same birthday (including the year).
Listen to the episode to see that basically all cases of `double voting’ can be accounted for by chance alone. And then you may want to read the paper on which the item was based, and visit the website of Sharad Goel (who was featured in the broadcast).
Recent Comments