overzicht   overview

Stern-Brocot breuken

Vraag en Antwoord spel op het Mathematics Stack Exchange forum: Er bestaat in de wiskunde een bijzonder elegante structuur waarin zich uitsluitend vereenvoudigde breuken bevinden en bovendien is deze structuur zodanig dat alle denkbare breuken er in voorkomen. We hebben het over een boom-structuur die bekend staat als de Stern-Brocot tree. Aangezien er op internet meerdere goede verhandelingen zijn over de Stern-Brocot tree wordt de lezer hiernaar verwezen. Ik heb aan de theorie niets toe te voegen. We zullen ons beperken tot een paar praktische opmerkingen. En we hebben wat programmatuur ontwikkeld.
Als eerste zullen we de eis stellen dat onze kleine rationale getallen tussen nul en één moeten liggen. Dit is zonder beperking van de algemeenheid, want als voor een breuk geldt dat $m/n > 1$ dan geldt altijd voor de omgekeerde breuk dat : $n/m < 1$ . We zoeken in de boom tussen $0/1$ en $1/1$ en zetten daarna de breuk op zijn kop. Dit is namelijk veel eenvoudiger dan te moeten beginnen met $0/1$ en $1/0$, vooral het laatste.
Het is wel prettig om een beeld te hebben van de Stern-Brocot structuur. Op grafisch zeer eenvoudige wijze (ASCII) wordt dit gerealiseerd in een Delphi Pascal module genaamd Wiskunde . Het module wordt gebruikt in een applicatie, waarvan de broncode is: 
program test;
Uses Wiskunde;
begin
  bijvoorbeeld(5);
end.
De uitvoer hiervan voor een diepte van de boom gelijk aan $(5+1)$ ziet eruit als volgt ($2^5+1=33$ regels): 
1/1------------------------------------
------------------------------5/6------
------------------------4/5------------
------------------------------7/9------
------------------3/4------------------
------------------------------8/11------
------------------------5/7------------
------------------------------7/10------
------------2/3------------------------
------------------------------7/11------
------------------------5/8------------
------------------------------8/13------
------------------3/5------------------
------------------------------7/12------
------------------------4/7------------
------------------------------5/9------
------1/2------------------------------
------------------------------4/9------
------------------------3/7------------
------------------------------5/12------
------------------2/5------------------
------------------------------5/13------
------------------------3/8------------
------------------------------4/11------
------------1/3------------------------
------------------------------3/10------
------------------------2/7------------
------------------------------3/11------
------------------1/4------------------
------------------------------2/9------
------------------------1/5------------
------------------------------1/6------
0/1------------------------------------
Een app schrijven die een kleine breuk in de Stern-Brocot boom opzoekt is niet zo moeilijk. Iets ingewikkelder wordt het als een dergelijke breuk wordt gerepresenteerd als een drijvende komma getal (i.e. floating point double precision number). Reken er namelijk maar niet op dat in een computer $0.1989$ werkelijk identiek is aan de (diskrete) breuk $1989/10000$ .

Irrationale getallen

Vraag en Antwoord spel op het Mathematics Stack Exchange forum: Pas echt interessant wordt de S-B boom als we te maken krijgen met irrationale getallen. Maar dan moeten we eerst weten wat irrationale getallen zijn. In de eerste plaats hoe we ermee moeten rekenen. Hierboven twee pogingen die ik heb ondernomen op het Mathematics forum. De meest succesvolle is de laatste. De rekenkunde van irrationale getallen - en van de reële getallen in het algemeen - wordt geheel en al duidelijk als men in de gaten houdt dat de reële getallen oorspronkelijk afkomstig zijn uit de Euclidische meetkunde en geen algebraïsche oorsprong hebben. In deze Euclidische meetkunde kunnnen de elementaire bewerkingen optellen, aftrekken, vermenigvuldigen en delen op perfekte wijze, namelijk met behulp van (lengtes van) lijnstukken worden gedefinieerd.
Dit gezegd hebbende moeten we toch vroeg of laat de sprong maken naar de algebra. Zoals reeds aangekondigd kan dit gedaan worden met behulp van de Stern-Brocot tree. Dit wordt gedemonstreerd aan de hand van een zeer bekend irrationaal getal: de wortel uit $2$. Reeds in de oudheid werd bewezen dat $\sqrt{2}$ geen breuk kan zijn. Men zal $\sqrt{2}$ dan ook niet terugvinden in de S-B boom. Wat wél kan worden getraceerd is een pad in de boom dat uiteindelijk zou moeten leiden naar de juiste waarde van de wortel uit $2$. Of liever gezegd naar de omgekeerde waarde $1/\sqrt{2}$ , want we zouden ons beperken tot breuken tussen $0$ en $1$. Dit pad in de S-B boom is in principe oneindig lang (façon de parler / bij wijze van spreken) en leidt tot breuken met een oneindig (dat wil zeggen: zeer) grote teller en een oneindig (dat wil zeggen: zeer) grote noemer. Neem om de gedachten te bepalen de uitkomst van genoemde demo : $$ \frac{131836323}{93222358} < \sqrt{2} < \frac{186444716}{131836323} $$ Maar met behulp van onze Implementable Set Theory en de bijbehorende rekenkunde met zeer grote getallen kunnen we nog wel wat meer: 
program demo;
Uses Rekenen;
begin
  wortel_twee(tien(100));
end.
Giving: 
   237615882925894844939311038672159564734946027184920
 / 168019802134529020067676914738440478110633605571601
 < sqrt(2) < 
   168019802134529020067676914738440478110633605571601
 / 118807941462947422469655519336079782367473013592460
 264 iterations
Or: $$ \frac{237615882925894844939311038672159564734946027184920} {168019802134529020067676914738440478110633605571601} < \sqrt{2} < \frac{168019802134529020067676914738440478110633605571601} {118807941462947422469655519336079782367473013592460} $$ Wat betekent dit nu? Het betekent dat alle irrationale getallen de vorm hebben van zeer grote breuken. Echter bij (materialisatie van) een oneindig grote teller maakt eentje meer of minder geen verschil. En ook bij (materialisatie van) een oneindig grote noemer maakt eentje meer of minder geen verschil. Bovendien zijn er vele keuzes mogelijk voor die teller en die noemer, al naar gelang we dieper of minder diep in de S-B boom zitten. De slotsom is dat, precies zoals bij "gewone" oneindig grote breuken, we een hele verzameling breuken hebben om het irrationale getal te representeren. Dat is iets meer dan de ordered pairs in bovenstaande referentie. Het enige verschil tussen rationale en irrationale getallen is dat de eerste een diskrete representatie hebben. Irrationale getallen hebben zo'n diskrete representatie niet. Irrationale getallen zijn per definitie altijd enigszins onnauwkeurig en zijn uitsluitend verbonden aan een continuüm. Conclusie: