Comment présenter l'algèbre de façon constructive par son début ? Cette question se pose également pour l'informatique. Comment au départ définir l'informatique et établir son premier langage ?
Nous utiliserons la théorie de l'information pour donner les premières réponses, pour expliquer les premiers choix de l'algèbre, et pour poser les premières conceptions du langage algorithmique. L'algèbre et l'informatique sont beaucoup plus proches qu'on ne le pense, et au départ de l'algèbre se trouve une conception informatique quasi-innée.
La recherche du langage de programmation canonique nous amène dès le premier abord dans une structure fondamentale qu'est l'algèbre libre engendrée par un élément.
Au départ, il n'y a pas de distinction entre programme et donnée, ni de granulation distinguant donnée et liste de données. On part d'une unique donnée notée `alpha`, qui est donc un programme pouvant s'appliquer sur une donnée pour produire une donnée. Et chaque donnée produite est donc également un programme pouvant s'appliquer à son tour sur une donnée pour produire une donnée, etc....
Le langage doit pouvoir noter ces différentes programmations sans les exécuter. Cela se fait par emboitement, en accolant le terme jouant le rôle de programme au terme jouant le rôle d'argument mis entre parenthèse. Ce nouveau terme ainsi assemblé joue le rôle d'une donnée, mais qui n'est pas encore produite, c'est un programme dont l'exécution va produire cette donnée.
Sans se préoccuper de l'exécution, on construit ainsi un premier langage fondamental qu'est le langage alpha engendré par un unique élément-opérateur-unaire `alpha`. Cela se formalise par les deux axiomes suivants :
(1) `alpha` est un terme.
(2) Tout terme `x` peut s'appliquer à tout terme `y` pour former par emboitement le terme `x(y)`
Exemples de terme du langage alpha : `alpha, alpha(alpha), alpha(alpha(alpha)), alpha(alpha)(alpha), alpha(alpha)(alpha(alpha))`. Il convient de bien distinguer les parenthèses d'appel accolées à un terme jouant le rôle d'opérateur, des prenthèses de priorisation. Ici, il n'y a que des parenthèses d'appel.
On note `L` l'ensemble des termes. Les éléments de cette structure `L` sont des transformations unaires dans `L`, c'est à dire des applications de `L"→"L`. Et on remarquera qu'elles sont toutes injectives. En effet, les termes sont des assemblages d'`alpha` et d'application. Et deux assemblages distincts désignent nécessairement deux éléments distincts. C'est la caractéristique d'engendrement d'une structure libre.
Classiquement on présente de langage alpha sous forme d'une algèbre libre engendrée par un élément générateur `alpha` et par un opérateur binaire d'application notée `"⁎"(".,.")` de syntaxe centrée. Ainsi apparait deux notations, l'écriture classique qu'est celle de l'aglèbre libre, et l'écriture dynamique qu'est celle du langage alpha :
Algèbre libre
Langage alpha
Cet structure `(L,"⁎"`) se nomme précisément « un magma monogène libre » engendré par un élément générateur `alpha` et un opérateur générateur `"⁎"(".,.")` ce qui se note :
`L="<"alpha, "⁎"(".,.")">"`
Le caractère libre précise que deux termes distincts, en tant qu'assemblage distinct d'éléments générateurs et d'opérateurs générateurs, désignent nécessairement deux éléments distincts de la structure. Cela équivaut à dire que l'élément `alpha` est libre vis-à-vis de l'opérateur `"⁎"` (ou inversement) dans `L`.
Et nous associons à chaque élément `a "∈" L`, l'application `(x|->a"⁎"x) in (L "→" L)`, de telle sorte que la notation dynamique `a(y) = a"⁎"y` puisse s'ajouter au langage de la structure `L` sans rien modifier de la structure.
L'algèbre libre `"<"alpha, "⁎"(".,.")">"` définissant le langage alpha, contient par plongement et par quotientage toutes les algèbres qui sont engendrées par un ensemble dénombrable d'éléments et d'opérateurs. Cela se démontre comme suit :
Considérons par exemple une structure `A` engendrée par `a,b,c,f("."),g(".,.")`. Considérons des copies libres de `a,b,c,f("."),g(".,.")` notées pareillement. La structure engendrée par ces copies libres forme l'algèbre libre `"<"a,b,c,f("."),g(".,.")">"`. C'est l'ensemble des compositions closes avec ces éléments et opérateurs générateurs. Si nous quotientons cette structure libre par les définitions des opérateurs sur `A`, on obtient alors la structure `A`.
Puis, la structure libre `"<"a,b,c,f("."),g(".,.")">"` se plonge dans la structure libre `"<"alpha, "⁎"(".,.")">"` pour des raisons canoniques liées à la notion de structure libre :
La structure libre étant définie à partir d'éléments générateurs libres et d'opérateurs générateurs libres, c'est à dire sans poser aucune contrainte d'égalité (où toutes assemblages distincts désignent nécessairement un éléments distinct), une composition dans cette structure libre désigne un nouvel élément libre vis-à-vis des autres opérateurs. Ainsi les trois éléments générateurs de la première structure `a,b,c` sont plongeables sur trois nouveaux éléments de l'autre structure créés à chaque fois par un appel d'`alpha` sur trois éléments distincts quelconques `alpha(e_1)`, `alpha(e_2)`, `alpha(e_3)`. Et on peut choisir au plus simple, par exemple : `alpha"⁎"alpha`, `alpha"⁎"(alpha"⁎"alpha)`, `alpha(alpha"⁎"(alpha"⁎"alpha))`. En notation dynamique, `alpha(alpha)`, `alpha(alpha(alpha))`, `alpha(alpha(alpha(alpha)))` que l'on note simplement `alpha(alpha)`, `alpha^2(alpha)`, `alpha^3(alpha)`. Et ce plongement respecte bien la loi de composition.
On plonge l'opérateur unaire `f(".")` sur un nouvel élément `f` que l'on interprète comme un opérateur unaire :
`f = (x|->f"⁎"x)`
On plonge l'opérateur binaire `g(".,.")` sur un nouvel élément `g` que l'on interprète comme un opérateur binaire définie par curryfication :
`g = (x,y|->(g"⁎"x)"⁎"y)`
Les éléments images de ces opérateurs constituant de nouveaux éléments dans une structure libre, aucune contrainte d'égalité ne pèse sur eux, et la traduction de `A` vers `L` restant alors injective constitue bien un plongement.
La demonstration s'étend aux cas des algèbres libres engendrées par un ensemble énumérable d'éléments et d'opérateurs libres, en prenant comme suite de nouveaux éléments libres:
`alpha(alpha), alpha^2(alpha), alpha^3(alpha),....,alpha^n(alpha),....`
L'élément `alpha(".")` joue le rôle d'énumérateur des éléments et opérateurs générateurs libre. On perçoit ainsi le pouvoir expressif considérable que peut porter une opération binaire `"⁎"(".,.")` non-associative.
L'algèbre libre `"<"alpha, "⁎"(".,.")">"` s'appelle le magma monogène libre.
Dans les fondements de l'algèbre que nous avons posées, nous avons utilisé quatres notions importantes que sont la loi binaire `"⁎"(".,.")`, la currifycation pour définir les opérateurs multi-aires, le plongement (c'est à dire le morphisme injectif) comme lien d'inclusion entre deux magmas, et le quotientage par une relation d'équivalence qui étend la notion d'égalité.
La loi `"⁎"` étant binaire, elle possède une loi symétrique notée `"⋆"` qui est définit en permutant les arguments de la loi :
`x"⁎"y = y"⋆"x`
Le magma définit par cette loi possède ainsi une image symétrique. On l'appelle le magma opposée, `"<"alpha, "⋆"(".,.")">"`
La currifycation permet de définir à partir de la loi binaire `"⁎"(".,.")`, des opérateurs d'arité plus grande. Exemple :
`f(x,y,z,t) = (((f"⁎"x)"⁎"y)"⁎"z)"⁎"t`
Le principe en est simple : L'opérateur quaternaire doit s'appliquer aux argument `x,y,z,t`. On étend la syntaxe pour qu'il puisse s'appliquer à un nombre inférieur d'arguments. S'il ne s'applique seulement qu'au premier argument `x` alors il produirant l'opérateur ternaire restant `f(x) = (y,z,t |-> f(x,y,z,t))`, et s'il s'applique seulement au deux premiers arguments `x,y` alors il produira l'opérateur binaire restant `f(x,y) = (z,t |-> f(x,y,z,t))`, etc.. Ainsi, nous avons `f(x,y,z,t)` `=` `f(x)(y,z,t)` `=` `f(x)(y,z)(t)` `=` `f(x)(y)(z)(t)` et nous avons aussi f(x)(y)` `=` `f(x,y), etc..
L'expression `f(x,y,z,t)` énumère les arguments de `f` séparés par des virgules. Délors, la virgule apparait comme un nouvel opérateur binaire canonique qui possède la propriété innée d'être associative, d'où l'absence de parenthèse dans la séquence des arguments d'un opérateur.
D'où vient cette propriété d'associativité ? Est-ce la même que celle propre à la composition d'opérateurs unaires ? Oui.
Considérons un opérateur quaternaire appliqué à 4 arguments `f(x,y,z,t) = (((f"⁎"x)"⁎"y)"⁎"z)"⁎"t`. Considérons la loi opposée `"⋆"`. L'égalité précédente s'écrit `f(x,y,z,t) = t "⋆"(z "⋆"(y"⋆"(x"⋆"f)))` et correspond à une composition d'opérateurs unaires `t[z[y[x[f]]]]` dans le magma opposée. Notez que l'on utilise des parenthèses d'appel `( )` dans le magma, et d'autres parenthèses d'appel `[ ]` dans le magma opposé. Il s'agit bien d'une composition d'opérateurs unaires, qui est par nature associative, et que l'on peut écrire en notation anglaise `(t"⋄"z"⋄"y"⋄"x)[z]`. Par convention on distingue les opérations dans le magma de celles dans le magma opposé comme suit :
Loi de composition Composition d'opérateurs unaires Appel unaire Appel binaire
Et nous avons les propriétés suivantes : `AAxAAyAAz,`
`(x"∘"y)(z)=x(y(z)) = x "⁎"(y"⁎"z) = (z"⋆"y)"⋆"x= z[y][x] = z[y,x]`
`(x"⋄"y)(z)=x[y[z]] = x "⋆"(y"⋆"z) = (z"⁎"y)"⁎"x= z(y)(x)=z(y,x)`
Les mathématiques s'appuient classiquement sur la théorie des ensembles plutôt que sur la linguistique, c'est pourquoi l'ensemble y joue un rôle central, prépondérant, ainsi que les applications et les produits cartésiens d'ensembles. Les types basées sur les ensembles, les applications et les produits cartésiens, vont proposer différents rôles possibles pour un élément comme autant d'éléments distincts.
On représente un ensemble par une lettre `M`. On peut délors concevoir l'ensemble des couples d'éléments de `M` que l'on note `M"×"M`. Puis on peut concevoir l'ensemble des transformations de `M` c'est à dire des applications de `M` vers `M`, que l'on note `(M->M)`. Puis on peut concevoir l'ensemble des applications de `M"×"M` vers `M` qui se note `(M"×"M->M)`, puis les applications de `M` vers l'ensemble des applications de `M` vers `M` qui se note `(M->(M->M))`, et ainsi de suite.
On adopte différente notation :
`(A"×"B)` : Ensemble des couples composés d'un premier élément de `A` et d'un second élément de `B`.
`(A->B)` : Ensemble des applications de `A` vers `B`.
`(A↪B)` : Ensemble des injections de `A` vers `B`.
`(A↔B)` : Ensemble des bijections de `A` vers `B`.
Et pour une application `f` de `A` vers `B`, pour toutes parties `X` de `A`, nous définissons l'image par `f` de `X` comme l'ensemble des images par `f` des élément de `X` :
`f(X) = {f(x) | x "∈" X}`
On considère un magma quelconque `(M, "⁎")`, c'est un ensemble `M` munie d'une loi quelconque `"⁎"` apparenant à `(M"×"M->M)`. Les éléments du magma se comportent comme des transformations de `M` c'est à dire des applications appartenant à `(M->M)`, en les faisant agire sur `M` par transformation à gauche.
Pour chaque élément `e "∈" M`, nous avons identiifé l'élément à un opérateur unaire, `e=(x|->e"⁎"x)`, qui est appelé une transformation à gauche (car on procède à cette transformation en multipliant l'entrée `x` par l'élément `e` placé à gauche de `x`). ce qui nous permet d'écrire `AAx "∈" M,` `e(x) = e"⁎"x`.
Les mathématiques préfèrent rendre explicite les deux rôles et leur lien. Cela se fait en définissant une autre notation pour les éléments `e` de `M` lorsqu'ils jouent le rôle d'opérateur unaire. Et par symétrie on considères aussi les transformations à droites : `AAe, AAx`,
`I_e =(x|->e"⁎"x)`
`D_e=(x|->x"⁎"e)``I_e(x) = e"⁎"x`
`D_e(x) = e"⁎"x `
L'application `I` (izquierda en espagnol, gauche en français) qui envoit l'élément `e` sur l'opérateur `I_e` appartient à `(M->(M->M))`, et de même pour l'application `D` (derecha en espagnol, droite en français) qui envoit l'élément `e` sur l'opérateur `D_e` :
`I = (e|->(x|->e"⁎"x))`
`D = (e|->(x|->x"⁎"e))`
Les éléments de `M` en tant qu'opérateurs unaires, muni de la composition de fonction `"∘"` forme un magma muni d'une loi `"∘"` associative. Commment appelle-t-on cette structure. Posons la question à ChatGPT :
Étant donné un magma `(M,"∗")`. Chaque élément `e` du magma `M` est associé à une application envoyant chaque élément `x` de `M` sur `e"∗"x`. L'ensemble de ces applications muni de la loi de composition forme un semi-groupe. Comment se nomme ce semi-groupe vis-à-vis du magma `M` ?
Très bonne question ! Soit `(M,"∗")` un magma.
À chaque élément `e"∈"M`, on associe l’application à gauche :`I_e : M→M, I_e(x)=e"∗"x`.
L’ensemble
`I(M)={I_e "|" e"∈"M}`
est un ensemble de transformations (applications de `M` dans lui-même).
Munissons-le de la composition de fonctions :`(I_e∘I_f)(x)=I_e(I_f(x))=e"∗"(f"∗"x)=(e"∗"f)"∗"x=I_(e"∗"f)(x)`
1) Si la loi `"∗"` du magma est associativealors la correspondance
`e↦I_e`
est un homomorphisme de semi-groupes de `(M,"∗")` vers `(I(M),"∘")`.
Ainsi, `(I(M),"∘")` est un semi-groupe isomorphe à l’image gauche de `M`.
2) Nom de ce semi-groupeCe semi-groupe s’appelle le :
semi-groupe des translations à gauche
(ou semi-groupe régulier à gauche ou encore semi-groupe des opérateurs à gauche) du magma `(M,"∗")`On le note parfois :
`I(M)={I_e "|" e"∈"M}⊆M^M`
`"∗"` n'étant pas associatif, on ne peut pas conclure que `I_e ∘ I_f = I_(e"∗"f)`.
On a seulement `(I_e ∘ I_f) (x) = e"∗"(f"∗"x)`.
Réflexion durant 8s
Je dois reconnaître la correction et préciser le nom approprié dans un cas non associatif : le cas de la représentation à gauche pour un magma. La composition semble toujours associative, mais il faut vérifier la clôture. Sans associativité, la composition peut ne pas être dans l'ensemble.
Le semigroupe généré par les translations à gauche est le semigroupe des transformations à gauche d’un magma, noté `"<"I_e "|" e"∈"M">"`, et est inclus dans `T(M)` sous composition. Ce semigroupe est bien défini, mais sa clôture ne doit pas nécessairement être vérifiée. En général, on l'appelle semigroupe des translations à gauche ou semigroupe régulier des transformations à gauche.
Tu as tout à fait raison : sans associativité, on n’a pas en général `I_e∘I_f=I_(e"∗"f) ` (on a seulement `(I_e∘I_f)(x)=e"∗"(f"∗"x)`). Du coup, l’ensemble `{I_e "|" e"∈"M}` n'est pas forcement clos pour la composition.
Le bon objet à considérer est alors :
le semigroupe des translations à gauche (ou semigroupe régulier des transformations à gauche) du magma `(M,"∗")`,
`S_I(M) = "<"I_e "|" e"∈"M">"subeM^M`
c'est-à-dire le sous-semigroupe de transformations de `M` engendré par les `I_e` (composition de fonctions).
- Si `∗` est associative, alors `S_I(M)={I_e "|" e"∈"M}`,
et l'application `e↦I_e` est un homomorphisme de semi-groupes avec `I_e∘I_f=I_(e"∗"f)`.
- En général (magma non associatif), on garde le nom ci-dessus, mais on insiste sur « semigroupe engendré par les translations à gauche ».
On définit de même le semigroupe des translations à droite `S_D(M)="<"D_e | e"∈"M">"` où `D_e = (x↦x"∗"e)`.
Le semi-groupe (aussi appelé demi-groupe) se définit comme étant un magma dans lequel la loi de composition est associative.
Tout demi-groupe monogène libre est isomorphe à `(NN"*","+")`. Et lorsque les éléments sont tous inversibles (ici dans l'exemple, la loi étant l'addition, nous dirons tous opposables) cela s'appelle un groupe. Tout groupe monogène libre est isomorphe à `(ZZ,"+")`.
Les applications de la forme `(x|->e"∗"x)` sont appelées les transformations à gauches du magma `M`, et ceux de la forme `(x|->x"∗"e)` sont appelées les transformations à droite du magma `M`,
L'application `I` (comme Izquierda en espagnol) de `M` vers `(M->M)` transforme l'élément `e` en la transformation à gauche `I_e=(x|->e"∗"x)`
L'application `D` (comme Derecha en espagnol) de `M` vers `(M->M)` transforme l'élément `e` en la transformation à droite `D_e=(x|->x"∗"e)`
L'ensemble image, `I(M) = {I_e "|" e "∈" M}` regroupe toutes les transformations à gauche. Il n'est pas forcement clos par composition d'applications. ll s'appelle l'ensemble des translations à gauche de `M`. Sa clôture par composition s'appelle le semigroupe des translations, et se note : `S_I(M)` `=` ` "<"I_e, "∘" "|" e "∈" M">"`, le pipe `|` permet d'indiquer que l'ensemble regroupe toutes les translations gauches `I_e` pour `e` parcourant `M`. Et les crochets désigne la cloture par composition close. On le note également par `S_I(M)` `=` `"<"I(M), "∘"">"`, les ensemble figurant entre crochet sont concaténés à l'énumération des éléments et opérateurs.
`S_I(M)="<"(x|->e"∗"x), "∘" "|" e "∈" M">"`
`S_I(M)="<"(x|->(x|->e"∗"x))(M), "∘"">"`
Contrairement à ChatGPT on préfère expliciter l'opérateur utilisé `"∘"` dans la structure. Ainsi, la structure `(S_I(M), "∘")` est associative mais n'a pas forcément d'élément neutre. Cela s'appelle un semi-groupe. De même le semi-groupe des translations à droites se note :
`S_D(M) = "<"(x|->(x|->x"∗"e))(M), "∘"">"`
On s'interesse à la forme de la structure, et non à l'identité de ses éléments ni de sa loi. On dira que deux structures sont de même forme s'il y a un moyen de traduction passant de l'une à l'autre sans que cela ne change aucune propriété propre à la structure. Autrement-dit, considérons un observateur se situant dans la structure `A`, il constatera les lois dans cette structure. Puis transférons-le par traduction dans l'autre structure. L'observateur constatera les mêmes lois et ne pourra donc pas savoir dans quelle strructure `A` ou `B` il se trouve. Une telle traduction correspond un morphisme bijectif autrement-dit un isomorphisme entre les deux structures. Considérons un magma `(A,"∗")` et un magma `(B,"•")` et considérons une application `f "∈" (A->B)`. On dit que `f` est un mophisme de `(A,"∗")` sur `(B,"•")` si et seulement si : `AAx,AAy,`
`f(x"∗"y)= f(x)"•"f(y)`
Et nous n'avons pas précisé le type de `x` et de `y` qui est en faite déterminé par inférence à partir du type de `"∗"` qui est `(A"×"A->A)`, du type de `f` qui est `(A->B)`, et du type de `"•"` qui est `(B"×"B->B)`
La structure, comme en informatique, définit un espace de noms. De telle sorte que le même symbole d'opérateur `"⁎"` peut être utilisé dans plusieurs structures, par exemple `(A,"⁎")` et `(B,"⁎")`. Et lorsque une expression peut être interprétée de deux façons possibles, on lève l'ambiguité en mettant en indice la structure à laquel l'opérateur appartient, par exemple : `x"⁎"_Ay` ou `x"⁎"_By`. Dans le premier cas cela en
`f(x"∗"y)= f(x)"∗"f(y)`
Et nous n'avons pas précisé le type de `x` et de `y` qui est en faite déterminé par inférence à partir du seul type de `f` qui est `(A->B)`.
Posons la question à ChatGPT
Étant donné un magma `(M,"⁎")`. On défini le magma opposé `(M,"•")` comme suit : Existe-t-il un isomorphisme de magma entre `(M,"⁎")` et `(M,"•")` ?`AAx,AAy, x"•"y = y"⁎"x`
Réflexion durant 31s J'étudie si les projections à gauche et à droite des magmas peuvent être isomorphes. Puisque φ(x * y) = φ(y), la condition de bijection n'est pas satisfaite. La contradiction apparaît lorsqu'on compare les projections à gauche et à droite. Il n'y a donc pas d'isomorphisme entre elles dans les magmas en général. Cela n'est vrai que pour certains cas particuliers, comme les groupes.
Pas en général.
Clarifions la condition
Un isomorphisme `f : (M,"⁎")→(M,"•")` doit vérifier, pour tout `x,y∈M`,
`f(x"⁎"y)=f(x)"•"f(y)=f(y)"⁎"f(x)`
Autrement dit, `f` est un anti-automorphisme de `(M,"⁎")`.
Contre-exemple
Prenez un ensemble `M` avec au moins deux éléments, par exemple `M={0,1}`, et définissez la loi ∗ comme suit :
`x"⁎"y:=x` (projection à gauche).
Alors le magma opposé `(M,"•")` est donné par
`x"•"y:=y` (projection à droite),
puisque `x"•"y=y"⁎"x=y`.
S’il existait une bijection `f : M→M` telle que `f(x"⁎"y)=f(x)"•"f(y)`, on aurait
`f(x"⁎"y)=f(x)"•"f(y)=f(y)`
Mais ici `x"⁎"y=x`, donc `f(x)=f(y)` pour tous `x,y`, ce qui force `f` à être constante, donc non bijective. Contradiction.
Il n’existe donc aucun isomorphisme dans ce cas.
`(M,"⁎")≇(M,"•")`
Quand un isomorphisme existe-t-il ?
Il existe précisément lorsqu’il y a une bijection `f :M→M` telle que
`f(x"⁎"y)=f(y)"⁎"f(x)` (anti-automorphisme)
Exemple où c’est vrai :
Groupes : `f(g)=g^-1` donne `f(x"⁎"y)=y^-1"⁎"x^-1=f(y)"⁎"f(x)`, donc tout groupe est isomorphe à son opposé.
Conclusion. La proposition est fausse pour un magma arbitraire ; elle devient vraie sous une hypothèse supplémentaire garantissant l’existence d’un anti-automorphisme.
La notion de forme d'une structure peut être encore généralisée en intégrant cette symétrie. On dira que deux srtructures de magma ont même forme s'il existe un isomorphisme ou un anti-isomorphisme entre les deux. Et cela signifiera que les propriétés d'une telle forme auront deux représentations possibles selon un anti-isomorphisme (c'est à dire en permutant les arguments de la loi), et que seulement l'une des deux représentation est affirmée.