KP Hart

KP's ramblings

Hogere Machten

Gisteren bekeken we een weergave in woorden van een kansberekening in een column van Maarten Keulemans. Vandaag kijken we even naar die berekening zelf en hoe je snel iets over de 5000ste macht van een breuk als 9999/10000 kunt zeggen.

Even ter herinnering:

En het protest op De Dam? Misschien had men gewoon geluk, berekende epidemioloog Frits Rosendaal (LUMC). ‘De kans om corona te hebben, was op dat moment klein, ongeveer een op tienduizend’, stelt Rosendaal. ‘Dat maakt de kans dat van de 5.000 aanwezigen er een of meer besmettelijk waren, op dat moment 39 procent: 1 min 9.999 gedeeld door 10.000, tot de macht 5.000. Vandaar dat er niks gebeurd is.’

Gisteren hebben we gezien dat de te berekenen kans er zo uit moet zien:

Nu kun je die macht in een rekenmachientje stoppen en als dat goed geprogrammeerd is krijg je ongeveer 0,6065, en dat geeft inderdaad, afgerond, een kans van 39 procent.

Met de juiste formules kun je bijna uit het hoofd een goede onderschatting van de macht maken, en daarmee een overschatting van die kans. De eerste formule is een ongelijkheid:

Deze ongelijkheid heeft een naam: De Ongelijkheid van Bernoulli, deze geldt voor alle x-en groter dan -1 (en ongelijk aan 0), en alle nauurlijke getallen. Als we 9999/10000 schrijven als 1-1/10000 kunnen we x=-1/10000 nemen, en n=5000, met als resultaat

Zonder al te veel moeite zien we dat de kans in ieder geval kleiner dan ½ was. Voor dit soort schattingen is de Ongelijkheid van Bernoulli een mooi stuk gereedschap om bij de hand te hebben.

Wat scherper

Kan het beter? Ja natuurlijk. Wat extra kennis over over de rij (1-1/n)n vertelt ons dat

en daaruit vinden we dan (met een relatieve fout van niet meer dan 0,0001):

Hierin is e het grondtal van de natuurlijke logaritme.

Onze macht is dan ongeveer de wortel uit 1/e; en daar hebben we een reeks voor die iedere eerstejaars wiskundestudent leert:

En de eerste paar termen geven ons een antwoord dat al heel dicht bij het resultaat van het rekenmachientje ligt.

Binomium

Voor degenen die het Binomium van Newton kennen (en beheersen): schrijf de eerste paar termen van de uitgewerkte macht maar eens op en vergelijk met de som voor 1/√e.

Spreken met haakjes

In een column van Maarten Keulemans in de Volkskrant werd aan het eind even snel aangegeven hoe groot de kans was dat er bij de Black-Live-Matter demonstratie op 2 juni iemand was die met corona besmet was. Aan het eind gebeurde iets dat mij op het verkeerde been zette.

Daar stond namelijk dit

En het protest op De Dam? Misschien had men gewoon geluk, berekende epidemioloog Frits Rosendaal (LUMC). ‘De kans om corona te hebben, was op dat moment klein, ongeveer een op tienduizend’, stelt Rosendaal. ‘Dat maakt de kans dat van de 5.000 aanwezigen er een of meer besmettelijk waren, op dat moment 39 procent: 1 min 9.999 gedeeld door 10.000, tot de macht 5.000. Vandaar dat er niks gebeurd is.’

Ik heb de zinsnede waar ik over struikelde even rood gemaakt. Het gaat mij om die komma.

Voor de komma staat dus “1 min 9.999 gedeeld door 10.000” en na de komma “tot de macht 5.000”. Die komma had voor mij de functie van haakjes, en met Mijnheer Van Dalen aan mij zijde las ik het gedeelte ervoor als

en met de komma als haakjes las ik

en daar staat gewoon 0,00015.000 en dat is 10-20.000, veel kleiner dan 0,39 dus.

Dat was niet de bedoeling. De bedoeling was dat de haakjes heel anders stonden, namelijk zo:

Dat is nog lastig in zo’n snelle zin te formuleren; als ik dit op college zou doen zou ik het natuurlijk op het bord schrijven maar soms spreek ik het uit voor ik het opschrijf. Ik zou er dit van maken: “1 min de 5000ste macht van: 9999 gedeeld door 10000”. En bij die “9999 gedeeld door 10000” zou ik de haakjes met mijn armen uitbeelden.

