L'analyse combinatoire est une branche des mathématiques discrètes qui consiste à dénombrer des structures définies sur des ensembles finis par des propriétés combinatoires. Elle s'approche, beaucoup plus que l'on ne pense, de l'informatique.
Le dénombrement est un calcul. Le véritable but en cette matière ne se restreint pas à trouver l'expression de la série finie qui donnera la valeur de ce calcul. Elle cherche à donner une expression, qui peut être plus générales qu'une série, la plus efficace à calculer ou la plus simple à définir. Autrement dit, un algorithme de calcul qui soit de complexité économe (simple à calculer) ou de définition économe (simple à écrire), soit à chaque fois deux objectifs potentiellement contradictoires, et donc souvent deux formulations.
C'est donc un effort de conception du langage des algorithmes et du langage des démonstrations sur ces algorithmes qu'il convient de mettre en oeuvre. Prenons par exemple la suite de Fibonacci qui est définie par :
`F(0)=0`
`F(1)=1`
`AAn">"1, F(n)=F(n"-"1)+F(n"-"2)`
La formule de Binet trouve un autre moyen de calcul :
`varphi = (1+sqrt(5))/2`
`AAn"⩾"0, F(n) = "arrondi"(( varphi^n)/sqrt(5) )`
La première expression, si elle est programmée avec mémoire des résultats intermédiaires, est la plus efficace en terme de complexité de calcul, tandis que la seconde formule peut être considérée d'un certain point de vue comme plus simple à écrire.
On suit en parallèle le chapitre De l'algèbre et du dénombrement
On commence par décrire 4 types d'assemblages rudimentaires que sont la liste, l'arrangement, le sac (ou multi-ensemble), et l'ensemble.
Le premier type d'assemblage que l'on conçoit sont les listes. On peut considérer la liste comme une succession de choix d'éléments pour produire un assemblage dans lequelle il n'y a aucune perte d'information.
On note entre parenthèse `(a,a,b)` les éléments d'une listes, sachant qu'ils peuvent être répétés plusieurs fois et que l'ordre compte. Soit une liste `L`, on note sa taille `|L|`. Exemple `"|"(a,b,a,a)"|"=4`. La liste vide se note `()`.
On appelle case n°`n` (ou cellule n°`n`) de la liste `L` , notée `L[n]`, l'emplacement n°`n` dans la liste, en commençant par `0`. Exemples `L"=" (a,b,c,d)`, `L[0]"="a`, `L[2]"="c`. On verra par la suite que la liste constitue l'archétype de l'application.
En faisant abstraction des répétitions, chaque liste `L` se transforme canoniquement en un arrangement notée `"%repetition"(L)` qui est l'arrangement des premières occurences des éléments de la liste.
En faisant abstraction de l'ordre des cases, chaque liste `L` se transforme canoniquement en un sac notée `"%ordre"(L)`, qui est le sac des éléments de la liste.
En faisant abstraction à la fois des répétition et de l'ordre des cases, chaque liste `L` se transforme canoniquement en un ensemble notée `"%repetition"("%ordre"(L))` ou bien `"%ordre"("%repetition"(L))` qui est l'ensemble des éléments présents au moins une fois dans la liste. Cet ensemble est aussi appelé le support de `L`.
Un arrangement est une liste d'éléments distincts. C'est aussi un ensemble muni d'un ordre total.
On note entre chevrons `⟨a,b,c⟩` les éléments d'un arrangement sachant qu'ils doivent nécessairement être distincts et que l'ordre compte. Soit un arrangement `A`, on note sa taille `|A|`. Exemple `|⟨a,b,c⟩|=3`. L'arrangement vide se note `⟨⟩`.
En faisant abstraction de l'ordre, chaque arrangement `A` se transforme canoniquement en un ensemble notée `"%ordre"(A)`, qui est l'ensemble des éléments présents dans l'arrangement. Cet ensemble est aussi appelé le support de `A`.
Un sac est une liste d'éléments à l'ordre près. Autrement dit le sac est une classe d'équivalence regroupant des listes, où la relation d'équivalence en question est : deux listes sont équivalentes si l'une peut être obtenue de l'autre en permutant ses cases.
On note entre symbole de sac `⟅a,a,b⟆` les éléments d'un sac, sachant qu'ils peuvent être répétés plusieurs fois. L'ordre n'y a pas d'importance. Soit un sac `S`, on note sa taille `|S|`. Exemple `|⟅a,a,b⟆|=3`. Le sac vide se note `⟅⟆`.
En faisant abstraction des répétitions, chaque sac `S` se transforme canoniquement en un ensemble notée `"%repetition"(S)`, qui est l'ensemble des éléments présents au moins une fois dans le sac. Cet ensemble est aussi appelé le support de `S`.
Un ensemble est un sac particulier où tous les éléments n'apparaissent qu'une seuls fois et sont deux à deux distincts. Un ensemble est un arrangement dans lequelle l'ordre n'a pas d'importance. Autrement dit l'ensemble est une classe d'équivalence regroupant des arrangements, où la relation d'équivalence en question est : deux arrangements sont équivalents si l'un peut être obtenue de l'autre en permutant ses éléments.
On note entre accolades `{a,b,c}` les éléments d'un ensemble sachant que l'ordre n'y a pas d'importance mais que les éléments doivent n'apparaitre qu'une seule fois et doivent nécessairement être deux à deux distincts. Soit un ensemble `E`, on note sa taille `|E|`. Exemple `|{a,b,c}|=3`. L'ensemble vide se note `{}`.
Pour transformer un ensemble en un arrangement il faut y définir un ordre totale.
Faire abstraction de l'ordre dans un arrangement consiste à quotienter la structure par le groupe des permutations. Il est possible de quotienter par un sous-groupe de premutation `Sigma`. Cela donne naissance aux types intermédaires de liste à permutation `Sigma` près qui se sépare en deux catégories celles où les éléments peuvent se répéter noté `⟅...⟆_Sigma` , et celles où les éléments ne peuvent pas se répéter `{...}_Sigma`
L'assemblage le plus précis est la liste, les autres assemblages correspondent à des ensembles de listes de même taille qui regroupe les différentes possibilités de listes. Une représentation globale disjonctive apparait sous forme d'ensemble de listes de même taille. Exemples où `Sigma` est le sous-groupe des permutations circulaires :
`(a,b,a,c) = {(a,b,a,c)}` `⟅a,b,a,c⟆={(a,a,b,c), (a,b,a,c), (b,a,a,c), (a,a,c,b), (a,b,c,a), (b,a,c,a), (a,c,a,b), (a,c,b,a), (b,c,a,a), (c,a,a,b), (c,a,b,a), (c,b,a,a) }`
`⟨a,b,c⟩={(a,b,c)}`
`{a,b,c}={(a,b,c),(b,c,a),(c,a,b)(a,c,b),(c,b,a),(b,a,c)}`
`{a,b,c}_Sigma={(a,b,c),(b,c,a),(c,a,b)}`
`⟅a,b,a,c⟆_Sigma={(a,b,a,c),(b,a,c,a),(a,c,a,b),(c,a,b,a)}`
La fonction `"%repetition"(.)` qui veut dire "aux répétions d'éléments près", appliquée à une liste va produire la liste des premières occurences.
La fonction `"%ordre"(.)` qui veut dire "à l'ordre près", appliquée à une liste va produire toutes les listes possibles obtenue par permutation de ses cases.
La suppression de l'ordre, qui est mise en oeuvre dans l'ensemble et le sac, consiste à compléter ces ensembles de listes par les listes obtenues en appliquant toutes les permutations possibles. Il est alors possible de concevoir des assemblages intermédiaires, non pas à l'ordre près, mais à un sous-groupe de permutation près, par exemple à une permutation circulaire près.
La fonction `"%"_Sigma(.)` qui veut dire "à une permutation de `sigma` prés", appliquée à une liste va produire toutes les listes possibles obtenue en appliquant les permutations de `Sigma` sur les cases de la liste.
La suppression des répétitions d'élément, qui est mise en oeuvre dans les ensembles et les arrangements, s'obtient en ne gardant que les premières occurrences des éléments.
L'approche informatique introduit un ordre système de tous les objets, et introduit la notion de classe d'objets. L'objets correspondra à l'élément, et la classe correspondra au type.
On définie 4 types qui vous jouer le rôle de classe dans un langage de programmation objet :
Le type fondamental est la liste qui mémorise une succession de choix d'éléments sans perte d'information.
L'ensemble se définie comme un ensemble de listes de même taille, et il admet une représentation unique en la liste des éléments de l'ensemble dans l'ordre système.
Le sac se définie comme un ensemble de listes de même taille, et il admet une représentation unique en la liste des éléments du sac dans l'ordre système.
L'arrangement est une liste d'éléments distincts.
L'héritage peut-être multiple. La liste à deux fils, le sac et l'arrangement. Cela signifie entre-autre que le sac est une liste particulière, et que l'arrangement est une liste particulière :
L'ensemble à deux pères, le sac et l'arrangement. Cela signifie entre-autre que l'ensemble est un sac particulier, et que l'ensemble est un arrangement particulier :
On définie l'opération d'union, noté `uu`, et s'appliquant aux objets de ces 4 types comme suit :
Ainsi par exemples :
`{a,b}uu{a,c} = {a,b,c}`
`⟨a,b⟩uu⟨a,c,b⟩=⟨a,b,c⟩`
`⟅a,a,b⟆uu⟅a,a,c⟆ = ⟅a,a,a,a,b,c⟆`
`(a,a,b)uu(a,a,c) =(a,a,b,a,a,c)`
On définit l'opération d'union disjointe notée `"+"` , c'est une union qui duplique le jeux des éléments du second membre déjà présent dans le premier membre, pour simuler une union disjoint. Elle s'applique aux objets de ces 4 types. L'opération d'union disjointes, `"+"` se comporte pareillement que l'union à part le fait qu'elle utilise une copie des éléments pour simuler une union disjointe. Ainsi par exemples :
`{a,b}uu{a,c} = {a,b,c}`
`{a,b}+{a,c} = "{a,b,a_1,c}`
`⟨a,b⟩uu⟨a,c,b⟩=⟨a,b,c⟩`
`⟨a,b⟩+⟨a,c,b⟩=⟨a,b,a_1,c,b_1⟩`
`⟅a,a,b⟆uu⟅a,a,c⟆ = ⟅a,a,a,a,b,c⟆`
`⟅a,a,b⟆+⟅a,a,c⟆ = ⟅a,a,a_1,a_1,b,c⟆`
`(a,a,b)uu(a,a,c) =(a,a,b,a,a,c)`
`(a,a,b)+(a,a,c) = (a,a,b,a_1,a_1,c)`
L'union disjointe est une opération de construction très pratique. Considérons par exemple l'ensemble `E={a,b}` alors nous avons :
`E+E+E={a,b,a_1,b_1,a_2,b_2}=E uu E_1 uu E_2`
Les ensembles totalement ordonnés sont des arrangements. Grace à cette opération on peut concevoir facilement des ensembles totalement ordonnée plus sophistiqués tel que `NN"+"NN` où `ZZ"+"ZZ`
Les mathématiques et la logique trouvent leurs fondements dans l'informatique, car le caractère exacte de cet science tient dans les processus d'exécution exacte que constitue la validation des preuves. La vadidation d'une preuve passe par l'exécution d'un programme informatique.
Mais déjà il y a une transcription canonique des énoncés mathématiques en programme informatiques, et qui sont d'arrêt sûr lorsque les possibilités parcourues sont en nombre fini. Nous commençons par nous familiariser avec cette transcription.
On s'autorise à regrouper entre `{...}` une liste d'éléments quelconques pour produire l'ensemble support de cette liste. Autrement dit, ce constructeur d'ensemble `{...}` est une application multi-aire qui prend `n` éléments (ou une liste de `n` éléments) pour retourner l'ensemble support. Ainsi nous avons `{y,x,x} = {x,y}`.
On fait de même avec les arrangements qui sont des ensembles totalement ordonnés. L'ordre des éléments correspond à leur première occurence dans l'appel. Autrement dit, ce constructeur d'arrangement `⟨...⟩` est une application multi-aire qui prend `n` éléments (ou une liste de `n` éléments) pour retourner l'arrangement des premières occurences. Ainsi nous avons `⟨y,x,x,y⟩ = ⟨y,x⟩`
À partir d'ensembles, on construit d'autres ensembles. Par exemple considérons un ensemble `E` et considéront l'ensemble suivant :
`{AA x "∈" E, R(x,x)}`
C'est l'ensemble de tout les termes `R(x,x)` obtenus lorsque `x` parcours `E`. Cet ensemble forme le graphe d'une relation dans `E`. Les arcs de cette relation sont représentés par les termes `R(".,.")` appartenant à cet ensemble. La partie déclarative universelle `AA x "∈" E` correspond ici à un énumérateur de tous les éléments de `E`. Cet ensemble se note aussi comme suit :
`{R(x,x) "/" EE x "∈" E}`
On peut étendre cette notation aux arrangements, en tenant compte de l'ordre dans l'énumération. Considérons un arrangement `A`, la partie déclarative `AA x "∈" A` correspond alors à un énumérateur des éléments de `A` dans l'ordre de `A`. Considérons l'arrangement suivant :
`⟨AA x "∈" A, sigma(x)⟩`
C'est l'arrangement des première occurences des valeurs `sigma(x)` qui apparaissent lorsque `x` parcourt `A` dans l'ordre de `A`, où `sigma` est une application définie sur le support de l'arrangement. Ainsi à partir d'arrangements on construit d'autres arrangements. On voit comment l'analyse combinatoire se rapproche de l'informatique, comment les formules mathématiques dans le domaine finie se traduisent en des programmes d'arrêt sûr.
Dans une formule mathématiques les variables ne désignent que des constantes. On perfectionnement le langage pour permettre aux variables de changer de valeur au cours d'un processus d'exécution. Les variables s'informatisent en quelque sorte. Les propositions sont ainsi transformées en programme informatiques.
Etant donné un ensemble `E`. La création d'un ensemble par l'ajout d'un élément `e`, se note `Euu{e}`. La même opération en mode modification physique se note `e"≫"E`. Elle va ajouter l'élement `e` à l'ensemble `E`. La variable `E` se trouve alors éventuellement modifiée sans avoir changé de nom.
Etant donné un ensemble `E`. La création d'un ensemble par l'ajout d'un élément ou éventuellement de sa copie si déjà présent, se note `E+{e}`. La même opération en mode modification physique se note `e"≫+"E`. Elle va ajouter l'élement `e` ou une copie de `e` si déjà présent noté `e_1` à l'ensemble `E`. La variable `E` se trouve alors modifiée sans avoir changé de nom.
Considérons maintenant un arrangement qui je le rappelle est un ensemble totalement ordonné. Ajouter un élément à cette arrangement consistera s'il n'y s'y trouve pas déjà, à l'ajouter en dernier, faisant que :
`⟨AA x "∈" A, x⟩ = A `
Le même symbole `uu` ou `+` et leur version élémentaire en modification physique `"≫"` ou `"≫+"`, est utilisé, repportant dans les type des arguments (liste, sac, arrangement ou ensemble) la détermination précise de l'opération.
On utilise le symbole `":="` pour procéder à une affectation de variable. L'instruction `x":="v` signifie que la variable `x` est réinitialisée à la valeur `v`.
Les ensembles sont des éléments d'un autre type, du type ensemble, et ils sont implémentés comme des listes physiquements modifiables contrairement à l'élément qui peut être dans certain cas immuable.
Il y a deux sortes d'affectation, l'instruction `A":="B`, après cette instruction `A` et `B` désignent le même ensemble qui est mémorisé quelque part, et l'instruction `A"::="B`, après cette instruction `A` est un second ensemble qui regroupe les mêmes éléments que `B` mais qui est mémorisé à un autre endroit, faisant que la modification physique de `A` ne va pas modifier `B` et réciproquement la modification physique de `B` ne va pas modifier `A`. Par contre la modification physique d'un élément de `A` aura une répercution sur `B` puisque cet élément appartient aussi à `B`.
L'instruction `A"::="B` signifie que la variable `A` est un nouvel ensemble qui a recopier les références aux éléments de `B`. Considérons par exemple :
`M "::=" ⟨⟩`
`AA x "∈" A, x"≫"M`
Après ces instructions la variable `M` est égale à `A`. les deux variables désigne le même ensemble, mais physiquement ils sont distinct, placés à deux endroits distincts de la mémoire. L'expression `AAx "∈" A` est interprété ici comme une boucle "for" où la variable `x` parcourt l'ensemble `A`. Ces instructions sont équivalentes à cette unique instruction qui copie l'ensemble `A` dans `M` :
`M"::="A`
Tandis que l'instruction `M":="A` initialise `M` comme étant l'ensemble `A`, ce qui fait que toutes modification physique de `M` va modifier `A`. Les variables `M` et `A` pointe vers le même objet qu'est cet ensemble.
Le comparateur d'égalité `"=="` ignore les différences d'adresses, ainsi `A"=="M` même si ils ont des adresse différentes.
Il en est de même pour les éléments. Ainsi `a"::="e` crée un élément `e_1` en faisant une copie de l'élément `e`. Les deux éléments sont identiques mais mémorisés en deux endroits distincts. Pour crée un nouvel élément, il convient d'ajouter l'option `"+"`
`e_1":=+"e`
Délors `e_1` n'est plus égale à `e`, mais en constitue une copie constitué par les mêmes références, faisant que toutes modification physique de l'un modifie physiquement l'autre qui n'est qu'une copie distinguée.
Nous avons décrit 4 types d'élément déjà sophistiqués. Recherchons des opérations de construction plus simple qui pourraient permettre de construire ces 4 types. Et essayons d'en proposer un éventail exhaustif, permettant (à isomorphie près) de procéder à toutes les constructions mathématiques combinatoires possibles.
Ainsi nous révèlerons le caractère récurcif de chaque construction, et pourrons programmer leur énumérateur et ainsi les dénombrer.
L'analyse combinatoire se résume à dénombrer tout ce que nous pouvons construire. Et comme, construire c'est programmer, naît l'idée qu'en développant le langage de programmation procédant à ces constructions nous puissions rendre facile le dénombrement des structures.
On part de l'élément natif, ou plus exactement de l'élémentum, un unique élément qui définit le rôle d'élément et qui sert de modèle pour tous les éléments, que l'on duplique en autant d'éléments distincts, pour en suite concevoir différents assemblages formants de nouveaux éléments, que l'on peut dupliquer de nouveau, formants encore de nouveaux éléments. Dupliquer l'élémentum est simple à décrire. Mais un élément peut être déjà le résultat d'une construction. Se pose alors la question, qu'est-ce que la duplication d'un tel élément ? Passe-t-elle par la duplication de tous ses sous-éléments qui ont été utilisés pour sa construction ?
La duplication appparait après l'élémentum originel comme la première opération de construction. Etant donné l'élémentum `e`, on s'autorise à en créer un double noté `s(e)`. Cette opération doit pouvoir se faire pour tout élément `x`, ce qui définit un foncteur unaire libre procèdant à cette transformation, noté `s(".")` où le suffix `(".")` indique l'arité unaire du foncteur.
Pour faire le lien avec le chapitre précédent, le foncteur `s(".")` se programme ainsi :
`s:= { x "|" y":=+"x "|" y}`
Le foncteur `s(".")` est dit libre par rapport à la structure intiale notée `"<"e">"`, car il est ajouté par extension élémentaire pour former la structure libre `"<"e, s(".")">"`. On regroupe entre crochet les éléments générateurs et les foncteurs générateur de la structure.
La définiton du foncteur unaire libre `s` est `s = x"↦"s(x)` où `s(x)` n'a pas d'autre évaluation que le terme scriptural `s(x)` où l'on a remplaçé `x` par sa valeur, où l'on entend par valeur de `x`, une composition d'éléments générateurs et de foncteurs générateurs produisant `x`, et qui est unique dans une structure libre.
A ce stade, la notion d'ensemble n'existe pas encore, seul le programme informatique nous est autorisé. Nous avons un énumérateur qui consiste à énumérer `e, s(e), s(s(e)), ....`. Voici un programme écrit dans un langage impératif qui procède à cette énumération :
`x":="e ";" {x"≫" ";" x":="s(x)}^oo`
Les égalités désignent des affectations, le point-virgule sépare les instructions qui s'exécutent séquentiellement, les instructions regroupées entre braquette `{...}` constitue un bloc de code, lorsque un bloc de code est élevé à la puissance `n` il est exécuté `n` fois, et losrqu'il est élevé à la puissance `oo` il forme une boucle sans fin. L'instruction `x"≫"` envoie la valeur de `x` sur la sortie. Ce faisant, l'exécution de ce programme produit une suite sans fin de valeurs. Ce même programme s'écrit à l'aide d'une grammaire :
`E← {e, s(E)}`
Où l'on a choisi d'utilisé le symbole `"←"` plutot que l'inclusion pour préciser le caractère dynamique de cette définition récursive qui constitue un énumérateur. On crée la structure des entiers naturels, composé d'un élément et d'un foncteur libre appelé successeur, noté `s(".")`. Ce même programme s'écrit à l'aide de la cloture par composition close :
`"<"e, s(".")">"`
Une première construction consiste à créer les entiers :
`0= e`
`1=s(e)`
`2=s(s(e))`
`3=s(s(s(e)))`
...
`n=s^n(e)`
...
Remarquez que `s^n(".")` est un foncteur obtenu par un programme :
`x |-> {x":="s(x)}^n ";" x"≫"`
Le bloc de code `{...}` élevé à la puissance `n` va s'exécuter `n` fois. Si `n` est égale à zéro, le bloc de code n'est pas executé, c'est pourquoi `s^0(x)"="x`.
Notez qu'il sera alors séduisant d'adopter la conversion implicite suivante entre entiers naturels et ensembles d'entiers naturels, lorsque nous aurons défini la structure d'ensemble :
`0= {}`
`1={0}`
`2={0,1}`
`3={0,1,2}`
...
`n={0,1,2,...,n"-"1}`
...
A ce stade, nous ne maitrisons pas la notion d'ensemble. Nous n'avons sous la main que des prograrmmes énumérateurs. C'est en développant des outils informatiques pour manipuler ces énumérateurs que l'on donnera corps à la notion d'ensemble et qu'on la définira comme un type.
Le langage engendré par l'élément `e` et le foncteur libre `s(".")` engendre la structure libre des entiers naturels `NN="<"e, s(".")">"` les braquettes signifiant la clôture par composition close. Mais à ce stade, on ne le perçois que comme un énumérateur `e, s(e), s(s(e)), ...`.
Ainsi nous sommes passés de la structure triviale ne contenant qu'un unique élément `"<"e">"`, par extension élémentaire en lui ajoutant un foncteur unaire libre `s(".")`, à la structure des entiers naturelles `"<"e, s(".")">"`
L'ensembles de tous les éléments n'est pas un ensemble, c'est pourquoi on dispose toujours d'un contexte qui nous place d'office dans un ensemble `E`, dans une structure en cours, et que l'on peut étendre par la suite. Et comme nous nous restreignons aux seuls éléments constructibles, on ne procédera qu'à des extensions constructibles. Dans la structure en cours, tous les éléments sont constructibles, c'est à dire, sont obtenus par au moins une composition close d'opérateurs générateurs et d'éléments générateurs.
Le foncteur transforme tout élément en un élément. Ce qui le distingue d'une application, c'est qu'il peut créer de nouveaux éléments. Le foncteur peut donc étendre la structure en cours. Il définit un procédé constructif d'extension de `E`. Il admet une forme particulière, dite libre, qui correspond à l'extension maximale possible, où chaque image du foncteur crée un nouvel élément indépendant.
On adopte la notation ensembliste des foncteurs qui permet d'appliquer un foncteur `f` sur un ensemble `A` pour produire l'ensemble image `f(A)`
`f(A) = {AAx"∈" A, "f(x)}`
Du point de vue informatique, il faut considérer deux cas, soit on crée un nouvel ensemble `f(A)`, soit on modifie l'ensemble `A` en changeant chaqu'un de ses éléments `x` par `f(x)`. Dans cette première notation les braquettes `{...}` indique que l'on crèe un nouvel ensemble. On notera le deuxième cas par l'instruction `f@(A)`
Considérons par exemple un foncteur unaire libre `s(".")`. Ce foncteur va créer un double de `E` noté `s(E)`, et il va créer un double de `s(E)` noté `s(s(E))` ou `s^2(E)`, et un double de `s^2(E)` noté `s^3(E)` et ainsi de suite. La structure étendue se note `E[s(".")]` en précisant que `s` est libre, et elle correspond à
`E[s(".")] = E+s(E)+s^2(E) +s^3(E)+...`
Où l'opération `"+"` correspond à l'union disjointe.
L'ajout du foncteur unaire à la structure `E` va donc procéder à son extension notée `barE` qui sera dorénavant l'ensemble par défaut où l'on se situe. Le foncteur unaire `f(".")` est alors défini par son graphe, un ensemble de couples d'éléments dans cet ensemble étendu `{AAx, x"↦"f(x)}`. C'est sa définition mathématique, c'est sa sémantique. Mais comme nous n'avons pas encore définit la notion d'ensemble, on le définit par un énumérateur de son graphe, ou ce qui revient au même, par un programme qui procède au calcul `x"↦"f(x)` pour tout élément `x`. Ainsi dans la pratique, on définit un programme qui calcul le foncteur, et il faut avoir à l'esprit que plusieurs programmes distincts peuvent calculer un même foncteur.
Tel que défini, le foncteur n'est pas un élément. C'est un élément d'un autre type, son type est `barE"→"barE`. D'où apparait le concept de type. L'élément est de type `barE` et le foncteur considéré ici est de type `barE"→"barE`
Etant donné une structure `E`. On procéde à une extension élémentaire en ajoutant un foncteur unaire libre `f(".")`. La nouvelle structure `barE` que l'on note `E[f(".")]` ou bien `"<"E,f(".")">"` se définit par la grammaires suivante :
`barE← {E, f(barE)}`
Avec la définition de `f` comme foncteur libre : `f = {AAx, x"↦"f(x)}` où `f(x)` n'a pas d'autre évaluation que le terme scriptural `f(x)` en remplaçant `x` par sa valeur qui est un élément de `bar E`.
L'ensemble `barE` est défini par son énumérateur programmé comme suit :
`E"≫"`
`A"::="E`
`{f(A)"≫"; A":=" f(A)}^oo`
L'instruction `A"::="E` est identique à l'instruction `A"="{}; E"≫"A`
L'instruction `A"≫"B` est identique à l'instruction `AAx"∈"A, x"≫"B`
L'instruction `f(A)"≫"` est identique à l'instruction `AAx"∈"A, f(x)"≫"`
L'instruction `A":=" f(A)"` est identique à l'instruction `(AAx"∈"A, f(x)"≫"B); A"::="B`
Le foncteur `f(".")` propose une implémentation canonique des éléments de `E[f(.)]` sous forme de terme engendré par `f(".")` et par les éléments de `E`. On décrit cette implémentation en présentant la structure `"<"E,f(".")">"` où, `E` étant un ensemble, tous les éléments de `E` sont indiqués comme étant des éléments générateurs de la nouvelle structure.
L'implémentation informatique introduit la notion de modification physique. Les différents objets peuvent être modifiés physiquement. L'objet le plus générale qu'est l'élément de n'importe quel type, est dit de type `Omega`, et peut être désigné par une variable. Cette variable est alors de type `&Omega`, ce qui signifie qu'elle désigne un élément de type `Omega`
La variable est donc le premier objet simple qui a un contenu, et donc qui peut être modifiée. La modification physique de cet objet se fait par les instructions d'affectation du genre `":="`. Et cela est suffisant comme possibilité de notation.
Les éléments, engendrés par duplication de l'élémentum, sont des objets immuables, c'est à dire qui ne peuvent pas être modifiés. Par contre les structures rudimentaires ; listes, sacs, arrangements, ensembles, peuvent être modifiées physiquement.
D'une manière générale, le suffixe `"@"` apposé à un foncteur ou à une fonction appliqué par notation ensembliste sur une structure rudimentaire indique qu'elle agit par modification physique de la structure rudimentaire. Ainsi pour un élément désigné par la variable `x`, l'instruction `f"@"(x)` va retourner une erreur car l'élément est immuable. Par contre, appliqué à une liste, un arranement, un sac ou un ensemble, elle va modifier la structure en changeant les éléments qui la compose `x` en `f(x)`. Exemple :
`A= ⟅a,b,a⟆_sigma`
`f(A) = ⟅f(a),f(b),f(a)⟆_sigma`
`A= ⟅a,b,a⟆_sigma``f"@"(A)`
`A= ⟅f(a),f(b),f(a)⟆_sigma`
L'élément pouvant désigner toute-chose et davantage, le foncteur unaire peut assurément être désigné par un élément, en revanche l'élément n'est pas nécessairement un foncteur unaire. Il est quand même plus simple d'avoir qu'un seul type d'élément. Pour cela il faut donner un même type de second rôle à tous les éléments, le role de foncteur unaire, et uniquement celui-ci c'est à dire sans ajouter de nom, de tel sorte que ce rôle de foncteur unaire doit vraiment identifier l'élément, c'est à dire que deux éléments distincts doivent avoir des rôles de foncteurs unaires distincts.
Cela signifie qu'il existe un foncteur injectif d'un type particulier `varphi` transformant l'élément en un foncteur unaire. Etant donné un élément `x`, l'image `varphi(x)` désigne le foncteur associé à `x`, qui est son second rôle. On notera `varphi(x)(y)` plus simplement par `x(y)`. Et comme `varphi` est injectif, nous avons :
`x"="y` <=> `varphi(x)"="varphi(y)`
`x"="y` <=> `AAz, x(z)"="y(z)`
La structure `E` engendré par un élément `e` et par un foncteur `varphi` d'un type particulier, E->(E->E), se note en une définition récurcive comme suit :
`E="<"e, varphi^(E->(E->E))">"`
Où l'exposant désigne le type de `varphi`. Puis on ajoute la définiton du raccourci d'écriture :
`AA(x,y) "∈" E^2, x(y) "=" varphi(x)(y)`
Et on choisie un `varphi` libre, c'est à dire qui associe à chaque élément un nouveau foncteur libre, ce qui s'écrit `varphi(x) = y"↦"x(y)` dans lequel `x(y)` n'a pas d'autre évaluation que le terme `x(y)` en remplaçant `x` par sa valeur et `y` par sa valeur, où l'on entend par valeur un élément de `E`.
La structure ainsi obtenue s'appelle l'algèbre monogène unaire libre, puisque tout élément peut s'appliquer à un élément pour produire un élément.
`E = {e, e(e), e(e(e)), e(e)(e), e(e)(e(e)), e(e)(e)(e), e(e(e(e))), e(e(e)(e)),...}`
On définit l'opération binaire `"⁎"(".,.")` de syntaxe centrée, appliquant le foncteur associé de premier argument sur le second argument. Quelque soit deux éléments `x,y` nous avons `x"⁎"y = x(y)`
`E = {e, e"⁎"e, e(e"⁎"e), (e"⁎"e)"⁎"e, (e"⁎"e)"⁎"(e"⁎"e), ((e"⁎"e)"⁎"e)"⁎"e), e"⁎"(e"⁎"(e"⁎"e)), e"⁎"((e"⁎"e)"⁎"e),...}`
On constate que `E` est l'ensemble des arbres binaires nus, correspondant au magma libre `"<"e, "⁎"(".,.")">"` que l'on dénomme habituellement par le symbole `bbbA`. Et il contient la structure initiale des entiers naturels qui se plonge en lui comme suit :
`bbbA`
La structure `bbbA` est une structure aussi fondamentale que `NN`. C'est pourquoi de nombreuses propriétés de `bbbA` vont être développées et utilisées comme résultats intermédiaires. L'énumérateur du magma est programmé par la grammaire suivante :
`bbbA← {e, (bbbA"⁎"bbbA)}`
La loi de composition interne du magma `"⁎"` est identique la loi de composition interne de l'algèbre unaire : `AAxAAy, x"⁎"y = x(y)` toujours valable quelques soit le nombre d'éléments générateurs, somme toute, une évidence.
Il existe une transcription canonique des grammaires de Chomsky en machines de Chomsky. Ces machines ont la capacité d'énumérer tous les langages énumérables. On applique cette transcription à un cas plus simple, d'une structure engendrées par une liste d'éléments et de foncteurs. Prenons par exemple la structure libre suivante :
`E= "<"a,b,f("."),g(".,.")">"`
Celle-ci correspond à la grammaire suivante :
`E←{a,b, f(E), g(E,E)}`
On programme la machine de Chomsky de manière à ce que dans le cas de foncteurs libres elle ne recalcul pas plusieurs fois un même élément. Pour cela, on crée plusieurs ensembles `A, B, C` en cours. On commence par énumèrer les éléments générateurs :
`A":="{}`
`{a,b}"≫"; {a,b}"≫"A`
On énumère les termes ne comprenant qu'un seul foncteur :
`B":="{}`
`f(A)"≫"; f(A)"≫"B`
`g(A,A)"≫"; g(A,A)"≫"B`
On énumère les termes ne comprenant que deux seuls foncteurs :
`C":="{}`
`f(B)"≫"C`
`g(B,B)"≫"C`
`g(A,B)"≫"C`
`g(B,A)"≫"C`
On énumère les termes ne comprenant que trois seuls foncteurs :
`D":="{}`
`f(C)"≫"D`
`g(C,C)"≫"D`
`g(A"∪"B,C)"≫"D`
`g(C,A"∪"B)"≫"D`
On voit alors un procédé récurcif possible qui remplace ces 4 dernières instructions par :
`B"≫"A`
`B"::="C`
`C"="{}`
`f(B)"≫"C`
`g(B,B)"≫"C`
`g(A,B)"≫"C`
`g(B,A)"≫"C`
La machine de Chomsky énumérant `E←{a,b, f(E), g(E,E)}` peut se programmer comme suit :
`A":="{}`
`{a,b}"≫"; {a,b}"≫"A``B":="{}`
`f(A)"≫"; f(A)"≫"B`
`g(A,A)"≫"; g(A,A)"≫"B``{`
`C":="{}`
`f(B)"≫"C`
`g(B,B)"≫"C`
`g(A,B)"≫"C`
`g(B,A)"≫"C``B"≫"A`
`B::=C`
`}^oo`
Elle énumère tous les termes d'une structure libre dans l'ordre de complexité mesurée en nombre de foncteurs utilisés. Si la structure n'est pas libre, il convient d'optimiser l'énumérateur en évitant les répétitions. Avant d'émettre un résultat, on vérifie que l'élément n'est pas déjà présent dans `A` ou `B` ou `C`.