A toute description locale correspond une description globale, qui apporte alors une intuition globale. Mais pour passer au niveau global, il faut munir l'object mathématique d'une dynamique susceptible de mettre en oeuvre un contexte global. Ainsi un semi-groupe `(M,"∗")` sera vu comme un semi-groupe de fonctions, où l'opération `"∗"` correspondra à la composition de fonctions. Et mieux encore, il sera vu comme un semi-groupe de transformations, des transformations opérant sur un système. C'est à dire que l'exécution d'une transformation fera changer l'état du système. Mais davantage encore, il y a dans l'exécution de cette transformation elle-même un procédé mécanique qui est mis en oeuvre, et qui est de même nature que celui du raisonnement mathématique auquel nous nous soumettons, construisant éléments et démonstrations, et qui opère sur le système comme sur notre propre pensée, une transformation, un changement d'état, ouvrant la porte au concept d'effectivité et au temps, en opérant une analogie entre transformation, temps et raisonnement.
Puis tout se passe comme si nous étions dans un jeu, et qu'à chaque tour nous devions jouer une transformation appartenant à ce semi-groupe.
Et une transformation n'est pas forcement réversible, c'est à dire qu'une fois opérée, il se peut qu'aucune autre transformation contenue dans `M` ne puisse faire revenir le système dans son état antérieur.
Et les transformations ne sont pas nécéssairement commutatives entre elles, il se peut qu'à la suite de plusieurs transformations successives l'état final du système dépende de l'ordre dans lequel se sont succédées ces transformations.
La description globale du semi-groupe commence par la description d'un ensemble de transformations d'un système, que l'on clos par composition.
Si le semi-groupe est commutatif alors une succession de transformations peut s'opérer dans n'importe quel ordre et représente, puisque l'on peut les ranger de faite, une accumulation de ressources. Chaque transformation effectuée correspond à une ressource accumulée. Notez que cela ne garantit pas que les ressources accumulées de s'annulent pas mutuellement. Et la non réversibilité indique que certaines ressources peuvent être acquises sans retour possible, c'est à dire sans qu'il soit possible de s'en défaire par la suite. L'acquisition d'une connaissance, sans possibilité de l'oublier après, est un exemple de telle ressource.
Le semi-groupe est dit de type fini s'il est engendré par un nombre fini d'éléments. Plus précisement, il est dit monogène s'il est engendré par un élément, bigène s'il est engendré par au moins deux éléments, trigène s'il est engendré par au moins 3 éléments, etc..
S'il existe un élément neutre alors la structure constitue un monoïde. Et dans le jeu, nous pouvons alors passer autant de tour que l'on veut au cours du jeu. Et si on est le seul joueur, on peut donc arréter le jeu à tout moment en décidant de passer indéfiniment.
Si dans le monoïde tous les éléments sont inversibles alors la struture constitue un groupe, et nous pouvons annuler toute transformation que nous avons faite en choisissant la transformation inverse et ainsi revenir à l'état du système tel qu'il était initialement. Chaque élément du groupe représente alors une transformation réversible.
On appelle séquence, une suite finie.
Un semi-groupe de type fini est dit libre s'il existe un ensemble fini d'éléments générateurs, qui génèrent le semi-groupe librement, c'est à dire tel que deux séquences distinctes d'éléments générateurs produisent nécessairement deux éléments distincts. En effet l'associativité de l'opération de composition assure que toute combinaison de générateurs se ramène à une séquence de générateurs. Le semi-groupe correspond alors exactement au langage libre engendré par ces générateurs.
Par ailleurs, on remarquera qu'une séquence d'éléments constitue l'argument d'un opérateur d'arité variable.
Les structures s'obtiennent à l'aide d'un jeu de construction dont les bases sont par principe simples. Et si on commence directement par l'utilisation d'une opération binaire comme moyen de construction, on saute alors une étape que nous analyserons plus tard. La première structure qui apparait alors est le Magma monogène libre. Il est unique à isomorphisme près de par le principe même de construction, et correspond aux arbres binaires nus. Voici sa présentation :
`"<"a,"∗>"`
Il comprend un élément générateur ici nommé `a`, et une opérateur binaire ici nommée `"∗"` qui constitue la loi de la structure. L'opérateur lorsqu'il s'applique, s'appelle l'opération, le produit. On précise parfois l'arité de l'opérateur `"∗"` en le notant ainsi `"∗(.,.)"`, mais il n'est pas utile de le rappeler si on l'a déjà définie préalablement dans un langage mère comme par exemple :
`L = "<"a, b, f"(.)", "+(.,.)", "∗(.,.)>"`
En mettant en exergue une opération fondamentale qu'est l'opération d'extension élémentaire à partir d'une plus petite structure choisie comme patron, le magma monogène libre se présente en notation programmative comme suit :
Magma `("∗") [a]`
La théorie du Magma est vide, c'est pourquoi le Magma `("∗")` se présente linguistiquement par `"<∗>"`. Ce langage d'opérateurs ne peut construire aucune composition close d'opérateurs, aucun produit d'éléments, puisqu'il ne possède aucun opérateur d'arité zéro, aucun élément. Parcontre il peut construire des compositions non closes d'opérateurs qui constituent des opérateurs d'arité supérieur à zéro, il peut construire par composition générale, au sens d'une programmation sans boucle, à partir de l'opérateur `"∗(.,.)"`, d'autres opérateurs tel que par exemple les opérateurs `f"(.)"` et `g"(.,.)"` définis par les constructions suivantes :
`f = (x |-> (x"∗"x)"∗"x)`
`g = ((x,y) |-> (x"∗"y)"∗"(y"∗"x))`
ou bien définis par les égalités suivantes :
`f(x) = (x"∗"x)"∗"x`
`g(x,y) = (x"∗"y)"∗"(y"∗"x)`
L'égalité s'applique pour tous les éléments `x` et `y` appartenant à la structure, mais comme la structure ne possède aucun élément, ce n'est pas l'égalité logique qui compte ici mais bien le programme de calcul des opérateurs, et qui en constitue leur implémentation, c'est à dire leur construction à l'aide d'un langage de programmation.
Les opérateurs `f` et `g` sont bien contenus anonymement dans la structure Magma `("∗")`, dans la mesure où ils peuvent être construits à partir de l'opérateur `"∗"` de la structure et à l'aide d'un langage de programmation que nous n'avons pas encore vraiment circonscrit.
D'une manière générale, on peut construire par programmation d'autres opérateurs tel que `h"(.,.)"` et `k"(.,.)"` définis par les programmes impératifs suivants :
`h(x,y) = (`
`u"≔"x`
`v"≔"y`
Tant_que `(u"="v)` répéter_max_10 `(u"≔"u"∗"x; v"≔"v"∗"y)`
`u`
`)`
`k(x,y) = (`
`u"≔"x`
`v"≔"y`
Tant_que `(u"="v)` répéter `(u"≔"u"∗"x ; v"≔"v"∗"y)`
`u`
`)`
Le langage de programmation utilisé est le suivant :
Un programme est une séquence d'instructions, séparés par des points virgules ou simplement des passages à la ligne. Les instructions sont exécutées les une à la suite des autres et la dernière instruction retourne le résultat du programme qui peut être un terme de la structure ou un booléen true ou false.
L'instruction `u"≔"x` modifie la valeur de la variable `u` en lui affectant celle de `x`.
L'instruction `u"="y` retourne `true` si `u` et `y` contiennent la même valeur et sinon retourne false.
L'instruction `u"≔"u"∗"x` modifie la valeur de la variable `u` en lui affectant le résultat de l'opération `u"∗"x` où les valeurs de `u` et `x` sont celles qu'elles avaient avant l'exécution de cette instruction.
L'instruction `u` retourne la valeur de la variable `u`.
L'opérateur de programmation binaire Tant_que `"⟮.⟯"` répéter _max_10 `"⟮.⟯"` prend deux arguments, le premier argument est un programme qui retourne une valeur bouléenne, true ou false, déterminant si la répétition doit s'arrêter, sachant que la répétition s'arrètera après la 10ième fois si elle ne s'est pas arrétée avant. Le second argument est le programme qui fait l'objet des répétitions.
L'opérateur de programmation binaire Tant_que `"⟮.⟯"` répéter `"⟮.⟯"` prend deux arguments, le premier argument est un programme qui retourne une valeur booléenne, true ou false, déterminant si la répétition doit s'arrêter, le second argument est le programme qui fait l'objet des répétitions.
Le programme `h"(.,.)"` donne toujours une réponse. L'opérateur `h"(.,.)"` est donc bien définie.
Par contre, il n'en est pas de même pour l'opérateur `k"(.,.)"`. Car ce programme peut ne pas s'arréter et ne donner aucune réponse pour certaines valeurs d'entrée. Si le programme ne s'arrète pas pour des valeurs d'entrée `(a,b)`, on dit qu'il produit l'infini de Turing, noté `oo`. C'est une valeur oracle, car il faut attendre un temps infni pour en être sûr. Et elle est unique, car selon les intuitionnistes, il n'y à rien au delà de l'infini. Qu'est-ce qu'un opérateur `k"(.,.)"` produisant l'infini de Turing pour certaines valeurs ou même pour toutes ? le terme exacte, mais désuet, est "non totalement calculable". Nous ne répondrons pas à cette question pour l'instant, et nous nous contenterons dans un premier temps d'étudier que des programmes dont l'arrêt est sûr, c'est à dire dont on est certain qu'ils s'arrèteront.
L'opérateur `h"(.,.)"`, comme tout opérateur, possède plusieurs implémentations possibles, c'est à dire plusieurs programmes le calculant, écrit dans un langage de programmation. Et on peut choisir compme langage de programmation, le langage de données de la structure auquel on ajoute des opérateurs spécifiques de programmation, et cela forme encore un langage d'opérateurs. Dans le langage de données, les mots sont appelés termes et sont les termes clos que l'on peut fabriquer à l'aide des opérateurs générateurs de la structure. Dans le langage de programmation, les mots sont appelés programmes et sont encore les termes clos que l'on peut fabriquer à l'aide des opérateurs générateurs de la structure augmenté de plusieurs opérateurs spécifiques de programmation.
De même l'opération `"∗"` peut possèder plusieurs implémentations le calculant. On dira que toutes les implémentations connues sont mémorisées dans la structure en une connaissance dite introspective.
Les opérateurs générateurs constituent le moteur de construction de la structure. Ils forment une gamme d'énumérateurs de tous les éléments (et opérateurs) de la structure. Cette gamme s'enrichie d'autant qu'il y a d'implémentations possibles des opérateurs générateurs. Et il n'y a pas de raison de privilègier un énumérateur par rapport à un autre. Aussi devons nous considérer plusieurs énumérateurs constituant une connaissance énumérative de la structure.
On distingue l'opérateur passif `"∗"`, et le mécanisme de construction associé. L'un est le symbole, élément du langage, l'autre est le programme, son implémentation, et constitue un composant d'un énumérateur. Lorsque la structure possède plusieurs énumérateurs connus, cela donne autant de points de vue énumératifs différents sur la structure. Les énumérateurs supplémentaires apportent des connaissances supplémentaires sur la structure. Ils ne sont pourtant que le résultat de déductions opérées sur la structure elle-même, mais comme ces déductions demandent un temps de calcul et de recherche non pondérable, leurs résultats constituent bel et bien un enrichissement par introspection.
L'extension élémentaire est notée en ajoutant à la structure plusieurs éléments nouveaux entre crochets `[ ]`. Les éléments doivent constitués un enrichissement du langage, c'est à dire ne doivent pas avoir été utilisés avant. Un même symbôle peut être réutilisé, mais il désignera alors un nouvel élément valable pour ce nouveau contexte et qui n'aura donc jamais été utilisé avant. L'élément `a` représente ici un nouvel élément quelconque qui sert à l'extension et qui aurait pu être désigné sous un autre symbôle. Nous pouvons ainsi écrire :
Magma `("∗") [a] = "<∗>" [a]`
Magma `("∗") [a] = "<∗",a">"`
Le magma monogène libre qui peut être noté Magma `("∗") [a]`, est qualifié de monogène car il est engendré par l'apport d'un seul élément, dit générateur, qui ajouté au patron Magma `("∗")`, permet d'engendrer complètement la structure, c'est à dire d'énumérer tous ses éléments. Une structure patronée est qualifié de monogène si elle s'obtient à partir de son patron en effectuant une extension élémentaire par un seul élément. Si on intègre cette propriété dans le patron, on obtient un nouveau patron :
Magma monogène `("∗",a) =` Magma `("∗") [a]`
Magma monogène `("∗",a) = "<∗>" [a]`
Magma monogène `("∗",a) = "<∗",a">"`
Le patron Magma monogène `("∗",a)` prend deux aguments. Le premier terme `∗` désigne l'opération interne, et le second terme `a` désigne l'élément générateur. Le magma monogène libre, Magma `("∗",a)`, est qualifié de libre car aucune règle d'égalité, en plus de celles qui pourraient existées dans la théorie du patron Magma `("∗")`, n'est ajoutées concernant cette extension élémentaire.
Le magma monogène libre, qui est pourtant une structure première, n'est pas d'un usage courant, et ses propriétés sont méconnues. Il représente l'ensemble des arbres binaires nus. Que pouvons nous construire sur cette structure ?, relations d'ordre ?, quelles propriétés ?, autres opérations ?, algorithmes ?, autres structures ?....
`"<"a"∗>" = {a, a"∗"a, a"∗"(a"∗"a), (a"∗"a)"∗"a, a"∗"(a"∗"(a"∗"a)), a"∗"((a"∗"a)"∗"a), (a"∗"a)"∗"(a"∗"a), (a"∗"(a"∗"a))"∗"a, ((a"∗"a)"∗"a)"∗"a, ...}`
L'expression peut s'écrire plus simplement si on adopte une convention d'écriture courante pour les produits. On utilise comme symbole de produit, l'absence de symbole. Mais il faut alors s'assurer que les noms des éléments soient reconnaissables s'ils sont collés les uns a la suite des autres. L'expression précédente peut se réécire comme suit :
Par convention, le produit `"∗"` se note par absence de symbole.
`"<"a,"∗>" = {a, aa, a(aa), (aa)a, a(a(aa)), a((aa)a), (aa)(aa), (a(aa))a, ((aa)a)a, ...}`
Si on intègre la qualité d'être libre dans le patron, on obtient le même patron :
Magma monogène libre `("∗",a) =` Magma monogène `("∗",a)`
Magma monogène libre `("∗",a) = "<∗",a">"`
Car le patron, par défaut, ne pose aucune règle d'égalité supplémentaire, ne procède à aucun quotientage autre que sa propre théorie. Il n'est donc pas nécessaire, dans le langage de présentation, de préciser que l'extension monogène est libre, puisque par l'absence de quotientage supplémentaire, l'extension est par défaut libre. L'ajouter, signifirait que l'on se place dans un autre contexte où par défaut nous ne saurions pas s'il existe ou non des règles d'égalité supplémentaires, et que le qualificatif libre nous informerait alors exactement qu'il n'y en a pas.
L'ensemble sous-jacent de la structure regroupe tous ses éléments. Et ces éléments sont le résultat d'un processus énumératif. Ainsi, par principe de construction, l'ensemble sous-jacent d'une structure est énumérable. Et chaque énumération produit un jeu d'éléments, une instantiation de la structure, une copie, qui en constitue, autant de fois que l'on veut, son ensemble sous-jacent.
L'extension élémentaire peut ajouter plusieurs nouveaux éléments regroupés dans un ensemble fini `A`. On la note pareillement mais en mentionnant l'ensemble des nouveaux éléments : `[A]`
Magma `("∗") [A] = "<∗>" [A]`
Magma `("∗") [A] = "<∗",A">"`
Notez que sont placé entre crochets les opérateurs générateurs ou des ensembles d'opérateurs générateurs, ces derniers étant implicitement remplacé par leur contenu.
La présentation programmative d'une telle structure se note sous le même nom mais qualifié de type fini, ce qui signifie qu'elle est engendrée par un nombre fini d'éléments générateurs, et en ajoutant l'ensemble `A` comme argument supplémentaire :
Magma de type fini `("∗",A)`
L'extension élémentaire infinie consiste à ajouter une infinité de nouveaux éléments, mais de façon énumérable. Car elle traduit l'infini potentiel dans le cadre de ce que peut faire l'Homme. Elle est donc unique. Elle consiste à ajouter les nouveaux éléments que l'on numérote par commodité et donc que l'on désigne par `NN = {1,2,3,...}`. On la note pareillement, mais en mentionnant l'ensemble des entiers naturels comme nouveaux éléments : `[NN]`
Magma `("∗") [NN] = "<∗>" [NN]`
La présentation programmative d'une telle structure se note comme suit en qualifiant la structure de type `oo`, et en ajoutant l'argument `NN` :
Magma de type `oo` `("∗",NN)`
Cette structure correspond aux arbres non commutatifs fini dont les feuilles sont des entiers naturels.
Pour prouver que nous avons bien là épuisé toutes les extensions élémentaires d'élément possibles, on procède à une extension élémentaire d'un élément supplémentaire et on démontre que la structure ainsi obtenue est isomorphe à la précédente.
La seconde structure qui apparait, et qui est en faite première puisqu'elle peut être définie avec seulement des opérateurs unaires, sans utiliser d'opérateur binaire comme on le verra dans le chapitre Langage Alpha, est le Semi-groupe monogène libre. Il est unique à isomorphisme près de par le principe même de construction, et correspond aux entiers naturels non nuls que l'on représente couramment à l'aide du symbole `NN"*"`. Sa présentation est la suivante :
` NN"*" = "<"1,"+>/"{(x"+"y)"+"z = x"+"(y"+"z)}`
Sa présentation en notation programmative peut s'écrire de plusieurs façons :
` NN"*" =` Semi-groupe `("+") [1]`
` NN"*" =` Semi-groupe monogène `("+",1)`
On utilise préférentiellement le symbole `"+"` pour désigner une opération à la fois associative et commutative que l'on appel somme, accumulation ou addition. Il s'avère que la structure de semi-groupe monogène, du fait de sa monogénéité, est commutative. C'est pourquoi on choisie de représenter son opération interne à l'aide du symbole `"+"` mais ce n'est pas obligatoire. Et on utilise préférentiellement le symbole `1` pour désigner un premier générateur avec une loi associative.
Le terme semi-groupe comme patron peut être interprété strictement. Auquel cas on a à faire à la structure Semi-groupe `("∗")`, une structure ne comprenant qu'une seul opération associative et aucun élément. Ou alors il peut être interprété de façon générale, et il englobe les différentes extensions possibles, jusqu'à l'extension de type `oo`.
La théorie du semi-groupe se résume en l'associativité de l'opération :
`∀x∀y∀z, (x"∗"y)"∗"z = x"∗"(y"∗"z)`
On utilise des variables `x,y,z...` préalablement quantifiées universellement sur un domaine correspondant à l'ensemble sous-jacent de la structure, de telle sorte qu'il ne sera pas nécessaire de rappeler leur quantification ni leur domaine. La règle d'égalité devient :
`(x"∗"y)"∗"z = x"∗"(y"∗"z)`
La convention de représenter le produit avec absence de symbole s'implifie l'expression :
`(xy)z = x(yz)`
L'associativité entraine une règle syntaxique nous permettant de nous dispenser des parenthèses :
`(xy)z = x(yz) = xyz`
Ainsi un produit associatif est une séquence finie d'éléments `xyzt...`.
Ces règles d'égalités vont être codifiées sous forme de fonction propositionnelle afin de pouvoir être réutiliser dans d'autres situations. La fonction propositionnelle prend en argument des opérateurs ou éléments et retourne une règle d'égalité, c'est à dire une formule n'utilisant comme élément de langage que les opérateurs et éléments transmis en arguments auxquels on ajoute le prédicat `=` et une liste de variables universelles `x,y,z...`, et l'unique connecteur logique `"et"`.
La fonction propositionnelle sera nommée en clair de façon compréhensible comme par exemple `{"+" ` est associatif`}`. Dans cette exemple, la fonction propositionnelle prend en argument un opérateur binaire `"+"` et retourne la règle d'égalité `(x"+"y)"+"z = x"+"(y"+"z)`. Et on ne notera pas les quantificateurs qui seront implicitement positionnés universel, ni le domaine qui sera implicitement limité à l'ensemble sous-jacent de la structure.
`{"+" ` est associatif`} = {(x"+"y)"+"z = x"+"(y"+"z)}`
On met ainsi en exergue une seconde opération fondamentale qu'est l'opération de quotientage par une relation d'équivalence construite à partir de règles d'égalité. Ces règles d'égalité forment une théorie dite d'égalité qui est mise entre accolade `{ }` et placée au dénominateur.
Les opérations de quotientage et d'extension élémentaire peuvent être combinées les une à la suites des autres, formant une suite de transformations de structure. La notation linguistique regroupe au numérateur entre crochet `"<" ">"` les opérateurs générateurs, et regroupe au dénominateur entre accolade `{ }` la théorie d'égalité :
Magma `("∗") = "<∗>"`
Semi-groupe `("∗") =` Magma `("∗") "/" {"∗"` est associatif`}`
Semi-groupe `("∗") = "<∗>/"{"∗"` est associatif`}`
Semi-groupe monogène `("∗",a) =` Semi-groupe `("∗") [a]`
Semi-groupe monogène `("∗",a) = "<∗>/"{"∗"` est associatif`} [a]`
Semi-groupe monogène `("∗",a) = "<∗>"[a] "/"{"∗"` est associatif`}`
Semi-groupe monogène `("∗",a) = "<"a,"∗>/"{"∗"` est associatif`}`
Semi-groupe monogène `("∗",a) =` Magma monogène `("∗",a) "/" {"∗"` est associatif`}`
Les extensions élémentaire ne sont pas réservés au seuls éléments. On peut effectuer une extension élémentaire libre à l'aide d'un nouvel opérateur d'arité supérieure à zéro. On considére la structure triviale `"<"a">"` qui ne comprent que l'unique élément `a`. Le semi-groupe monogène peut alors être obtenu par extension de cette structure triviale en ajoutant un opérateur binaire `"∗(.,.)"` et en quotientant par la règle d'égalité d'associativité de cet opérateur :
Semi-groupe monogène `("∗",a) = "<"a">" ["∗"] "/" {"∗"` est associatif`}`
Comme cette structure s'avère commutative, on préférera pour des raisons intuitive et mémotechnique utiliser comme symbole d'opération non pas le produit `"∗"` mais la somme `"+"` et on pourra utiliser sans ambiguité le symbole `1` comme élément générateur.
Semi-groupe monogène `("+",1)`
Une somme au sens général est une séquence finie d'éléments `x"+"y"+"z"+"t"+"...`.
Etant donné une structure `K`, sa présentation comprend une liste d'opérateurs générateurs placée entre crochets `"<"...">"` divisé par une théorie d'égalité placé entre accolade `{...}`. Le langage de la structure est `"<"...">"`. Un terme désigne un élément. L'élément représente une classe d'équivalence, la classe des termes qui le désignent. L'ensemble sous-jacent de la structure se note `"<"...">"_K`, l'indice `K` précisant que les opérateurs générateurs évoqués sont ceux de la structure `K` et non des opérateurs libres.
Par convention, pour simplifier l'écriture, lorsqu'un ensemble est inséré dans de telles listes, il est implicitement remplacé par son contenu. Ainsi nous avons `"<"{a,b},c">"` `=` `"<"a,b,c">"` `=` `"<"{a,b,c}">"` et de même pour les théories, nous avons `{T,{R,S}}` `=` `{T,R,S}` `=` `T "et" R "et" S`.
Étant donné un magma monogène `M` défini comme suit :
`M =` Magma monogène `("∗",a)`
`M = "<"a,"∗"">"`
Sa théorie d'égalité étant vide, il n'y a pas de différence entre son ensemble sous-jacent et son langage `"<"a,"∗"">"` . Les classes d'équivalences sont des singletons. Chaque terme désigne de façon biunivoque un élément. Aussi nous écrivons :
`"<"a,"∗"">"_M = "<"a,"∗"">"`
Ou autrement dit :
`a_M = a`
`"∗"_M = "∗"`
Les opérateurs en tant qu'élément de `M` se note `a_M` et `"∗"_M` et en tant que symboles se note `a` et `"∗"`. Et du fait de la déclaration `M =` Magma monogène `("∗",a)`, structure qui n'a pas de théorie, l'élément est égale au symbole, la structure `M` est égale à la structure libre `"<"a,"∗"">"`. Parcontre, dès que la théorie d'égalité n'est plus vide, ce n'est plus le cas. Étant donné un semi-groupe `S` défini comme suit :
`S =` Semi-groupe monogène `("∗",a)`
`S = "<"a,"∗"">/"{(x"+"y)"+"z = x"+"(y"+"z)}`
L'ensemble sous-jacent est alors égale à l'ensemble des classes d'équivalence définie sur le langage :
`S = "<"a,"∗"">"_S = ("<"a,"∗>")/({(x"+"y)"+"z = x"+"(y"+"z)})`
Le langage est noté `"<"a,"∗>"`. Les opérateurs générateurs `a` et `"∗"` sont dits libres. L'ensemble sous-jacent est noté `"<"a,"∗>"_S` ou bien `"<"a_S,"∗"_S">"`. Les éléments de la structure sont désignés par les termes, et représente la classe des termes qui les désignent. On note par le symbole `"≡"` l'égalité littérale de deux termes du langage de `S`. Et on définie l'égalité entre élément comme étant une relation d'équivalence plus lache notée par `"="` définie comme suit : Quelque soit deux termes `x` et `y` appartenant au langage de `S`, nous avons `x"="y` si et seulement si la théorie d'égalité de `S` démontre `x"="y`, ce qui se note `S⊢(x"="y)`.
Voici quelques éléments et leurs classes d'équivalence de termes associés dans `S` :
`a_S = {a}`
`a_Sa_S = {aa}`
`a_Sa_Sa_S = {(aa)a, a(aa)}`
`a_Sa_Sa_Sa_S = {((aa)a)a,(a(aa))a, (aa)(aa), a((aa)a), a(a(aa))}`
On remarque que tout mot du langage de `S` admet une forme normale consistant grace à l'associativité à déplacer les parenthèses le plus à gauche du mot possible comme par exemple : `((aa)(aa))a = ((((aa)a)a)a)` ce qui se note `aaaaa` en adoptant l'ordre d'évaluation de gauche à droite. Cette forme normal constitue un mot particulier de la classe de mots qui peut être utilisé pour désigner l'élément de la structure.
Dans un semi-groupe de type fini
`S =` Semi-groupe de type fini `("∗", A)`
L'ensemble `A` doit être fini et contient les éléments générateurs.
on remarque que tout mot du langage admet une forme normale consistant grace à l'associativité à déplacer pareillement les parenthèses le plus à gauche du mot possible comme par exemple : `((xz)(yx))x = ((((xz)y)x)x)` ce qui désigne une suite fini d'éléments générateurs `xzyx x` en adoptant l'ordre d'évaluation de gauche à droite. Cette forme normale constitue une bijection entre l'ensemble sous-jacent `S` et l'ensemble des mots de `A"*"-{epsilon}` dans lequel on a enlevé le mot vide `epsilon`. Le symbole `"*"` est le symbole de Kleene. `A"*"` est l'ensemble des suites finie d'éléments appartenant à `A`. Le symbole `epsilon` est le mot vide. Cela se généralise pour n'importe quel ensemble énumérable d'éléments générateurs `A`.
C'est pourquoi le semi-groupe libre de type fini, se note de deux façons :
`S =` Semi-groupe de type fini `("∗", A)`
`S = A"*" - {epsilon}` munie de l'opérateur de concaténation.
Cette structure correspond aux mots d'alphabet `A` sans le mot vide.
Il est possible d'utiliser des opérateurs générateurs non libres, qui ont déjà été définie.
Après l'une des deux définitions suivantes :
`S =` Semi-groupe monogène `("∗",a)`
`S = "<"a,"∗"">/"{(x"+"y)"+"z = x"+"(y"+"z)}`
Les opérateurs `"∗"` et `a` sont toujours libre, mais les opérateurs `"∗"_S` et `a_S` ne sont pas libres et font partie de la structure `S`. Ainsi `S = "<"a_S,"∗"_S">"`. Par contre avec la définition suivante :
Soit `("∗",a)` un semi-groupe monogène `S`
Cette déclaration définie les opérateurs `"∗"` et `a` tels que `"<"a,"∗>"=S`, et ainsi ils ne sont plus libres, mais sont des opérateurs qui font partie de la structure `S`. Tous se passe alors comme si la théorie d'égalité de `S` avait été incorporée dans la définition des opérateurs par la définition de la structure `S`.
Le langage de `S` est l'ensemble des emboitements finis clos appelés termes, qu'il est possible de faire avec les opérateurs générateurs de la structure pris en tant que symboles libres, et forme ainsi une structure libre. Tandis que l'ensemble sous-jacent est l'ensemble des compositions finies closes qu'il est possible de faire avec les opérateurs générateurs de la structure.
L'emboitement correspond à une composition que l'on n'aurait pas évaluée.
Une théorie d'égalité utilise un langage d'opérateurs d'arité fixe, l'unique prédicat d'égalité `"="`, le seul connecteur logique`"et"`, et des variables `x,y,z,...` pouvant être quantifiées universelle ou existentielle. Donc une théorie d'égalité n'utilise pas de négation, ni de disjonction.
---- 19 août 2019 ----
A toute théorie d'égalité correspond une structure de langage minimal qui en est sa matérialisation en quelque sorte, comprenant tous les opérateurs apparaissant au moins une fois dans l'expression de la théorie. Néanmoins la structure peut être augmenté de nouveaux opérateurs sans changer sa théorie d'égalité. Elle n'est alors plus de langage minimal car elle utilise un langage d'opérateurs plus riche.
Il y a donc dans toute structure une partie déclarative qui déclare le langage d'opérateurs utilisé. Cette partie s'appelle la présentation de la structure. Elle correspond aux extensions élémentaires, ou dit autrement à la déclaration des opérateurs générateurs de la structure, et est regroupée dans une autre partie de la théorie de la structure, dite théorie d'engendrement, et dont nous reparlerons plus-tard lorsque nous aborderons la récurrence.
Une théorie d'égalité écrite avec des opérateurs d'arité fixe, le prédicat `=`, les variables universelles `x,y,z...`, et les seuls connecteurs logiques `"et, ou"`, se développe en conjonction de clauses d'égalité de manière unique à l'ordre près des clauses, à l'ordre près des égalités dans chaque clause, et à la permutation près des variables universelles dans chaque clause, les variables universelles n'ayant de portée qu'à l'intérieur d'une clause.
L'égalité représente le niveau atomique. La clause d'égalité représente le niveau moléculaire.
Ainsi une théorie d'égalité admet une forme normale unique, un développement en conjonction de clauses unique. La forme normale de la théorie est appelée l'expression de la théorie. Néanmoins deux théories distinctes, c'est à dire d'expressions distinctes, peuvent être logiquement équivalentes.
Les mathématiques sont une science exacte, une machine peut énumérer toutes les déductions possibles. Les règles de déduction appliquées à l'expression d'une théorie `T` forme un énumérateur des propositions démontrables par `T`. La définition intuitionniste d'une théorie est cet énumérateur qui énumère toutes les propositions que la théorie peut démontrer. L'ensemble des propositions sous forme normale, démontrable par `T`, se note `"<"T">"`.
De la même façon qu'une structure de type fini énumère tous ses éléments par un procédé mécanique dit programmatif appelé énumérateur de la structure, une théorie énumère toutes les démonstrations qu'elle peut faire et donc toutes les propositions qu'elle peut démontrer, par un procédé mécanique dit programmatif appelé énumérateur de la théorie.
Cela signifie que quelque soit une proposition démontrable par la théorie `T`, l'énumérateur de la théorie `T` le produira en un temps fini, certe non borné.
Les théories d'égalité ne peuvent démontrer que des clauses d'égalité. Elles écartent une première symétrie qu'est la négation pour ouvrir sur d'autres symétries moins évidentes et propres à la construction. Une clause d'égalité est soit démontrée par `T` au bout d'un temps fini (non borné), ou soit n'est jamais démontrée par `T`.
Ainsi une théorie d'égalité n'infirme jamais aucune clause d'égalité. Une théorie d'égalité ne démontre que des clauses d'égalité. Autrement dit, une théorie d'égalité semi-décide les clauses d'égalité. Aussi, on est jamais sûre qu'une théorie `T` ne puisse pas démontrer une clause d'égalité, car pour le savoir il faudrait passer en revue toutes les démonstrations possibles ce qui demenderait un temps infini.
Les premières opérations de construction de structure que nous avons explorées sont :
Autrement dit, soit on ajoute un élément ou un opérateur au langage, ou soit on ajoute une clause d'égalité à la théorie.
La théorie d'une structure se résume donc en une énumération finie de clauses d'égalité mise entre accolade `{ }`. On dira que le Semi-groupe monogène `("+",1)` possède comme théorie `{"+"` est associatif`}`. Mais il peut y avoir plusieurs théorie équivalentes. Et il n'y a pas de raison de privilègier une théorie par rapport à une autre équivalente, aussi devons nous considérer plusieurs théories connues et équivalentes constituant ainsi une connaissance théorique de la structure. Cela constitue autant de points du vue logiques différents sur la structure. Les théories équivalentes supplémentaires apportent des connaissances supplémentaires sur la structure. Elles sont pourtant déduites de la première théorie, mais comme ces déductions demandent un temps de calcul et de recherche non pondérable, elles constituent bel et bien un enrichissement par introspection.
Un opérateur d'arité zéro est un élément de l'ensemble sous-jacent, mais tous les éléments ne sont pas considérés, seuls ceux qui sont nommés et ainsi rendus constructibles sont considérés. Un opérateur unaire est une application de l'ensemble sous-jacent sur lui-même, mais toutes les applications ne sont pas considérées, seules celles construites le sont, c'est à dire en tout cas calculable et dont le calcul est nommé. Un opérateur binaire est une application de l'ensemble des couples d'éléments de l'ensemble sous-jacent vers l'ensemble sous-jacent, et la même remarque s'applique. Etc..
La réunion de deux structures doit pouvoir se faire symétriquement, c'est à dire sans considérer que l'une phagocyte l'autre d'une quelconque manière. Et pour cela il faudra mettre en oeuvre un procédé symétrique. L'union libre disjointe est un tel procédé symétrique. C'est l'union qui propose le moins de contraintes. En faite, il n'y a aucune contrainte autre que celle de figurer sous des noms distincts dans un même schéma de langage d'opérateurs.
Deux structures forment, en dehors de toute contrainte, une bi-structure, c'est à dire une structure où il y a deux ensembles sous-jacents. Tous les opérateurs générateurs d'une structures sont considérés distincts des opérateurs générateurs de l'autres structure, ce qui garantie la possibilité de les rendrent égaux au cas par cas selon notre bon vouloir en ajoutant les égalités voulues à la théorie d'égalités.
Les deux ensembles sous-jacents sont respectivement idedentifiés par deux semi-prédicats. Un semi-prédicat et un prédicat calculable, et tel que son calcul est d'arrêt sûr pour tous les arguments satisfaisant le prédicat.
On ramène cette bi-structure en une structure comme suit :
Par exemple considérons deux structures :
`A = "<∘",a">/"{"∘"` est associatif`}`
`B = "<∗",b">/"{(x"∗"x)"∗"x"="x}`
Les ensembles sous-jacents des structures sont désignés par les mêmes lettres que les structures. La structure résultante de l'union libre disjointe notée `A+B` est :
`A+B = "<∘","∗",a,b">", A"(.)", B"(.)" "/" {` `A(a)`
de l'ensemble `A`.`A(x)` et `A(y) => A(x"∘"y)` `A(x)` et `A(y)` et `A(z) => (x"∘"y)"∘"z "=" x"∘"(y"∘"z)` `B(b)`
de l'ensemble `B`.`B(x)` et `B(y) => B(x"∗"y)` `B(x) => (x"∗"x)"∗"x= x` `}` (1). `A+B` comprend les générateurs de `A` et de `B` et deux semi-prédicats `A(.)` et `B(.)`.
(2). L'élément `a` appartient à `A`.
(3). L'opération `"∘"` est interne dans `A`.
(4). L'opération `"∘"` est associatif dans `A`.
(5). L'élément `b` appartient à `B`.
(6). L'opération `"∗"` est interne dans `B`.
(7). L'opération `"∗"` possède la propriété `(x"∗"x)"∗"x= x` dans `B`.
On remarque que les expressions de la forme :
`(A(x)` et `A(y))` `=>` `A(x"∘"y)`
se développent en :
`A(x"∘"y)` ou `¬A(x)` ou `¬A(y)`
La théorie d'égalités s'étend en introduisant une nouvelle notation, les semi-prédicats `A"(.)", B"(.)"` et leurs complémentaires `¬A"(.)", ¬B"(.)"`. L'opérateur logique de négation `¬` n'est pas utilisé autrement. La théorie est donc toujours considérée comme une théorie d'égalité, mais étendue par l'utilisation de deux semi-prédicats et leur complémentaires.
Un littérale est soit un semi-prédicat appliqué à un terme ou soit une égalité appliquée à deux termes.
Une théorie écrite avec des opérateurs d'arité fixe, le prédicat `=`, les semi-prédicats `A"(.)", B"(.)"` et leurs complémentaires `¬A"(.)", ¬B"(.)"`, les variables universelles `x,y,z...`, et les seuls connecteurs logiques `"et, ou"`, se développe en conjonction de clauses de littéraux de manière unique à l'ordre près des clauses, à l'ordre près des littéraux dans chaque clause, et à la permutation près des variables universelles dans chaque clause, les variables universelles n'ayant de portée qu'à l'intérieur d'une clause.
Le littéral représente le niveau atomique. La clause représente le niveau moléculaire
Le semi-prédicat est dit bien construit lorsqu'il habille un énumérateur bien construit. Sa définition doit obéir à des règles de récursivité simples.
Aucune contradiction ne peut apparaître du simple fait de l'union libre disjointe de deux structures. La théorie résultante est similaire à une théorie d'égalité malgré le perfectionnement que représente l'introduction des semi-prédicats bien construits et leur complémentaires.
Pour exprimer la propriété de l'existance d'un élément neutre sans utiliser de quantificateur existentiel, il est nécessaire d'ajouter au langage un élément qui joura le rôle de cet élément neutre. C'est pourquoi le monoïde se construit à partir du semi-groupe en ajoutant à son langage un tel élément, et en quotientant par les propriétés d'égalités relatives au rôle d'élément neutre.
Préférentiellement on note l'élément neutre pour une loi associative et commutative par le symbole `0`. et pour une loi générale, par le symbole `1`. L'une s'inscrit dans une notation dite additive, l'autre plus générale s'inscrit dans une notation dite multiplicative.
Considérons le Semi-groupe `("+") [1]` qui correspond à `NN"*"`. Le `1` en notation additive est le premier élément générateur. On remarque que si on ajoute l'élément neutre `0`, alors le monoïde obtenu correspond aux entiers naturels `NN` et n'est plus ni monogène, ni libre. Il est bigène est possède une théorie plus complexe. Les clauses supplémentaires sont énumérées et mises au dénominateur, et chacune complète la relation d'équivalence définie sur la structure libre.
Plusieurs cheminements de constructions sont possibles :
`NN = "<"0,1,"+>/"{"+"` est associatif`, 0` est élément neutre de `"+"}`
`NN =` Magma `("+") [0]"/"{"+"` est associatif`} [1]"/"{0 ` est élément neutre de `"+"}`
`NN =` Semi-groupe `("+") [1,0] "/" {0` est élément neutre de `"+"}`
`NN =` Semi-groupe `("+") [0] "/" {0` est élément neutre de `"+"} [1]`
`NN =` Semi-groupe monogène `("+",0) "/" {0` est élément neutre de `"+"} [1]`
`NN =` Semi-groupe monogène `("+",1) [0] "/" {0` est élément neutre de `"+"}`
`NN =` Semi-groupe bigène `("+",0,1) "/" {0` est élément neutre de `"+"}``{"+"` est associatif`} = {(x"+"y)"+"z=x"+"(y"+"z)}`
`{0` est élément neutre de `"+"} = {x"+"0=x, 0"+"x=x}`
On intègre dans le patron Semi-groupe, la propriété de l'existence d'un élément neutre que l'on devra nommer, et on obtient le patron Monoïde qui par extension élémentaire donne la structure des entiers naturels :
`NN =` Monoïde `("+",0) [1]`
Le patron Monoïde `("+",0)` prend deux aguments. Le premier terme `"+"` désigne l'opération associative interne, et le second terme `0` désigne l'élément neutre. On redéfinie les notions de liberté et de monogénéité relative à ce nouveau patron. La troisième sructure qui apparait est alors le Monoïde monogène libre. Il est unique à isomorphisme près et correspond aux entiers naturels `NN`. Sa présentation en notation programmative puis linguistique est la suivante :
`NN =` Monoïde monogène `("+",0,1)`
`NN = "<+",0,1">/"{(x"+"y)"+"z=x"+"(y"+"z), x"+"0=x, 0"+"x=x}`
Le patron Monoïde monogène `("+",0,1)` prend trois aguments. Le premier terme `+` désigne l'opération associative interne, le second terme `0` désigne l'élément neutre, et le troisième terme `1` désigne l'élément générateur. L'élément générateur engendre tous les éléments qui ne sont pas déjà définie dans le langage du patron.
Dans le Semi-groupe `("+") [0,1]`, si `0` est un élément neutre pour chaque éléments générateurs, cela entraine par récurrence que `0` est l'élément neutre pour tous les éléments du semi-groupe, et reciproquement. Aussi dans un Semi-groupe bigène `("+",0,1)`, grâce à l'associativité de l'opération `"+"`, nous avons l'équivalence suivante :
`{0` est l'élément neutre de `"+"} <=> {0"+"0"="0, 0"+"1"="1, 1"+"0"="1}`
Et dans un Semi-groupe trigène `("+",0,1,i)`, nous avons l'équivalence suivante :
`{0` est l'élément neutre de `"+"} <=> {0"+"0"="0, 0"+"1"="1, 1"+"0"="1, 0"+"i"="i, i"+"0"="i}`
Et ainsi de suite.
Il s'en suit que le Monoïde monogène `("+",0,1)` possède deux théories équivalentes :
Monoïde monogène `("+",0,1) = "<+",0,1">/"{(x"+"y)"+"z"="x"+"(y"+"z), x"+"0"="x, 0"+"x"="x}`
Monoïde monogène `("+",0,1) = "<+",0,1">/"{(x"+"y)"+"z"="x"+"(y"+"z), 0"+"0"="0, 0"+"1"="1, 1"+"0"="1}`
Néanmoins lorsque l'on compare les théories d'égalité, celles-ci ne sont pas équivalente !
`{(x"+"y)"+"z=x"+"(y"+"z), x"+"0=x, 0"+"x=x}`
`{(x"+"y)"+"z=x"+"(y"+"z), 0"+"0=0, 0"+"1=1, 1"+"0=1}`
Cela s'explique, car la théorie d'égalité indiquée au dénominateur n'est qu'une partie de la théorie de la structure. Il manque une propriété essentielle qui sort de la logique du premier ordre et qui affirme que le monoïde est engendré par `"<+",0,1">`. Et on regroupe cette partie dans la théorie d'engendrement.
La structure comprend formellement 3 théories, une théorie d'égalité, une théorie d'engendrement et une théorie tout court, cette dernière étant la conjonction des deux autres. Tandis que ce que l'on entend par théorie du patron est la théorie d'égalité seul, seul théorie a être du premier ordre.
C'est pourquoi on autorise l'écriture suivante pour regrouper la théorie d'égalité et la théorie d'engendrement en la théorie de la structure proprement dite :
`{bbbS"=<+",0,1">", (x"+"y)"+"z"="x"+"(y"+"z), x"+"0"="x, 0"+"x"="x}`
Le symbole `bbbS` désigne l'ensemble sous-jacent de la structure, et les crochets `"<>"` désigne la cloture par composition close. Ainsi nous avons bien :
`{bbbS"=<+",0,1">", (x"+"y)"+"z"="x"+"(y"+"z), x"+"0"="x, 0"+"x"="x}`
`<=>`
`{bbbS"=<+",0,1">", (x"+"y)"+"z"="x"+"(y"+"z), 0"+"0"="0, 0"+"1"="1, 1"+"0"="1}`
Notez qu'une extension élémentaire ne se fait pas à partir de la théorie d'une structure mais se fait à partir uniquement de sa théorie d'égalité, en imposant aux opérateurs ajoutés de se conformer à cette théorie d'égalité.
Par contre l'union libre de deux structures se fait à partir des théories des deux structures.
On définie donc un autre type d'extension qui se fait à partir de la théories de la structure (théorie d'égalité et théorie d'engendrement), qu'est l'extension libre. L 'extension libre d'une structure `bbbS` par un élément `e` est l'union libre disjointe de la structure `bbbS` avec la structure singleton `"<"e">"` ce qui se note `bbbS+"<"e">"`. Et dans ce cas, on voit bien que la théorie d'égalité de `bbbS` n'est pas imposée à l'élément `e`.
Dans la notation classique, la théorie d'une structure est séparée pareillement en deux parties, mais pas exactement sur la même frontière. Elle comprend une théorie d'engendrement qui ne désigne aucun élément de la présentation et qui la plus part du temps est omise ou laissée inconnue, et une théorie du premier ordre plus complète qu'une simple théorie d'égalité qui désigne les éléments de la présentation grâce aux quantificateurs existentiels. Ainsi le monoïde `M` sera noté de façon classique par :
`(M,"∗")` Monoïde
Le symbole `M` représente l'ensemble sous-jacent du monoïde. Et pour qu'il désigne le monoïde il faut le qualifié explicitement de monoïde `M`
L'opération interne `"∗"` est définie comme étant une application de `M^2->M` et donc une relation de `M^2->M` et donc un sous ensemble de `M^3`. Et pour lever toutes ambiguité, elle est désigné par le symbole `"∗"_M` et est appelé la loi interne du monoïde `M`.
La théorie d'engendrement du monoïde sera omise.
La théorie du premier ordre du monoïde `M` est notée sous forme d'une fonction propositionnelle portant le nom de la structure Monoïde`("∗")` :
Monoïde`("∗") = {`
`AAxAAyAAz, (x"∗"y)"∗"z"="x"∗"(y"∗"z)`
`EE1AAx,`
`x"∗"1"="x`
`1"∗"x"="x`
`}`
Les quantificateurs ont une portée implicitement définie sur `M`.
Le symbole `1` se comporte comme une variable.
Pour exprimer la propriété de réversibilité sans utiliser de quantificateur existentiel, il est nécessaire d'ajouter au langage un élément qui joura le rôle d'élément neutre et aussi d'ajouter une opération qui jouera le rôle de la fonction calculant l'inverse. C'est pourquoi le groupe se construit à partir du monoïde en lui ajoutant un opérateur unaire inv`"(.)"`.
Groupe `("∗", 1, `inv`) =` Monoïde `("∗",1)[`inv`] "/" {`inv est l'inverse pour atteindre `1` avec `"∗"}`
Préférentiellement, en notation additive cette fonction inv`"(.)"` s'appelle la négation et se note `"-(.)"`. Etant donné un élément `x`, l'élément `"-"x` est appelé l'opposé de `x`. Tandis qu'en notation multiplicative cette fonction inv`"(.)"` s'appelle l'inversion et se note parfois `(x"↦"x^-1)`. Etant donné un élément `x`, l'élément `x^-1 = tt"inv"(x)` est appelé l'inverse de `x`. On le note aussi à l'aide de la division `1"/"x` où `1` doit être l'élément neutre car la division à droite ou à gauche est alors identique. Parcontre la division par `x` d'un élément quelconque `y`, du fait de l'éventuelle non commutativité de la loi `"∗"`, doit préciser si elle s'effectue à droite ou à gauche de `y`.
`y` divisé à droite par `x` : `x^-1y` `y` divisé à gauche par `x` : `yx^-1`
Les notions de liberté et de monogénéité se redéfinissent relativement à ce nouveau patron. La quatrième structure qui apparait est le Groupe monogène libre. Il est unique à isomorphisme près, et correspond aux entiers relatifs `ZZ`. Et la loi étant associative et commutative on choisie la notation additive :
`ZZ =` Groupe monogène `("+", 0, "-", 1)`
`ZZ =` Groupe `("+", 0, "-")[1]`
`ZZ = "<"0, 1, "-", "+>" "/" {`
`"+"` est associative
`0` est l'élément neutre pour `"+"`
`"-"` est l'opposé pour atteindre `0` avec `"+"`
`}``{"+"` est associative`} = {(x"+"y)"+"z"="x"+"(y"+"z)}`
`{0` est l'élément neutre pour `"+"} = {x"+"0"="x, 0"+"x"="x}`
`{"-"` est l'opposé pour atteindre `0` avec `"+"} = {x"+"("-"x)"="0, ("-"x)"+"x"="0}`
Le langage mère que nous utilisons est `{0,1, "-(.)", "+(.,.)"}` auquel on ajoute les variables universelles `x,y,z`.
Le patron Groupe monogène `("+", 0, "-", 1)` contient l'implémentation de l'opération binaire `"+"`, de l'élément neutre `0`, de l'opération unaire `"-"`, et de l'élément générateur `1`, qui sont désignés dans un ordre précis. Parcontre la présentation `"<"0, 1, "-", "+>"` énumère les opérateurs générateurs dans un ordre quelconque. Notez que l'élément générateur `1` permet d'engendrer tous les éléments de la structure à l'aide des 3 opérateurs précédement définis `"+", 0 , "-"`.
Considérons la structure suivante :
Groupe monogène `("+",0,"-",1)`
Le langage de la structure est :
`"<+(.,.)", 0, "-(.)",1">"`
La théorie d'égalité de la structure est :
`"+"` est associative
`0` est l'élément neutre pour `"+"`
`"-"` est l'opposé pour atteindre `0` avec `"+"`
La théorie d'engendrement de la structure est :
`bbbS"=<+(.,.)", 0, "-(.)",1">"`
La théorie de la structure est la conjonction des deux. On résume cela en disant que le Groupe monogène `("+",0,"-",1)` correspond à la structure suivante :
` "<+", "-", 0, 1">" "/" {`
`(x"+"y)"+"z=x"+"(y"+"z)`
`x"+"("-"x)=0`
`("-"x)"+"x=0`
`x"+"0=x`
`0"+"x=x`
`}`
L'élément générateur `1` peut être ajouté à lui-même autant de fois, et tant que le résultat n'est pas égal à `0`, il ne peut pas être égal à une valeur précédemment calculée, car sinon l'ajout de `"-"1` entrainerait un tel résultat égal antérieur. `x"="y => (x"-"1)"="(y"-"1)`. Donc un groupe monogène est :
La notation classique du groupe `G` est :
`(G,"∗")` Groupe
Le symbole `G` représente l'ensemble sous-jacent du groupe. L'opération interne `"∗"` est désigné par le symbole `"∗"_G` et est appelé la loi interne du groupe `G`. La théorie d'engendrement du groupe est omise. La théorie du premier ordre du groupe `G` est notée sous forme d'une fonction propositionnelle portant le nom du patron de la structure avec une majuscule Groupe`("∗")` :
Groupe`("∗") = {`
`AAxAAyAAz, (x"∗"y)"∗"z"="x"∗"(y"∗"z)`
`EE1AAxEEy,`
`1"∗"x"="x`
`x"∗"1"="x`
`x"∗"y"="1`
`y"∗"x"="1`
`}`
Les quantificateurs ont une portée implicitement définie sur `G`. Le symbole `1` se comporte comme une variable. L'opérateur d'inversion inv est implicitement définie dans l'axiome :
`EE1AAxEEy, x"∗"y"="1 "et" y"∗"x"="1`
Les quantificateurs `AAxEEy, P(x,y)` introduisent une dépendance entre le choix de `y` et celui de `x`. Cette proposition est équivalente à `EEy"(.)"AAx, P(x,y(x))`si on accepte l'axiome du choix, et s'appelle la skolémisée. Par contre si on ne prend pas l'axiome du choix comme une règle de raisonnement, alors nous n'avons qu'une implication :
`AAxEEy, P(x,y) ⇐ EEy"(.)"AAx, P(x,y(x))`
La théorie d'un groupe `(G, "∗")` comprend une théorie d'engendrement qui ne désigne aucun élément de la présentation ni la fonction inverse mais seulement la loi interne `"∗"`, et qui la plus part du temps est omise ou laissée inconnue. Et elle comprend une théorie du premier ordre plus complète qu'une simple théorie d'égalité, qui désigne les éléments de la présentation grâce aux quantificateurs `EEx`, et qui désigne les fonctions unaires de la présentation grace aux quantificateurs imbriqués `AAxEEy`.
La récurrence et à la base de toutes constructions infinies. On la présente classiquement appliquée à l'ensemble des entiers naturels `NN` comme suit. Etant donné une fonction propositionnelle unaire `P` définie sur `NN`, c'est à dire une fonction de `NN"→"{`true, false`}`, l'axiome de récurrence est le suivant :
Notez que seul la structure de semi-groupe monogène est utilisée, et qu'il n'y a nul besoin de connaître le zéro. Il conviendrait donc, dans l'exposé générale des mathématiques, de définir la récurrence, d'abord appliquée à l'ensemble des entiers strictement positifs `NN"*"` comme suit :
`((P(1)),(AAn"∈"NN"*, "P(n) "⇒" P(n"+"1)))`
Mais il est tout à fait possible de définir la récurrence sans faire intervenir les entiers. On parle alors de récurrence générale. La récurrence est étroitement liée à la structure, car c'est elle qui explicite la théorie d'engendrement de la structure.
Le principe est le même que pour les entiers, mais au lieu de s'appliquer qu'à un seul élément et qu'à un seul moyen de construction, il s'applique à un ensemble d'opérateurs générateurs `E`.
On dit qu'une fonction propositionnelle unaire `P` est transmise par un opérateur, si et seulement si l'évaluation de cet opérateur, en ne prenant comme entréz que des éléments satisfaisant `P`, produit nécessairement un élément satisfaisant `P`.
Par exemple, étant donné les 3 opérateurs suivants `a,f"(.)",g"(.,.)"` que l'on regroupe en un ensemble `E={a,f,g}`, la fonction propositionnelle unaire `P` est transmise par les opérateurs de `E` si et seulement si :
`AAx"∈<"a,f,g">", P(x)"⇒"P(f(x))`
`AA(x,y)"∈<"a,f,g">"^2, (P(x)` et `P(y)) "⇒" P(g(x,y))`
Le principe de récurrence générale affirme que si une fonction propositionnelle unaire `P` est transmise par les éléments et opérateurs de `E`, alors elle sera vrai pour tout les éléments engendrés par `E` que l'on note `"<"E">"`.
`E = {a,f"(.)",g"(.,.)"}`
`AAx"∈<"E">", P(x)"⇒"P(f(x))`
`AA(x,y)"∈<"E">"^2, (P(x)` et `P(y)) "⇒" P(g(x,y))``=>`
L'ensemble `"<"E">"` constitue la structure engendrée par `E`.
Le patron groupe bigène `("∗",1,tt"inv",a,b)` prend cinq aguments. Le premier terme `"∗"` désigne l'opération associative interne, le second terme `1` désigne l'élément neutre, le troisième terme `tt"inv"` désigne l'opération calculant l'inverse, le quatrième terme `a` désigne le prermier élément générateur, et le cinquième terme `b` désigne le second élément générateur.
Le Groupe bigène `("∗",1,tt"inv",a,b)` correspond à la structure suivante :
` "<"a,b,1,"∗",tt"inv>" "/" {`
`(x"∗"y)"∗"z=x"∗"(y"∗"z)`
`x"∗"x^-1=1`
`x^-1"∗"x=1`
`x"∗"1=∗`
`1"∗"x=x`
`}`
Considérons le groupe suivant :
`G =` Groupe bigène `("∗",1,tt"inv",a,b)`
Considérons la notation `"<x,y,z,...>"` comme étant l'ensemble des éléments calculables par une combinaisons finie d'éléments `x,y,z,...` et des opérateurs `"∗"` et `1` et `tt"inv"`. Ainsi nous randons implicite les opérateurs de groupe dans l'opération d'engendrement, et nous pouvons écrire :
`G = "<"a,b">"`
Ce groupe `G` admet donc deux sous-groupes `"<"a">"` et `"<"b">"`. Et on construit leur union libre en tant que groupe, comme étant le groupe libre bigène quotienté par la théorie de `"<"a">"` restreinte à `"<"a">"` et la théorie de `"<"b">"`restreinte à `"<"b">"`. Cela produit un nouveau concept d'union libre, « l'union libre en tant que groupe ». Le premier concept évoqué étant « l'union libre en tant que magma ».
Etant donné un groupe `(G,"∗")` et un ensemble `E sube G`. L'ensemble `E` est dit générateur si et seulement si tout élément de `G` peut être obtenue par une combinaison finie d'éléments de `E` et de `1` et, de `"∗"` et de `tt"inv"`. Et l'ensemble `E` est dit indépendant si et seulement si aucun élément de `E` ne peut être obtenue par une combinaison finie des autres éléments de `E` et de `1` et de `"∗"` et de `tt"inv"`.
On adopte une notation programmative plus générale définissant une structure de type fini ou non, et mettant en exergue l'ensemble de tous les éléments ajoutés par extension élémentaire, et qui forme un ensemble générateur et indépendant. Notez alors que l'élément neutre ne fait pas partie de cet ensemble. Le patron Groupe représente un groupe engendré par un ensemble générateur. Et on considère deux groupes :
`G =` Groupe `("∗", 1, tt"inv", E_G)`
`H =` Groupe `("∗", 1, tt"inv", E_H)`
`E_G` et `E_H` sont les ensembles générateurs. Ces deux groupes s'expriment en notation linguistique comme suit :
`G = "<"E_G,1,"∗", tt"inv>" "/" {"groupe"("∗",1,tt"inv"),T_G}`
`H = "<"E_H,1,"∗", tt"inv>" "/" {"groupe"("∗",1,tt"inv"),T_H}`
Les propositions `T_G` et `T_H` sont appelées les spécificités théoriques de `G` et `H` autres que celle d'être un groupe.
La fonction propositionnelle `"groupe"("∗",1,tt"inv")` est définie par :
`"groupe" (⋅, e, f) "=" {`
`(x"⋅"y)"⋅"z=x"⋅"(y"⋅"z)`
`x"⋅"f(x)=e`
`f(x)"⋅"x=e`
`x"⋅"e=x`
`e"⋅"x=x`
`}`
Vous noterez alors la distinction entre `"groupe"("∗",1,tt"inv")` et `"Groupe"("∗")`, le premier constituant la skolémisé du second. Si on accepte l'axiome du choix comme une règle de raisonnement alors nous avons :
`"Groupe"("∗") <=> EE1EEtt"inv(.)", "groupe"("∗",1,tt"inv")`
Par contre si on ne prend pas l'axiome du choix comme une règle de raisonnement, alors nous n'avons qu'une implication :
`"Groupe"("∗") ⇐ EE1EEtt"inv(.)", "groupe"("∗",1,tt"inv")`
Par convention les ensembles placés entre crochet doivent être substitué à leur contenant :
`"<"{a,b},c">" = "<"a,b,c">"`
et de même pour les théories placées entre crochet `"<>"` ou crochet `{}` qui signife je le rappel une conjonction :
`"<"{P_1,P_2},P_3">" = "<"P_1,P_2,P_3">"`
`{{P_1,P_2},P_3} = {P_1,P_2,P_3}`
Puis on rend implicite la présence de `"∗",1,tt"inv"` dans les crochets d'engendrement en le précisant ainsi dans le contexte. Nous avons donc :
`"<"E_G">" = G`
`"<"E_H">" = H`
L'union libre en tant que groupe est une union de groupe qui produit un groupe coïncidant sur chacun des deux groupes et qui propose le moins de contrainte. On construit donc le groupe union libre de `G` et `H`, notée `G•H`, comme suit :
`G•H="<"1, E_G,E_H, "∗", tt"inv>" "/" {T_G"|"_("<"E_G">"), T_H"|"_("<"E_H">"), "groupe"("∗",1,tt"inv")}`
On peut appliquer cette union libre a deux groupes ayant des opérations internes de nom différent `"∗"_G` et `"∗"_H`, mais dont l'intersection doit constituer un groupe dans lequel les deux opérations `"∗"_G` et `"∗"_H` coïncident et donc où les deux éléments neutres `1_G` et `1_H` coïncident. On construit alors le groupe union libre de `G` et `H`, notée `G•H`, de la même façon en renommant les opérations par l'unique opération `"∗"` de l'union libre en tant que groupe.
----- 17 mars 2018 -----