Morgen zullen we even naar die 5000ste macht kijken: hoe kun je snel zien dat hij groter dan een half is? En dus die kans kleiner dan een half?

Het laatste cijfer

Op twitter werd gevraagd naar het laatste cijfer van het getal van Graham. Grappig genoeg heeft dat een redelijk eenvoudig antwoord.

In deze coronatijden krijgen ouders vragen van hun kinderen die deze meestal aan de onderwijzer(es) vragen, zoals

Nu is het getal van Graham het resultaat van een ongelooflijk aantal malen machten van 3 nemen, in een toren van 3-en. Het resulterende getal is nog groter. Maar hoe zou je het laatste cijfer van dat getal kunnen bepalen? Dat is eenvoudiger dan het lijkt. We doen het in stappen.

Om te beginnen het getal is een macht van 3 en als we de eerste paar machten van 3 opschrijven, en alleen het laatste cijfer noteren vinden we 3, 9, 7, 1, 3, 9, 7, 1, … Dat dit zich zo blijft herhalen wordt duidelijk als je je realiseert dat het laatste cijfer van 3×n alleen van het laatste cijfer van n afhangt.

Welke van die vier cijfers is het nu? Welnu de exponent van het getal is weer een macht van drie en dus oneven. Dat betekent dat we alleen een 3 of een 7 als mogelijkheid overhouden. Als we van die exponent de rest kunnen vinden bij deling door 4 weten we welk van de twee het is.

Schrijf die resten maar op: 31 heeft rest 3; 32 heeft rest 1; 33 heeft rest 3; 34 heeft rest 1; … het patroon wordt duidelijk: bij oneven exponenten is het 1 en bij oneven exponenten is het 3.

Maar we hebben een toren van drieën, dus de exponent van de exponent is oneven en het eindcijfer is gelijk aan 7.

Iets geavanceerder

