Une approche empirique et formelle de la construction du corps des nombres entiers, rationnels, réels, complexes et quaternioniques.
Un corps est un ensemble `K` muni de deux lois de compositions `"+"` et `"∗"` satisfaisant les propriétés suivantes :
L'addition `"+"` est associative et commutative. La multiplication `"∗"` est associative et distributive sur l'addition à droite et à gauche. L'addition possède un élément neutre. La multiplication possède un élément neutre à la fois à droite et à gauche. L'addition admet un opposé. La multiplication admet un opposé que l'on appelle inverse sauf pour l'élément neutre de l'addition.
Pour être rigoureux, on transcrit ces propriétés dans le langage de la logique du premier ordre en prenant comme domaine l'ensemble `K`, et on les met sous forme d'une conjonction de clauses prénexe qui constitue la théorie du corps :
Déclaration de variables `EE0EE1AAxEEoEEiAAyAAz {` (1) Commutativité de l'addition :
`x"+"y"="y"+"x` (2) Associativité de l'addition : `(x"+"y)"+"z"="x"+"(y"+"z)` (3) Associativité de la multiplication : `(x"∗"y)"∗"z"="x"∗"(y"∗"z)` (4) Distributivité à gauche : `x"∗"(y"+"z)"="(x"∗"y)"+"(x"∗"z)` (5) Distributivité à droite : `(y"+"z)"∗"x=(y"∗"x)"+"(z"∗"x)` (6) Elément neutre de l'addition : `x"+"0"="x` (7) Elément neutre à gauche de la multiplication : `1"∗"x"="x` (8) Elément neutre à droite de la multiplication : `x"∗"1"="x` (9) L'opposé : `x"+"o"="0` (10) L'nverse à gauche : `x "=" 0 "ou" i"∗"x"="1` (11) L'inverse à droite : `x "=" 0 "ou" x"∗"i"="1` `}`
Notez qu'il faut considérer les symbole `0` et `1` comme des variables à part entière (similaires aux variables `x`,`y`,`z`,`o`,`i`). Notez que ces 11 propriétés étant sous la portée d'une déclaration commune de variables contenant des variables existentielles, elles ne constituent pas 11 axiomes séparées. On les regroupes dans une fonction propositionnelle `P(0,1,x,o,i,y,z)` :
`P(0,1,x,o,i,y,z) <=> ((x"+"y"="y"+"x),((x"+"y)"+"z"="x"+"(y"+"z)),((x"∗"y)"∗"z"="x"∗"(y"∗"z)),(x"∗"(y"+"z)"="(x"∗"y)"+"(x"∗"z)),((y"+"z)"∗"x=(y"∗"x)"+"(z"∗"x)),(x"+"0"="x),(1"∗"x"="x),(x"∗"1"="x),(x"+"o"="0),(x "=" 0 "ou" i"∗"x"="1),(x "=" 0 "ou" x"∗"i"="1))`
Notez que le saut de ligne correspond à une conjonction. La structure de corps `K` est désignée par le triplet suivant :
`(K,"+","∗")`
Où `K` est l'ensemble sous-jacent, et où `"+(.,.)"` et `"∗(.,.)"` sont deux lois de compositions c'est à dire des opérateurs binaires internes définis partout sur `K"×"K` et satisfaisant la théorie suivante :
`EE0EE1AAxEEoEEiAAyAAz P(0,1,x,o,i,y,z)`
La définition du corps s'agrémente de cinq règles syntaxiques : Les opérateurs `"+(.,.)"` et `"∗(.,.)"` ont une syntaxe centrée et la multiplication est de syntaxe prioritaire sur celle de l'addition. De tel sorte que, grace à l'associativité de ces opérations, l'absence de parenthèse dans une combinaison quelconque d'additions et de multiplications n'est plus ambigüe. La multiplication `"∗"` se note également par absence de symbole simplement en juxtaposant les arguments, `x"∗"y=xy`.
Grace à l'axiome du choix, il est possible de choisir les variables déclarées existentiellement pour chaque situation antérieur. La théorie sous forme prénexe étant `EE0EE1AAxEEoEEiAAyAAz P(0,1x,o,i,y,z)`, pour chaque situation caractérisée par la connaissance de `x` on choisit arbitrairement une solution, une valeur de `o` et de `i` que l'on nomme `o(x)` et `i(x)` puisque ce choix dépend de `x`. La théorie sous forme skolémisée s'écrit dans le langage logique du second ordre comme suit, où les quantificateurs existentiels de `o` et de `i` sont passés devant le quantificateur universel de `x` :
`EE0EE1EEo(".")EEi(".")AAxAAyAAz P(0,1x,o(x),i(x),y,z)`
Puis on procède à une extension du langage de la structure qui ne possédait jusqu'alors que les deux opérateurs binaires `"+(.,.)"` et `"∗(.,.)"`. On ajoute au langage deux éléments `0` et `1` et deux opérateurs unaires `o(".")` et `i(".")`. Puis on renomme ces deux opérateurs unaires, `o(".")` en `"-(.)"` plus apte à évoquer le calcul de l'opposé, et `i(".")` en `"÷(.)"` plus apte à évoquer le calcul de l'inverse. La structure de corps `K` est alors désignée par le septuplet suivant :
`(K,"+",0,"-","∗",1,"÷")`
Où `K` est l'ensemble sous-jacent, et où `"+(.,.)"` et `"∗(.,.)"` désignent deux lois opérateurs binaires internes et définis partout sur `K"×"K`, où `0` et `1` désignent chacun un élément de `K`, où `"-(.)"` désigne un opérateur unaire interne et défini partout sur `K`, et où `"÷(.)"` désigne un opérateur unaire interne et défini partout sur `K"-"{0}` et satisfaisant la théorie suivante :
`AAxAAyAAz P(0,1,x,"-"(x),"÷"(y),y,z)`
La définition du corps s'agrémente de sept règles syntaxiques supplémentaires. On note les opérateurs unaires `"-(.)"` et `"÷(.)"` sans mettre de parenthèse en juxtaposant l'opérateur à l'opérande. Ainsi, `"-"(x)` et noté `"-"x`, et `"÷"(x)` est noté `"÷"x`. Puis ces opérations sont posées de priorité supérieur aux autres faisant que `"-"x"+"y` vaut `("-"x)"+"y` et que `"÷"xy` vaut `("÷"x)y`. Puis la juxtaposition d'un élément à l'opérateur `"-"` est interprétée comme une addition, faisant que `x"-"y"-z` = `x"+"("-"y)"+"("-"z)`. Puis la juxtaposition d'un élément à l'opérateur `"÷"` est interprétée comme une multiplication, faisant que `x"÷"y"÷"z` = `x("÷"y)("÷"z)`. Puis on note l'inverse de `x` par `x^-1`. Ainsi `"÷"x = x^-1`.
La logique du premier ordre se suffit à elle-même pour raisonner et n'a pas besoin de la théorie des ensembles pour fonder des mathématiques. La théorie du corps vue de l'intérieur n'a pas besoin du concept d'ensemble. L'ensemble sera remplacé par le prédicat.
Le corps vu de l'intérieur se définit en présentant son langage `("+(.,.)",0,"-(.)","∗(.,.)",1,"÷(.)")` et sa théorie qui comprend 11 axiomes :
`AAxAAyAAz {` `x"+"y"="y"+"x` `(x"+"y)"+"z"="x"+"(y"+"z)` `x(yz)=(xy)z` `x(y"+"z)=xy"+"xz` `(y"+"z)x=yx"+"zx` `x"+"0"="x` `1"∗"x"="x` `x"∗"1"="x` `x"+"("-"x)=0` `x"="0" ou "x x^-1 "="1` `x"="0" ou "x^-1x"="1` `}`
Les propriétés d'absorption de `0` ne figure pas comme axiome car elles sont déduisibles :
`x"∗"0=0`
`0"∗"x=0`
En effet nous avons :
`x"∗"0=x"∗"(0+0)`
`x"∗"0=x"∗"0+x"∗"0`
`x"∗"0-x"∗"0=x"∗"0+x"∗"0-x"∗"0`
`0=x"∗"0`
Donc l'élément `0` est absorbant à droite. On démontre de même que `0` est absorbant à gauche.
Si le corps est commutatif, son axiomatique tient en 9 axiomes :
`AAxAAyAAz {` `x"+"y"="y"+"x` `xy=yx` `(x"+"y)"+"z"="x"+"(y"+"z)` `x(yz)=(xy)z` `x(y"+"z)=xy"+"xz` `x"+"0"="x` `x"∗"1"="x` `x"+"("-"x)=0` `x"="0" ou "x x^-1"="1` `}`
L'absence d'ensemble sous-jacent apporte une petite différence, une faculté supplémentaire, à savoir que la théorie du corps peut s'appliquer non seulement à tout ensemble choisie comme domaine mais également à la catégorie de tous les éléments qui..., elle... , ne constitue pas un ensemble.
Sans introduire de nouveaux éléments d'où le qualificatif agène, la structure de corps précédement décrite comprend déjà 2 éléments que sont le zéro `0` et l'unité `1`. L'unité `1` avec l'addition va engendrer librement le demi-anneau `NN` d'où le qualificatif libre, et avec la soustraction, va engendrer l'anneau des entiers relatifs `ZZ`, et à l'aide de la division, va engendrer le corps des rationnels `QQ`. Et c'est la complétion de l'espace métrique `QQ` qui va engendrer le corps des réels `RR` comme suit :
Tout réel est désigné par une suite de Cauchy à coefficient rationnel `(x_n)_(n in NN)` où `x_n"∈"QQ`, c'est-à-dire par une suite convergente de rationnels mais sans préciser vers quoi :
`AA q"∈"NN, EE k"∈"NN, AAn">"k, ||x_n-x_k||"<"1/q`
Quelque soit un diamètre ici égale à `2"/"q` aussi petit que l'on veut en prenant un entier `q` aussi grand que l'on veut, il existe un indice `k` à partir du quel tout les éléments de la suite sont dans un intervalle de cette taille. Ainsi avons-nous défini une suite convergente sans avoir précisé vers quoi elle convergeait. Cette suite définit un réel. Deux suites de Cauchy `(x_n)_(n in NN)` et `(y_n)_(n in NN)` définissent le même réel si et seulement si leur différence `(x_n-y_n)_(n in NN)` est une suite convergeante vers zéro. Voilà comment est construit `RR`.
La première opération que nous allons définir est l'élévation à la puissance `(b,x)|->b^x`. Celle-ci se définit d'abord empiriquement dans `NN"*×"NN"*"` comme suit :
`b^n = overset("n fois")(overbrace(b"∗"b"∗"..."∗"b))`
Le nombre `b` s'appelle la base de l'exponentielle, le nombre `n` s'appelle le degré. Comment passer de la définition empirique à la définition formelle ? En remplaçant les trois petit points de l'éllipse par un programme de taille finie. C'est d'ailleurs ainsi qu'il faut interpréter la définition elliptique pour lui donner son sens formel :
`overset("n fois")(overbrace(b"∗"b"∗"..."∗"b)) = prod_(i=1)^(i=n) b`
L'élévation à la puissance obéït à une propriété remarquable :
`AAbAAxAAy, b^(x+y)=b^xb^y`
Cette propriété va permettre d'étendre de manière unique l'élèvation à la puissance `(b,x)|->b^x` sur `RR"*×"RR`.
Supposons que `b^0` existe. Alors en appliquant la propriété précédente nous avons :
`b=b^1=b^(0+1)=b^0b^1=b^0b` Donc : `b^0=1`
Supposons que `b^-1` existe. Alors nous avons :
`1=b^0=b^(1-1)=b^(1+(-1))=b^1b^-1= b b^-1`
Donc `b^-1` est l'inverse de `b`. Donc `b` est inversible, et donc ne peut pas être étendu à zéro, `b"≠"0`, et `b^-1=÷b`. Par la suite, on préférera noter l'inverse de `x` par `x^-1` plutôt que par `÷x`.
Supposons que `b^(1/2)` existe. Alors nous avons :
`b^(1/2)b^(1/2) = b`
Autrement dit `b^(1/2)` est la racine-carré de `b`. On la note avec le symbole de racine-carré :
`b^(1/2)=sqrt(b)`
Mais quelle est-elle ? Comment définir ce réel ? Par une suite de Cauchy, car les réels sont tous définis par des suites de Cauchy à coefficients rationnels. Le plus simple pour établir cette suite de Cauchy et d'utiliser un algorithme de calcul convergeant vers `sqrt(b)` tel qu'inspiré par l'algorithme de Newton.
On part d'une valeur `x` proche de `sqrt(b)` qui est soit `b` ou soit `-b` :
`x"+"epsilon = sqrt(b)`
`(x"+"epsilon)^2 = b`
`x^2 + 2xepsilon + epsilon^2 = b`
Et on cherhe à calculer une nouvelle valeur de `x` davantage proche de `sqrt(b)` ou de `-sqrt(b)`. Dans l'équation précédente, si on néglige `epsilon^2` devant `x^2`, on obtient la méthode de Héron :
La valeur approchée suivante est `x"+"epsilon`. La série de Heron se définit par :`x^2 + 2xepsilon ≈ b`
`x + 2epsilon ≈ b/x`
`2(x "+" epsilon) ≈ x"+"b/x`
`x"+"epsilon ≈ 1/2(x"+"b/x)`
`x_(n+1) = 1/2(x_n "+" b/x_n)`
Que l'on peut écrire sous forme d'algorithme :
`x:=1/2(x"+"b/x)`
Reste à démontrer que cette suite converge toujours quelque soit la valeur initiale, et qu'elle converge vers un unique réel ou sa négative qui, tout deux, multipliés par eux-même sont égaux à `b`.
L'esprit humain étant limité, on ne peut pas proposer d'étape mettant en interaction un trop grand nombre de variables à la fois, sous peine de bloquer l'analyse et de rebuter le lecteur. Nos travaux ne doivent pas être réservés qu'à quelques rares spécialistes ayant développé une capacité d'analyse hors du commun et qui seraient seuls capablent de nous lire, mais doit au contraire s'addresser au plus grand nombre, seule garantie du caractère démocratique de notre entreprise. Cela nécessite de bien choisir le cheminement pour ne passer que par des étapes simples.
L'unicité des solutions dans `RR` tient en grande partie à une caractéristique essentielle du corps des réels qu'est son ordre total. L'ordre total sur `RR` est le prolongement de l'ordre total sur `QQ` qui découle de l'ordre total sur `ZZ` qui lui même découle de la construction libre de `NN"*"` à partir de l'unité `1`. La dernière étape se démontre formellement en étudiant les suites de Cauchy, en constatant que l'on peut comparer un réel et un rationnel et en remarquant que pour chaque couples de réels `(x,y)` distints quelconques `x"≠"y`, il existe trois rationnels `a,b,c` tels que `a"<"x"<"b"<"y"<"c` ou `a"<"y"<"b"<"x"<"c`.
Le principe de construction libre de `NN"*"` n'est pas une propriété exprimable en logique du premier ordre. Cela complique la définition formelle de l'ordre issu de cette construction. C'est pourquoi l'approche classique, pour contourner la difficulté, pose les axiomes de l'ordre en même temps que ceux du corps. Mais il convient alors de procèder par étape pour ne pas être aveuglé par nos propres constructions, en définissant d'abord les structures ordonnées les plus simples. La première étape est la construction de `NN` appelé la demi-droite discrète ou le monoïde monogène libre, dans lequel l'ordre est défini par une proposition du second ordre dont on transcrit certaines de ses conséquences en proposition du premier ordre que l'on ajoute à l'axiomatique.
Un premier constat global qu'il convient de faire, est la simplicité axiomatique du corps dans sa forme de Skolem qui n'est composé que de propositions universelles d'égalité dans le domaine de Herbrand `"<@"K, 0,1,"+(.,.)","-(.)","∗(.,.)","÷(.)"">"` où il faut remplacer `"@"K` par le contenu de `K`. Cela nous invite à un raccourci conceptuel, à l'adoption plus facile d'une partie du paradigme mathématique dit égalitaire. C'est une hypothèse sémantique. Les structures classiques, dépouillées de leur théorie, sont des magmas généralisés, c'est à dire des langages libres engendrant le domaine de Herband. L'hypothèse sémantique consiste à dire que toutes ces égalités axiomatiques qui correspondent à des fusions d'éléments dans le domaine de Herbrand, peuvent s'appliquer complètement à tous les éléments du domaine de Herbrand, et ceci quelque soit la cardinalité de cet ensemble.
En informatique, le choix d'un langage de programmation réellement adapté au problème constitue la moitier de sa résolution. Il en est de même en mathématiques. Le choix d'un langage formel sur mesure adapté au problème constitue la moitier de sa résolution. C'est pourquoi une grande partie de l'étude consistera à établir ce langage.
Pour éviter l'usage intensif des parenthèses, on définit les priorités syntaxiques, des plus faibles aux plus fortes, pour les opérateurs binaires comme suit :
`+` `"∗"` `|->` `"=,≠,<,>,⩽,⩾"...` `"et","ou"` `"⇒","⇐"` `<=>` `AA,EE`
faisant que :
`x"="y => P(x,y)` signifit `(x"="y) => P(x,y)` et non `x "=" (y => P(x,y))`.
`x "et" y => z "ou" t` signifit `(x "et" y) => (z "ou" t)` et non `x "et" ((y=>z) "ou" t)`.
`AAx,P(x) => AAy,Q(y)` signifit `AAx,(P(x) => AAy,Q(y))` et non `(AAx,P(x)) => AAy,Q(y)`.
`x|->x"+"x` signifit `x|->(x"+"x)` et non `(x|->x)"+"x`.
Les mathématiques se fondent par la logique dans un formalisme Hilbertien post-Chomsky, où la théorie des ensembles n'est plus indispensable pour fonder les mathématiques. L'ensemble est remplacé par le prédicat, et le terme désignant l'élément prend davantage de réalité par son formalisme que l'élément lui-même.
Néanmoins la notion d'ensemble perdure, assurement à l'abri de tous les paradoxes lorsque il est fini ou énumérable. Il engendre une autre notion similaires qu'est le type, une notion plus proche du langage et de l'informatique qui permet de définir les types de transformation de données passant d'une donnée de type `A` à une donnée de type `B`. C'est pourquoi lorsque l'on suit cette voie, on définit en premier la notion d'application qui est une fonction définie partout sur son ensemble de départ, d'un ensemble de départ `A` vers un ensemble d'arrivée `B`, transformant toute donnée de type `A` en une donnée de type `B`.
La notion d'application est couramment utilisée en informatique. Elle est plus simple que celle de fonction car elle garantit toujours un résultat dans l'ensemble d'arrivé. L'application `f` de `A` vers `B`, appliquée à un élément `x` de `A`, va produire l'élément `f(x)` de `B`. On dira que `x` est de type `A` et que `f(x)` est de type `B`. Néanmoins il y a une différence entre ces deux notions, type et ensemble, une subtilité propre au langage formel à la base du raisonnement formel. Les expressions `x` et `f(x)` sont des termes obéïsant à certaines contraintes exigées par le type et désignant chacun un élément. Une même expression peut être perçu selon différents types. Changer le type d'une expression dans la mesure du possible, ne modifie pas l'expression. Celle-ci porte en elle un sens logique qui transcende plusieurs types. C'est comme changer de point de vue, changer de subjectivité. Cet aspect qui traite du type fait partie de la logique formelle. L'autre aspect qui traite de l'ensemble et de l'élément reste ouvert..., sans causer pour autant de crise des fondements, car le premier aspect suffit pour fonder les mathématiques par les règles de raisonnement formel.
Les mathématiques peuvent être vues comme une extension de l'informatique mettant en oeuvre la possibilité conceptuelle d'exécuter un nombre infini quelconque d'instructions dans une mémoire d'une taille infinie quelconque. C'est ainsi que l'on peut résumer le paradigme mathématique intégrant l'axiome du choix, l'axiome qui permet de faire une infinité de choix arbitraires. Cet axiome permet de construire ces programmes de taille infinie quelconque et de les exécuter.
Une application `f` de `A` vers `B` est un ensemble d'arcs inclus dans `A"×"B` tel que pour chaque élément de `A` il existe un et un seul arc partant. L'ensemble des applications de `A` vers `B` se note `A"→"B`. Il existe une seconde notation qui est `B^A`, l'élévation de `B` à la puissance `A`, qui est le produit `B"×"B"×"B..."×"B` répété `|A|` fois, et que l'on note sous forme d'un produit formel en précisant qu'il s'agit du produit cartésien d'ensembles.
`A"→"B = B^A = prod_(a in A)B`
Les notation suivantes sont possibles :
`f "∈" (A"→"B) f"="(f(a))_(a in A) f"="{(a,f(a)) "/" a "∈" A}`
La définition d'une application de `A` vers `B` est :
`f "∈" (A"→"B)`
`f "⊂" A"×"B`
`AA x "∈" A"," EE y "∈" B,`
`(x,y) "∈" f `
`AAz"∈" B, (x,z) "∈"f => z"="y`
que l'on note aussi comme suit :
`f "∈" (A"→"B)`
`f "⊂" A"×"B`
`AA x "∈" A"," EE!y "∈" B, (x,y) "∈" f `
Le programme qui exécute de façon transfinie cette fonction `f(".")` peut s'écrire ainsi :
`x|->`
`AA (a,b) "∈" f {`
` "if" a"="x "then return" b`
`}`
On s'évertue à donner la définition la plus générale d'une fonction en se basant sur la logique formelle. Une fonction `f` s'applique à un élément et retourne soit un élément appelé image ou soit rien. Autrement-dit une fonction peut à priori s'appliquer à tout mais ne produit pas toujours un résultat. Lorsqu'elle est définie sur un ensembe de départ, la différence qu'il y a entre une fonction et une application tient en ce que la fonction n'est pas définie partout sur son ensemble de départ.
On construit notre langage logique en considérant que tout terme désigne un élément, ceci afin d'accéder au domaine de Herbarnd avec toute la facilité de la construction des termes. Mais avec une fonction `f(".")`, en l'appliquant à un élément `x` quelconque, le terme résultant `f(x)` ne désigne pas toujours un élément !. Le terme `f(x)` n'est autorisé dans le langage que s'il désigne un élément. Il existe un moyen simple d'éviter cette complexification du langage qui consiste à définir un élément spécial pour désigner le hors domaine des fonctions.
Par convention, lorsqu'une fonction `f` n'est pas définie sur l'entrée `x` alors son application à `x` produit le terme `f(x)` qui est égal à l'élément spécial `"⧫"` indiquant le hors-domaine. Et toute nos fonctions appliquées à un hors-domaine `"⧫"` ou à une liste d'arguments comprenant un hors-domaine `"⧫"` doivent, par principe, retourner le hors domaine `"⧫"`. Et tous nos ensembles, par principe, ne doivent pas contenir l'élément hors-domaine `"⧫"`.
Il existe un second moyen d'éviter cette complexification qui consiste à étendre la fonction aux ensembles et donc à généraliser la notion de fonction en la notion de relation. En effet, une relation `f` de `A` vers `B` est un sous-ensemble d'arcs quelconque de `A"×"B`, et on dira que la relation `f` appliquée à un élément `x` de `A` que l'on note `f "⸨"{x}"⸩"` désigne un sous-ensemble de `B` qui est l'ensemble des éléments atteignables en partant de `x` et en empruntant un arc de `f` partant de `x`.
La relation f est une application de l'ensemble des parties de `A` noté `ccP(A)` vers l'ensemble des parties de `B` noté `ccP(B)` que l'on note `f "⸨.⸩"` pour la distinguer de l'application `f` de `A` vers `B` notée `f(".")`.
Cette méthode à l'inconvénient de tout de suite vous propulser dans la logique du second ordre car utilisant deux types de variable, des variables élémentaires et des variables ensemblistes, ce qui n'est pas le cas avec la première méthode.
Ces deux notations ne se contredisent pas, et seront utilisées toutes les deux dans la suite de notre étude. Ainsi par exemple considérons l'application `f = (x|->g(x,x))`, et considérons les éléments `a,b` et l'ensemble `H={a,b}`. Nous avons :
`f(a) = g(a,a)`
`f"⸨"{a}"⸩" = {g(a,a)}`
`f"⸨"H"⸩" = f"⸨"{a,b}"⸩" = {g(a,a), g(b,b)}`
`f(H) = f({a,b})= g({a,b},{a,b})`
D'une manière générale, une structure unipolaire se définit en munissant un unique ensemble `E`, d'opérateurs définis dans `E`. Par exemple la structure `(E, a, f("."), g(".,."))` possède un ensemble sous-jacent `E`, un élément `a in E`, une application `f in (E"→"E)` et une application `g in (E"×"E"→"E)`.
On précède à une restriction logique en ne considérant que les seules éléments de l'ensemble sous-jacent `E` pour établir la définition interne de la structure. Dans cette restriction logique, l'expression « Quelque soit `x` » signifie « Quelque soit `x` appartenant à `E` », et l'expression « Il existe `x` » signifie « Il existe `x` appartenant à `E` ». La théorie de la structure doit être écrite dans le langage connu de la structure, et constitue sa définition interne. La structure comprend deux langages :
Chaque termes de ces langages désigne un élément de `E`. La théorie interne de la structure est vide. Car il est déjà présupposé par la notion de structure que ses opérateurs sont des applications internes définies partout dans la structure.
`sf"Structure"(a, f("."), g(".,.")) <=> "Vrai"`
Dans la définition interne, la structure n'a pas de nom puisque nous sommes à l'intérieur et que à cause de la restriction logique, l'extérieur n'existe pas. La structure définit le langage logique connu, c'est à dire les éléments et applications connues. Et sa théorie doit être écrite dans ce langage. Mais si on se place dans un ensemble `U` plus vaste contenant `E` et aux délimitations arbitrairement grande pour assurer le caractère interne des opérateurs évoquées, alors la définition externe devient la suivante :
`sf"Structure"(E "|" a, f("."), g(".,.")) <=> ((a in E),(f in (E"→"E)),(g in (E"×"E"→"E)))`
Où `E` est un ensemble. Il convient d'écrire cette définition dans le formalisme de la logique du second ordre qui ignore le concept d'ensemble ou plus exactement qui le remplace par celui de prédicat. Un prédicat est une application de `U` vers les booléens. L'ensemble `E` est le sous-ensemble de `U` défini par le prédicat `bbE(".")` :
`E= {x "/" bbE(x)}`
On redéfinit une structure unipolaire en étendant les opérateurs sur un ensemble plus vaste `U` lui-même clos par composition de ces opérateurs. Cela est toujours possible, c'est pourquoi la définition externe de la structure va correspondre à la définition interne d'une structure plus grande. L'extension des opérateurs est libre, arbitaire et inconnue. Ainsi, dire que `f in (E"→"E)` affirme simplement que l'application `f` est interne à `E`, ou dit d'une autre façon, que `E` est fermé sous `f`, mais ne présage pas des extensions possibles à l'extérieur de `E`, des extensions qui restent totalement libres et que l'on peut définir comme on veut. De même pour `g(".,.")`. La définition externe de la structure s'écrit formellement comme suit :
`sf"Structure"(bbE("."), a, f("."), g(".,.")) <=> ((bbE(a)),(AAx"," bbE(x) => bbE(f(x))),(AAxAAy"," bbE(x) "et" bbE(y) => bbE(g(x,y))))`
Notez la priorité syntaxique du connecteur `"et"` qui est plus élevée que celle du connecteur `=>`. La définition externe de la structure `E` est identique la définition interne d'une structure plus vaste `U` possédant la structure `E` comme sous-ensemble. Elle forme à son tour une structure composée d'opérateurs qui sont des applications internes définies sur `U`. L'ensemble `U` est donc clos par composition de ces opérateurs qui sont des applications étendues arbitraires. La structure est toujours unipolaire et possède un prédicat `bbE(".")` définissant le sous-ensemble `E`.
La structure `E` est dite agène si elle est engendrée par ses opérateurs générateurs `a,f("."), g(".,.")`, ce qui se note :
`"<"a,f("."), g(".,.")">"=E`
Les crochets `"<...>"` désigne la clôture par composition, c'est l'ensemble de toutes les compositions finies d'opérateurs qu'il est possible de faire avec un nombre quelconque d'occurences d'opérateurs parmi ceux figurant dans les dits crochets... Cette propriété n'est pas une proposition logique du premier ordre.
On considère un sous-ensemble quelconque `P` contenant `a` et stable par les opérateurs c'est à dire tel que `f"⸨"P"⸩"subeP` et `g⸨P"×"P⸩subeP`. Par récurrence on démontre que `P` contient bien toutes les compositions finies d'opérateurs parmi `a,f("."), g(".,.")`. Ainsi, pour affirmer que `E` est agène, il suffit de démontrer que ces présupposée entrainent que `P= E`
`sf"Structure agène"(a, f("."), g(".,.")) <=> (AAP, a"∈"P "et" f"⸨"P"⸩⊆"P "et" g"⸨"P"×"P"⸩⊆"P) => P"="E`
Ce qui s'écrit formellement en logique du second ordre comme suit :
`sf"Structure agène"(a, f("."), g(".,.")) <=>`
`( AAP("."), {: (P(1)),(AAx"," P(x)=>P(f(x))),(AAxAAy"," P(x) "et" P(y) => P(g(x,y)))) :}=> AAx P(x)`
On voit que la définiton de cet ensemble correspond à la règle de raisonnement par récurrence premettant de parcourir cet ensemble par un algorithme. Voir comment ChatGPT répond à ce genre de question : ChatGPT.
La structure agène `E` est dite libre si à partir des opérateurs de la présentation de la structure l'on peut parcourir cet ensemble `E` en découvrant toujours de nouveaux éléments sans jamais revenir en arrière. Cela entraine l'injectivité des applications `f` et `g` mais pas seulement. Tout les termes distincts, qui sont une composition distincte d'opérateurs parmi `a, f("."), g(".,.")`, désignent des éléments distincts de `E`.
Dans le langage de grammaire, on définit `E` de façon récurcive par l'équation `E = {a,f(E),g(E,E)}`. Comment écrire formellement cette propriété en logique du second ordre ?
Le demi-groupe `(E,"+")` est une structure qui porte comme seul axiome l'associativité de sa loi :
`sf"Demi-groupe"("+")` |
`<=>` |
|
Ici, la loi interne `"+"` n'est pas forcement commutative, on fera donc attention ici à cet usage inhabituel de l'addition. L'ensemble `E` muni de la loi `"+"` forme un demi-groupe. C'est donc un ensemble d'éléments quelconques dans lequel est défini une loi binaire interne respectant cet axiome, et ce sont là les seuls informations que nous avons sur cette structure. Une loi dite interne dans `E` est par définition définie partout sur `E`. On dira que la fonction `"+"` est une application binaire définie dans `E`.
On fait agire le demi-groupe `E` sur lui même par translation à gauche. C'est à dire que l'on donne un second rôle à chaque élément `x` appartenant à `E`, celui d'une application de `E` sur `E` autrement dit, définie dans `E`, qui est `(u|->x"+"u)`. Ainsi `E` s'identifie à un ensemble d'application unaires nommées et définie dans un ensemble où la composition d'application correspond à la somme dans le demi-groupe :
Dans cet identification, l'application possède également un identifiant, qui est son nom, de tel sorte que deux application de nom distincts peuvent avoir le même graphe. Il y a donc une source de confusion. Il convient de réserver le terme d'application à la seul caractéristique de son graphe. Son nom constitue alors une extension qu'il faut préciser. On parlera d'applications nommées, le couple d'une application caractérisée par son graphe `(u|->x"+"u)` et d'un nom `x`.
Voyons comment nous pouvons enrichir le langage. On note `x(u)` la fonction `x"(.)"` appliqué à `u`, où `x` joue ici son second rôle. On attribut ainsi à `x` son second rôle, celui de l'application `u|->x"+"u`. Cette attribution se note :
`x"🠄"(u|->x"+"u)`
Délors `x` se comporte comme une application unaire appartenant à `E"→"E`, tout en étant un élément de `E`.
`x(u)=x"+"u`
Notez que l'on n'a pas préciser la nature de `u` dans la définition de la fonction `u|->x"+"u`. Cela n'est pas utile car `u` étant passé en argument de la loi `+`, l'opérateur `+"(.,.)"` étant défini que sur `E`, s'il n'appartient pas à `E` alors `x"+"u="⧫"` est hors domaine. Notez qu'une application de `E` sur `E` est par principe définie partout sur `E`, tandis qu'une fonction `h` de `E` sur `E` n'est pas forcement définie partout sur `E` et qu'il peut y avoir des éléments `x` appartenant à `E` tel que `h(x)"=⧫"` le hors domaine.
À priori, du point de vue informatique, l'élément `x` n'a qu'un seul attribut de fonction, et si on lui attribut une autre fonction alors celle-ci va écraser l'ancienne fonction. Puis il faut pouvoir faire cette attribution pour tous les éléments de la structure `E`. Cela se note en interne comme suit. On introduit ainsi des concepts informatiques dans le langage mathématiques :
`AAx, x"🠄"(u|->x"+"u)`
On dira que l'on fait agire `E` sur lui-même par translation à gauche.
`x(u)=x"+"u`
`y(u)=y"+"u`
`(x"+"y)(u)=(x"+"y)"+"u``(x"∘"y)(u)=x(y(u))=x(y"+"u)=x"+"(y"+"u)=(x"+"y)"+"u=(x"+"y)(u)`
Le demi-groupe `(E,"+")` est donc identifiable à un ensemble d'applications nommées définie sur un ensemble et munie de la loi de composition d'application. Les applications désignées étant nommées cela signifit qu'il peut y avoir plusieurs même application sous des noms différents. Cette identification se note formellement par un morphisme surjectif `varphi` de demi-groupe :
Où `A"⊂"(E"→"E)`. L'application `varphi` est un morphisme si et seulement si quelque soit `x,y` élements de `E` nous avons cette égalité qui permet de traduire les termes du demi-groupe `(E,"+")` en termes du demi-groupe `(A,"∘")`, mais la traduction n'est pas biunivoque.
Et `varphi` est surjectif si et seulement si tous les éléments de `A` sont atteint. Il manque la propriété s'injectivité pour obtenir l'isomorphisme. les applications désignées étant nommées cela signifit qu'il peut y avoir plusieurs même application sous des noms différents, rendant le morphisme non-injectif.
Pour tout demi-groupe `(E,"∘")` il existe un demi-groupe opposé `(E,"·")` où la loi est définie par `AAxAAy, x"·"y=y"∘"x`. C'est la symétrie du sens de l'écriture qui induit cette dualité et qui apparait lorsque la loi n'est pas commutative.
Considérons un demi-groupe `(E,"+")` quelconque. Les physiciens préférent faire agire le demi-groupe `E` sur lui même par translation à droite. Chaque élément `x` du demi-groupe correspond à une translation, qui intuitivement se traduit par l'ajout de `x` à droite, `u|->u"+"x`. Et on constate alors que la règle de composition est dans l'ordre inverse `x"∘"y=y"+"x`. En effet :
`x(u)=u"+"x`
`y(u)=u"+"y`
`(x"+"y)(u)=u"+"(x"+"y)``(x"∘"y)(u)=x(y(u))=x(u"+"y)=(u"+"y)"+"x=u"+"(y"+"x)=(y"+"x)(u)`
Cette dissymétrie apparente vient du choix arbitraire de l'opération de composition de fonctions. La notation anglaise `(x"∘"y"∘"z)(u)` est dans le sens inverse de la notation française `u^(zyx)`. Et il n'y a pas de choix canonique, les deux opérations sont symétriques et se distinguent entre-elles uniquement par l'ordre inverse de leurs arguments. Considérons deux fonctions quelconques `x"(.)"` et `y"(.)"` et considérons un élément quelconque `u`. Il y a deux opérations de composition de fonction, l'une anglaise notée `"∘"`, l'autre française notée par absence de symbole simplement en juxtaposant les fonctions ou par le symbole point `"·"`. Ces deux fonctions sont identiques à ceci près que leurs arguments sont placée dans l'ordre inverse :
`x"∘"y=yx`
Et il y a deux opérations d'applique de fonction, l'une anglaise qui se note `x(u)` et l'autre française qui se note `u^x`, toutes deux désignant la même image de `u` par la fonction `x"(.)"`.
`x(u)=u^x`
Et nous avons :
`(x"∘"y)(u) = x(y(u)) = (u^y)^x = u^(yx)`
On remarque que dans le demi-groupe `E` que l'on fait agire sur lui-même par translation à gauche, deux éléments `x,y` peuvent avoir le même second rôle `(u|->x"+"u)=(u|->y"+"u)`, une égalité de graphe de fonction, et donc représenter la même fonction sous deux noms différents `x,y`.
`AAu, x"+"u"="y"+"u`
Pour que le demi-groupe `E` puisse s'identifier complètement à un ensemble de fonctions, où la fonction n'est pas caractérisée par son nom mais uniquement par son rôle c'est à dire par son graphe, il faut une condition supplémentaire. Chaque élément distinct doit avoir un comportement différent dans son second rôle afin qu'il puisse s'identifier à son second rôle de façon unique. On dira que la structure n'a pas d'élément clone.
`AAxAAy, (AAu, x"+"u"="y"+"u) => x"="y`
Calculons la forme skolémisée :
`AAxAAy, (EEu, x"+"u"≠"y"+"u) "ou" x"="y`
`EEu"(.,.)"AAxAAy, x "+"u(x,y)"≠"y"+"u(x,y) "ou" x"="y`
La fonction `u"(.,.)"` que l'on renomme en `varphi"(.,.)"` est le séparateur. Pour chaque couple `(x,y)`, il détermine un élément `u` qui distinguera les deux fonctions second rôles de `x` et de `y`, en garantissant que `x"+"u"≠"y"+"u`.
`sf"Demi-groupe sans-clone"("+", varphi)` |
`<=>` |
|
La sructure se définie dans une forme non-skolémisée plus simplement comme suit :
`sf"Demi-groupe sans-clone"("+")` |
`<=>` |
|
où si `x ≠ y` alors l'application `varphi(x,y)` va retourner une valeur `u` telle que `x"+"u ≠ y"+"u`
Tout ensemble de fonctions unaires, muni de la loi de composition de fonctions, admet une clôture par composition qui forme une structure de demi-groupe, car la composition de fonctions unaires est associative. Quelque soit trois fonctions `f,g,h` nous avons :
`f"∘"(g"∘"h) = (f"∘"g)"∘"h`
`(f"∘"g)(u) = f(g(u))`
Ce qui s'écrit en notation française :
`(hg)f=h(gf)`
`u^(gf) = (u^g)^f`
Où l'opérateur `"∘"` est la composition de fonctions en notation anglaise, et où l'opérateur point `"·"`, parfois notée par absence de symbole simplement en juxtaposant les fonctions, est la composition de fonctions en notation française, l'opération opposée de `"∘"`, c'est à dire que `f"∘"g=gf`.
Où l'applique anglaise de fonction se note `x(u)`, et l'applique française se note `u^x`, toutes deux désignant la même image de `u` par la fonction `x"(.)"`, c'est à dire que `x(u)=u^x`.
De même, tout ensemble d'application unaires définies sur un ensemble, muni de la loi de composition de fonction, admet une clôture par composition qui forme une structure de demi-groupe, car la composition de d'application unaires est associative et interne.
Notez que quelque soit un ensemble de fonctions unaires, il définie un ensemble minimal sur lequel il opère. Il est alors possible d'étendre cet ensemble en lui ajoutant un élément `zeta`, et d'étendre chaque fonction en remplaçant sa valeur résultat hors domaine par la valeur `zeta`. Ce faisant, l'ensemble de fonctions ainsi étendues devient un ensemble d'applications. De ce fait, les demis-groupes d'applications unaires sur un ensembles sont (à isomorphisme près) les demi-groupes de fonctions unaires.
Mais par contre ils ne constituent qu'une partie des demi-groupes (à isomorphisme près) à cause des clones.
L'ajout d'un élément neutre va suprimer les clones et définir la structure de monoïde.
Le demi-groupe monogène libre constitue la demi-droite discrète. Mais nous ne pouvons pas encore définir le caractère libre qui fait référence au magma. Le demi-groupe `(E,"+")` est monogène quand il existe un élément générateur, noté `1`, qui, ajouté à la présentation de la structure, va engendrer toute la structure par clôture par composition des opérateurs générateurs c'est à dire de `1` et de `+"(.,.)"`.
`"<"1,"+(,.)>"=E"`
Cette propriété n'est pas une proposition logique du premier ordre. Les crochets `"<...>"` désigne la clôture par composition, c'est l'ensemble de toutes les compositions finies d'opérateurs qu'il est possible de faire avec un nombre quelconque d'occurences d'opérateurs parmi ceux figurant dans les dits crochets... On verra que la définiton de cet ensemble correspondra à la règle de raisonnement par récurrence premettant de parcourir cet ensemble par la pensée.
`sf"Demi-groupe" ("+")`
`AAx, x"∈<"1,"+(,.)>"``E = {1, 1"+"1, 1"+"1"+"1, 1"+"1"+"1"+"1, ...}`
Du fait de l'associativité de l'addition, il n'est pas utile de mettre des parenthèses et il parait évident que le semi-groupe monogène est commutatif. Comment peut-on le démontrer formellement ? La propriété de monogénéïté n'étant pas du premier ordre, elle s'exprime dans un langage logique d'ordre 2, utilisant 2 types de variables que sont les éléments et les fonctions.
Le prédicat, qui est une fonction retournant un booléen, joue le rôle d'ensemble. Et nous n'avons pas besoin de la théorie des ensembles mais seulement des règles formelles de déduction logique pour raisonner.
La démonstration de la commutativité du demi-groupe monogène constitue un exemple remarquable d'exercice mettant en oeuvre cette logique formelle du second ordre. La démonstration nécessite l'usage de la récurrence. La démonstration va consister à parcourir `E` comme si c'était un magma, en partant de l'élément générateur `1` et en construisant à l'aide de l'opération `"+(.,.)"` tous les éléments possibles. À partir de l'élément générateur `1` si on ajoute `1` à droite ou `1` à gauche, on énumère potentiellement deux éléments, et si on répète l'opération pour chaque élément énuméré, on finit par énumérer tout les éléments. Par cette méthode on parcourt en faite le magma monogène `(E,"+",1)`.
On commence par démontrer la commutativité de `1` avec les autres éléments du demi-groupe `AAx, x"+"1=1"+"x`. On définit une fonction propositionnelle `bbP"(.)"` comme suit :
`bbP(x)=(x"+"1=1"+"x)`
Le principe du raisonnement par récurrence n'est pas exprimable dans la logique du premier ordre. Il correspond à la définition que l'on s'est donnée de la clôture par compostion décrite au chapitre sur la récurrence. Quelque soit un prédicat unaire `bbP"(.)"`, si `bbP(1)`, et si quelque soit `x` nous avons `bbP(x)=> bbP(x"+"1)` et si nous avons `bbP(x)=> bbP(1"+"x)`, alors par réccurence on en déduit que `bbP(x)` est vrai pour tous les éléments `x` de la structure. Voyons si nous avons toutes ces prémisses :
`bbP(1)`,
Supposons `bbP(x)`, alors :
`x"+"1=1"+"x`
`(x"+"1)"+"1=(1"+"x)"+"1`
`(x"+"1)"+"1=1"+"(x"+"1) `
`bbP(x"+"1) ``x"+"1=1"+"x`
`1"+"(x"+"1)=1"+"(1"+"x) `
`(1"+"x)"+"1=1"+"(1"+"x) `
`bbP(1"+"x)`
Donc par récurence `AAx, bbP(x)` c'est à dire `AAx, x"+"1=1"+"x`.
Le raisonnement par récurrence pour parcourir `E` devient plus simple. Quelque soit un prédicat unaire `bbP"(.)"`, si `bbP(1)`, et si quelque soit `x` nous avons `bbP(x)=> bbP(x"+"1)` alors par réccurence on en déduit que `bbP(x)` est vrai pour tous les éléments `x` de la structure.
Pour montrer formellement que le demi-groupe monogène est commutatif, on pose la proposition `bbP(x,y) = (x"+"y"="y"+"x)` et on utilise un raisonnement par récurrence similaire. Le prédicat n'est pas unaire. La règle de récurrence se perfectionne, toujours selon un principe constructif.
Quelque soit un prédicat binaire `bbP"(.,.)"`, si `bbP(1,1)` et si quelque soit `x,y` nous avons
`bbP(x,y)=> bbP(x"+"1,y)`
`bbP(x,y)=> bbP(x,y"+"1)`
alors par réccurence on en déduit que `bbP(x,y)` est vrai pour tous les éléments `x` et `y` de la structure. Voyons si nous avons toutes ces prémisses :
`bbP(1,1)`,
Supposons `bbP(x,y)` alors
`x"+"y=y"+"x`
`(x"+"y)"+"1=(y"+"x)"+"1`
`x"+"(y"+"1)=y"+"(x"+"1)`
`x"+"(1"+"y)=y"+"(x"+"1)`
`(x"+"1)"+"y=y"+"(x"+"1)`
`bbP(x"+"1,y)``x"+"(y"+"1)=y"+"(x"+"1)`
`x"+"(y"+"1)=y"+"(1"+"x)`
`x"+"(y"+"1)=(y"+"1)"+"x`
`bbP(x,y"+"1)`
Donc par récurrence `AAxAAy, bbP(x,y)` c'est à dire `AAxAAy, x"+"y=y"+"x`. La loi `"+"` est commutative.
La loi étant commutative, l'ajout de l'élément générateur `1` à n'importe quel élément `x` à droite ou à gauche produit un seul élément appelé son successeur. On définit la fonction successeur `s(".")` ainsi :
`s(x)=x"+"1=1"+"x`
Et nous avons `"<"1,"+(.,.)>" = "<"1, s"(.)>"`, une identification entre une structure de demi-groupe monogène et une structure de suite monogène.
La structure de suite `(E, s"(.)")` est une structure magmatique encore plus rudimentaire que le magma. Elle ne posséde qu'un opérateur unaire interne. C'est un ensemble `E` dans lequel est définie une application `s` de `E` dans `E` appelée successeur. Chaque élément ayant un successeur, la structure est appelée suite. C'est la plus simple des structures classiques. Et pourtant cette structure définie tous les systèmes dynamiques où `E` est l'ensemble des états et `s` est une transformation d'états.
La suite `(E,s"(.)")` est monogène quand il existe un élément générateur, noté `1`, qui, ajouté à la présentation de la structure, va engendrer toute la structure par clôture par composition des opérateurs générateurs c'est à dire de `1` et de `s"(.)"`.
`"<"1,s"(.)>"=E"`
La défintion de l'ensemble engendrée par `1` et `s` noté `"<"1,s"(.)>"` n'est pas du premier ordre. Les crochets `"<...>"` désigne la clôture par composition. C'est l'ensemble de toutes les compositions finies d'opérateurs qu'il est possible de faire avec un nombre quelconque d'occurences d'opérateurs parmi ceux figurant dans les dits crochets. Sa définition correspond à la règle de raisonnement par récurrence qui permet de parcourir l'ensemble par la pensée :
`AA bbP"(.)", bbP(1) "et" (AAx, bbP(x)=>bbP(s(x)) ) => AAx"∈<"1,s"(.)>", bbP(x)`
Ainsi la définition de la suite monogène est celle-ci :
`sf"Suite monogène"(s("."), 1)` |
`<=>` |
|
Littéralement : Quelque soit une partie `P` contenant `1` et qui est stable par `s(".")`, c'est à dire tel que `s "⸨"P"⸩" sube P`, alors `P"="E`.
La suite monogène libre constitue la demi-droite discrète. La suite monogène est dite libre lorsque l'on peut établir une bijection entre `"<"1,s"(.)>"` et `NN` qui est `s^n(1)|->n`, autrement-dit lorsque `"<"1,s"(.)>"` constitue une structure de Péano. La définition en logique du second ordre s'écrit :
`sf"Suite monogène libre"("+", 1)` |
`<=>` |
|
Littéralement : `1` n'a pas de prédécesseur, l'application `s(".")` est injective, et toute partie contenant `1` et qui est stable par `s(".")`, est égale à `E`.
---- 14 avril 2024 ----
Il est toujours possible d'ajouter un élément neutre à un demi-groupe sans changer la loi restreinte aux autres éléments. En effet, Etant donné un demi-groupe `(E,"+")`. On ajoute un nouvel élément `0` en complétant la loi `"+(.,.)"` comme suit :
`AAx,`
`x"+"0=x`
`0"+"x=x`
Et on constate que la structure résultante respecte toujours l'associativité. Cela permet de construire la structures de monoïde qui, mise sous forme de skolème, se définit comme suit :
`AAxAAyAAz,` `x"+"(y"+"z) = (x"+"y)"+"z`
`x+0=0`
`0+x=0`
On en déduit également que tout demi-groupe est inclus dans un monoïde, ce qui permettra en étudiant le monoïde d'en apprendre davantage sur le demi-groupe.
En faisant agire le monoïde `E` sur lui même par translation à gauche, c'est à dire en donnant un second rôle à chaque élément `x` appartenant à `E` celui d'une application de `E` sur `E` qui est `(u|->x"+"u)`, ce que l'on note par l'expression informatique :
`AAx, x"🠄"(u|->x"+"u)`
L'élément neutre `0` qui correspond à l'application identité `0 = (u|->u)`, va compléter les graphes des fonctions nommées et va ainsi permettre de les distinguer. Autrement dit, il ne peut y avoir de clone. On le démontre par l'absurde. Supposons l'existence de deux fonctions nommées distintes qui sont clones `a,b`, alors quelque soit `u`, nous avons `a(u)"="b(u)` et donc `a"+"u"="b"+"u` et donc `a"+"0"="b"+"0` et donc `a"="b`. Donc le morphisme définie au chapitre 8 devient un isomorphisme, et le monoïde est identifiable à un ensemble d'application unaires.
Tout monoïde est isomorphe à un ensemble d'applications unaires définies sur un ensemble, clos par composition de fonctions, muni de la loi de composition de fonctions et dans lequel il y a une fonction identité `(x|->x)`
Et réciproquement :
Tout ensemble d'applications unaires définies sur un ensemble, clos par composition de fonctions, muni de la loi de composition de fonctions et dans lequel il y a une fonction identité `(x|->x)`, forme un monoïde.
Les applications étant des fonctions, et la fonction identité étendant toutes les applications identités, on conclut également que :
Tout monoïde est isomorphe à un ensemble de fonctions unaires, clos par composition de fonctions, muni de la loi de composition de fonctions et comprenant la fonction identité `(x|->x)`.
Et réciproquement :
Tout ensemble de fonction unaires, clos par composition de fonctions, muni de la loi de composition de fonctions et comprenant la fonction identité `(x|->x)`, forme un monoïde.
Exemple singulier : Considérons la fonction nulle définie nulle part, `(x|->"⧫")`. Cette fonction joue le rôle d'élément absorbant pour la loi de composition de fonctions. En effet, la fonction nulle produisant toujours le hors domaine, composée à toute fonction dans n'importe quel ordre, produira toujours du hors domaine, et donc la composition sera égale par son graphe à la fonction nulle. Dans un monoïde, s'il existe un élément absorbant, il est forcement unique, et constitue l'élément neutre. Délors le monoïde en question ne peut contenir que ce seul élément.
Le raisonnement par récurrence fait au chapitre précédent, et qui constitue une récurrence primitive, se généralise comme suit grâce à la notion de structure : Un ensemble d'éléments et de fonctions produisant des éléments tel que par exemple `{a,b,f"(.)",g"(.,.)"}` forme une structure anonyme engendrée, notée : `"<"a,b,f"(.)",g"(.,.)>"`. Quelque soit une fonction propositionnelle `P"(.)"`, la règle de déduction par récurrence primitive est la suivante. Et elle définit en même temps l'opérateur de clôture par composition `"<"...">"` :
`AAxAAy,` `P(a)`
`P(b)`
`P(x)=>P(f(x))`
`P(x) "et" P(y) => P(g(x,y))`
Si les fonctions ne sont pas définies partout, la règle de déduction par récurrence évolue, ainsi que la définition de l'operateur de clôture par composition `"<"...">"` :
`AAxAAy,` `P(a)`
`P(b)`
`f(x)"≠⧫" "et" P(x)=>P(f(x))`
`g(x,y)"≠⧫" "et" P(x) "et" P(y) => P(g(x,y))`
Attention à bien respecter la priorité syntaxique de l'implication qui est plus faible que celle de la conjonction, mais plus forte que la portées des quantifications. Noté sous forme d'une conjonction de clauses prénexes :
`AAxAAy,` `P(a)`
`P(b)`
`f(x)"=⧫" "ou" "¬"P(x) "ou" P(f(x))`
`g(x,y)"=⧫" "ou" "¬"P(x) "ou" "¬"P(y) "ou" P(g(x,y)) `
Le raisonnement par récurrence s'applique également à des prédicats d'arité supérieur. Quelque soit une fonction propositionnelle `P"(.,.)"`, la règle de déduction par récurrence est la suivante. Et elle définit en même temps l'opérateur de clôture par composition `"<"...">"`, mais appliquée à deux éléments à la fois :
`AAxAAyAAz,` `P(a,a)`
`P(a,b)`
`P(b,a)`
`P(b,b)`
`P(x,y)=>P(f(x),y)`
`P(x,y)=>P(x,f(y))`
`P(x,y) "et" P(z,y) => P(g(x,z),y)`
`P(x,y) "et" P(x,z) => P(x,g(y,z))`
Noté sous forme d'une conjonction de clauses prénexes, et traitant du cas ou les fonctions `f,g` ne sont pas définies partout :
`AAxAAyAAz,` `P(a,a)`
`P(a,b)`
`P(b,a)`
`P(b,b)`
`f(x)"=⧫" "ou" "¬"P(x,y) "ou" P(f(x),y)`
`f(x)"=⧫" "ou" "¬"P(x,y) "ou" P(x,f(y))`
`g(x,y)"=⧫" "ou" "¬"P(x,y) "ou" "¬"P(z,y) "ou" P(g(x,z),y)`
`g(x,y)"=⧫" "ou" "¬"P(x,y) "ou" "¬"P(x,z) "ou" P(x,g(y,z))`
Nous verrons comment enrichire le langage pour rédiger une règle de raisonnement par récurrence intégrant toutes les arités possibles ici.
Puis il existe des récurrences non-primitives, telle celle utilisée pour définir la fonction d'Ackermann, et qui dévoile de nouvelles capacités de raisonnement ainsi que de nouvelles sortes de structures plus complexes.
Démontrons maintenant que le demi-groupe monogène n'a pas de clone. Quelque soit `x,y` deux éléments du demi-groupe s'ils sont des clones alors `x"+"1=y"+"1` et si nous arrivons à déduire de cela que `x=y`, nous aurons démontré l'absence de clone, et plus que cela, nous aurons démontré que `1` est un élément simplifiable droite.
Mais on peut tout de suite faire une classification des demi-groupes monogènes. C'est à dire identifier chaque demi-groupe monogène à isomorphisme près. Pour cela on va construire tous les demi-groupes monogène possibles.
Le premier est la structure singleton notée `C_1` de thoérie `1"+"1=1`, puis la structure cyclique d'orde `2` notée `C_2` de théorie `{1,1"+"1} "distinct et" 1"+"1"+"1=1`, puis la structure cyclique d'ordre `n>1` notée `C_n` de théorie suivante
`C_n <=> `{1, 1"+"1, } "distinct et" overset("n fois")(overbrace(1"+"1"+"..."1"))=1`
Cela se démontre par récurrence d'une manière similaire. On pose la proposition `P(x,y) = (x"+"1"="y"+"1 => x=y )`. C'est à dire sous forme de clause :
`P(x,y) = (x"+"1"≠"y"+"1 "ou" x"="y )`
`P(x"+"1,y) = (x"+"1"+"1"≠"y"+"1 "ou" x"+"1"="y )`
Si `P(1,1)` et si quelque soit `x,y`, si `P(x,y) => P(x"+"1,y)` et si `P(x,y) => P(x,y"+"1)` alors par récurrence on en déduit que `AAxAAy, P(x,y)`. Voyons si nous avons toutes ces prémisses :
`P(1,1)`,
Supposons `P(x,y)` alors
`x"+"1"≠"y"+"1 "ou" x"="y`
si `x"+"1"+"1 = y"+"1 alors x"+"1"=1
---- 14 avril 2024 ----
La construction du monoïde passe par celle du demi-groupe et passe par une étape encore plus simple, qui est antérieur, et qui est la structure de magma `(E,"+")`. C'est une structure avec une loi binaire interne `+"(.,.)"` sur laquelle il n'y a aucune théorie. Néanmoins la forme binaire de la loi admet une construction libre unique que nous avons déjà entrevue en mettant en oeuvre un raisonnement par récurrence qui énumère tous les éléments.
Notez que le semi-groupe monogène est sans clone
Le magma monogène libre s'appelle aussi la structure des arbres binaires nus.
La théorie du magma `(E,"+")` est vide, c'est juste un langage, une loi binaire interne `"+(.,.)"` sur laquelle nous n'avons pas de connaissance.
Le magma monogène `(E,"+","1")` possède un opérateur binaire `"+(.,.)"`, un élément générateur `1`, et satisfait la propriété d'engendrement :
`"<"1,"+>"=E`.
Le magma monogène libre `(E,"+","1")` est le domaine de Herbrand engendré par le langage `{1, "+(.,.)"}`.
`E = {1, 1"+"1, (1"+"1)"+"1, 1"+"(1"+"1), 1"+"(1"+"(1"+"1)), (1"+"1)"+"(1"+"1), ...}`
Le caractère libre affirme que tous les termes désignent des éléments distincts. De telle sorte que l'ensemble des éléments de `E` sont les termes, et correspondent aux arbres binaires où les noeud sont des `+"(.,.)"` et ou les feuilles sont des `1`. Le magma monogène libre `(E,"+","1")` se note souvant à l'aide d'une grammaire ou d'une équation récurcive d'ensembles, en supposant que l'opération `"+"` procède à une construction libre :
`E = {1, E"+"E}`
Cette formule signifie que l'ensemble `E` contient l'élément `1` et les termes de la forme `(x"+"y)` où `x` appartient à `E` et `y` appartient à `E`. C'est une définition récurcive primitive. Cette formule constitue un énumérateur des éléments de `E`, et ne sont retenus que les termes de taille finie.
Le magma bigène libre `(E,"+","a",b")` est le domaine de Herbrand engendré par le langage `{a,b, "+(.,.)"}`. C'est la structure des arbres binaires dont les feuilles appartiennent à `{a,b}`. Il est dit bigène car on lui a adjoint deux éléments générateurs `a, b`, et `E` satisfait la propriété d'engendrement :
`"<"a,b,"+>"=E`
Il est dit libre car chaque terme distinct du domaine de Herbrand désigne un élément distinct de la structure. Il peut se noter sous forme d'une grammaire ou d'une équation récurcive d'ensembles, toujours en supposant que l'opération `"+"` procède à une construction libre :
`E = {a,b, E"+"E}`
On définit l'ajout d'un élément libre `i` comme suit : Étant donné une structure exemple `(E,f"(.)",g"(.,.)")`, où il est sous-entendu que `f` et `g` sont des fonctions internes c'est à dire des fonctions de `E` sur `E` et de `E"×"E` sur `E`. L'ajout de l'élément libre `i` engendre une structure étendue `L=E"<"i">"` presque libre. C'est l'ensemble des arbres avec deux types de noeuds `f"(.)"` ou `g"(.,.)"` mais où le terme de type `f(E)` est remplacé par sa valeur appartenant à `E` et le terme de type `g(E,E)` est remplacé par sa valeur appartenant à `E`. Autrement dit, en posant `barE = L"-"E`, le sous-ensemble des éléments qui n'appartiennent pas à `E`, c'est l'ensemble des arbres avec deux types de noeuds `f"(.)"` ou `g"(.,.)"` mais dont les types possibles sont `f(barE)`, `g(barE,L)`, `g(L,barE)`. Cela abouti à la définition récurcive suivante :
`L = {E, barE}`
`barE = {i, f(barE), g(barE,L), g(L,barE)}`
Toujours en supposant que les opérations `f"(.)", g"(.,.)"` procède à des constructions libres c'est à dire forment des termes qui ne s'évaluent pas, excepté pour les cas `f(x)` avec `x "∈" E` et les cas `g(x,y)` avec `(x,y) "∈" E^2`. Ne sont retenue que les termes de taille finie. Les termes obtenus sont des arbres ayant des noeuds unaire `f` appliqué à un terme n'appartenant pas à `E`, et des noeuds binaire `g` appliqué à au moins un terme n'appartenant pas à `E`, et où les feuilles appartiennent à `Euu{i}`. Ce sont des arbres composés de deux sortes de noeux `f"(.)"` et `g"(.,.)"`, dont tout les sous-termes qui peuvent s'évalués en éléments de `E` selon sa construction sont remplacés par leur valeur. Ces termes sont identifiés distinctement par leur expression à égalité près de `i, f, g` et des éléments de `E`.
Évidement la structure obtenue `E"<"i">"` n'a aucune raison de respecter la théorie initiale car les éléments ajoutés ne sont forcés d'obéïre à aucune règle d'égalité mais seulement contraints d'être inégaux aux éléments déjà existant et entre-eux.
Remarquez que les noeud de l'arbre ont un label qui est la fonction correspondante `f` ou `g`. Ce label doit être considéré comme un sous-terme. Aussi il convient de le placer comme le premier fils du noeud. On voit alors l'extension possible, donnant à chaque élément un rôle de fonction, étendant le langage terminologique en langage alpha. En langage teminologique, ce premier fils ne peut être qu'un opérateur de la présentation de la structure. En langage alpha, il peut être n'importe quel terme.
Il est possible de définir une notion d'extension libre plus générale appliquée à une fonction. On utilise une fonction dite "libre" qui constitue un constructeur de nouveaux éléments dont on assure qu'ils sont distincts de tous les autres, par un procédé d'identification irréfutable qui est le terme produit par la dite fonction à égalité près de ses sous-termes. Cela correspond à l'extension par ajout d'une fonction libre par exemple `h"(.,.)"`. Étant donné une structure exemple `(E,f"(.)",g"(.,.)")`, l'ajout de la fonction libre `h"(.,.)"` engendre une structure étendue `L=E"<"h"(.,.)>"` presque libre. C'est l'ensemble des arbres avec trois types de noeuds `f"(.)"` ou `g"(.,.)"` ou `h"(.,.)"` mais où le terme de type `f(E)` est remplacé par un élément de `E` et le terme de type `g(E,E)` est remplacé par un élément de `E`. Autrement dit, en posant `barE = L"-"E`, le sous-ensemble des éléments qui n'appartiennent pas à `E`, c'est l'ensemble des arbres avec trois types de noeuds `f"(.)"` ou `g"(.,.)"` ou `h"(.,.)"` mais dont les types possibles sont `f(barE)`, `g(barE,L)`, `g(L,barE)`, `h(L,L)`. Cela abouti à la définition récurcive suivante :
`L = {E, barE}`
`barE = {f(barE), g(barE,L), g(L,barE), h(L,L)}`
Toujours en supposant que les opérations `f"(.)", g"(.,.)", h"(.,.)"` procède à des constructions libres c'est à dire forment des termes qui ne s'évaluent pas, excepté pour les cas `f(x)` avec `x "∈" E` et les cas `g(x,y)` avec `(x,y) "∈" E^2`. Ne sont retenue que les termes de taille finie. Ce sont des arbres composés de trois sortes de noeux `f"(.)"` et `g"(.,.)"` et `h"(.,.)"`, dont tout les sous-termes qui peuvent s'évalués en éléments de `E` selon sa construction sont remplacés par leur valeur. Ces termes sont identifiés distinctement par leur expression à égalité près de `f, g, h` et des éléments de `E`.
Puis la fonction n'est pas forcement libre partout ni définie partout. La fonction peut être définie libre que sur certaines entrées, On désigne ce cas par une valeur symbolique, l'idéogramme "tiré vers le haut; transpercer; lutte libre CJK" `扎`. Dans les autre cas, elle doit être égale à un élément de la structure en construction ou au hors domaine. On définie ainsi une fonction patron de même non.
`L = {E, barE}`
`barE = {f(barE), g(barE,L), g(L,barE), h(L,L)"/扎"}`
Par exemple, si la fonction patron `h(a,b)=扎` alors le terme générique `h(L,L)"/扎"` va produire l'assemblage `h(a,b)` comme étant un nouvel élément identifié par le terme `h(a,b)` à l'égalité prêt de ses sous-termes `h, a, b`. La fonction patron `h` appartient à l'ensemble de fonctions `L×L ->Luu{"扎"}`.
Évidement la structure obtenue `E"<"h"(.,.)>"` n'a aucune raison de respecter la théorie initiale car les éléments ajoutés ne sont forcés d'obéïre à aucune règle d'égalité mais seulement contraint d'être inégaux aux éléments déjà existant et entre-eux.
La demi-droite qui est la structure de monoïde monogène libre, peut se construire à partir de la structure vide, notée Ø, par extension libre par un élément et une fonction unaire : `NN"*"= Ø"<"1,s"(.)>" = "<"1,s"(.)>"` où `s"(.)"` ne doit pas être prédéfinie c'est à dire doit être constamment égale à `扎`. Et en ajoutant le zéro `NN=(<0,1,s(.)>)/("{"AAx, 0"+"x"="x "et" x"+"0"="x"}")`
Etant donné deux structures, par exemple `(A,"+(.,.)")` et `(B,"*(.,.)")`. Le produit libre `L` de ces deux structures est une structure `(L,"+","*")` presque libre. C'est l'ensemble des arbres avec deux types de noeuds `"+"` ou `"*"` mais où le terme de type `A"+"A` est remplacé par un terme de type `A` et le terme de type `B"*"B` est remplacé par un terme de type `B`. Autrement dit, c'est l'ensemble des arbres avec deux types de noeuds `"+"` ou `"*"` mais dont les types possibles sont `barA"+"L`, `L"+"barA`, `barB"*"L`, `L"*"barB`, où `barA"=" L"-"A` est le sous-ensemble `barA sub L` des éléments qui n'appartiennent pas à `A`, et où `barB"=" L"-"B` est le sous-ensemble `barB sub L` des éléments qui n'appartiennent pas à `B`. La définitions récurcive de `L` est la suivante :
`L={A, barA}={B, barB}`
`barA={B, barA"+"L, L"+"barA, barB"*"L, L"*"barB}`
`barB={A, barA"+"L, L"+"barA, barB"*"L, L"*"barB}`
Un élément de `L` est un arbre composé de deux sortes de noeux `"+"` et `"*"`, dont tout les sous-termes qui peuvent s'évalués en éléments de `A` ou de `B` sont remplacés par leur valeur. On utilise le même symbole `"扎"` pour désigner le produit libre de structure :
`L = A扎B`
Le demi-groupe `(E,"+")` se construit à partir du magma `(E,"+")` en rendant chaque élément du magma de la forme `(x"+"y)"+"z` égal à `x"+"(y"+"z)`. L'algorithme se note :
`AAxAAyAAz, (x"+"y)"+"z" 🠄 "x"+"(y"+"z)`
La priorité syntaxique de `" 🠄 "` est plus faible que celle de l'addition, mais plus forte que la portée des quantificateurs. Notez que ces attributions-fusions d'éléments ne sont pas intégrées dans un calcul. On suppose qu'elles se réalisent en parallèle toutes en même temps, sur un ensemble d'éléments non nécessairement dénombrable, proposant ainsi un paradigme au delà du calcul, et qui est applicable de façon plus vaste pour toute théorie pouvant se mettre sous la forme d'une conjonction d'égalités universelles. Une fois appliqué cet algorithme, on obtient à coup sûre une structure `(E,"+")` dans laquelle la propriété d'associativité est respectée.
`AAxAAyAAz, (x"+"y)"+"z"="x"+"(y"+"z)`
On dira que deux éléments `a,b` du magma sont équivalent `a"≈"b` si et seulement s'ils sont rendus égaux par cet algorithme. La définition de cette relation d'équivalence est alors :
`a"≈"b`
`a"="b" ou "EExEEyEEz,((a=(x"+"y)"+"z),(b=x"+"(y"+"z)))`
Une autre façon de procéder consiste à regrouper toutes les propositions connues sur la strucure en une théorie `T`. S'il n'y a aucune autre information que l'associativité de la loi alors `T` est juste la théorie du demi-groupe:
`T={AAxAAyAAz, (x"+"y)"+"z"="x"+"(y"+"z)}`
Mais avec cette seul information on risque de ne pas pouvoir déduire grand chose. On ajoute dans la théorie `T` le graphe de la loi `"+"`. On définit alors la relation d'équivalence comme suit :
`a"≈"b <=> (T|-- a"="b)`
où `|--` signifit démontrable dans le langage de la structure. La déduction est le résultat d'un calcul fini à partir d'un ensemble de données non-nécessairement fini `T`.
Dans le cas générale, la théorie `T` n'est pas complète et il peut exister des éléments `a, b` non-équivalents indiscernables c'est à dire tel que `a"≉"b` et `T⊬a"≠"b`, c'est à dire tel que `T` ne peut ni démontrer l'égalité `a"="b` ni démontrer l'inégalité `a"≠"b`.
Une relation d'équivalence `"≈"` dans un ensemble `E` est une fonction de `E^2` vers les booléens `{0,1}`. On note :
La relation `≈` est dite d'équivalence si et seulement si elle vérifit les propriétés suivantes :
`AAxAAyAAz,`
`x"≈"x,` Réflexif
`x"≈"y=>y"≈"x,` Symétrique
`x"≈"y "et" y"≈"z => x"≈"z` Transitif
Que l'on peut réécrire sous forme de clauses :
`AAxAAyAAz,`
`x"≈"x,`
`x"≉"y "ou" y"≈"x,`
`x"≉"y "ou" y"≉"z "ou" x"≈"z`
On note `[x]` la classe d'équivalence contenant `x`.
`[x]={y "/" x"≈"y}`
Les classe d'équivalences sont nécessairement disjointes car grâce à la transitivité si deux éléments de deux classes d'équivalence s'avèrent équivalent alors les deux classes fusionnent en une seule classe. L'ensemble `E` est partitionné en classes d'équivalences. L'ensemble quotient `E"/≈"` est l'ensemble des classes d'équivalence :
`E/"≈" = {[x] "/" x"∈"E}`
Considérons un magma `(E,"+")` et une théorie `T` écrite dans le langage de la structure. On définit la relation de `T`- équivalence notée `"≈"` comme suit :
`x"≈"y<=> (T|-- x"="y)`
Du fait des règles de raisonnement mises en oeuvre dans le système de démonstration désigné par l'opérateur de déduction `|--`, la relation de `T`-équivalence `"≈"` est bien une relation d'équivalence. La classe de `T`- équivalence de `x` notée `[x]` est :
`[x]={y "/" x"≈"y}`
Et on définit la structure quotient `(E,"+")"/"T` comme suit :
`("("E,"+)" )/T = ("("E,"+)" )/"≈" = {[x] "/" x"∈"E}= {{y "/" (T|-- x"="y)} "/" x"∈"E}`
Les extensions libres et les quotientages permettent de fabriquer toutes les structures classiques. Par exemple le demi-groupe monogène se définit comme suit :
`("<"1,"+(.,.)>")`
Par exemple le demi-groupe abelien se définit comme suit :
`("("E,"+(.,.))")/(AAxAAyAAz","(((x"+"y)"+"z"="x"+"(y"+"z)),(x"+"y"="y"+"x))`
A l'aide de l'extension libre et du quotientage par une théorie, on construit toutes les structures classiques. Néanmois la formalisation exacte n'est pas encore complètement décrite. C'est ce que nous allons tenter de faire dans la suite de cette exposé et qui aboutira à la conception d'un démonstrateur de théorème.