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 aboutissant à la valeur rechercher 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, le sac (ou multi-ensemble), l'arrangement, 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 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 mais les répétitions, si. 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 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 ensemble est un sac particulier où tous les éléments sont deux à deux distincs et n'apparaissent qu'une seuls fois. 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 arranements sont équivalents si l'un peut être obtenue de l'autr 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é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.
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 :
`(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)}`
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 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 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 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 :
Et 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 :
On définit l'opération d'union avec duplication, notée `+` , et s'appliquant aux objets de ces 4 types comme suit : L'opération d'union avec duplication, "+"` se comporte pareillement que l'union à part le fait qu'elle utilise une copie de l'éléménent lorsqu'elle rencontre dans le second argument un élément déjà présent dans le premier argument. 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⟩=⟨a,b,c⟩`
`⟨a,b⟩+⟨a,c⟩=⟨a,b,a_1,c⟩`
`⟅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)`
Considérons un 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 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 "∈" A}`
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 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. 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 est immuable. Il y a alors 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`.
L'instruction `A"::="B` signifie que la variable `A` est un nouvel ensemble qui a recopier les é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 même si physiquement ils sont distinct, placé à deux endroits distincts. L'expression `AAx "∈" A` est interprété ici comme une boucle "for" où la variable `x` parcourt l'ensemble `A`. On perfectionne le langage de programmation. Les instructions précédentes sont équivalente à celles-ci :
`M "::=" ⟨⟩`
`A"≫"M`
Et elles 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. La question de se pose pas pour les éléments qui sont par principe non-modifiables.
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 du 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.
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 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éfinit 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'extensions 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.
On adopte la notation ensembliste des foncteurs définie par exemple pour un foncteur `f` et un ensemble `A` comme suit :
`f(A) = {AAx"∈" A, "f(x)}`
Du point de vue informatique, il faut considérer deux cas, dans le premier cas on crée un nouvel ensemble `f(A)`, dans l'autre cas on modifie l'ensemble `A` en changeant chaqu'un de ses éléments `x` par `f(x)`. On notera ce deuxième cas par l'instruction tel que par exemple `"map"(A,f)`
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 et 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'é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 é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`, 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 dans 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, sommme 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)}`
La machine de Chomsky correspond au programme :
---- 1 juin 2025 ----
`{a,b}"≫"`
`A"::="{a,b}`
`{f(A)"≫"; g(L,A)"≫"; A"::=" f(A); g(A,A)"≫"A }^oo`
`L":="{};A":="{};B":="{}`
`a"≫"A;a"≫"`
`b"≫"A;b"≫"`
`{`
`AAx"∈"A, f(x)"≫"V;f(x)"≫"`
`AAx"∈"A,AAy"∈"A, g(x,y)"≫"V;g(x,y)"≫"`
`"@"U"≫"L`
`U"="{};"@"V"≫"U`
`}^oo`
Elle énumère tous les termes d'une structure libre dans l'ordre de complexité. Si la structure n'est pas libre, il convient d'optimiser l'énumérateur en évitant les répétitions :
`L":="{};A":="{};B":="{}`
`a"∉"L "et" a"∉"A => a"≫"A;a"≫"`
`b"∉"L "et" a"∉"A => b"≫"A;b"≫"`
`{`
`AAx"∈"A,f(x)"∉"L "et" f(x)"∉"A => f(x)"≫"V;f(x)"≫"`
`AAx"∈"A,AAy"∈"A, g(x,y)"∉"L "et" g(x,y)"∉"A => g(x,y)"≫"V;g(x,y)"≫"`
`"@"U"≫"L`
`U"="{};"@"V"≫"U`
`}^oo`
Les structures en générale s'obtiennent en quotientant une structure libre par une relation d'équivalence respectant les foncteurs générateurs. Etant donné une relaton d'équivalence `"≈"`. On dit qu'elle respecte les foncteurs `f(".")` et `g(".,.")` si et seulement si : `AAxAAyAAaAAb,`
`x"≈"y => f(x)"≈"f(y)`
`x"≈"y "et" a"≈"b => g(x,a)"≈"g(y,b)`
L'ensemble des classes d'équivalence forme alors la structure quotient. Pour rappel une relation `"≈"` est dite d'équivalence si et seulement si elle est transitive, symétrique et reflexive : `AAxAAyAAz,`
`x"≈"y "et" y"≈"z => x"≈"z`
`x"≈"y => y"≈"z`
`x"≈"x`
Le quotientage de structures non-libres se fait de la même façon.
Etant donnée une relation d'équivalence `"≈"` quelconque, celle-ci engendre une équivalence (plus large ou égale) respectueuse des foncteurs générateurs. On la construit par un algorithme parcourant la structure. Prenons par exemple la structure libre suivante : `E= "<"e,f("."),g(".,.")">"` et considérons une relation d'équivalence `"≈"` définie sur cette structure.
On va construire les classes d'équivalences sous forme d'arbres où la racine de l'arbre sera le représentant de la classe d'équivalence. Chaque élément est associé à un autre élément qui est son successeur dans sa classe. Au dépard, chaque élément est associé à lui-même. Le représentant de l'élément est parmi tous ses successeurs, celui du bout qui est son propre successeur. Puis on parcours tous les couples `(x,y)` d'éléments, et à chaque fois que `x"≈"y` on associe le représentant de `x` au représentant de `y`. En procédant ainsi, on construit les classes d'équivalence sous forme d'arbre.
Le parcours de `E` se fait par ordre de complexité, d'abord les éléments générateurs puis les termes ne comprenant qu'un foncteur générateur, puis ne comprenant que la composition de deux foncteurs générateurs, etc.. On peut alors parcourir `E^2` selon une comlexité en diagonal (de la même façon que l'on parcourt `NN^2`).
On perfectionne l'algorithme pour augmenter la relation d'équivalence juste ce qu'il faut afin qu'elle respecte les foncteurs. Lorsque l'on rencontre un couple `f(x),f(y)` tel que `x"≈"y` alors on fusionne les classes `f(x)` et `f(y)`, en associant le représentant de `f(x)` au représentant de `f(y)`. Et de même, lorsque l'on rencontre un couple `g(x,y),g(a,b)` tel que `x"≈"y` et `a"≈"b` alors on fusionne les classes `g(x,y)` et `g(a,b)`, en associant le représentant de `g(x,y)` au représentant de `g(a,b)`.
---- 31 mai 2025 ----
La grammaire forrmel est un ensemble d'instructions. La grammaire apparait comme deux ensembles finis, un ensemble de mots étendus et un ensemble de règles de réécriture. L'ensemble de mots étendus ne sera utilisé dans l'algorithme d'énumération qu'au cours d'une phase d'intitialisation. La grammaire formelle est traduite en un programme informatique comme suit. la traduction est globalement canonique dans le sens où elle n'introduit pas d'arbitraire non-local. Les mots étendus contenus dans la grammaire sont traités dans la phase d'initialisation. L'ordre arbitraire des règles de la grammaire va bien sûr induire un ordre arbitraire d'énumération du langage mais limité uniquement à chaque cycle.
La liste V accumule les nouveaux mots étendus produits lors du cycle en cours. La liste U contient tous les nouveaux mots étendus produits lors du cycle précédent. Et la liste L contient tous les nouveaux mots étendus produits lors des cycles précédant le cycle précédent. Chaque mot produit possède un niveau de complexité de calcul qui est le numéro de cycle dans lequel il est produit.
---- 30 mai 2025 ----
On donne un second rôle à l'élément qui
Et il est facile de rendre cela possible avec une perte d'information minime. On donne aux éléments `e` qui ne possède pas de rôle de foncteur, un rôle de foncteur unaire particulier.
Et on va choisir la solution la plus libre qui n'entraine aucune perte d'information dans les choix futures, une fonction unaire libre, qui appliqué à tout élément `x` retourne l'élément identifié de façon scriptale par le terme `e(x)`. Ce foncteur se note par son graphe `{AAx, x"↦"e(x)}` dans lequel `e(x)` n'a pas d'autre évaluation que le terme `e(x)`.
4.2.1)
l est identifié à son graphe. Considérons un foncteur unaire `f(".")` quelconque, nous avons :
`f={AAx, x"↦"f(x)}`
`f` n'est ici qu'une variable, le foncteur n'a pas de noms propres révélé dans cette définition, sauf lorsqu'il est un foncteur générique libre, auquel cas, appliqué à un élément quelconque `x` il retourne un terme constitué de son nom appliqué à `x`.
Le foncteur est identifié à son graphe (c'est sa définition mathématique, appelée aussi sa sémantique). Dans la pratique on définit un programme qui calcul le foncteur, et plusieurs programmes distincts peuvent calculer un même foncteur.
on peut donc l'ajouter à notre langage en construction et ainsi agrandire la structure libre en `"<"e,s,s(".")">"`
Dés lors, l'élément `e` ne parait plus indispenssable, et si on le retire du langage, on obtient alors la structure `"<"s,s(".")">"`
Et `s` apparait alors comme le second élément, un foncteur unaire libre. Il en est même le prototype qui servira de modèle pour tous les foncteurs unaires libre. Ainsi `s(s)` constitue un autre foncteur unaire libre.
Le foncteur se distingue de l'élément en ce qu'il n'a pas d'identité propre, il est identifié à son graphe. Considérons un foncteur unaire `f(".")` quelconque, nous avons :
`f={AAx, x"↦"f(x)}`
`f` n'est ici qu'une variable, le foncteur n'a pas de noms propres révélé dans cette définition, sauf lorsqu'il est un foncteur générique libre, auquel cas, appliqué à un élément quelconque `x` il retourne un terme constitué de son nom appliqué à `x`.
Le foncteur est identifié à son graphe (c'est sa définition mathématique, appelée aussi sa sémantique). Dans la pratique on définit un programme qui calcul le foncteur, et plusieurs programmes distincts peuvent calculer un même foncteur.
Ainsi, si `e` n'est pas un foncteur, il devient le foncteur libre de nom `e`, ce qui ce note `e"="{AAx, x"↦"e(x)}` dans lequel `e(x)` n'a pas d'autre évaluation que le terme `e(x)`.
Et le second élément `s` n'a alors plus lieu d'être. On renaît dans une algèbre unaire libre engendrée par un élément `e` jouant le rôle de foncteur unaire libre.
Si on veut rigoureusement un système équivalent, il faut compléter l'algèbre unaire libre ainsi défini par un ensemble de foncteurs libres appartenant à cette algèbre qui représente l'ensemble des éléments qui n'étaient initialement pas des foncteurs.
---- 29/05/2025 ----