Door K.P. Hart
In dit vervolg op deze blogpost ga ik het hebben over het ordenen van boeken.
Bij de twitterdiscussie over 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: 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óór 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.
Foto door Charlie Salazar via Pexels.
Dit stuk verscheen eerder op het blog van K.P. Hart.
Als je een boek beschouwt als een string van letters (inclusief leestekens, spaties, etc) of woorden (idem), dan kan je dus de letters of tokens een nummer geven. Daarmee is een boek een string van nummers.
Om het einde van de string aan te duiden, kan je het boek beeindigen met een speciaal getal (ik stel voor: nul). Die komt dus een keer voor in ieder boek: aan het eind. Een leeg boek bestaat dus uit alleen een nul.
Het enige probleem is dat je de grootte van het alfabet niet tevoren kent. Er kunnen nieuwe boeken in beeld komen met nieuwe letters of woorden. Die een nieuw (hoger) nummer moeten krijgen. En dan beland je in Hilbert’s bibliotheek.
Gelukkig zijn ze in openbare bibliotheken van die idiote nummering overgegaan
naar onderwerpen