Une strucure algébrique est un ensemble d'éléments `E`, dit ensemble sous-jacent, munie d'opérateurs de type `E^n->E`. Exemple de structure algèbrique :
`(E, s("."), f(".,."),g(".,."))`
Cette forme de structure (à l'aide d'un mécanisme de réécriture dont nous montrons un exemple) comprend des structures de définition plus générale. Par exemple, considérons une structure où chaque élément est une fonction appartenant à `(E"×"E)->(E->(E"×"E))`, c'est à dire une fonction s'appliquant à un couple d'éléments de `E` pour produire une fonction qui appliquée à un élément de `E` produit un couple d'éléments de `E`. On traduit cette situation en redéfinissant une structure sur l'ensemble sous-jacent `E` et en ajoutant simplement deux opérateurs `U: E^4->E` et `V: E^4 -> E` définit comme suit : `a(b,c)(d)` `"="` `(U(a,b,c,d),V(a,b,c,d))`. La nouvelle structure se définit alors par `(E, U(".,.,.,."), V(".,.,.,."))`.
C'est pourquoi ce genre de structure appelé structure algèbrique joue un rôle centrale dans la constuction des mathématiques. A chaque structure algèbrique est associée un langage algèbrique où les termes sont des compositions closes d'opérateurs et d'éléments de la structure. Ce langage correspond à une structure libre plus grande. Prenons par exemple la structure, `(E, s("."), f(".,."))`. Elle donne naissance au langage défini par la grammaire suivante :
`L ← {E, s(L),g(L,L)}`
Et ce langage constitue une structure libre beaucoup plus grande `(L, s("."), f(".,."))` avec `EsubL`. Elle est libre au sens où deux termes distinct désignent toujours deux éléments distincts dans la structure `L`. Les opérateurs `s` et `f` portent les mêmes noms dans les deux structures `E` et `L`. Si on souhaite les différencier, ce qui est nécessaire s'ils s'appliquent à des éléments appartenant à la fois à `L` et `E`, alors on indice l'opérateur avec le nom de sa structure. Par exemple si `E= {a,b,c}` alors nous pouvons écrire :
`L= {a, c, s_L(a), s(s_L(b)), f_L(a,a), f(c,s_L(b)), f(f(a,s_L(b)),c),...}`
Par convention, l'engendrement d'une telle structure libre se note en mettant entre crochet les générateurs :
`L ="<"E, s("."), f(".,.")">"`
La structure `E` est le quotientage de structure libre `L` par la théorie d'égalité des opérateurs de `E` qui sont prolongés par les opérateurs de `L`. Autrement-dit les opérateurs de `E` et les opérateurs `L` coïncident sur `E`.
`(E, s("."), f(".,.")) = ("<"E, s("."), f(".,.")">")/({AA(x,y) "∈" E^2, s_L(x) = s_E(x), f_L(x,y) = f_E(x,y)})`
La recherche de la forme normale constitue une question extrêmement générale pour les structures algèbriques exprimables.
Avant de définir une forme normale des éléments on doit d'abord définir une expressions possibles des éléments. Dans une structure algèbrique, les éléments n'ont pas nécessairement d'expression. Celle-ci vient en complérment de la définition de la structure. Un complément qui donne à chaque élément des expressions possibles dans un langage algèbrique (qui constitue lui-même par définition une structure algébrique libre).
L'expression de l'élément est un terme du langage, il est appelé le "signifiant". L'élément désigné par le terme est appelé le "signifié". La fonction de désignation `varphi` s'applique à un terme du langage pour retourner l'élément qu'il désigne. Elle s'applique au signifinant pour produire le signifié.
---- 14 octobre 2025 ----
L'élément est exprimable dans ce langage s'il existe au moins un terme qui le désigne. La structure est exprimable dans ce langage si tous ses éléments sont exprimables dans ce langage.
Ainsi dans le cas général, une structure algébrique `S` exprimable dans un langage algèbrique `L` comprend une fonction surjective `varphi` qui appliquée à un terme du langage `L`, soit n'est pas définie, ou bien produit un élément de la structure `S`. La surjectivité est demandée pour que chaque élément de la structure soit désigné par au moins un terme.
Il y a alors deux concepts clés que sont la séparabilité des éléments et la forme normale des éléments.
La structure exprimée dans le langage `L` est dite séparable, si quelque soit deux éléments de la structure, connaissant une expression de chacun d'eux `x,y` dans `L`, il existe un algorithme, autrement-dit un procédé calculatoire s'appliquant aux expression `x` et `y`, qui se termine toujours en un temps fini en répondant oui ou non à la question : "`x` et `y` désignent-il le même élément de la structure ? ", `varphi(x)=varphi(y) ?`
Avec la séparabilité est défini une relation d'équivalence sur `L`. Chaque classe d'équivalence correspond à un élément de la structure, et il y a une classe supplémentaire de tous les termes pour lesquels la fonction de désignation `varphi` n'est pas défini. La structure s'obtient en quotientant le langage `L` par cette relation d'équivalence. L'élément coorrespondant à la classe des termes ne désignant rien correspond à l'élément conceptuel `"FALLAR"` que retourne une fonction lorsqu'on l'applique en dehors de son domaine de définition.
---- 14 octobre 2025 ----
Le raisonnement est un calcul. Dire qu'il existe un calcul pour déterminer si x=y ou non à partir de leur expression dans `L`, C'est identique que de dire qu'il existe une théorie `T` de langage `L` tel que T démontre x=y si x et y
Un cas plus simple mais qui s'avère tout aussi puissant, utilise le propre langage de la structure à la quel on ajoute une liste d'élément générateur, pour donner des expressions à chaque élément, et pour contenir l'éventuelle forme normale.
Une forme normale se définit de façon générale comme suit. On dit qu'une struture admet une forme normal
un procédé de construction exhaustif et un procédé de constrution de la forme normal à partir de l'expression d'un élément
---- 7 septembre 2025 ----
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`
Considérer les quantitées modulo `n` de chaque élément d'un sac permet de définir ce qu'est un sac modulo `n`. Chaque éléments dans un sac modulo `n` ne peut être répété qu'au plus `n"-"1` fois. Et si on met un nouvel élément n fois dans un sac modulo `n`, le résultat est un sac modulo `n` qui n'en contient pas.
Les arrangement, les sac et les ensembles sont des structures présenté ici précédement décrite
Par exemple, considérons un sac composé de `a` modulo `n_a`, de `b` modulo `n_b`, et de `c` modulo `oo`, les quantités sont mesurée à des modulo près spécifique pour chaque élément. Les éléments sont mis dans le sac et se combinent uniquement avec eux-même en un groupe cyclique.
Considérer les quantitées d'élément identique comme valant `0,1,2,...,n,n"+"1,...,m` où la valeur `m` est ramené à la valeur `n`. C'est la loi de composition d'un monoïde monogène. Les éléments sont des `sf"poêle"(n,m)` c'est à dire engendre chacun un monoïde de `m` valeurs entières où `m"="n`.
Par exemple, un sac composé de `a` qui constitue une `sf"poêle"(n,m)`, de `b` modulo `3`, et de `c` modulo `oo`, les quantités sont mesurée selon des poêles (monoïdes monogènes) spécifiques pour chaque élément. Les éléments sont mis dans le sac et se combinent uniquement avec eux-même en un monoïde monogène.
Les résultats précédents s'appliquent aux listes. L'ordre des premiers éléments est maintenue
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`.