Als je hebt leren rekenen modulo getallen (`klokrekenen’) gaat het sneller.

Onze vondst van periode 4 vind je door te zeggen 31=3,
32=9, 33=27=7 modulo 10, 34=3×7=21=1 modulo 10 en zodra we 1 hebben gevonden is duidelijk dat we de periode hebben.

Dan moeten we modulo 4 rekenen om te weten of we 3 of 7 krijgen, maar 3=-1 modulo 4, dus 3k=(-1)k modulo 4 en dan is duidelijk wat we krijgen bij een oneven exponent.

Opgave

Probeer zelf de laatste twee cijfers van het getal van Graham te bepalen. Het duurt iets langer maar met een beetje volhouden kom je er wel.

De fundamenten (ahem) van de astrologie

Er stak vandaag op twitter een stormpje op over een artikel in NRC over de populariteit van astrologie onder hoogopgeleiden. De krant had meer moeten benadrukken dat astrologie gewoon onzin is en dat er bij die desbetreffende hoogopgeleiden een steekje los is. Ik zou graag gezien hebben dat de wetenschapsbijlage een stuk geplaatst had over andere aspecten van de astrologie: onder andere de nogal zwakke fundamenten onder de oorspronkelijke dierenriem.

Wie een boek (of website) over de geschiedenis van de wiskunde en natuurwetenschappen leest komt er snel achter dat astronomie en astrologie zich oorspronkelijk gezamenlijk ontwikkelden. De Wikipediapagina “Astrology and Astronomy” biedt voldoende startpunten voor een ontdekkingstocht. In het kort: de stand van de sterren had praktisch belang voor plaatsbepaling, tijdsmeting en voorspellingen van hemelverschijnselen als zons- en maansverduisteringen. Waarschijnlijk door de misvatting Post Hoc Ergo Propter Hoc gebruikte men de stand van de sterren ook voor andere voorspellingen. Evengoed is de astrologie mede de oorzaak van de ontwikkeling van grote delen van de klassieke wiskunde.

De fundamenten

In mijn achterhoofd zat nog een herinnering aan een stuk dat ik gelezen had waarin verteld werd dat de dierenriem sinds de Babyloniërs hem hadden gemaakt behoorlijk opgeschoven was.

Met wat zoekwerk vond ik op de site van stylist.co.uk een vermakelijk artikel dat onder verwijzing naar een pagina van NASA uitlegt dat onze westerse sterrebeelden voor geen meter kloppen met wat er aan de hemel te zien is.

Samengevat:

  • de Babyloniërs trokken een rechte lijn vanuit de aarde door de zon en bekeken telkens door welk sterrebeeld die lijn ging. Maar in plaats van netjes de tijden dat de sterrebeelden gesneden werden aan te houden verdeelde men de cirkel in twaalf nette segmenten van 30 graden elk. Niet alleen werd er dus behoorlijk gesmokkeld, er werd zelfs een sterrebeeld weggemoffeld: Ophiuchus.
  • door de verandering van de stand van de aardas zijn de sterrebeelden een stuk opgeschoven; de data die we gebruiken om sterrebeelden aan personen toe te kennen kloppen niet meer met wat echt boven ons te zien is.

Op de pagina van stylist.co.uk staat een handig tabelletje waarop te zien is hoe mis het allemaal is: Kreeft eindigt niet op 22 juli maar begint op 20 juli en eindigt op 10 augustus; en Schorpioen duurt eigenlijk maar een week (en begint pas een dag nadat het officieel geëindigd is).

Continuïteitsmaximalisatie

Op twitter, via Japka-d. Bouma, een mooi woord gevonden: continuïteitsmaximalisatie. Ik vroeg me meteen af of ik daar wiskundig chocola van kon maken.

Hier is de tweet waar het mee begon.

Op het eerste gezicht lijkt er aan continuïteit weinig te maximaliseren: een functie is continu of niet en daar is de kous mee af, lijkt het. Maar de situatie waar het in de tweet om gaat wijst in een richting waar de ene continuïteit beter is dan de andere. Het gaat er om een overname van een bedrijf zo goed mogelijk te laten verlopen.

Natuurlijk wil je bij een overname geen plotselinge sprongen zien; dat komt overeen met het wiskundige idee van continuïteit: het traject van de opvolger begint waar dat van de voorganger stopt. Maar dat is niet genoeg; de grafiek van de absolute-waardefunctie laat zien wat in de praktijk wat ongewenst is: een plotselinge verandering van richting.

De trajecten moeten glad aansluiten (`glad’ is eigenlijk een beter woord dan `continu’, gladheidsmaximalisatie dus); de aansluiting moet differentieerbaar verlopen. Maar, een plotse verandering van snelheid is ook niet prettig; dus de snelheid ook maar glad (differentieerbaar) houden dus (continue versnelling). Wat men zich echter niet realiseert is dat de derde afgeleide, de afgeleide van de versnelling dus, ook niet al te veel moet veriëren: die derde afgeleide heet de jerk (de ruk) van een beweging en is veelal de hoofdoorzak van misselijkheid.

Zo kunnen we natuurlijk door blijven gaan en steeds meer gladheid eisen. Dan komt er van maximalisatie niet veel terecht. Maar er is wel een maximum te benoemen. In eerste instantie zou je zeggen dat oneindig vaak differentieerbaar toch wel het beste is wat gehaald kan worden. Er is zo’n mooie overgang: definieer f(x)=0 voor x≤0, en voor x>0 nemen we f(x)=exp(-1/x); een plaatje van de grafiek voor x tussen 0 en 1 op Wolfram Alpha laat zien dat hier inderdaad een zeer gladde overgang bereikt wordt. Deze functie is inderdaad superglad: oneindig vaak differentieerbaar in 0.

Is dat het maximaal haalbare? Nee, onder de supergladde functies zijn er die extra-superglad zijn: de analytische functies; daar is de functie hierboven er niet een van. Analytische functies zijn de echte continuïteitsmaximaliseerders en de meeste functies die mooi lijken zijn het ook: de sinus, de cosinus, de e-macht, de wortel, … allemaal analytisch.

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):

  1. Neem een verzameling U en laat k de kardinaliteit van U zijn (eindig of oneindig)
  2. 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.
  3. 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.
  4. 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.
  5. De deelconjuncts van de conjuncts in W vormen een verzameling V die, volgens de regels in (6), kardinaliteit k heeft. Niks mis mee.
  6. 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.
  7. 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 S0de 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 20 (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:

syntax-boom

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 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.

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.

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:

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.

© 2011 TU Delft