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