] >
Is een transformatie van een verzameling , dan is er met simpele recursie voor iedere een rij in vastgelegd:
dus
4.13 Voorbeeld. Laat de transformatie van Voorbeeld 4.1 zijn. Het verloop van onder is de rij . Het verloop van is .
In de pythonmodule combinatorics.py zetten we een paar functies die (een deel van) het verloop van een element onder een transformatie geven. De functie course(f,N,a) geeft de eerste N termen van het verloop van het element a onder de transformatie f.
Hieronder enkele voorbeelden van transformaties f voor het gebruik met de Pythonfunctie course(f,N,a). De eerste is de transformatie van Voorbeeld 4.1. De andere komen van integer.py. De transformatie lambda x:isum(x,7) bijvoorbeeld is de transformatie die bij x het natuurlijke getal 7 optelt.
Voor een heb je bij iedere zo een , m.a.w. je hebt een transformatie van . Deze transformaties zijn het makkelijkst te definiëren als je de samenstelling van transformaties gebruikt:
4.14 Definitie. Zij een transformatie van . De transformaties met van zijn gedefinieerd door
De transformatie van heet de -de geïtereerde van .
Een ander woord voor ‘transformatie’ is ‘operator’. Men zegt ook dat een transformatie van (= operator op ) werkt (= opereert) op de elementen van . Ook spreekt men van het toepassen van een transformatie. Het itereren van een transformatie is het herhaald toepassen van die transformatie.
Bewijs. De rij voldoet aan de definitie van het verloop:
4.16 Definitie. Een tweetal bestaande uit een verzameling en een transformatie noemen we soms ook een (discreet) dynamisch systeem.
Als je het hebt over een dynamisch systeem , dan geeft dat aan dat je geïnteresseerd bent in het verloop van elementen onder . In feite is het niets anders dan een transformatie. Verder is er de suggestie dat het gaat om een proces dat zich in de tijd afspeelt: je begint met een op tijdstip en je doorloopt de rij ; op tijdstip ben je in .
4.17 Voorbeelden. Met behulp van geïtereerden van transformaties zijn de bewerkingen optellen, vermenigvuldigen en machtsverheffen goed te zien als herhaald uitvoeren van een transformatie:
4.18 Propositie (Rekenregels voor geïtereerden). Zij een transformatie van een verzameling , laten en natuurlijke getallen zijn en zij verder een transformatie van die commuteert met , d.w.z. . Dan
Bewijs. In: ”Getallen”, Epsilon deel 65, uitgegeven door Epsilon-Uitgaven. □
Deze regels hebben we met inductie bewezen. Los daarvan is het van belang dat de regels ook intuïtief duidelijk zijn. De notatie betekent de samenstelling van keer de transformatie , ofwel . De eerste regel is dan wel duidelijk:
Op deze manier zijn ook de andere regels te begrijpen.
De functie iterate(f,n,a) geeft het beeld van a onder de n-de geïtereerde van f.