Posts in category verzamelingen
Lariekoek? II
We gaan het artikel Sets and Sentences van D. Terrence Langendoen en Paul Postal opnieuw lezen. De vorige keer heb ik de inhoud beschreven; nu bekijken we die nogmaals, maar met een wiskundig oog.
Zoals vorige keer beschreven gaat het er in het artikel om te laten zien dat in een Natuurlijke Taal de mogelijke zinnen een zeer grote collectie vormen: te groot om `verzameling’ genoemd te mogen worden. We volgen de redenering stap voor stap.
De definitie van Co-ordinate compound constituent is vorige keer al schematisch weergegeven door het volgende plaatje:
De top T is hier de co-ordinate compound constituent en de andere knopen zijn de conjucten waar T uit gevormd is. Die conjuncten bestaan uit een connectief en `constituent’. Ietwat simplistisch: T ontstaat door de constituents door middel van connectieven aan elkaar te plakken.
In punt (6) van het artikel wordt gedetailleerd beschreven hoe dat plakken in zijjn werk moet gaan, of preciezer: er wordt geformuleerd wat de relatie tussen de verzameling U van constituents en de compound T moet zijn. Uit die formulering zou je een plakmethode kunnen distilleren. Van punt (6) citeer ik deelpunt (d)
if two elements of U occur as subconjuncts of conjuncts C1 and C2 of T then C1 and C2 occur in a fixed order. Where C1 and C2 are of distinct length assume the shorter precedes; where C1 and C2 are the same length, assume some arbitrary order.
Als een student zoiets opschrijft trek ik mijn rode pen: ten eerste om het gebruik van `fixed’ en `arbitrary’ vlak achter elkaar, en ten tweede om dat `arbitrary’. Dat lees ik als “doe maar wat” en daar schrijf ik dus “Hoe dan?” bij. Ik kom straks nog op dit punt terug.
Verder in punt (6) wordt T een `co-ordinate projection’ van U genoemd en U de `projection set’ van U. Inderdaad: U is door T uniek bepaald maar niet andersom; het woord `arbitrary’ lijkt daar op te duiden.
Dan volgt een alinea waarin wordt beargumenteerd dat elke verzameling U een co-ordinate projection heeft. Dit zou `straightforward’ moeten zijn, volgens de schrijvers althans. Hier zijn de stappen (de `category Q’ die ter sprake komt is een niet nader gespecificeerde abstracte categorie van zinnen):
- Neem een verzameling U en laat k de kardinaliteit van U zijn (eindig of oneindig)
- Citaat:
Clearly, from the purely formal point of view, there is a co-ordinate compound W belonging to the category Q.
Dat klinkt mooi maar het heeft geen enkele bewijskracht; geen enkele rechtvaardiging, geen indicatie waar die W vandaan zou moeten komen. - Citaat:
Since there are no size restrictions on co-ordinate compounds, W can have any number, finite (more than one) or transfinite of immediate constituents.
Dit is slechte (wiskundige) stijl: eerst lijkt W vast, dan gaat hij alsnog variëren. Een betere formulering zou zijn: “er zijn co-ordinate compounds van alle mogelijke kardinaliteiten”. Die betere formulering maakt de bewering niet automatisch waar, er is nog steeds geen concrete rechtvaardiging gegeven. - Citaat:
W can then, in particular have exactly k such constituents.
Nogmaals: die vaste W is omgevormd tot een gepaste W. Niet mooi, maar vooruit dan maar. - De deelconjuncts van de conjuncts in W vormen een verzameling V die, volgens de regels in (6), kardinaliteit k heeft. Niks mis mee.
- Citaat:
To show that W is a co-ordinate projection of U, it then in effect suffices that there exist a one-to-one mapping from U to V.
Niet dus. Hoe je definitie (6) ook wendt of keert, dit haal je er niet uit. Wil W een co-ordinate projection van U zijn dan zal de verzameling V exact gelijk aan de verzameling U moeten zijn; een bijectieve afbeelding tussen die twee is echt niet genoeg. - Citaat:
But this is trivial, since the two sets have the same number of elements.
Dit klopt, maar ik verdenk de schrijvers ervan dat ze niet doorhebben wat hier achter zit. Georg Cantor definieerde `kardinaliteit’ op een manier die eigenlijk nietszeggend is, zie de tweede post in deze serie. Hij bewees daarna dat `hebben gelijke kardinaliteit’ equivalent is met `er bestaat een bijectieve afbeelding tussen’, maar tegenwoordig is dat laatste de definitie van het eerste.
Afsluiting
In het artikel formuleren Langendoen en Postal nu een afsluitingsprincipe. Na een waarschuwing dat niet elke co-ordinate projection noodzakelijkerwijs welgevormd is komt het volgende Closure Principle for Co-ordinate Compounding:
If U is a set of constituents each belonging to the collection, Sw, of (well-formed) constituents of category Q of any natural language, then Sw contains the co-ordinate projection of U.
Hoezo “the co-ordinate projection”? Uniciteit van die projecties is nog niet aan de orde geweest en over die collectie Sw is niet (expliciet) gezegd dat elke verzameling zinnen maar op één manier tot een grotere zin samen te voegen is.
Na een opmerking over het recursieve karakter van dit principe noemen de schrijvers de categorie S van zinnen als een categorie waarop het principe van toepassing is, althans: ze beweren dat (maar geven geen bewijs).
Dat weerhoudt ze er niet van het principe twee keer uit te spreken voor S. Eerst via een bijna letterlijke herhaling, met Q vervangen door S, en dan nog een keer met behulp van een formule(!): the co-ordinate projection van een verzameling U noteren we CP(U) en dan krijgen we
(∀U)(U⊂L → CP(U)∈L)
Hierin is L de collectie van alle elementen van de categorie S van een natuurlijke taal (voor mij betekent dat L=S want L en S hebben dezelfde elementen, maar er is misschien een subtiel verschil tussen de collectie van elementen van een categorie en de categorie zelf). Merk op dat hier het onbepaalde lidwoord definitief bepaald geworden is. Zonder het expliciet uit te spreken hebben de schrijvers kennelijk besloten dat compounding maar op één manier kan; de functienotatie CP(U) kan niet anders geïnterpreteerd worden.
Maar hoe is CP(U) gedefinieerd dan? Dat wordt niet duidelijk; een illustratie met met verzamelingen van drie, vier zinnen die tot één worden samengevoegd overtuigt mij niet.
Een soort van hierarchie
Dan komt eindelijk datgene waar ik al lang op zat te wachten: The Cantorian Analogue, waarin bewezen gaat worden dat de zinnen in een natuurlijke taal geen verzameling vormen. Overigens, een definitie van `verzameling’ hebben we nog niet echt gehad.
Het bewijs gaat aanvankelijk met gebruik van een verzameling zinnen als in de vorige post, de schrijvers gebruiken {Babar is happy; I know that Babar is happy; I know that I know that Babar is happy, …}. Die verzameling noemen ze S0.
Ik kort de zinnen even af: z0 is “Babar is happy” en, gegeven zn is zn+1 de zin “I know that zn“.
Onder de aanname dat de natuurlijke taal L aan het afsluitingsprincipe voldoet omvat L ook de verzameling S1 die bestaat uit S0 en de co-ordinate projections van de deelverzamelingen van S0 met twee of meer elementen. De formulering verdient het nauwkeurig gelezen te worden.
Then L also contains a set S1, made up of all the sentences of S0 together with all and only the co-ordinate projections of every subset of S0 with at least two elemente, that is, with a set containing one co-ordinate projection for each member of the power set of S0 whose cardinality is at least 2.
Deze zin deugt niet. De delen voor en na `that is’ spreken elkaar tegen. De eerste versie van S1 bevat alle co-ordinate projections van alle deelverzamelingen van S0 — de projecties van iedere deelverzameling —; de tweede versie bevat van elke deelverzameling (precies) één projectie. Daarnaast is de eerste versie uniek bepaald door het `all and only’, daar is `the set S1‘ dus meer op zijn plaats; in het tweede deel past `a set’ wel.
Je zou het meervoud `projections’ enkelvoud kunnen maken; dat sluit wat beter aan bij de formulering van de afsluitingeigenschap, the projection zou dan telkens de functiewaarde CP(U) kunnen zijn. Maar dan gaat het ook mis: vóór het `that is’ is de keuze van projectie duidelijk vastgelegd, maar na `that is’ zit er nog potentiële willekeur in de keuze van projectie, er staat niet expliciet dat die one projection ook echt CP(U) is.
De schrijvers geven dan een voorbeeld van hoe S1 er uit zou kunnen zien (dus toch geen welbepaalde verzameling):
{z0; z1; z2; …; z0 and z1; z0 and z2; …; z0, z1, and z2 …} (voor alle duidelijkheid: de punt-komma’s scheiden de zinnen en de komma’s dienen als connectieven in de zinnen).
Dan volgt een lange alinea waarin met veel omhaal van woorden de kardinaliteit van S1 wordt bepaald. Door het `één projectie per verzameling’ is dat niet moeilijk: dat is dezelfde kardinaliteit als die van de familie van alle deelverzamelingen van S0 en omdat S0 aftelbaar oneindig is, en dus kardinaliteit ℵ0 (alef-nul) heeft is die kardinaliteit gelijk aan 2ℵ0 (2-tot-de-macht-alef-nul) en niet ℵ1, zoals Langendoen en Postal opschrijven. Ergens bij hun bestudering van de verzamelingenleer is er iets misgegaan en is de Continuümhypothese waar geworden.
Zoals wellicht verwacht wordt dit proces voortgezet. Er komt een rij verzamelingen S0, S1, S2, …, netjes recursief gedefinieerd door Sn+1=Sn∪Kn. Hierbij is Kn telkens de verzameling projecties van deelverzamelingen van Sn. In formule
Kn={x:(∃y)(y⊆Sn ∧ x is the co-ordinate projection of y)}
Hier had dus ook Kn={x:(∃y)(y⊆Sn ∧ x=CP(y))} kunnen staan.
Op deze manier komt er een hierarchie van verzamelingen zinnen tot stand; die zinnen worden steeds complexer en de verzamelingen steeds groter. De schrijvers claimen onterecht dat voor elke n het kardinaalgetal van Sn gelijk is aan ℵn. De juiste formule is een machtsverheffing met een torentje van n tweeën, met bovenaan nog een ℵ0. Dat kardinaalgetal noteren we in de verzamelingenleer als ℶn (beth-n).
Dit verhaal culmineert in wat de schrijvers The NL Vastness Theorem noemen: Natural Languages are not sets.
Het bewijs verloopt uit het ongerijmde. Neem aan dat L een verzameling is. Het proces van co-ordinate projection definieert een injectieve afbeelding van de machtsverzameling van L naar L zelf. Dat kan niet volgens een stelling van Cantor: elke verzameling heeft strikt meer deelverzamelingen dan elementen. Tegenspraak.
Er is echter een groot MAAR, en daar gaan we het nu over hebben.
Ordeningen en lengten
Het `bewijs’ in het artikel staat vol met impliciete aannamen over het gedrag van verzamelingen die een niet-wiskundige waarschijnlijk niet zo snel zullen opvallen. Er zijn twee dingen die nogal schadelijk zijn voor de redenering zoals hierboven beschreven.
Ten eerste de ordening, ik heb er bij de beschrijving van de co-ordinate projection al op gezinspeeld: daar zit, op zijn zachtst gezegd, een onvolledigheid.
Die onvolledigheid duikt op bij de overgang van S1 naar S2, en nog erger bij de stap daarna van S2 naar S3.
Bij de eerste stap, van S0 naar S1, is er niets aan de hand: we hebben onze verzameling S0 genummerd en die nummering ordent elke deelverzameling van S0, waarmee zo’n deelverzameling een natuurlijke projectie heeft, ook als deze oneindig veel elementen heeft. Dit levert natuurlijk wel zinnen zonder einde op.
Daarna, van S1 naar S2, hebben we een probleem: er zijn (overaftelbaar) veel zinnen van oneindige lengte (allemaal even lang als de verzameling der natuurlijke getallen). Daar gaat het `fixed’ en `arbitrary’ van punt (6)(d) dus wringen. Hoe orden je zo’n verzameling zinnen? De heren Langendoen en Postal spreken zich daar niet over uit.
Gelukkig kunnen we hier de lexicografische ordening gebruiken: kijk naar het eerste teken (inclusief spaties) waar de zinnen verschillen en neem een besluit op basis van de ordening van de tekens. Zie ook de post Boekenplanken voor gevorderden waar een aspect van die ordening aan de orde komt dat hier de zaak ook compliceert: er zijn heel veel verzamelingen die de eigenschap hebben dat tussen elk tweetal zinnen oneindig veel zinnen staan en die ook geen eerste zin hebben. Als we die ordening gebruiken om projecties te maken dan krijgen we dus zinnen zonder begin, zonder einde, en met voegwoorden die gaan ten minste één kant niet zien wat ze verbinden.
Het kan nog erger. We kunnen de verzameling S2 opvatten als de familie van alle deelverzamelingen van de reële rechte R. En op die familie kan geen lineaire ordening gedefinieerd worden. Het sleutelbegrip is hier `definiëren’: er is geen formule die de familie deelverzamelingen van R zó sorteert dat elk tweetal verzamelingen vergelijkbaar is. De stap van S2 naar S3 kan eigenlijk niet genomen worden.
Ten tweede is er nog het begrip lengte van een zin. Cantor heeft een hele theorie van orde-typen (`lengten’) van lineair geordende verzamelingen ontwikkeld. Wat daar vooral opvalt is dat er veel onvergelijkbare orde-typen zijn. En die kom je ook tegen bij de stap van S2 naar S3: het voorsorteren op `lengte’ gaat dus ook al niet.
Welordeningen?
“Maar, er zijn toch welordeningen?”, hoor ik degenen die wat verzamelingenleer hebben bestudeerd opwerpen. Dat klopt, en we hebben ook nog Zermelo’s Welordeningsstelling, die zegt dat elke verzameling een welordening heeft. Bij een welordening zijn de elementen zo gesorteert dat elke deelverzameling (niet-leeg) een eerste element heeft. Welordeningen zijn ook nog onderling vergelijkbaar, dus die co-ordinate projections schrijf je zo op.
Inderdaad, maar die welordeningsstelling is equivalent met het Keuzeaxioma en daarmee hoogst niet-constructief. Zoals de verzameling S2 geen definieerbare lineaire ordening heeft heeft S1 geen definieerbare welordening.
Je kunt met welordeningen werken maar dan laat je de willekeur van het Keuzeaxioma binnen en daarmee ben elke zweem van een grammatica kwijt.
Ik weet niet of je dan nog van een natuurlijke taal kunt spreken.
Korte samenvatting
We zijn hier nog niet aan het einde van het artikel Sets and Sentences gekomen. Er gebeurt wiskundig niet veel nieuws meer en het derde deel beargumenteerd dat zo ongeveer alle theoriën over natuurlijke getallen uit de tijd van schrijven niet deug(d)en. De argumenten steunen op The NL Vastness Theorem.
In het bewijs van die stelling zitten gaten. En die gaten bestaan vooral uit ontbrekende definities en aannamen.
Zo wordt nergens echt vastgelegd wat een verzameling eigenlijk is; het dichtst bij een definitie komt men in het bewijs van de Vastness Theorem: het kenmerkende van een verzameling is dat deze een kardinaliteit, een `aantal elementen’, heeft. Dat is de omgekeerde wereld en ook niet echt nodig.
Cantor definieerde eerst `Menge’ en pas daarna `Machtigkeit’; naar moderne maatstaven hebben die definities weinig inhoud maar ze stuurden de intuïtie wel de goede kant op.
De manier waarop ik het `bewijs’ van de stelling heb opgeschreven laat zien dat die aanname over kardinaliteit vermeden kan worden; we hebben alleen goede afspraken over het hebben van meer, minder en evenveel elementen nodig en dat kan zonder die aantallen te definiëren of benoemen. Net als we geen eenheid van lengte nodig hebben om uit te maken of ik langer, korter, of even lang ben als Marc van Oostendorp: zet ons naast elkaar en je weet het.
Zoals al opgemerkt zijn de centrale noties van het artikel niet goed afgesproken; de definities lijken, gezien de gegeven voorbeelden, vooral ingegeven door de eindige situatie. Bij het suggestief opschrijven van de verzameling S1 zien we ook alleen maar eindige zinnen.
Ik vermoed dat niemand de schrijvers heeft gevraagd hoe men het zich moet voorstellen: een collectie zinnen die geordend is als de rationale getallen: zonder begin, zonder eind en met tussen elk tweetal zinnen ondindig veel andere. Hoe maak je daar een goedlopende zin van?
Lariekoek? I
Dit is de vierde in een korte serie blogposts naar aanleiding van een discussie op twitter over dit stuk op Neerlandistiek.nl van Marc van Oostendorp dat zelf weer een reactie op dit artikel van Paul Postal was. In de eerste post kwalificeerde ik een opmerking uit het stuk van Postal als lariekoek. Daar gaat deze post over.
De opmerking van Postal betreft de grootte van de `collectie’ van alle boeken in een taal. Die collectie is niet alleen oneindig groot, niet alleen overaftelbaar, maar zelfs groter dan elke denkbare verzameling. Voor (een idee van) het bewijs van deze bewering verwijst Postal naar het artikel Sets and Sentences en een boek, The Vastness of Natural Languages, beide geschreven door hemzelf en D. Terrence Langendoen.
Ik heb wat met verzamelingen en wilde daarom wel eens zien waarom de collectie boeken in een Natuurlijke Taal zo groot moest zijn. Het boek heb ik niet te pakken kunnen krijgen maar deze recensie beweert dat de kern van de inhoud al in het artikel staat. laten we dat artikel dan maar eens bekijken.
Het artikel bestaat uit drie delen: een korte inleiding, een deel waarin “naar analogie met Cantors’s resultaten” wordt beargumenteerd dat de zinnen in een natuurlijke taal geen verzameling vormen, en een deel met conclusies.
Dat tweede deel begint met wat definities die het beschrijven van constructies van nieuwe `zinnen’ uit oude mogelijk moeten maken. Het hoofdingrediënt is dat van een conjunct, dat is een eenheid die bestaat uit een connectief en een deelconjuct. Die conjuncties kunnen in/tot `co-ordinate compound constituents’ samengevoegd worden. Zo’n co-ordinate compound moet wel echt `compound’ zijn en dus uit ten minste twee conjuncten gevormd worden.
Vervolgens spreken de schrijvers af hoe uit een verzameling U van constituents een co-ordinate compound constituent T gemaakt kan worden; of beter: hoe we kunnen zien dat T uit U gemaakt is. Elke conjuct in T heeft een element van U als deelconjunct, elk element van U is deelconjunct van precies één conjuct van T, en de conjuncten in T zijn geordend (daarover later meer).
In dit geval is T een `co-ordinate projection‘ van U, en U is de `projection set van T. Let op het gebruik van `een’ en `de’ in de vorige zin.
Ik kan begrijpen dat dit allemaal nogal abstract overkomt en ik moest het zelf een paar keer lezen voor ik dacht door te hebben wat er aan de hand is. Achter al die termen zitten plaatjes als het onderstaande verscholen:
De verzameling U bestaat uit de constituents `Marc’ en `KP’; uit elk element van U kunnen we een conjunct maken door er een connectief aan vast te plakken. Dat connectief kan leeg zijn, zoals bij `Marc’ omdat, bijvoorbeeld, je aan het begin van een zin geen voegwoord gebruikt en toch iets nodig hebt om je conjuct te markeren. Daar nemen we dan ∅ maar voor. In de woorden van Langendoen en Postal: C1 en C2 zijn de dochters van T, die zusters zijn elk een conjuct, bestaande uit een connectief en een deelconjuct.
De hoofdaanname, of het hoofdaxioma, is nu dat elke verzameling constituents tot een co-ordinate compound constituent gevormd kan worden. De (co-ordinate compound) constituents waar we het verder over zullen hebben zijn gewoon zinnen, en daarom zal ik ze verder ook maar zo noemen.
Om te beginnen maken we oneindig veel zinnen:
- De reële rechte is overaftelbaar
- Ik weet dat de reële rechte overaftelbaar is
- Ik weet dat ik weet dat de reële rechte overaftelbaar is
- Ik weet dat ik weet dat ik weet dat de reële rechte overaftelbaar is
- …
Niet erg opwindende zinnen maar daar gaat het niet om: er is een duidelijke procedure die voor elk natuurlijk getal n een zin Z(n) construeert. Dit is een voorbeeld van een recursieve definitie: als we een beginobject beschrijven en een recept aangeven om elk volgende object te maken dan beschouwen we de constructie als voltooid.
Voor elke deelverzameling U van deze verzameling {Z(n):n∈N} van zinnen bestaat er dus een zin waarvan de deelconjucten precies de zinnen uit U zijn. Dat geeft ons dan overaftelbaar veel zinnen.
Daarmee is het hek van de dam: we kunnen blijven doorgaan en elke deelverzameling van de nieuwe verzameling zinnen weer samensmeden tot een nieuwe zin. En weer, en weer, en weer, …
De conclusie van Langendoen en Postal is nu dat alle zinnen die we zo kunnen maken geen verzameling vormen. Hier komt de analogie met Cantor’s resultaten om de hoek kijken. Cantor bewees namelijk dat elke verzameling strikt meer deelverzamelingen heeft dan elementen. Als je dit toepast op `de verzameling van alle verzamelingen’ kom je in de knoop: de elementen van die `verzameling’ zijn precies zijn deelverzamelingen, maar dat kan niet omdat er meer deelverzamelingen dan elementen zijn. De entiteit `de verzameling van alle verzamelingen’ bestaat dus niet.
Dezelfde redenering is nu van toepassing op `de verzameling van alle zinnen in een natuurlijke taal’: elke deelverzameling bepaalt een zin en verschillende deelverzamelingen bepalen verschillende zinnen en dat druist in tegen de conclusie van Cantor: altijd strikt meer deelverzamelingen dan elementen.
Waarom Lariekoek?
Waarom denk ik dat dit lariekoek is? Dat heeft vooral te maken met de manier waarop Langendoen en Postal hun `bewijs’ presenteren. Daar is wiskundig veel op af te dingen. Maar deze post is al behoorlijk lang en ik bewaar mijn wiskundige opmerkingen, bijvoorbeeld over de bovengenoemde ordeningen daarom maar voor deel twee.
Getallen bestaan (eigenlijk) niet
Dit is de derde in een korte serie blogposts naar aanleiding van een discussie op twitter over dit stuk op Neerlandistiek.nl van Marc van Oostendorp dat zelf weer een rectaie op dit artikel van Paul Postal was. De eerdere delen staan hier en hier.
Tussen al die tweets maakte ik de volgende opmerkingen:
Daar komt nog bij dat `getal' als aantal’ strikt genomen gedefinieerd moet worden; verzamelingen hebben geen intrinsiek `aantal elementen'. Boeken zijn inderdaad eerder stellingen. https://t.co/Mjjth2qDKd
— (((K P Hart))) (@hartkp) October 15, 2019
Daar wil ik het vandaag even over hebben. Wat zijn getallen eigenlijk? Die vraag werd zelfs op de Nationale Wetenschapsagenda gesteld en ik heb daar al eens een antwoord op gegeven. Ik wil dat hier wat uitgebreider doen.
Getallen
Om te beginnen: in de discussie en de stukken ging het over natuurlijke getallen en die werden vereenzelvigd met hun decimale schrijfwijze. Dat is, in deze tijd, heel natuurlijk: afgezien van jaartallen in Romeinse notatie op gevels van gebouwen (en als paginanummers in boeken vóór de echte inhoud begint) zien we getallen eigenlijk alleen opgeschreven met behulp van de indo-arabische cijfers en de positionele schrijfwijze.
Gegeven deze vereenzelviging is er wel iets te zeggen voor het idee dat boeken en getallen iets gemeen hebben: rijen symbolen met een welgedefinieerde inhoud.
Aan de andere kant: getallen zijn in zekere zin absoluut: ze zijn bestand tegen vertalingen. Twaalf, twelve, douze, tolv, dvanást’, teyan-a-bub, … verwijzen allemaal naar exact dezelfde hoeveelheid streepjes: ||||||||||||.
Als ik een stuk tekst van mezelf in het Engels vertaal is die exactheid weg. Sommige nederlandse woorden en uitdrukkingen doen het niet zo goed in letterlijke vertaling (“laat maar” versus “let but”) en een equivalent-bij-benadering is slechts dat: een benadering. Vergelijk deze twee stukken over de Gulden Snede maar: nederlands versus engels.
Meer, minder, even veel
Maar goed, terug naar de vraag over de aard, of het bestaan, van getallen. Ik denk/vind dat getallen, in de zin van aantallen, niet bestaan.
“Maar we tellen toch dagelijks dingen”, hoor ik u zeggen. Inderdaad, maar de zaken die we daarbij gebruiken zijn bedacht, ze bestaan niet in het wild. Ooit `het getal dat wij in het Nederlands drie noemen’ gezien? En hierbij wel de gebruikelijke notaties loslaten, het symbool 3 telt niet, en III ook niet, en γ’ ook niet.
Maar er is meer: in de verzamelingenleer is het na invoering van de bekende soorten afbeeldingen, injectief, surjectie, en bijectie een koud kunstje te definiëren wanneer de ene verzameling minder, meer, of even veel elementen heeft als een andere. Kleine kinderen weten dat al heel snel, en zonder tellen: haal uit beider zakje snoepjes telkens tegelijkertijd één snoepje. Het zakje dat het eerst leeg is bevatte minder snoepjes dan het andere en gelijk leegraken betekent even veel. Probeer het zelf maar eens: neem twee lepels hagelslag en zoek zo uit welke lepel de meeste korrels heeft.
Maar als je in de verzamelingen een antwoord wilt geven op de vraag “Hoeveel elementen?” sta je in het begin met de mond vol tanden. Na vrij veel werk lukt het een klasse van standaardverzamelingen af te zonderen waarmee andere verzamelingen gemeten kunnen worden en zo een `aantal elementen’ opgeplakt kunnen krijgen. Dat wil zeggen: dit werkt voor eindige verzamelingen, waarbij `eindig’ zo wordt gedefinieerd dat `het’ ook inderdaad werkt.
Hoeveel?
Hoe zit het met willekeurige verzamelingen? Georg Cantor dacht dat er zoiets als `het aantal elementen’ moest zijn; hij had zelfs een definitie:
,Mächtigkeit` oder ,Cardinalzahl` von M nennen wir den Allgemeinbegriff, welcher mit Hülfe unseres activen Denkvermögens dadurch aus der Menge M hervorgeht, dass von der Beschaffenheit ihrer verschiedenen Elemente m und von der Ordnung ihres Gegebenseins abstrahirt wird.
Uit die definitie halen we de volgende eisen waar dat Kardinaalgetal C(M) aan zou moeten voldoen:
- M en C(M) hebben even veel elementen (als bij de zakjes snoep), in vaktaal: er is een bijectie tussen M en C(M) — C(M) is dus ook een verzameling
- als er tussen M en N een bijectie bestaan dan C(M)=C(N)
Als er dus zo’n functie is dan kunnen we C(M) `het aantal elementen’ van M noemen.
En, helaas, zo’n functie kun je niet definiëren. Het bewijs van die ondefinieerbaarheid hoop ik maandag 16 december tijdens het laatste college van de Mastermath-cursus Set Theory af te ronden.
Wat betekent dit? Dat verzamelingen geen `intrinsiek’ aantal elementen hebben. Je kunt niet meer doen dan zelf een hoeveelheid standaardverzamelingen af te spreken waarmee je op zinvolle wijze betekenis aan `het aantal elementen’ kunt geven. Getallen zijn geen natuurverschijnselen maar mensenwerk.
Dit gebeurde vaker
De vraag wie van twee mensen langer of korter is is zo beantwoord: hou ze tegen elkaar aan en je ziet het. Om de vraag “Hoe lang zijn die twee mensen?” te beantwoorden zijn in de loop der tijd veel systemen bedacht, sommigen wat logischer dan de andere. Ons metrieke stelsel is overgebleven, ongetwijfeld door de voor de hand liggende definitie van de meter: neem de halve meridiaan van de noordpool door Parijs naar de evenaar en hak die in 10.000.000 even grote stukjes; elk stukje is, per definitie, één meter lang.
Oh, en `teyan-a-bub’? Dat gebruik je bij het tellen van schapen in Weardale.
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.
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.
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.
Upgoer Five
Today I was reminded of the Upgoer Five Editor, which was inspired by this XKCD cartoon (an explanation of the workings of the Saturn V rocket in very simple words).
I knew I had tried it once and thanks to twitter I could find my `explanation’ of bijections and a `definition’ of infinity again. This is just a short post so that I have an obvious place to look for the link to that short piece, when I need it.
Also, it will be fun to do this in Norwegian.
Het vermoeden van Duffin en Schaeffer
Recentelijk is het Duffin-Schaeffer-vermoeden bewezen. U kunt de preprint hier lezen. In de krant is er ook aandacht aan besteed. Ik wil hier iets meer over de wiskunde achter dit vermoeden vertellen.
Het vermoeden, nu dus een stelling, zegt iets over het benaderen van irrationale getallen met behulp van rationale getallen. De vraag is in het algemeen hoe efficiëent dergelijke benaderingen kunnen zijn.
Nu zullen de meningen over wat efficiënt is uiteen lopen maar de benaderingen die we in de praktijk gebruiken, namelijk afgekapte decimale ontwikkelingen, zijn het niet echt. Als die afgekapte ontwikkelingen als breuk schrijft is die breuk vrijwel nooit te vereenvoudigen: de benadering 3.14159265358979323846264338327 van π levert een onvereenvoudigbare breuk met een grote teller en een grote noemer.
Een goede benadering is er een waar de nauwkeurigheid groot is, vergeleken met de grootte van teller en noemer. Zo kun je 22/7 een goede benadering van π noemen omdat het verschil 22/7-π kleiner is dan 1/49. Het criterium dat we hier hanteren is: p/q is een goede benadering van α als |α-p/q| kleiner is dan 1/q2. Overigens is 19/6 ook een goede benadering: 19/6-π is kleiner dan 1/36.
Een beetje spelen met een rekenmachientje laat zien dat er geen goede benaderingen van π zijn met noemers 8 of 9.
Het vermoeden van Duffin en Schaeffer, nu dus de stelling van Dimitris Koukoulopoulos en James Maynard, gaat overigens niet over individuele irrationale getallen als π of √2. Het bekijkt de zaak van de andere kant en doet uitspraken over hoeveel irrationale getallen veel goede benaderingen hebben.
Je kunt bijvoorbeeld een vaste noemer n nemen en kijken welke getallen een goede benadering met noemer n hebben. Hierbij beperken we ons tot het interval (0,1); getallen in andere intervallen krijgen we door over een geheel getal op te schuiven.
Nu is meteen duidelijk welke getallen een goede benadering met noemer n hebben: die liggen in de intervalletjes van de vorm (k/n-1/n2,k/n+1/n2), met k=1,…,n-1, en in (0,1/n2) en (1-1/n2,1).
De totale lengte van die intervallen is gelijk aan 2/n (reken maar na).
Hiermee kun je voorspellingen doen: omdat 2/10+2/11+2/12+2/13+2/14+2/15 kleiner is dan 1 zijn er getallen zonder goede benadering met noemers 10 tot en met 15.
Noem de vereniging van de intervalletjes hierboven even An. Met behulp van de Categoriestelling van Baire kun je bewijzen dat er een relatief `dikke’ deelverzameling van het interval (0,1) is waarvan elk element tot oneindig veel van de An behoort en dus oneindig veel goede benaderingen heeft.
Dit nu is de aard van de stelling van Dimitris Koukoulopoulos en James Maynard: deze geeft, bij bepaalde definities van `goede benadering’, voorwaarden onder welke de verzameling getallen met oneindig veel goede benaderingen heel `dik’ is of juist heel `dun’, waarbij `dik’ en `dun’ ondubbelzinnige definities hebben. Daarnaast geeft de stelling ook een dichotomie: `dik’ en `dun’ zijn de enige mogelijkheden. Het is nooit zo dat ongeveer de helft van de getallen oneindig veel goede benaderingen hebben; de kans is altijd gelijk aan nul (wat niet betekent dat er geen getallen zonder oneindig veel goede benaderingen zijn) of gelijk aan één.
In het krantenartikel wordt nog het volgende voorbeeld van `mooie’ benaderingen gegeven: als hierboven moet |α-p/q| kleiner zijn dan 1/q2, maar q moet zelf ook een kwadraat zijn. In dat geval is de kans op oneindig veel mooie benaderingen gelijk aan nul, maar de bovengenoemde stelling van Baire garandeert toch dat er heel veel irrationale getallen met oneindig veel goede benaderingen zijn.
Ten slotte: voor de definitie van `goed’ waar dit stuk mee begon geldt dat <emelk irrationaal getal oneindig veel goede benaderingen heeft. Dat bewijs je niet met de methoden die hier beschreven zijn, daar moet je wat dieper de getaltheorie in duiken. Zie hiervoor de Wikipediapagina’s over Benaderingsstelling van Dirichlet en over Kettingbreuken.
Recent Comments