Une relation est un ensemble de couples `(x,y)`. Autement dit, relation et graphe sont synonymes. Chaque couple `(x,y)` désigne un arc orienté partant de `x` pour aller sur `y`.
Vous aurez remarqué que l'on n'a pas défini ce que l'on entendait par ensemble ni par éléments. C'est le propre du point de vue élémentarien de ne pas restreindre en apparence le domaine de ses constructions. Car il les restreint d'une manière principielle, en s'appuyant sur le seul principe constructif pour en assurer sa cohérence. Ce principe se résume à exclure les objects mathématiques possèdant une quantité d'information infinie.
En effet, de tels objects paraissent physiquement absurdes car ils possèderaient une masse infinie...
En dehors de la question byzantine de savoir si ces objets peuvent exister ou non, il faut rappeller que ce principe n'est qu'un point de vue, n'est qu'un autre éclairage... Et il existe une traduction entre les mathématiques acceptant l'axiome du choix (c'est à dire utilisant des objects possédant une quantité d'information infinie) et celles réfutant l'axiome du choix. De telle sorte que ni l'une ni l'autre n'apporte plus. Seul la prosopopée change. Seul le débat sur la pertinence des concepts et leur appellation prend d'autres voix, et c'est bien là le sens politique qui est en jeu.
Il n'est pas nécessaire de faire référence à l'infini, aux Dieux, à la transcendance, aux étoiles d'or sur fond bleu ou blanc, à une prétendue légitimité divine, une immanence infini... Les mathématiques aussi prétentieusement exactes ne peuvent prétendre, pas plus que nul autre, poser le mystère de l'existence du monde et de nous-mêmes. Elles ne font qu'effleurer ces grandes énigmes comme tout art.
La relation `f` est dite fonctionnelle, c'est à dire constitue une fonction, si et seulement si pour tout élément `x`, soit il n'y a pas d'arête qui part de `x`, ou soit il n'y en a qu'une seul. Et cette arête détermine alors une unique image de `x` que l'on note `x_f` ou que l'on note `f(x)`. C'est pourquoi on qualifie aussi cette relation de déterministe. Les 5 concepts ; fonction, relation fonctionnelle, graphe fonctionnel, relation déterministe, graphe déterministe, sont synonymes.
On note `x |->_f y` pour indiquer qu'il existe une arête (dans la graphe de la fonction `f`) qui part de `x` pour aller en `y`, autrement dit `f(x)` existe et est égale à `y`.
On décrit la fonction selon sa capacité à nous faire déplacer d'un élément à un autre, en respectant le sens des arêtes. Mais il se peut qu'aucune arête ne parte de `x`, auquel cas `f(x)` n'existe pas. Et c'est embêtant d'avoir un langage qui exprime quelque chose qui n'existe pas..., cela complexifie inutilement la programmation, la construction des algorithmes, en obligeant à tester si l'élément existe avant de pouvoir l'utiliser. Pour remédier à cela, on transforme la fonction en une application. Si un point `x` ne fait pas parti du domaine de `f`, c'est à dire s'il n'existe pas d'arc dans `f` partant de `x` où autrement dit si `f(x)` n'existe pas, alors on considère qu'on ne peut pas se déplacer ailleur que sur `x`. Cela revient à ajouter un arc partant de `x` pour aller sur `x`. L'image de `x` par defaut est alors `x` lui-même. Par défaut `f(x)=x`. La fonction ainsi obtenue devient une application définie partout, c'est à dire du point de vue élémentarien définie sur toutes les constructions possibles.
Une autre façon de procéder sans faire ce choix topologique de permettre de faire du surplace lorsqu'il n'y a pas d'arête, consiste à transcrire l'inexistance à l'aide d'un symbole. Et on choisie le symbole `"FAIL"` qui dénote l'échec du calcul à vouloir déterminer une image. Ainsi lorsque `f(x)` n'existe pas, nous dirons que `f(x) = "FAIL"`. Cela consiste à ajouter un élément, l'élément `"FAIL"`, et à étendre toutes les fonctions en donnant comme image à tous les éléments en dehors de leur domaine la valeur `"FAIL"`. Noter que cette extentions des fonctions n'occasionne aucune perte d'information contrairement à la première méthode.
Il apparait une opération fondamentale sur les fonctions qu'est la composition de fonctions, et que l'on note de façon française par absence de symbole, ou bien de façon anglaise à l'aide du symbole `@` en inversant l'ordre des arguments.
`fg = g@f`
Considérons trois fonctions `f,g,h`. Considérons l'expression suivante :
`x |->_f y |->_g z |->_h t`
Cela signifie qu'il existe une arête dans `f` (entendez dans le graphe de la fonction `f`) partant de `x` pour aller sur `y`, qu'il existe une arête dans `g` partant de `y` pour aller sur `z` et qu'il existe une arête dans `h` partant de `z` pour aller sur `t`, autrement dit :
`y_g = z`
`z_h = t`
`z=g(y)`
`t = h(z)`
On remarque que la composition d'application est associative. C'est pourquoi il n'est pas nécessaire de mettre des parenthèses pour préciser l'ordre d'évaluation. En notation française la composition `f(gh)` est égale à `(fg)h` et est notée simplement `fgh`. En notation anglaise la composition `h@(g@f)` est égale à `(h@g)@f` et est notée simplement `h@g@f`. Nous avons :
` fgh = h@g@f`
On peut se poser la question de savoir si le rôle que joue l'élément `x` peut être intégré au rôle que jouent les fonctions `f,g,h`. Autrement dit nous pourrions considérer une fonction `alpha` qui serait associée à l'élément `x` et considérer la composition `alpha fgh` qui serait associée à l'élément `x_(fgh)`. Pour obtenir cette traduction on peut associer à chaque élément `x` la fonction constante `alpha` qui produit toujours `x` quelque soit l'entré, ce qui se note `alpha = (y|->x)`. Toute composition de fonction de la forme `alphaf` constituera alors la fonction `alphaf = (y|->x_f)`, une fonction constante retournant `x_f` et sera donc bien associés à l'élément `x_f`.
Un magma `(S,**)` est une structure composée d'une opération binaire. Elle comprent un ensemble sous-jacent `S` et une opération binaire qui est interne à `S`, c'est à dire telle que quelque soit `x` et `y` appartenant à `S`, l'élément `x**y` est défini et appartient à `S`.
La structure est désigner par défaut par la même lettre `S` que celle de son ensemble sous-jacent, ainsi `S =(S,**)` et on laisse le soin au contexte de lever l'ambiguité pour savoir s'il on parle d'un ensemble ou d'une structure.
On s'intéresse à la forme de la structure et non à sa nature. Deux structures sont de même forme s'il existe une traduction fidèle permettant de passer de l'une à l'autre. Cette traduction fidèle s'appelle un isomorphisme, ou morphisme bijectif.
Deux structures de même formes sont isomorphes. Leur nature peut être différente mais il existe un isomorphisme, une traduction fidèle, permettant de passer de l'une à l'autre, une transormation réversible qui respecte la forme.
Soit deux structures `(A,**)` et `(B,**)`. Les opérations internes sont par défaut supposées distinctes, c'est pourquoi en dehors du cadre de leur structure il est nécessaire de rappeler à quelle structure elles appartiennent. On les notera `**_A` et `**_B` en les indiçant ainsi par le nom de leur structure.
Par contre, si l'opération `**` s'applique à deux éléments de la structure, il n'est pas nécessaire de préciser à quel structure appartient l'opération, car elle appartient nécessairement à la structure qui possède les éléments en question, l'opération n'étant pas définie ailleur. Ainsi lorsqu'il n'y a pas d'ambiguité, l'opération est noté de façon identique par `**`.
Une fonction `f` est un isomorphisme de `(A,**)` vers `(B,**)` si et seulement si elle vérifie :
Morphisme : `AA (x,y) in A^2, f(x**y) = f(x)**f(y)`
Surjectif : `AA y in B, EE x in A, f(x)=y` Injectif : `AA (x,y) in A^2, f(x)=f(y) => x=y`
L'isomorphisme inverse se note `f^(-1)`.
Deux structures `(A,**)` et `(B,**)`sont isomorphes s'il existe un isomorphisme passant de l'une à l'autre. Et on notera cela par :
`(A,**)~=(B,**)`
Si nous étendons la fonction `f` en l'appliquant à l'opérateur `**_A` pour produire l'opérateur `**_B`, c'est à dire telle que `**_A |-> **_B`, alors la propriété de morphisme devient (en notation française) :
`(x**y)_f = x_f **_f y_f`
Il s'agit bien d'un mécanisme de traduction, chaque composante d'une expression telle que par exemple `(x**y)**z` est remplacée par son image `(x_f **_f y_f) **_f z_f` en respectant la forme, et cette traduction est fidèle dans le sens qu'elle constitue une bijection entre les deux ensembles sous-jacents `A` et `B`.
Pour définir des propriétés sur un magma `(S,**)`, il faut d'abord définir un langage logique. La struture elle-même donne un élément de langage (autre que le symbole `S` qui désigne son ensemble sous-jacent) qu'est l'opérateur binaire `**"(.,.)"`.
En ajoutant l'égalité `=` qui est un prédicat binaire `="(.,.)"`, et en ajoutant des inconnues `x,y,z...` appartenant à `S`, mais qui seront quantifiées uniquement universellement, puis en utilisant les seuls connecteurs logiques `"et"," ou",` mais sans jamais utiliser la négation, on obtient un premier langage qu'est le langage des théories d'égalités du premier ordre. Le premier ordre signifiant qu'il n'y a qu'une seul sorte de variable, les variables universelles sur l'ensemble sous-jacent.
Pourquoi exclure la négation ? c'est pour ne garder que des quantificateurs universelles et exclure les quantificateurs existentielles et ainsi limiter le langage d'opérateurs. Le langage d'opérateur peut être augmenté arbitrairement en utilisant les quantificateurs existentielles. Les théorie d'égalité ont des propriétés qui permettent de construire et d'ordonner les structures.
Deux structure `(A,**)` et `(B,**)` sont dites équivalentes si et seulement si toutes les propriétés d'égalité du premier ordre vrai dans l'une sont vrai dans l'autre et réciproquement. Et on notera cela par :
`(A,**)-=(B,**)`
Deux structures isomorphes sont équivalentes, car la traduction fidèle s'étend naturellement au langage logique des théories d'égalité. Par exemple considérons la propriété de commutativité qui est bien une propriété d'égalité du premier ordre :
`AA(x,y)inA^2, x**y = y**x`
On en déduit à l'aide de l'isomorphisme `f` que :
`AA(x,y)inA^2, f(x)**f(y) = f(y)**f(x)`
Et donc que :
`AA(u,v)inB^2, u**v = v**u`
qui constitue la même propriété de commutativité mais appliquée à l'autre structure.
Le langage logique d'égalité du premier ordre se définie récursivement comme suit :
1- Un terme est une composition close d'opérateurs de la structure.
2- Un littéral est une égalité entre deux termes.
3-
Une clause d'égalité et une disjonction fini de littéraux. (Clause vide = faux.)
4-
Une proposition est une conjonction fini de clauses d'égalité. (Conjonction vide = vrai.)
On étend l'isomorphisme `f` aux propositions logique d'égalité du premier ordre à l'aide des définitions récurcives suivantes :
1- Quelque soit un terme `t`, on calcule `f(t)` en appliquant `f` à chaque composante du terme.
2- Quelque soit un littérale `t_1=t_2`, nous posons `f(t_1=t_2) = f(t_1) = f(t_2)`
3- Quelque soit deux clauses `C_1` et `C_2`, nous posons `f(C_1` ou `C_2) = f(C_1)` ou `f(C_2)`
4- Quelque soit deux proposition `P_1` et `P_2`, nous posons `f(P_1` et `P_2) = f(P_1)` et `f(P_2)`
Rappelons que les variables `x,y,z,...` sont implicitement quantifiées universellement sur la structure en cours, et donc que `f(x),f(y),f(z),...` jouent le rôle de variables quantifiées universellement sur la structure image.
Ainsi quelque soit une proposition `P` vrai dans `(A,**)`, la proposition `f(P)` est vrai dans `(B,**)`.
Ainsi l'isomorphisme entraine l'équivalence.
La réciproque est fausse. Deux magmas `(A,**)` et `(B,**)` équivalents peuvent ne pas être isomorphes. Cela prouve que le langage logique d'égalité du premier ordre est loin d'être suffisant pour décrire toutes les formes de magma fussent-t-il élémentarien. Les contres exemples seront facile à trouver lorsqu'on étudiera le langage logique d'égalité du second ordre.
---- 12 février 2017 ----
Pour construire un contre exemple, on peut partir d'une structure `(S, **)` avec une opération associative `**`, autrement dit d'un semi-groupe. Une opération interne `**` associative se note souvent par l'absence de symbole lorsqu'il n'y a pas d'ambiguité. Puis on peut choisir une propriété d'égalité qui n'est pas du premier ordre et qui affirme par exemple que tout élément engendre un groupe fini. Cette propriété s'écrit sous forme d'une clause infinie énumérable c'est à dire comprenant une infinité énumérable de littéraux :
`x x"="x "ou" x x x"="x "ou" x x x x"="x "ou" x x x x x "="x ...`
On peut utiliser les entiers pour exprimer cette clause :
`x^2"="x "ou" x^3"="x "ou" x^4"="x "ou" x^5"="x ...`
Et l'écrire ainsi de manière condensée :
`AA x, EE n "∈" NN, n"≥"2 "/" x^n"="x`
Mais on voit bien que cette clause n'est pas du premier ordre (elle utilise nécessairement soit deux types de variables ou soit une clause infinie énumérable). Et elle est bien transportée par isomorphisme. Si deux goupes sont isomorphes et que l'un respecte cette clause alors l'autre également respecte cette clause.
Puis il faut construire un exemple de structure respectant cette clause et une autre non, mais suffisamment proche pour que toute proposition d'égalité du premier ordre vrai dans l'une soit vrai dans l'autre. On pense naturellement aux deux groupes abeliens suivants :
`bbbA = (ZZ"/"2ZZ)×(ZZ"/"3ZZ)×(ZZ"/"4ZZ)×(ZZ"/"5ZZ)×... (ZZ"/"nZZ)×...`
`bbbA×ZZ`
Le symbole `...`, appellé elipse, signifie qu'il sagit d'une suite infinie. Il existe plusieurs façons habituelles de définir une telle suite infinie. Un élément `x` appartenant à ce groupe `bbbA` est déterminé par la liste de ses composantes `x=(x_2,x_3,x_4,x_5,...,x_n,...)`. Et comme nous sommes dans le cadre de la logique élémentarienne, où toute suite doit être calculable, cette suite doit être calculable. C'est à dire qu'il doit exister un programme de taille finie qui énumère toutes les composantes de `x`.
Mais l'elipse peut aussi être interprété de façon encore plus restrictive comme l'ensemble des suites finies c'est à dire toujours nulle à partir d'un indice arbitrairement grand. (Il faut pour cela qu'un élément neutre est été définie et qui joura le rôle du nulle.) Le programme d'énumération correspond alors à l'énumération des composantes jusqu'à cette indice suffisament grand mais fini qui assure ainsi la finitude du programme. Pour lever toute ambiguité, lorsque l'elipse est interprété dans ce second sens, on ajoute le qualificatif `"finie"` à la fin de la suite :
`bbbB = (ZZ"/"2ZZ)×(ZZ"/"3ZZ)×(ZZ"/"4ZZ)×(ZZ"/"5ZZ)×... (ZZ"/"nZZ)×..." finie" `
`bbbB×ZZ`
Nous avons ainsi 4 groupes non isomorphes, bons candidats, qui ont toutes les chances d'être 2 à 2 équivalents en égalité du premier ordre.
On enrichie le langage en utilisant la négation. Délors il est possible de supposer l'existence d'éléments et opérateurs supplémentaires à la présentation de la structure mais néanmoins en nombre fini car une formule du premier ordre est par définition de taille finie.
Deux structure `(A,**)` et `(B,×)` sont dites élémentairement équivalentes si et seulement si toutes les propriétés du premier ordre vrai dans l'une sont vrai dans l'autre et réciproquement.
Deux structures isomorphes sont élémentairement équivalentes, car la traduction fidèle s'étend tout naturellement au langage logique. Par exemple considérons la propriété de l'existence d'un élément absorbant et de l'existence d'un second élément différent de celui-ci, propriété qui est bien du premier ordre :
`EE x "∈" A, EE y "∈" A, AAz "∈" A, x**z"="x "et" z**x"="x "et" x"≠"y`
On en déduit à l'aide de l'isomorphisme `f` que :
`EE x "∈" A, EE y "∈" A, AAz "∈" A, f(x)"×"f(z)"="f(x) "et" f(z)"×"f(x)"="f(x) "et" f(x)"≠"f(y)`
Et donc que :
`EE p "∈" B, EE q "∈" B, AA r "∈" B, p"×"r"="p "et" r"×"p"="p "et" p"≠"q`
qui constitue la même propriété d'existence d'un élément absorbant et d'un second élément différent de celui-ci, mais appliquée à l'autre structure.
La réciproque est fausse. Deux structures `(A,**)` et `(B,×)` élémentairement équivalentes peuvent ne pas être isomorphes. Cela prouve que le langage logique du premier ordre est loin d'être suffisant pour décrire toutes les formes de structure d'une opération binaire fusse-t-elle élémentarienne.
Une propriété d'égalité parmis les plus simple à exprimer sans être du premier ordre, est par exemple la monogénéité de la structure. (Remarquez qu'un semi-groupe monogène est nécessairement abelien.) Considérons un semi-groupe `(S, **)` avec une opération associative `**` que l'on note souvent par absence de symbole lorsqu'il n'y a pas d'ambiguité. Les compositions s'apparentent alors à des mots sur l'alphabet `S`. Être monogène signifie qu'il existe un élément générateur. Cette propriété s'écrit sous forme d'une clause infinie énumérable :
`EE g, AA x, x"="g "ou" x"="gg "ou" x "="ggg "ou" x"="gggg ...`
Cela s'écrit de manière plus condencée par :
`EE g, AA x, EE n "∈" NN, n"≥"1 "/" x"="g^n`
Et en adoptant les symboles de cloture `< >` et d'appartenance à cette cloture `in`, cela s'écrit de manière plus condensée encore :
`EE g, AA x, x in "<"g">"`
De même la propriété de bigénéité se note par :
`EE a,EE b, AA x, x in "<"a,b">"`
De même la propriété de trigénéité se note par :
`EE a,EE b,EE c, AA x, x in "<"a,b,c">"`
Vous remarquerez que la cloture `"<"a,b">"` correspond à l'ensemble des mots non-vide sur l'alphabet `{a,b}` que l'on note quelque fois `{a,b}"+"` ou `{a,b}"*"-{epsilon}` où `epsilon` désigne le mot vide, ou bien avec l'elipse `{a,b}×({a,b}×{a,b}×{a,b}... "finie")`
Le semi-groupe libre bigène est élémentairement équivalent au semi-groupe libre trigène. La démonstration est assez ardue.
Relation et graphe sont synonymes. (Voir théorie des graphes.)
La relation `f` est dite non déterministe, si elle ne constitue pas une fonction c'est à dire s'il existe au moins un élément `x` pour lequel il y a plus d'une arête qui part de `x` pour aller sur des sommets différents. Ces arêtes constituent alors autant d'alternatives. L'ensemble des images de `x` que l'on note par `{x}_f` ou par `f{x}`, correspond à l'ensemble des éléments successeurs de `x`, c'est à dire atteignable à partir de `x` en empruntant une arête partant de `x`.
On note `x |->_f y` pour indiquer qu'il existe une arête dans le graphe `f` qui part de `x` pour aller sur `y`, autrement dit `y` est un successeur de `x` ce qui s'écrit par `y "∈" f{x}`.
Un élément `x` est dit terminal si aucune arête ne part de `x`, c'est à dire s'il ne possède aucun sucesseur. Dans ce cas, l'ensemble des successeurs de `x` est l'ensemble vide. `f{x} = Ø`.
On étend la fonction successeur `f` par union de telle sorte qu'il est possible de calculer les éléments successeurs à un ensemble `A` que l'on note `f(A)` est qui est définie par :
`x "∈" f(A)` ssi `EE u "∈" A, x "∈" f{u}`
L'ensemble des descendants de `x`, noté `hat f{x}` est la limite de `{x}uu f{x} uu f{f{x}} uu ...`. De même pour un ensemble `A`, l'ensemble des descendants de `A`, noté `hat f"("A")"` est la limite de `A uu f(A) uu f(f(A)) uu ...`, c'est à dire l'ensemble des descendants d'au moins un élément de `A`.
Ainsi on définie les concepts de successeur, d'adjacent et de descendant :
L'ensemble des successeurs de `A` est `f(A)`
L'ensemble des adjacents à `A` est `f(A)-A`
L'ensemble des descendants de `A` est `hat f "("A")"`
C'est alors qu'il apparait judicieux de valuer cet ensemble, pour pouvoir mesurer et contenir d'une certaine façon l'indéterminisme. On peut le valuer par des nombres entiers positifs ce qui le transforme en multi-ensemble, un multi-ensemble de successeurs. On compte par exemple le nombre de chemins distincts de même longueur accédant à un élément. On peut aussi le valuer par des nombres réels. On peut définir une probabilité d'accès par des chemins de même longueur en supposant à chaque sommet une égale propabilité de passage sur chaque arc par exemple.
La propriété d'associativité de la composition des fonctions fait que tout ensemble de fonctions clos par composition constitue un semi-groupe de fonctions.
Un semi-groupe de fonctions est un ensemble quelconque de fonctions munie de l'opération de composition de fonction `@`, et qui est clos par cette opération.
Considérons 3 fonctions `f,g,h`. Le semi-groupe engendré par ces trois fonctions se note en notation linguistique par :
`"<"f, g, h, @">"`
où `@` est le symbole désignant l'opération de composition de fonction. Et il n'y a pas de quotientage par des règles d'égalités supplémentaires.
Tout semi-groupe est isomorphe à un semi-groupe de fonctions. En effet, on peut toujours faire opérer un semi-groupe sur lui-même par translation gauche.
Soit `(S, **)` un semi-groupe définie en notation classique. On fait agire `S` sur lui même en associant à chaque élément `s` de `S`, la fonction `hat s` définie par `x|->s**x`. Et `S` devient ainsi isomorphe à un semi-groupe de fonctions.
Dés lors il est toujours possible d'ajouter un élément neutre dans un semi-groupe n'en possèdant pas, de la même façon que l'on peut ajouter la fonction identité dans un semi-groupe de fonctions si elle n'est pas déjà présente. Un semi-groupe possèdant un élément neutre s'appelle un monoïde.
La multiplication interne d'un semi-groupe est associative, et se note par absence de symbole lorsqu'il n'y a pas d'ambiguité.
Considérons un semi-groupe `(S, **)` sur lequel nous n'avons pas d'autre connaissance. Considérons des inconnues `x, y, z...` appartenant à `S` et quantifiées universellement. Quel sont les littéraux d'égalités possibles de dimension 1, c'est à dire n'utilisant qu'une seul variable universelle ? Voici un exemple de littéral d'égalité à une seul variable `x**x**x=x**x`. D'une manière générale, les littéraux d'égalité de dimension 1 sont de la forme `x^n"=" x^m` avec `(n,m) "∈" (NN^**)^2`, et il n'y en a pas d'autre. Les clauses d'égalité de dimension 1 sont des combinaisons de tels littéraux à l'aide du connecteur `"ou"`, et les théories d'égalité de dimension 1 sont des combinaisons de tels clauses à l'aide du connecteur `"et"`. La classification des théories d'égalité de dimension 1 d'un semi-groupe se ramène à un problème arithmétique.
Un semi-groupe libre ne possède pas d'élément neutre.
Une structure se présente en notation linguistique par `L"/"T` où `L` est le langage d'opérateurs de la structure, et où `T` est la théorie d'égalité de la structure.
Le semi-groupe `(S,**)` comprend un ensemble sous-jacent `S` et une multiplication interne `**` associative, que l'on note par absence de symbole lorsqu'il n'y a pas d'ambiguité. En résumé nous avons un langage d'opérateurs qui ne comprend qu'une opération `"<"**">"` et une théorie d'égalité composée d'un unique axiome qu'est l'associativité :
`AA(x,y,z)"∈"S^3, x(yz) "=" (xy)z`
Le semi-groupe agène est un ensemble vide, car c'est une structure engendré par une unique opération binaire sans éléments générateurs. On ne peut pas construire de terme clos. On ne peut pas construire d'élément.
Le semi-groupe monogène libre se présente en notation linguistique et programmative comme suit :
`"<" g, **">" "/" {x(yz) = (xy)z}`
Semi-groupe monogène `(**,g)`
Le patron Semi-groupe monogène donne un rôle à chacun de ses arguments dans un ordre précis, le 1er argument désigne l'opérateur binaire, le 2nd argument désigne l'élément générateur. Il est dit libre si on n'ajoute pas de propriété d'égalité à sa théorie. Le semi-groupe monogène libre correspond aux entiers naturels strictement positifs en notation multiplicative :
`{1, 2, 3, ..., n,...} -> {g, gg, ggg, ... , g^n, ...}`
La règle de composition est la suivante.
`AA(n,m) in (N^**)^2, g^n ** g^m = g ^(n+m)`
Le semi-groupe bigène se présente en notation linguistique et programmative comme suit :
`"<"a,b,**">" "/" {x(yz) = (xy)z}`
Semi-groupe bigène `(**,a,b)`
Le patron Semi-groupe bigène donne un rôle à chacun de ses arguments dans un ordre précis, le 1er argument désigne l'opérateur binaire, le 2nd argument désigne le premier élément générateur, le 3 ième argument désigne le second élément générateur. Il est dit libre si on n'ajoute pas de propriété d'égalité à sa théorie. Le semi-groupe bigène libre correspond à l'ensemble des mots non vides sur un alphabet à 2 lettres, l'opération interne correspond à la concaténation de mots.
On utilise l'étoile de Kleene pour définir l'ensemble des mots de taille finie. Ainsi `{a,b}^**` désigne l'ensemble des mots sur l'alphabet `{a,b}`. Le mot vide se note `epsilon`. L'ensemble des mots non-vide sur l'alphabet `{a,b}` se note `"<"a,b">"` ou quelque fois `{a,b}"+"` ou bien `{a,b}"*"-{epsilon}`ou bien encore avec l'elipse `{a,b}×({a,b}×{a,b}×{a,b} ... "finie")`
Le semi-groupe `n`-gène libre correspond à l'ensemble des mots non vides sur un alphabet à `n` lettres.
Le semi-groupe `oo`-gène libre correspond à l'ensemble des mots d'un alphabet comprenant une infinité énumérable de lettres. C'est à dire `NN"*"` mais en utilisant ici l'étoile de Kleene, c'est l'ensemble des mots de taille finie, composé de lettres qui sont les entiers naturels (chaque entier naturel désigne une lettre distincte).
Selon le paradigme élémentarien, tout élément du semi-groupe est définie par une formule de taille finie, c'est à dire ici par un mot, et est donc nécessairement engendrée par un nombre fini d'éléments générateurs.
Selon le paradigme élémentarien, il n'y a pas d'autres semi-groupe libres à isomorphisme près. Ils sont caractérisés par une dimension qui est le cardinal de l'ensemble de leurs générateurs et qui peut être `0,1,2,3,....` ou `oo`.
Considérons un semi-groupe libre `(S,**)`. Deux éléments `a, b` sont dits indépendants ssi tout combinaison distincte engendrée par `a` et `b` désignent nécessairement des éléments distinct. De même un ensemble d'éléments est dit indépendant ssi tout combinaison finie distincte engendrée par ces éléments désignent nécessairement des éléments distincts.
Inversement un ensemble d'éléments est dit lié (ou dépendant) ssi il existe deux combinaisons finies distinctes engendrées par ces éléments qui sont égales. Par exemple si nous avons `abacd = dabac` alors l'ensemble `{a,b,c,d}` est lié (ou dépendant).
Un ensemble d'éléments est dit générateurs ssi il engendre tous les autres élément.
Une base est un ensemble à la fois indépendant et générateur.
Un semi-groupe libre ne possède qu'une seul base.
Cette notion d'indépendance correspond à un matroïde.
Un semi-groupe abelien libre ne possède pas d'élément neutre.
Le semi-groupe abelien `(S,+)` comprend un ensemble sous-jacent `S` et une multiplication interne `+`, associative et commutative. En résumé nous avons un langage d'opérateurs qui ne comprend qu'une opération `"<"+">"` et une théorie d'égalité composée de deux axiomes :
`AA(x,y,z)"∈"S^3, x(yz) "=" (xy)z`
`AA(x,y)"∈"S^3, xy "=" yx`
Le semi-groupe abelien agène est un ensemble vide.
Le semi-groupe abelien monogène libre est le même que le semi-groupe monogène libre.
Le semi-groupe abelien bigène se présente en notation linguistique et programmative comme suit :
`"<"a,b,+">" "/" {x(yz) = (xy)z, xy=yx}`
Semi-groupe abelien bigène `(+,a,b)`
Le patron Semi-groupe abelien bigène donne un rôle à chacun de ses arguments dans un ordre précis, le 1er argument désigne l'opérateur binaire, le 2nd argument désigne le premier élément générateur, le 3 ième argument désigne le second élément générateur. Le semi-groupe bigène libre correspond à l'ensemble des couples d'entiers naturels, sans le couple `(0,0)`. L'opération interne correspond à la somme vectorielle.
Le semi-groupe `n`-gène libre correspond à l'ensemble des n-uplet d'entiers naturels sans le n-uplet `(0,0,0,...,0)`.
Le semi-groupe `oo`-gène libre correspond à l'ensemble des vecteurs de dimension finie d'entiers naturels. C'est à dire des fonctions de `NN -> NN` nulle à partir d'une valeur arbitrairement grande.
Selon le paradigme élémentarien, il n'y a pas d'autres semi-groupe abelien libres à isomorphisme près. Ils sont caractérisés par une dimension qui est le cardinal de l'ensemble de leurs générateurs et qui peut être `0,1,2,3,....` ou `oo`.
Considérons un semi-groupe abelien libre `(S,+)`. On choisie la notation additive lorsque le semi-groupe est abelien :
`a+a = 2a`
`a+a+a = 3a`
`a+b+a+b+a = 3a+2b`
Deux éléments `a, b` sont dits indépendants ssi toute combinaison abelienne distincte engendrée par `a` et `b` désignent nécessairement des éléments distincts. Ce que l'on entend par combinaisons abélienne c'est la somme d'une sommation de `a` et d'une sommation de `b`. La combinaison abélienne est de la forme :
`na+mb`
avec `(n,m)inN^2-(0,0)`.
De même un ensemble d'éléments est dit indépendant ssi toute combinaison abelienne finie distincte engendrée par ces éléments désignent nécessairement des éléments distincts.
Inversement un ensemble d'éléments est dit lié (ou dépendant) ssi il existe deux combinaisons finies distinctes engendrées par ces éléments qui sont égales. Par exemple si nous avons `2a+c+d = a+2b+d` alors l'ensemble `{a,b,c,d}` est lié (ou dépendant).
Un ensemble d'éléments est dit générateurs ssi il engendre tous les autres élément.
Une base est un ensemble à la fois indépendant et générateur.
Un semi-groupe abelien libre ne possède qu'une seul base.
Cette notion d'indépendance correspond à un matroïde.
---- 26 janvier 2016 ----