I) Structures fondamentales
selon le point de vue élémentarien

 

1) Semi-groupe

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 soummettons, construisant éléments et démonstrations, et qui opère sur le système comme sur notre propre système de raisonnement, 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.

On remarquera qu'une séquence d'éléments constitue l'argument d'un opérateur d'arité variable.

2) Les premières structures dévoilées

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. Sa présentation en notation linguistique est la suivante :

`"<"1,"+>"`

Il comprend un élément générateur ici nommé `1`, et une opération binaire ici nommée `+`. 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, 1, 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 `("+") [1]`

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 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éfinie par les constructions suivantes :

`f    =   x |-> (x+x)+x`
`g    =   (x,y) |-> (x+y)+(y+x)`

ou bien définie 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. Puis, d'une façon plus générale, on construit par programmation d'autres opérateurs tel que `h"(.,.)"` définie par le programme impératif suivant :

`h(x,y) = (u:=x ; v:=y ; `Repeat_until_max` (10, u=v, (u:=u+x ; v:=v+y)) ; u)`

Le langage de programmation utilisé est le suivant :

Un programme est soit une instruction ou bien une séquence d'instructions séparés par des point-virgules et entourées de parenthèse, les instructions sont exécutées les une à la suite des autres et la dernière instruction retourne le résultat du programme.

L'instruction `u:=x` modifie la valeur de `u` en lui affectant celle de `x`.

L'instruction `u=y` retourne true si `u` et `y` contiennent la même valeur et retourne false sinon.

L'instruction `u` retourne la valeur de `u`.

La fonction ternaire Repeat_until_max prend trois arguments, le premier argument est un entier qui précise le nombre maximum de répétitions, le second argument est un programme qui retourne une valeur true ou false et qui détermine si la répétition doit s'arrêter, le troisième argument est le programme qui fait l'objet des répétitions.

La fonction binaire Repeat_until prend deux arguments, le premier argument est un programme qui retourne une valeur true ou false et qui détermine si la répétition doit s'arrêter, le troisième argument est le programme qui fait l'objet des répétitions.

Ce programme 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"(.,.)"` définie par le programme suivant :

`k(x,y) = (u:=x ; v:=y ; `Repeat_until` (u=v, (u:=u+x ; v:=v+y)) ; u)`

Ce programme peut ne pas s'arréter et ne donner aucune réponse pour certaines valeurs d'entré `(x,y)`. Si le programme ne s'arrète pas pour des valeurs particulières `(a,b)`, alors c'est que `k(a,b)` produit l'infini de Turing noté `oo`, une valeur oracle (car il faut attendre un temps infni pour en être sûr) 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 ? le terme exacte 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 le langage de la structure augmentée de quelques opérateurs de programmation tels que la fonction binaire associative notée par le point virgule d'assemblage d'instructions en série `"(.;.)"`, la fonction binaire Repeat_until`"(.,.)"`, la fonction ternaire Repeat_until_max`"(.,.,.)"`. 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 `1` représente ici un nouvel élément quelconque qui sert à l'extension et qui aurait pu être désigné sous un autre symbôle tel que `e` par exemple. Nous pouvons ainsi écrire :

Magma `("+") [1]   =   "<+>" [1]`
Magma `("+") [1]   =   "<+",1">"`

Le magma monogène libre qui peut être noté Magma `("+") [1]`, 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 `("+",1)   =`   Magma `("+") [1]`
Magma monogène `("+",1)   =   "<+>" [1]`
Magma monogène `("+",1)   =   "<+",1">"`

Le patron Magma monogène `("+",1)` prend deux aguments. Le premier terme `+` désigne l'opération interne, et le second terme `1` désigne l'élément générateur. Le magma monogène libre, Magma `("+") [1]`, 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. Que pouvons nous construire sur cette structure ?, relations d'ordre ?, quelles propriétés ?, autres opérations ?, algorithmes ?, autres structures ?....

`"<"1,"+>" = {1, 1"+"1, 1"+"(1"+"1), (1"+"1)"+"1, 1"+"(1"+"(1"+"1)), 1"+"((1"+"1)"+"1), (1"+"1)"+"(1"+"1), (1"+"(1"+"1))"+"1, ((1"+"1)"+"1)"+"1, ...}`

Si on intègre la qualité d'être libre dans le patron, on obtient le même patron :

Magma monogène libre `("+",1)   =`   Magma monogène `("+",1)`
Magma monogène libre `("+",1)   =   "<+",1">"`

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.

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 plus tard, 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. On utilisera le symbole spécifique `⓵` pour désigner l'ensemble des entiers naturels non nuls. Sa présentation en notation linguistique est la suivante :

` ⓵ = "<"1,"+>/"{(x"+"y)"+"z = x"+"(y"+"z)}`

Sa présentation en notation programmative peut s'écrire de plusieurs façons :

` ⓵ =` Semi-groupe `("+") [1]`
` ⓵ =` Semi-groupe monogène `("+",1)`

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 génératrice 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.

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 de telle sorte qu'il ne sera pas nécessaire de rappeler leur quantification. La règle d'égalité devient alors :

`(x"+"y)"+"z = x"+"(y"+"z)`

Dans le cas général, la règle d'égalité est une disjonction d'égalités, et est appelée une clause d'égalité. Nous avons fait ici le choix de décomposer la théorie en une conjonction de clause de littéraux, mais d'autres décompositions sont possibles.

Ces règles d'égalités vont être codifiées sous forme de fonction propositionnelle afin de pouvoir les 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é, une clause d'égalité, c'est à dire une formule n'utilisant comme élément de langage que des opérateurs et éléments déjà définis auxquels on ajoute le prédicat `=`, une liste de variables universelles `x,y,z...`, et le connecteur logique `"ou"`.

Par commodité, on regroupe plusieurs clauses en une conjonction de clauses qui pourra être codifiée en une seul fonction propositionnelle. L'ajout de clauses correspond au 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 clause `(x"+"y)"+"z = x"+"(y"+"z)`. Et on ne notera pas les quantificateurs qui seront implicitement positionnés universel.

`{"+" ` 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é appelées clauses. Ces clauses forment une théorie 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 `<>` un ensemble d'opérateurs générateurs, et regroupe au dénominateur entre accolade `{ }` un ensemble de propriétées dites génératrices ou appellées axiomes :

Magma `("+")   =   "<+>"`

Semi-groupe `("+")   =`   Magma `("+") "/" {"+"` est associatif`}`
Semi-groupe `("+")   =  "<+>/"{"+"` est associatif`}`

Semi-groupe monogène `("+",1)  =`   Semi-groupe `("+") [1]`
Semi-groupe monogène `("+",1)  =   "<+>/"{"+"` est associatif`} [1]`
Semi-groupe monogène `("+",1)  =  "<+>"[1] "/"{"+"` est associatif`}`
Semi-groupe monogène `("+",1)  =  "<"1,"+>/"{"+"` est associatif`}`

Les extensions ne sont pas réservés au seuls éléments. On peut effectuer une extension libre à l'aide d'un nouveau symbôle d'opérateur. On considére la structure triviale `"<"1">"` qui ne comprent que l'unique élément `1`. 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 propriété d'associativité de cet opérateur :

Semi-groupe monogène `("+",1)   =   "<"1">" ["+"] "/" {"+"` est associatif`}`

3) Les théories d'égalités

Une théorie d'égalité utilise un langage d'opérateurs d'arité fixe, l'unique prédicat d'égalité `=`, les des deux seuls opérations logiques `{"et", "ou"}`, et des variables universelles `x,y,z,...`

Donc une théorie d'égalité n'utilise pas de négation, ni de variables existencielles. Et les variables sont implicitement quantifiés universellement

A toute théorie d'égalité correspond une structure minimale qui en est sa materialisation en quelque sorte. Se faisant, on construit une théorie d'égalité en construisant sa structure minimale et reciproquement. Néanmoins la structure peut être augmenté de nouveaux opérateurs sans changer sa théorie d'égalité. Elle n'est alors plus minimale car elle utilise un langage d'opérateurs plus riche.

Il y a donc dans toutes structures une partie déclarative qui pose le langage d'opérateurs utilisé. Cette partie s'appelle la présentation de la structure. Elle correspond aux extensions élémentaires et à la déclaration des opérateurs générateurs du langage.

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.

La dimension d'une clause est le plus grand nombres de noms distincts de variables universelles apparaissant dans la clause. La dimension d'une  théorie d'égalité est la plus grande dimension de ses clauses, après avoir été mise sous forme normale. La dimension minimale d'une théorie et la plus petite dimension parmi toutes ses expressions équivalentes.

Le langage d'une théorie est l'ensemble des opérateurs, autres que les variables universelles `x,y,z...` apparaissant dans l'expression de la théorie. Le langage minimal d'une théorie est le plus petit ensemble d'opérateurs, autres que les variables universelles `x,y,z...` apparaissant dans au moins une théorie logiquement équivalente.

Une théorie est définie de façon intuitionniste par un énumérateur de ses démonstrations, et donc également par un énumérateur de toutes les propositions qu"elle peut démontrer.

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`. 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` suffisamment complexe 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.

4) Les structures

Les premières opérations de construction de structure que nous avons explorées sont :

  1. L'extension élémentaire qui consiste à ajouter au langage d'opérateurs un nouvel élément, ou un nouvel opérateur, en respectant la théorie du patron. Ces éléments nouveaux, ou opérateurs nouveaux s'ajoutent aux opérateurs générateurs déjà définis par le patron.
  2. Le quotientage par une relation d'équivalence construite à partir de règles d'égalités appelées clauses d'égalité. Ces nouvelles clauses s'ajoutent à la théorie définie par le patron.

Autrement dit, soit on ajoute un élément, ou un opérateur d'arité supérieur, 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. Un opérateur d'arité un est une application de l'ensemble sous-jacent sur lui-même. Un opérateur d'arité deux est une application de l'ensemble des couples d'éléments de l'ensemble sous-jacent vers l'ensemble sous-jacent. Etc..

5) L'union libre disjointe de deux structures, `"+"`

La réunion de deux structures doit pouvoir se faire symétriquement, c'est à dire sans considérer que l'une phagocyte l'autre. Et pour cela il faudra mettre en oeuvre un procédé symétrique, une logique respectueuse de l'indépendance. Mais nous n'allons pas tout de suite être confronté à cette exigence.

Deux structures forment, en dehors de toute contrainte, une bis-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.

On ramène cette bis-structure en une structure comme suit :

  1. Le langage comprend la réunion des opérateurs générateurs des deux structures (en les différenciant s'ils avaient des noms identiques).
  2. L'ensemble sous-jacent est un ensemble beaucoup plus vaste obtenu par la cloture par compositions closes d'opérateurs générateurs des deux structures. Il comprend naturellement les deux ensembles sous-jacent initiaux. Les opérateurs opèrent donc sur un ensemble beaucoup plus vaste. Et comme il n'y a pas de théorie au sujet des éléments situés en dehors de ces deux ensembles sous-jacent initiaux, tous les emboitements possibles d'opérateurs sortant du cadre de ces deux structures initiales sont libres et donc concidérés distincts si d'expression distinctes.
  3. On ajoute au langage deux demi-prédicats pour définir chacun des deux ensembles sous-jacents initiaux.
  4. La théorie comprend la conjonction des deux théories mais pour lesquelles les variables universelles évoquées sont restreintes par les prédicats respectifs aux deux ensembles sous-jacents initiaux, les théories évoquées ne s'appliquant respectivement qu'à ces deux ensembles.
  5. Les deux prédicats sont définis récurcivement en implémentant la couverture de chaque opérateurs générateurs correspondant à la structure initiale.

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 celles des structures. La structure résultante de l'union libre disjointe `A+B` est :

`"<"@,**,a,b">,"A"(.)", B"(.) / "{`
 
      `A(a),` Définition récurcive 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),` Patron de `A`
      `B(b),` Définition récurcive de l'ensemble `B`
      `B(x)" et "B(y)  =>  B(x**y),`
      `B(x)  =>  (x**x)**x= x` Patron de `B`
`}`  

On remarque alors que les expressions `(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 est donc étendue en introduisant des demi-prédicats `A"(.)", B"(.)"` et leurs compléments `¬A"(.)", ¬B"(.)"`. Et l'opérateur logique de négation `¬` n'est pas utilisé autrement, faisant que la théorie est toujours considérée comme une théorie d'égalité.

Dans l'union libre disjointe de deux structures définie par des théories d'égalités, aucune contradiction ne peut apparaître car la théorie résultante est similaire à une théorie d'égalité malgré le perfectionnement que représente l'introduction des demi-prédicats bien construits et leur complémentaires.

Une union libre non complétement disjointe, dans laquelles par exemple un opérateur `R"(.,.)"` serait en commun, s'obtient en procédant à l'union libre disjointe avec les opérateurs de nom différencié par exemple `R"(.,.)"` et `S"(.,.)"`, puis en quotientannt par l'égalité des deux opérateurs en question, c'est à dire par la clause d'égalité `R(x,y)=S(x,y)`, autrement dit que l'on ajoute à la théorie.

6) Monoïde

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 lui ajoutant un opérateur zero-air `0`, et en quotientant par les propriétés d'égalités relatives à cet élément neutre.

Considérons le Semi-groupe `("+") [1]`, on remarque que si on ajoute l'élément neutre, 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, définissant chacune une relation d'équivalence 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 `"+"`, la propriété `{0` est l'élément neutre de `"+"}` est équivalente à la propriété `{0"+"0=0,  0"+"1=1,  1"+"0=1}`, et dans un Semi-groupe trigène `("+",0,1,i)`, elle est équivalente à la propriété `{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 semblent 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 indiquée au dénominateur n'est que la théorie d'égalité, et elle est insuffisante. Il manque une propriété qui sort de la logique du premier ordre et qui affirme que le monoïde est engendré par `"<+",0,1">`, et que l'on regroupe dans la théorie d'engendrement.

La structure est sa théorie d'égalité augmenté de sa théorie d'engendrement, tandis que ce que l'on entend par théorie du patron est la théorie d'égalité seul.

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 proprement dite :

`{<+",0,1">=".", (x"+"y)"+"z=x"+"(y"+"z),  x"+"0=x,  0"+"x=x}`

Les crochets `"< >"` désigne la cloture par composition close, et l'opérateur `"."` désigne l'ensemble sous-jacent de la structure. Ainsi nous avons bien :

`{<+",0,1">=".", (x"+"y)"+"z=x"+"(y"+"z),  x"+"0=x,  0"+"x=x}`
      `<=>`
`{<+",0,1">=".", (x"+"y)"+"z=x"+"(y"+"z),  0"+"0=0,  0"+"1=1,  1"+"0=1}`

7) Groupe

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 `"-(.)"`.

Groupe `("+", 0, "-")   =`   Monoïde `("+",0)["-"]"/"{"-"` est l'opposé pour atteindre `0` avec `"+"}`

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`.

`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émments de la structure à l'aide des 3 opérateurs précédement définie `"+", 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 :

`{"<+(.,.)", 0, "-(.)",1">"="."}`

La théorie de la structure est :

`{"<+(.,.)", 0, "-(.)",1">"=".", "+"` est associative`,  0` est l'élément neutre pour `"+",  "-"` est l'opposé pour atteindre 0 avec `"+"}`

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`
`}`

8) Décentralisation

La structure centralise sa théorie d'égalité et sa théorie d'engendrement au travers une séquence d'opérateurs le tout quotienté par une théorie d'égalité. On s'autorise d'enrichir les opérateurs afin qu'ils puissent transporter des structures. Par exemple :

`"+" =` Groupe `("+(.,.)", 0, -"(.)")`

Cette expression définie un Groupe sous l'appellation de l'opérateur `"+"`. L'opérateur "+(.,.)" se trouve maintenant masqué par la nouvelle définition de l'opérateur "+" qui l'enrichie d'une structure. Cette structure ne comprend, comme élément, que l'élément `0`. Parcontre elle comprend toutes les opérations qu'il est possible de construire à l'aide de ces trois opérateurs `"+(.,.)", 0, -"(.)"` par le biais de tout programme de taille finie et d'arrêt sûr.

Maintenant considérons l'expression suivante :

G = Groupe monogène `("+",1)`

Les arguments sont une séquence qui s'applatie, et ainsi l'expression et donc équivalente à :

`G =` Groupe monogène `("+(.,.)", 0, -"(.)", 1)`

Et cela vérifie bien la syntaxe du constructeur de groupe monogène.

Les noms des constructeurs sont à ralonge et leur séquence d'arguments s'allonge aussi. Un constructeur peut prendre comme argument un autre constructeur, auquel cas il le remplace par sa séquence d'arguments et il procède à un aplatissement des séquences d'arguments puis il regroupement des théories d'égalités.

9) Les structures aux théories incomplètes

La notation programmative permet facilement de construire des structures aux théories incomplètes. Par exemple considérons le groupe monogène définie par :

`G  =`   Groupe monogène `("+", 0, "-", 1)" / "{1+1=0 " ou " 1+1+1=0}`

Ce groupe est à la fois le groupe `C_2` et le groupe `C_3`. Tout se passe comme si la question n'était pas tranchée. C'est à dire que la théorie du groupe `G`, que l'on désigne par la même lettre, ne peut pas démontrer ni `1+1+1=0` ni `1+1=0`, mais parcontre, peut démontrer `1+1+1 = 0 " ou " 1+1=0`.

`G ⊬  1+1+1 = 0`
`G ⊬  1+1 = 0`
`G |--  1+1+1 = 0 " ou " 1+1=0`

La structure est pourtant bien construite et engendrée, mais nous ne savons pas si `1+1 = 0` tant qu'on ne la pas démontré. Et c'est le propre des théories d'égalités que de laisser un doute sur chaque égalité entre éléments, qui ne pourra jamais être complètement résolue. Notamment si l'arithmétique savère contradictoire, tous les éléments sont égaux entre eux, ce qui signifie que dans un univers suffisament grand où telle propriété est, tout est égal.

10) Extension libre

Contrairement à l'extention élémentaire, l'extention libre ajoute un élément (ou un opérateur) qui n'est contraint par aucune théorie et donc qui ne respecte pas la théorie de la structure d'accueil. L'extention libre correspond à l'union libre avec une structure libre.

On peut concevoir une extension de structure par l'ajout d'un élément sans que celui-ci, ainsi que tous les élémentnts engendrés du fait de l'introduction de celui-ci comme générateur supplémentaire, ne respectent les lois de la structure initiale, et ne soient restreint à aucune règle d'égalité, on parlera d'extension libre

Par exemple `"<"**,a">/"{**` est associatif`, a**a**a=a} + "<"s">" ` désigne une structure bigène dans laquel `a**s` est différent de `s**a` et de même où `s**(a**a)` est différent de `(s**a) ** a`.

11) Extension élémentaire

L'extention est qualifiée d'élémentaire en référence à la notion d'équivalence élémentaire... simplement parce que l'élément que l'on ajoute ne se distingue pas, par une propriété du premier ordre, des autres éléments. Dit simplement, le nouvel élément que l'on rajoute satisfait la théorie de la structure d'accueil qui est une théorie du premier ordre. Les extensions ne sont pas réservées aux seuls éléments. On peut effectuer une extension élémentaire à l'aide d'un nouvel opérateur d'arité supérieur à zéro. Par exemple considérons le Monoïde monogène `("+",0,a)`. Nous pouvons y ajouter l'opérateur unaire `f"(.)"`, et cela se note Monoïde monogène `("+", 0, a) [f"(.)"]`. L'extension est qualifiée d'élémentaire parce que l'opérateur que l'on rajoute, ne se distingue pas par lui-même et de ces productions des autres opérateurs par une propriété du premier ordre. Dit autrement, le nouvelle opérateur produit toujours des éléments qui satisfont la théorie de la structure d'accueil qui est une théorie du premier ordre.

L'expression `f"(.)"` désigne une fonction s'appliquant à un élément de la structure pour produire un élément de la structure, et l'expression `"+(.,.)"` désigne une fonction s'appliquant à deux éléments de la structure pour produire un élément de la structure. Vous aurez remarqué que contrairement à la notation classique, l'ensemble sous-jacent n'apparait pas. L'ensemble sous-jacent est l'ensemble des éléments (opérateurs d'arité zéro) constructibles par composition close d'opérateurs générateurs, et cet ensemble est implicitement représenté par le symbôle point.

Monoïde monogène `("+(.,.)",0,a) = "<+(.,.)", 0, a ">/"{"+"` est associatif`, 0` est l'élément neutre pour `"+"}`
Monoïde monogène `("+(.,.)",0,a) [f"(.)"] = "<+(.,.)", 0, a, f"(.)>/"{"+"` est associatif`, 0` est l'élément neutre pour `"+"}`

Conventionellement l'arité des opérateurs est mentionné dans un langage mère tel que `L = {a, b, f"(.)", "+(.,.)"}` qui sert de contexte et il n'est pas nécessaire de rappeller l'arité des opérateurs dans les présentations de structure :

Monoïde monogène `("+",0,a) = "<+", 0, a">/"{"+"` est associatif`, 0` est l'élément neutre pour `"+"}`
Monoïde monogène `("+",0,a) [f] = "<+", f, 0, a">/"{"+"` est associatif`, 0` est l'élément neutre pour `"+"}`

Une structure peut se décomposer en une suite d'extensions et de quotientages ajoutant un symbôle du langage à la fois et ajoutant d'éventuelles clauses d'égalités à la théorie en utilisant le symbôle de l'extension ou évententuellement les symbôles des extensions précédentes et du patron mais en aucun cas des symbôles des extensions suivantes.

Groupe monogène `("+",0,"-",1)`
     `=`
Magma `("+")"/"{(x"+"y)"+"z=x"+"(y"+"z)}[0]"/"{x"+"0=x,  0"+"x=x}["-"]"/"{x"+"("-"x)=0,  ("-"x)"+"x=0}[1]`

12) Les relations d'équivalence

En notation linguistique, une structure se présente comme le quotient d'un langage libre d'opérateurs `L` par une théorie d'égalité `T`.

`L"/"T`

`L` est un langage libre, c'est à dire un ensemble fini d'opérateurs que l'on présente entre crochet `"< >"`.

`T` est une théorie d'égalité, c'est à dire un ensemble fini de clauses d"égalité que l'on présente entre braquette `{ }`, chaque clause n'utilisant que des opérateurs de `L`, le prédicat `=`, des variables universelles `x,y,z...`, et le connecteur `"ou"`.

On étend par clôture, `L` et `T`, en ajoutant tous les objects qui peuvent être construits à partir des objects initiaux. Ainsi `L` devient l'ensemble de tous les opérateurs pouvant être construits à partir de `L`, il comprend l'ensemble des éléments contructibles par composition close d'opérateur, et est appelé structure libre, et `T` devient l'ensemble de toutes les clauses d'égalité pouvant être démontrés à partir de `T`.

`L` contient tous les opérateurs constructibles par calcul, c'est à dire constructible jusqu'au niveau 6 selon l'échelle du chapitre suivant. Le niveau 7 est traité à part car cela correspond aux opérateurs qui peuvent produirent l'infini de Turing, c'est à dire ne pas donner de réponse en un temps fini.

`L` représente le langage de données pour les éléments qu'il peut construire à partir d'opérateurs prédéfinie. Et il représente aussi le langage de programmation pour les opérateurs qu'il peut construire. Tandis que `T` représente le langage de propriété.

`T` définie une relation d'équivalence sur la structure libre `L`. Deux éléments `x, y`, de la structure libre `L` sont dits `T`-égaux si `T` démontre leur égalité. On note `x =_T y` pour signifier que `x` et `y` sont égaux pour la théorie `T`, c'est à dire `x =_T y` si et seulemet si `T |-- x=y`.

`T` définie une relation d'équivalence parmi les opérateurs constructibles de `L` de même arités. Deux opérateurs `L`-constructibles `r, s` de même arité sont dits `T`-égaux si `T` démontre leur égalité quelque soit leur arguments, c'est à dire dans le cas unaire, nous avons `r =_T s` si et seulement si `T |-- ∀x, r(x)=s(x)`. Nous avons :

`a =_T b`                       si et seulemet si     `T |-- a=b`
`r"(.)" =_T s"(.)"`             si et seulemet si     `T |-- ∀x, r(x)=s(x)`
`f"(.,.)" =_T g"(.,.)"`         si et seulemet si     `T |--∀x,∀y, f(x,y)=g(x,y)`
`u"(.,.,.)" =_T v"(.,.,.)"`    si et seulemet si     `T |-- ∀x,∀y,∀z, u(x,y,z)=v(x,y,z)`
...

Et il n'y a que deux cas possibles : soit `T` démontre l'égalité des deux opérateurs, soit `T` ne peut pas démontrer l'égalité des deux opérateurs. Mais pour être sûr de l'infirmative, c'est à dire que `T` ne démontre pas la propriété d'égalité, il faut passer en revue toutes les démonstrations possibles ce qui prendrait un temps infini. C'est pourquoi l'infirmative constitue un oracle.

D'une manière plus générale on utilisera la notation `=_T`, non pas seulement avec des opérateurs de même arité, mais avec des expressions quelconques contenant des variables universelle comme par exemple :

`g(z,f(x,y)) =_T v(y,x,f(z,x))`

Cette expression signifie que

`T |-- ∀x,∀y,∀z, g(z,f(x,y))=v(y,x,f(z,x))`

Ainsi le problème de l'égalité d'opérateurs s'inscrit dans un problème plus générale qu'est l'égalité d'expression possédant des variables quantifiées universellement. Et si nous n'utilisons que des variables quantifiés universellement alors nous pouvons rendre impicite les quantificateurs universelles et ces relations d'équivalences s'écrivent plus simplement telle que pour l'exemple :

`T|--g(z,f(x,y))=v(y,x,f(z,x))`

 

---- 6 mai 2017 ----

 

 

10) Relativisme culturel et empirisme

Mais dans la pratique, on raisonne dans un système de pensé qui s'appuie sur des connaissances et qui nous procure un horizon, certe illusoire, mais bien pratique. Le choix des connaissances, appelée culture, va définir le système de pensé et déterminer cet horizon.

---

Il y a une sorte de dualité entre énumérateurs et démonstrateurs, entre éléments et propriétés. Il y a deux sortes de connaissances étroitement imbriquées l'une à l'autre, les connaissances énumératives et les connaissances démonstratives. Les premières énumèrent les éléments et opérateurs, les secondes énumèrent les propriétés sur ces éléments et opérateurs.

Une sorte de métrique s'établie sur l'ensemble des éléments et opérateurs constructibles, ansi que sur l'ensemble des propositions démontrables. Un élément proche est un élément qui va apparaitre parmis les premiers dans l'énumération des éléments, tandis qu'un élément éloignés sera énuméré trés tardivement. Et il en est de même pour les propriétés.

Les éléments sont énumérés, et les propriétés sont également énumérés. Il s'en suit qu'une approche statistique relative à ces deux choix d'énumérations est possible. Pour un ensemble et pour une propriété arbitraire s'appliquant à un élément de cet ensemble, on comptabilise les éléments pour lesquels la propriété est démontrable avant d'atteindre l'horizon. Il est alors possible d'établire une valuation subjective de cette propriété pour l'ensemble en question. De là nait l'empirisme, un empirisme nécessairement relatif à ses connaissances, c'est pourquoi il est subjectif.

Un ensemble d'éléments possèdent subjectivement une propriété pour tous ses éléments si et seulement si, pour tous ses éléments constructibles avant le demi-horizon, la propriété est démontré avant l'horizon.

---

Mais on peut aller plus loin encore dans le préjugé et définir la négation subjective, ce qui change la nature du raisonnement jusqu'à présent car il n'y pas de négation dans les théories d'égalités. On définie la négation subjective. Une proposition est subjectivement fausse si elle n'est jamais énumérée ou énuméré trés trés tardivement derrière un double horizon définie par le système de pensé. On verra qu'il est nécessaire de laissser ce no-man's-land aussi grand entre le vrai et le faux, pour repousser les contradictions découlant de cette négation au delà de l'horizon, recouvrant des propriétés ni subjectivement vrai ni subjectivement fausse pouvant ainsi compléter le système de pensé. C'est l'approche empirique du théorème d'incomplétude de Godel.

Le raisonnement fait à partir d'hypothèses fausses est aussi utile que celui fait à partir d'hypothèses vrais. La négation subjective trouve donc toutes sa place dans le raisonnement mathématique. Il correspond dans un cas trivial à la démonstration par l'absurde, mais il est aussi utile dans un cas plus général, engendrant une valuation logique subjective.

 

7) L'ajout d'une théorie d'engendrement (ou la définition d'un ensemble par cloture par composition close d'opérateurs)

 

11) La récurrence

La réccurence est consubstantielle à la notion de structure

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 `P"(.)"` définie sur `NN`, c'est à dire une fonction de `NN->{`true, false`}`, l'axiome de réccurence est le suivant :

`P(0)`
`AA n in NN,  P(n) => P(n+1)`
`=>`
`AA n in NN,  P(n)`

Notez que seul la structure de semi-groupe monogène est utilisée, et qu'il n'y a nullement 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 comme suit :

`P(1)`
`AA n in ⓵,  P(n) => P(n+1)`
`=>`
`AA n in ⓵,  P(n)`

Mais il est tout à fait possible de définir la réccurence sans faire intervenir les entiers. On parle alors de récurrence générale. Le principe est le même, mais au lieu de s'appliquer qu'à un seul élément `1` et qu'à un seul moyen de construction qu'est l'incrémentation `n|->n+1` et qui doivent tout deux respecter la validité d'une proposition `P"(.)"`, il s'applique à un ensemble d'éléments de base `B` et à un ensemble d'opérateurs de base `C` qui doivent tout deux respecter la validité d'une proposition `P"(.)"`. L'axiome de récurrence générale conclut que toute construction faite à partir d'éléments appartenant à `B` et d'opérateurs appartenant à `C`, c'est à dire tous les éléments désignés par des termes clos du langage `C uu B`, vérifient nécessairement la propriété `P"(.)"`. Autrement dit, pour la structure dont la présentation est constituée des éléments de `B` et des opérateurs de `C` et que l'on note `"<@"B,"@"C">"`, tous ses éléments satisfont nécessairement `P"(.)"`. Le principe affirme égalment que toutes constructions d'opérateurs d'arité quelconque obtenue par programmation d'arrêt sûr à partir du langage `C uu B` respectent la validité de la proposition `P"(.)"`.

On peut ne pas distinguer éléments et opérateurs, un élément étant considéré comme un opérateur d'arité zéro c'est à dire ne prenant aucun argument mais retournant sa valeur, auquel cas la réccurence générale se présente comme suit :

Si tous les opérateurs `x` appartenant à un ensemble `B` respecte la validité d'une propriété `P` alors tous les opérateurs de la structure engendrée par `B` respectent la validité de la propriété `P`.

Nous notons cet axiome par l'expression suivante :

`(B "|=" P) <=> ("<@"B"> |=" P)`

Mais commençons d'abord par un exemple : Si des éléments `a, b` satisfont une propriété `P"(.)"`, c'est à dire si nous avons `P(a)` et `P(b)`, et que des opérateurs `f"(.)", g"(.,.)"` respectent la validité de la propriété `P"(.)"` sur la structure `"<"a,b,f"(.)",g"(.,.)>"`, c'est à dire si pour tout élément `x` de la structure `"<"a,b,f"(.)",g"(.,.)>"` nous avons `P(x) => P(f(x))` et si pour tout couple d'éléments `x` et `y` appartenants à la structure `"<"a,b,f"(.)",g"(.,.)>"` nous avons `(P(x) " et " P(y)) => P(g(x,y))`, alors les hypothèses sont réunies pour pouvoir appliquer la récurrence générale :

    `P(a)`
    `P(b)`

    `AAx in"<"a,b,f"(.)",g"(.,.)>",  P(x) => P(f(x))`
    `AA(x,y)in"<"a,b,f"(.)",g"(.,.)>"^2,  P(x) " et " P(y) => P(g(x,y))`

Grace au principe de récurrence générale, nous déduisons que tous les éléments de la structure `"<"a,b,f"(.)",g"(.,.)>"` satisfont la propriété `P(.)`. Nous déduisons par exemple que `P(g(b,f(a)))`. Et nous déduisons que tous les opérateurs constructibles dans cette structure respectent la validité de la propriété `P"(.)"`. Nous déduisons par exemple que l'opérateur `h"(.,.)"` définie par le programme impératif suivant, respecte la validité de `P"(.)"` :

`h(x,y) = (u:=x ; v:=y ; `Repeat_until_max` (10, u=v, (u:=g(u,x) ; v:=g(v,y))) ; u)`

Dire que, l'opérateur `h"(.,.)"` respecte la validité de la propriété `P"(.)"`, se formalise comme suit :

`AA (x,y) in "<"a,b,f"(.)",g"(.,.)>"^2,  (P(x) " et " P(y))=>P(h(x,y))`

Et nous avons pris l'ensemble le plus petit où cette propriété de respect doit être vérifiée et qui correspond à une structure engendrée `"<"a,b,f"(.)",g"(.,.)>"`. Ainsi, la réccurence générale met en oeuvre le principe de clôture, un principe co-substantiel à la notion de structure, et une cloture qui respecte la validité d'une propriéé `P"(.)"` ou dit autrement qui ransporte une propriété.

`AAx in"<"a,b,f"(.)",g"(.,.)>",  P(x)`
`AA o in "<"a,b,f"(.)",g"(.,.)>"_1 AAx in "<"a,b,f"(.)",g"(.,.)>", P(x) => P(o(x))`
`AA o in "<"a,b,f"(.)",g"(.,.)>"_2 AA(x,y)in "<"a,b,f"(.)",g"(.,.)>"^2, (P(x),P(y)) => P(o(x,y))`
`AA o in "<"a,b,f"(.)",g"(.,.)>"_3 AA(x,y,z)in "<"a,b,f"(.)",g"(.,.)>"^3, (P(x),P(y),P(z)) => P(o(x,y,z))`
...

Le concept de récurence révèle dans sa généralité sa simplicité et son évidence. Il convient donc de trouver un langage formel, une formulation à la hauteur de cette simplicité.

Langage formel d'opérateurs `("in","out")`-aire

Afin de pouvoir manipuler des listes d'arguments on formalise les listes. Une liste de `n` composantes est un opérateur d'arité `(0,n)`. Le premier chiffre est l'arité d'entré de l'opérateur. Comme celui-ci ne prend aucun argument, c'est zéro. Le second chiffre est l'arité de sortie et vaut `n` car la liste révèle `n` composantes qui constitue `n` résultats dans un ordre définie par la liste. Ainsi un opérateur d'arité `(2,3)` prend une liste de deux arguments et retourne une liste de `3` résultats.

Puis on utilise le symbole `in` pour dire qu'une composante appartient à une liste. Ainsi nou avons par exemple `a in (1,a,x)`

Les ensembles finis sont des listes finies. Les ensembles infini sont des structures engendrées de type fini.

On généralise la notation de structure engendrée. Etant donnée une liste `L`, on utilise le symbole `"@"L` pour insérer dans une énumération les éléments de la liste `L`. Ainsi par exemple si `L= (1,a,x)` alors l'expression `("@"L, b, "@"L)` est égale à `(1,a,x,b,1,a,x)`.

On généralise la notation de structure engendrée. Ainsi `"<@"L">"_n` désigne l'ensemble des opérateurs d'arité `(n,1)` constructible par programmation d'arrêt sûr à partir du langage d'opérateurs `L`. Et `"<@"L">"_"fini"` désigne l'ensemble des opérateurs d'arité d'entré fini et d'arité de sortie toujours égale à 1, constructible par programmation d'arrêt sûr à partir du langage d'opérateurs `L`. Et `"<@"L">"^2` désigne l'ensemble des couples d'éléments de `"<@"L">"`. Et `"<@"L">"^"fini"` désigne l'ensemble des listes d'éléments de `"<@"L">"`.

Un opérateur `o` respecte la validité d'une propriété `P` dans `"<@"L">"` si et seulement si `o` est une fonction de `"<@"L">" -> {`true, false`}`:

`AA A in "<@"L">"^("in"(o)),  (AA x in A,  P(x)) => P(o("@"A))`

Et on note cela par :

`o_("<@"L">") "|=" P`

Et on dit que `o` transporte `P` dans `"<@"L">"`

---------------------------------------------------------------

4) Une alternative à la théorie des ensembles

L'approche élémentarienne remplace les ensembles énumérables par des structures de type finie (entendez par là, engendrée par un nombre fini d'opérateurs) et n'utilise pas la théorie des ensembles qu'elle peut même en partie réfuter.

La structure énumérante est la clef de voûte qui lie les trois pans du langage : le langage programmatif pour l'énumérateur, le langage de propriété pour la théorie, et le langage de donné pour l'élément. La structure énumérante materialise la théorie par le calcul, c'est pourquoi elle ne contient que ce qui peut se calculer.

L'équivalence joue le rôle d'égalité dans la structure. Les éléments de la structure sont les classes d'équivalences, et chaque classe peut être désigné par n'importe quel de ses éléments.

D'un point du vue constructif, un élément est une construction produite par un énumérateur. Et si la théorie de la structure ne démontre pas l'équivalence entre deux constructions, alors c'est que ces deux constructions désignent deux éléments distincts de la structure caractérisés par leur expression distincte. Aussi, dans une théorie d'égalité suffisamment complexe, nous ne sommes jamais certain que deux éléments ne puissent pas être distincts. Il faudrait passer en revue toutes les démonstrations possibles et vérifier qu'aucune d'entre elles n'affirme l'égalité entre ces deux éléments, ce qui demanderait un temps infini.

Un ensemble est énumérable s'il existe une machine pouvant l'énumérer. Un ensemble est non énumérable s'il n'existe aucune machine capable de l'énumérer.

Le principe d'incomplétude signifie que le complément d'un ensemble énumérable, dans un ensemble mère plus vaste mais énumérable, n'est pas toujours énumérable.

"Les élémentariens ne font que calculer...". Ils considèrent qu'il n'existe pas de fonction non calculable. Ils considèrent qu'il n'existe pas d'ensemble qui soit à la fois non énumérable et de complémentaire non énumérable. Et davantage encore, ils rompent la symétrie en appellant ensemble, la face énumérable, et ombre, la face pouvant être non énumérable.

La procédure d'énumération des éléments d'une structure constitue la véritable fondation des ensembles énumérables. Ainsi un ensemble énumérable est défini de façon élémentarienne par un énumérateur de ses éléments. De même une théorie est définie par un énumérateur de toutes les propositions qu'elle peut démontrer, et qui est appellé le grand énumérateur. Néanmoins, le complémentaire d'un ensemble énumérable pouvant être non énumérable, les élémentariens définissent un ensemble par son énumérateur ou par l'énumérateur de son complémentaire, et il considère inexistant les ensembles qui sont à la fois non énumérable et de complément non énumérable.

Dans la vision élémentarienne, la théorie définie en elle son propre modèle. Et elle définie des ensembles énumérables ou de complément énumérable qui sont en quelque sorte énumérés ou de complément énuméré par la théorie elle-même : L'ensemble `E` énumère un de ses éléments `e` si et seulement si la théorie démontre que `e` appartient à `E`. Et elle énumère un de ses éléments complémentaires `e` si et seulement si la théorie démontre que `e` n'appartient pas à `E`. Et les indécis, c'est à dire les éléments que la théorie ne tranche pas doivent être rangé dans l'ombre.

Cela se fait en introduisant une règle logique d'un ordre supérieur, donnant un sens logique à la non réponse, c'est à dire interprétant la réponse oracle de l'infini de Turing.

La définition d'un ensemble `E` dans la théorie se fait par l'intermédiaire d'un prédicat `E"(.)"` explicite (ou implicite comme on le verra plus loin) qui définie l'ensemble `E` comme suit :

`T "⊢" E(x)` signifie que `x inE`
`T "⊢"¬E(x)` signifie que `x !inE`
`T "⊬" E(x)` et `T"⊬"¬E(x)` signifie que `x !in E` et que le complémentaire de `E` est non énumérable et constitue une ombre.

Le prédicat `E"(.)"` est une fonction calculable. Elle est constituée du grand énumérateur de la théorie, et appliqué à un élément `x`, elle retourne `1` si `T "⊢" E(x)` , retourne `0` si `T "⊢"¬E(x)` et retourne `oo` l'infini de Turing si `T "⊬" E(x)` et `T"⊬"¬E(x)`.

Ainsi la théorie doit choisir qu'elle face de `E` est l'ensemble et l'autre face est l'ombre, `E` ou son complémentaire. Cela a pour conséquence une règle syntaxique particulière sur les prédicats définissant ces ensembles. Ils doivent avoir une forme récurcive de telle sorte que le choix forcé des indécis mis dans l'ombre (lorsque le calcul du prédicat est sans fin et correspond à l'infini de Turing) ne puisse pas introduire de contradiction.

---- 6 mai 2017 ----

 

5) Les prédicats

On enrichie le langage logique en utilisant des prédicats. Les prédicats comme les opérateurs, s'appliquent à n'importe quel élément de l'ensemble sous-jacent de la structure. Mais à la différence des opérateurs, les prédicats ne produisent pas en retour un élément de l'ensemble sous-jacent, mais retourne directement une valeur de vérité.

L'ajout d'un prédicat dans une structure s'apparente à une extension élémentaire dégénérée. On simule l'ajout d'un prédicat `A"(.)"` par l'ajout d'un opérateur `f"(.)"` et on fixe le sens de celui-ci en prenant un éléments `e`, de tel sorte que `A(x)` si et seulement si `f(x)=e`, et que `¬A(x)` si et seulement si `f(x)!=e`. On remarquera alors qu'il y a une dissymétrie, `A"(.)"` est un énumérateur, tandis que `¬A"(.)"` n'est pas un énumérateur (dans une théorie d'égalité, l'inégalité n'est jamais prouvée).

L'usage des prédicats unaires permet de définir des sous-ensembles dans l'ensemble sous-jacent de la structure.

Selon le point de vue classique, le prédicat est défini dans un modèle qui possède un pouvoir expressif immanent, d'un ordre supérieur à celui d'une théorie. Il se construit, comme le modèle, en faisant une infinité de choix arbitraires. Donc il peut ne pas être calculable.

Le prédicat unaire `A"(.)"` définie un ensemble auquel on donne le même nom `A`. C'est l'ensemble des éléments `x` tel que `A(x)`. Et sa négation définie l'ensemble complémentaire dans l'ensemble sous-jacent de la structure :

`A`
`=` `{x" / "A(x)}`
`¬A`
`=` `{x" / "¬A(x)}`

Ainsi l'expression `x in A` est identique à l'expression `A(x)`. Et l'expression `x !in A` qui correspond à l'expression `¬(x in A)` est identique à l'expression `¬A(x)`.

Selon le point de vue élémentarien, il n'y a pas de modèle au pouvoir immanent constitué d'une infinité de choix arbitraires. Tout doit être constructible, calculable. La théorie construit son propre modèle par des procédés uniquements calculables et en nombre fini. Les prédicats sont donc des fonctions calculables de l'ensemble sous-jacent vers `{"⊥","⊤",oo}``oo` désigne l'infini de Turing et où les valeurs `"⊤"`, `"⊥"`, désigne les valeurs de vérité, vrai, faux.

Voici un moyen mémotechnique pour se souvenir de ces deux symboles : Le vrai représente une tautologie et est représenté par le symbole `"⊤"` ressemblant à la lettre T. Le faux est représenté par le symbole inversé `"⊥"`.

Considérons un prédicat unaire `A"(.)" ` défini dans une structure, cela signifie que le moyen de calculer le prédicat `A` est complétement décrit dans la théorie de la structure. La théorie, en énumèrant tout ce qu'elle peut démontrer, va énumérer les éléments de `A` dont on peut prouver qu'ils appartiennent à `A`. Cet ensemble se note `"⊢"A`. La théorie va énumérer les éléments de `"¬"A` dont on peut prouver qu'ils n'appartiennent pas à `A`. Cet ensemble se note `"⊢¬"A`. Le complémentaire de ces deux ensembles réunies constitura l'ensemble `ccIA` des éléments individuellement non tranchés par la théorie. C'est ainsi que les élémentariens définisent les ensembles `"⊢"A`, `"⊢¬"A` , `ccIA`.

`"⊢"A`
`=` `{x" / "|-- A(x)}` est énumérable
`"⊢¬"A`
`=` `{x" / "|-- ¬A(x)}` est énumérable
`ccIA`
`=` `{x" / "(⊬A(x))" et "(⊬¬A(x))` peut ne pas être énumérable

Autrement dit :

`A(x) = "⊤"`
si et seulement si
`|--A(x)`
`A(x) = "⊥"`
si et seulement si
`|--¬A(x)`
`A(x) = oo`
si et seulement si
`(⊬A(x)) " et " (⊬¬A(x))`

L'ensemble `ccIA` regroupe les éléments, qui pris individuellement, sont indépendants de `A`. Considérons un élément `e in ccIA`. Cet élément est indépendant de `A`. La proposition `e in A` est indépendante de la théorie. La théorie ne peut pas démontrer cette proposition `e in A` ni sa négation `e !in A`. La théorie peut être complétée en ajoutant cette proposition ou sa négation, en une nouvelle théorie sans la rendre contradictoire. Mais cette propriété ne marche que pour l'ajout d'un élément à la fois.

Qu'elle forme doit avoir la théorie pour que quelque soit deux éléments non tranchés `(a,b)`, l'ajout de la proposition `a in A` n'entraine pas la proposition `b !in A` ?. Un moyen d'obtenir cette propriété consiste à définir le prédicat `A` de façon uniquement récurcive. On dira alors que le prédicat est bien fondé.

On veut que la théorie tranche tous les éléments c'est à dire que l'ensemble `ccIA` soit vide. Cela se peut en procédant à un choix supplémentaire, mais qui n'est pas exprimable au premier ordre. Ce choix supplémentaire consiste à réfuter tous les éléments dont on ne peut pas démontrer qu'ils appartiennent à `A`. On le formalise par l'axiome suivant :

`AAx,  ( ⊬A(x) ) => ¬A(x)`

ou d'une manière équivalente par l'axiome :

`A = {x" / "⊢A(x)}`

La théorie augmentée de cet axiome `A = {x" / "|--A(x)}` définie bien complètement le prédicat `A"(.)"`, c'est à dire l'ensemble `A` et son ensemble complémentaire `¬A`, comme le ferait un modèle. Le prédicat `A"(.)"` est bien fondé s'il est définie de façon uniquement récurcive. Délors le prédicat `A"(.)"` se comporte comme un énumérateur des éléments de l'ensemble `A`. C'est à dire que `A = {x" / " |--A(x)}` ce qui revient à dire que les élément indépendants de `A` sont tous réfutés.

`A`
`=` `{x" / "|-- A(x)}` Est énumérable
`"¬"A`
`=` `{x" / "⊬ A(x)}` Peut ne pas être énumérable

Conventionellement pour un prédicat bien fondé, la forme affirmative désigne l'énumération et la forme négative désigne le complémentaire de l'énumération.

On note le complémentaires d'un ensemble à l'aide du préfixe `¬`. L'ensembles `"¬⊢"A` se note `"⊬"A`. L'ensembles `"¬⊢¬"A` se note `"⊬¬"A`.

Selon le point de vue classique, pour chaque ensemble `A`, il y a 6 ensembles à considérer `A, "¬"A, "⊢"A, "⊢¬"A, "⊬"A, "⊬¬"A` qui se définissent comme suit :

`A`
`=` `{x" / "A(x)}` Peut ne pas être énumérable
`"¬"A`
`=` `{x" / "¬A(x)}` Peut ne pas être énumérable
`"⊢"A`
`=` `{x " /  ⊢"A(x)}` Est énumérable
`"⊢¬"A`
`=` `{x " /  ⊢"¬A(x)}` Est énumérable
`"⊬"A`
`=` `{x " /  ⊬"A(x)}` Peut ne pas être énumérable
`"⊬¬"A`
`=` `{x " /  ⊬"¬A(x)}` Peut ne pas être énumérable

L'ensemble des élément indépendants de `A` est :

`ccIA = ("⊬"A) nn ("⊬¬"A)`

Le complémentaire de cet ensemble est :

`"¬"ccIA = ("⊢"A) uu ("⊢¬"A)`

Il est possible de définir une seconde négation, notée `"⊬"` qui se différencie de la négation `¬`, et qui donc appliquée à un ensemble définie une autre notion d'ensemble complémentaire :

`"¬"A`
`=` `{x" / "¬A(x)}` Négation classique
`"⊬"A`
`=` `{x" /  ⊬"A(x)}` Négation intuitionniste

Nous avons :

`"¬"A sub "⊬"A`
`"⊢"A sub A`
`"⊢¬"A sub ¬A`
`"¬"A sub "⊬"A`
`A sub "⊬"¬A`

Selon le point de vue élémentarien, la même description est valable mais en plus simple puisqu'on enlève tout les ensembles qui ne sont pas soit énumérable ou soit de complément énumérable, car considérée comme inexistant.

On s'inscrit dans le cadre d'un principe constructif. On n'utilisera que des prédicats obéïssant à ce principe constructif, c'est à dire bien fondés, définis uniquement récurcivement. Cela assure leur complète définition. (Cela nous permettra par la même occasion d'éviter le paradoxe de Russel.)

Déjà les opérateurs sont constructifs par nature dans le sens que, a priori, étant libres, ils produisent de façon déterminée l'emboitement libre correspondant. Par exemple l'opérateur `f"(.,.)"` appliqué à `a` et `b` produira le terme `f(a,b)`.

Pour les prédicats, ce principe constructif se traduit par un principe d'énumérabilité. Il serait simple que tout ensemble soit énumérable par principe, mais un fait important vient perturber cette utopie, c'est que le complément d'un ensemble énumérable, dans un ensemble mère plus vaste mais énumérable, n'est pas toujours énumérable. Par ailleur, la négation d'un prédicat doit pouvoir s'utiliser comme on utilise un prédicat. Le complément d'un ensemble doit pouvoir s'utiliser comme un ensemble. C'est pourquoi on impose comme nécessité à un ensemble, qu'il est une de ses faces énumérables, soit lui-même ou bien son complémentaire.

Un ensemble est dit décidable si et seulement si lui-même et son compémentaire sont tous deux énumérables. On parlera de demi-ensemble et de demi-prédicat. Le demi-ensemble est un ensemble énumérable dont le complémentaire peut ne pas être énumérable. Le demi-prédicat est un prédicat muni d'une propriété du second ordre comme quoi la réponse `oo` correspond à la réponse faux `"⊥"`. Les demi-prédicats définissent les demi-ensembles. Pour les élémentariens, il n'existe pas d'ensemble non énumérable dont le complément n'est pas énumérable.

En conclusion, la définition d'un demi-prédicat `A"(.)"` dans une théorie `T` doit obéir à un principe constructif, il doit être définie uniquement récurcivement, et il doit être accompagné de l'axiome supplémentaire définissant complètement l'ensemble `A` à partir du prédicat calculable `A"(.)"` que voici :

`AAx,  (⊬A(x)) => ¬A(x)`

L'ensemble mère sur lequel porte le quantificateur universelle `AA` est l'ensemble sous-jacent de la structure, un ensemble assurement énumérable.

Un ensemble énumérable est appelé simplement une énumération. Il y a une différence de nature entre une énumération et le complémentaire d'une énumération, ce dernier pouvant être non énumérable.

Si le prédicat `A"(.)"` est totalement calculable, c'est à dire s'il est calculable par une machine qui donne toujours une réponse vrai `"⊤"` ou faux `"⊥"` en un temps fini, alors tous les éléments sont tranchés et `ccIA=Ø`. On dit que l'ensemble `A` est décidable.

Si le prédicat `A"(.)"` est calculable, c'est à dire s'il est calculable par une machine mais qui peut ne jamais donner de réponse, ce qui se note par la réponse oracle `oo` appellée l'infini de Turing. Alors, la théorie énumère l'ensemble `"⊢"A` c'est à dire les éléments `x` tel que `|--A(x)`. On dit que l'ensemble `"⊢"A` est énumérable . De même `"⊢"¬A` est énumérable.

La théorie énumère complétement `{x" / "|--A(x)}`. C'est alors qu'intervient le point de vu élémentarien, un choix devant être fait à savoir si les éléments individuellement non tranchés peuvent être réfutés dans une théorie enrichie par la proposition `AAx,  (⊬A(x)) => ¬A(x)` sans occasionner de contradiction. L'ajout de cette axiome correspond au choix de définition du demi-ensemble `A = {x" / "|--A(x)} ` qui correspond à l'ensemble minimal parmis tous les modèles possibles. La non contradiction provient du fait que le prédicats doit être bien défini et qu'il peut donc constituer un demi-prédicat.

Comme les prédicats ne sont pas des constructeurs d'éléments on choisie de les placer à l'exterieur des crochets de cloture par composition close `"< >"`. La théorie, qui devra contenir leurs défnition récurcive, sera regroupée avec la théorie d'égalité de la structure et mise au dénominateur. Et c'est la théorie elle-même qui sert d'énumérateur.

Par exemple :

`"<+(.,.)",a,b">", A"(.) /"{A(a),(A(x)" et "A(y))=>A(x"+"y)}`

Le prédicat `A"(.)"` est définie dans la théorie de la structure qui est entre crochets `{}`. Sa définition est uniquement récursive et donc on peut ajouter l'axiome `AAx,  (⊬A(x)) => ¬A(x)` sans occasionner de contradiction. La théorie énumère toutes les propositions qu'elle peut démontrer. L'énumérateur du prédicat `A"(.)"` est constitué par la théorie de la structure :

`A(x) <=> (|--A(x))`
`x in A<=> (|--A(x))`
`A = {x" / "|--A(x)}`

Mais on ne peut faire ce choix que parceque le prédicat `A"(.)"` est bien construit c'est à dire définie uniquement recursivement, sans prendre le risque de rendre la théorie incohérente.

La proposition `⊬A(x)` s'appel un oracle car dans le cas général, il faut attendre d'avoir parcouru toutes les propositions démontrables par la théorie de la structure pour avoir la réponse à cette proposition, c'est à dire attendre un temps infini pour avoir la réponse.

Du point de vue élémentarien, si `⊬A(x)` alors nous avons `¬A(x)`, ce qui signifie intuitivement qu'il n'existe rien au delà de l'infini de Turing, principe éminemment intuitionniste. Tout se passe comme ci on avait ajouté à la théorie, l'axiome `AAx,  (⊬A(x)) => ¬A(x)`-----------------------------------

 

Le Semi-groupe `("+")` qui est définie par `"<+>/"{"+"` est associatif`}`, ne contient aucun élément. Mais il contient des opérateurs tel que `g"(.,.)"` définie par la déclaration `g   =    (x,y) -> (x"+"y)"+"(y"+"x)`. Ces opérateurs sont obtenus par composition générale, au sens d'une programmation sans boucle, à partir le l'opérateur `"+(.,.)"`. Ces programmes sans boucles sont énumérables et il existe un énumérateur qui les énumère. Et on peut aussi programmer un calcul au sens d'une programmation avec boucle "for" dont l'arrêt est borné, pour construire de nouveaux opérateurs. Ces programmes avec boucles "for" sont énumérables et il existe un énumérateur qui les énumère. Mais on peut aussi programmer un calcul au sens d'une programmation plus générale dite µ-récurcive dont l'arrêt est sûr mais non borné, pour construire de nouveaux opérateurs. Ces programmes µ-récurcif sont également énumérables et il existe un énumérateur qui les énumère. Mais on peut aussi programmer une recherche, au sens d'une programmation générale pour construire de nouveaux opérateurs, mais ces programmes peuvent pour certaines valeurs ne jamais s'arréter et ne jamais donner de résultat. Ces programmes au sens générale sont également énumérables et il existe un énumérateur qui les énumère.

La description de ces nouveaux opérateurs va nous amener à définir un langage de programmation qui complètera le langage d'opérateurs de base en ajoutant des opérateurs de programmation. Ces opérateurs de programmation respecteront un certain nombre de règles spécifiques, appelés protocoles, qui seront mis en oeuvre au dessus du langage d'opérateurs de base. On définie 7 niveaux de protocole ou de langage de programmation. Ainsi on réunifie le langage de donnée et le langage de programmation.

On prend comme exemple, le semi-groupe commutatif bigène libre :

`S = "<"1, i, "+>/"{"+"` est associatif`, "+"` est commutatif`}`

Cette structure correspond au couples d'entiers naturels en enlevant l'élément `(0,0)` munie de l'addition composante par composante. Nous allons explorer les 7 niveaux de protocole en programmant à chaque fois un exemple d'opérateur.

Les opérateurs constructibles dans cette structure font partie de la structure. La structure est définie par ce qu'elle peut construire à partir de ses opérateurs de base, modulo sa théorie d'égalité. On classifie plusieurs niveaux de construction selon la puissance d'expression du moteur énumérant les programmes, c'est à dire selon le niveau de protocole ou de langage de programmation :

Niveau n°0 - Base - Ce niveau ne contient que les opérateurs de base, qui sont les éléments et opérateurs générateurs exposés dans la présentation de la structure. Exemples : `1`, `i` , `"+"`

Niveau n°1 - Termes clos - Ce niveau contient tous les éléments, opérateurs d'arité zéro, qu'il est possible de construire par composition close d'opérateurs de base. Exemples : `1`, `i`, `1"+"1`,  `1"+"i`,  `i"+"1`,  `(1"+"i)"+"1`,  `1"+"(i"+"1)`, ...

Niveau n°2 - Termes non clos - Ce niveau contient tous les opérateurs qu'il est possible de construire par composition non nécessairement close d'opérateurs de base, et où les places libres de gauche à droite et sans changer d'aucune façon l'ordre, constituent l'ordre d'appel des arguments. Cela correspond à la logique polonaise. Exemple : l'opérateur `(.+1)+((i+.)+.)` correspond à l'opérateur `(x,y,z)->(x+1)+((i+y)+z)`, et grace à l'associativité et la commmutativité cet opérateur est égal à l'opérateur `(x,y,z)->1+i+x+y+z`

Niveau n°3 - Composition générale - Ce niveau contient tous les opérateurs qu'il est possible de construire à partir des précédents à l'aide de la composition générale. Cela correspond à la programmation sans boucle ni condition. On introduit dans le langage le méta opérateur `->` qui prend en premier argument une entête constituée de `n` variables de noms distincts, et qui prend comme second argument un terme clos du langage étendu par ces `n` variables, appelé corps de l'opérateur. Cela produit un opérateur d'arité `n`. Lors de l'appel de l'opérateur d'arité `n`, l'entête récupère les `n` arguments d'appel dans ses `n` variables locales. Exemples : `x->x`,   `x->x+x`,   `(x,y)->x+y+x+1`. Noter que ce niveau permet de définir la fonction identité `x->x`

Masquage

L'utilisation de ce protocole de manière imbriquée tel que par exemple `x->(y->f(y))`, va entrainer la définition d'un typage, et un mécanisme de variables locales et de variables masquées. Les variables d'appel, à gauche du méta-opérateur de définition `->` sont de nouvelles variables locale à la fonction. Et si elles ont été utilisé lors d'appel antérieur, il s'agit alors de nouvelle variable portant le même noms. Par exemple l'opérateur d'expression `x->(x->(x+a))` comprend deux niveaux de contexte emboités et la variable `x` du premier contexte est masquée par la variable `x` du second contexte, faisant que cette expression est équivalente à `x->(y->(y+a))`

Currification

Puisque qu'un opérateur `f` d'arité `n` est un programme avec `n` entrés, on peut scinder la liste des entrés en deux morceaux contigüs `n_1 + n_2 = n`, et considérer que `f` est une fonction d'arité `n_1` retournant une fonction d'arité `n_2`. Et ce procédé peut être répété. Par exemple nous avons :

`x -> (y -> g(x,y)) = (x,y) -> g(x,y)`
`x -> ((y,z) -> h(x,y,z)) = (x,y,z) -> h(x,y,z)`
`x -> (y -> (z -> h(x,y,z))) = (x,y,z) -> h(x,y,z)`

La currification réduit ainsi le nombre de types différents d'opérateurs. Et il y a deux formes normales, la forme série qui utilise un opérateur de construction d'application binaire `->`, et la forme liste qui n'utilise qu'une seul fois un opérateur de construction d'application d'arité variable `->`. Par exemple l'opérateur `x--> ((y,z) --> h(x,y,z))` admet une forme normale série `x -> (y -> (z -> h(x,y,z)))` et admet une forme normale liste `(x,y,z) -> h(x,y,z)`

Extension implicite

Si on autorise l'utilisation de variables tel que `x,y` dans le corps sans qu'elles n'apparaissent dans l'entête, on se place alors dans le langage étendu par extension élémentaire.

Par exemple l'opérateur `f  =   x->a"+"x` se place dans la structure étendue `S[a]` qui se présente comme Semi-groupe trigène `("+",1,i,a)` c'est à dire `"<+",1,i,a">/"{"+"` est associatif`, "+"` est commutatif`}`

Introduction des listes

On introduit les listes finie, ce qui permet de définir les couples, les triplets, etc..., ainsi que les opérateurs d'arité de sortie supérieur à `1` tel que `x->(x,  x"+"1,  x"+"x)`. Si on s'intéresse à la complexité du calcul des opérateurs, il faut étudier les opérateurs d'arité de sortie supérieur à `1`, car ils mettent en oeuvre le calcul parallèle.

Il y a deux formes normales de currification, en liste ou en série. Exemples :

Exemple
Forme normale liste
Forme normale série
`x -> (y -> g(x,y), a)`  `((x,y) -> g(x,y), x->a)`   `(x -> (y -> g(x,y)), x -> a)`  
`x -> ((y,z) -> a, y -> f(y))`    `((x,y,z) -> a, (x,y) -> f(y))` (x -> (y -> (z -> a)), x -> (y -> f(y)))`

Niveau n°4 - Programmation primitive récurcive - Arret borné

Contient tous les opérateurs qu'il est possible de construire à partir des précédents à l'aide de la programmation primitive récurcive, c'est à dire programmés par composition et par récursion primitive, ou dit autrement dans un langage de programmation impératif, programmés uniquement avec des boucles "for" et non avec les boucles "while", et sans modifier les indexes des boucles "for" autrement que par augmentation, ni modifier les bornes des boucles "for" autrement que par réduction, permettant ainsi de garantir l'arrêt borné du programme.

Ce niveau introduit la récursivité primitve. On la définie de manière plus générale appliquée à une structure autre que les entiers. La récursivité générale met simplement en oeuvre le principe de clôture, un principe co-substantiel à la notion de structure. A savoir : Si des éléments a, b satisfont une propriété P(.), c'est à dire si nous avons P(a) et P(b), et que des opérateurs f(.), g(.,.) respectent la propriété P(.) sur la structure <a,b,f(.),g(.,.)>, c'est à dire si pour tout élément x de la structure <a,b,f(.),g(.,.)> nous avons P(x) => P(f(x)) et si pour tout couple d'éléments x et y appartenants à la structure <a,b,f(.),g(.,.)> nous avons P(x) et P(y) => P(g(x,y)), alors nous pouvons déduire par récurrence généralisée que tous les éléments de la structure <a,b,f(.),g(.,.)> satisfont la propriété P(.). Nous déduisons par exemple P(g(b,f(a))).

    P(a)
    P(b)
,
    ∀x∈<a,b,f(.),g(.,.)>, P(x) => P(f(x)),
    ∀(x,y)∈<a,b,f(.),g(.,.)>2, P(x) et P(y) => P(g(x,y))
=>
∀x∈<a,b,f(.),g(.,.)>, P(x)

On note une séquence de n variables comme suit : u = (u1, u2, u3...., un).

Une fonction primitive récurcive r d'arité n+1 se construit à partir de k opérateurs tels que par exemple a, b, f(.), g(.,.), formant implicitement une structure <a,b,f(.),g(.,.)>, et à partir de k fonctions r1, r2, r3...., rk, une fonction par opérateur, d'arité égale à n plus deux fois l'arité de l'opérateur. La fonction r se programme alors comme une suite d'alternative :

r(u, a) = r1(u)
r(u, b) = r2(u)
r(u, f(x)) = r3(u, x, r(u,x))
r(u, g(x,y)) = r4(u, x, y, r(u,x), r(u,y))

Notez que les dernières alternatives sont récurcives. La fonction r est réappelée dans un ou plusieurs arguments. L'opérateur r se note à l'aide du méta-opérateur d'alternative | comme suit, chaque alternative étant passée à la ligne pour plus de clarté :

r = (u, a) --> r1(u) |
      (u, b) --> r2(u) |
      (u, f(x)) --> r3(u, x, r(u,x)) |
      (u, g(x,y)) --> r4(u, x, y, r(u,x), r(u,y))

C'est une liste d'alternatives à prendre dans l'ordre. Lors de l'appel r(w)w est une séquence de n+1 termes clos, la fonction r va tester l'unification de w avec la première entête (u,a). Si l'unification réussi alors la fonction r retourne r1(u), et si l'unification échoue alors on passe à l'alternative suivante, etc...

La récurcivité primitive peut ainsi être construite indépendament des entiers. De tel sorte que les entiers ne sont plus une structure particulière, nécessaire à la récurrence.

---- 6 juillet 2014 ----

 

-----------------------

 

Une variable universelle x se présente comme une mémoire pouvant contenir un élément constructible, c'est à dire un terme clos du langage de base.

Puis on considère une variable un peu plus générale qui contient un opérateur d'arité n définie par un programme µ-récursif, c'est à dire une variable qui contient un programme à n entrés dont l'arrêt est sûr. Le programme appliqué à n éléments va construire un résultat à l'aide d'opérateurs qui, s'ils ne sont pas définis par d'autre programme, ne seront pas évalués mais utilisés comme des légos de construction. Et, il n'y a pas de différence entre donnée et programmme. Une généralisation possible consiste à étendre ainsi le domaine de ces variables afin qu'elles puissent contenir n'importe quel opérateur µ-récursif d'arité fixe, c'est à dire n'importe quel programme agissant sur un nombre fixe d'entrés et dont l'arrêt est sûr. (C'est le principe de finitude que nous mettons en avant. Toute donnée, programme ou théorie, du moment qu'elle est finie, peut être mémorisée dans une mémoire. Et cela constitue le principe de base de la construction informatique.)

 

------------------

 

 

Niveau n°5 - programmation µ-recurcive - Arret sûr

Contient tous les opérateurs qu'il est possible de construire à partir des précédents et à l'aide de la programmation µ-recurcive, c'est à dire programmés comme au niveau précédent mais en ajoutant une opération supplémentaire appelée la minimalisation de prédicats sûrs, c'est à dire programmés dans un langage de programmation impératif, en utilisant des boucles "while" seulement lorsque on est sûr qu'il y aura un arrêt de la boucle "while", un arrêt non nécessairement borné, mais un arrêt garanti du programme. On obtient ainsi tous les opérateurs totalement calculables.

Ce niveau introduit la minimalisation de prédicat sûr.

Etant donné un prédicat n+1 aire, P(ω,x), avec ω représentant une séquence de n arguments ω = (ω1, ω2, ω3...., ωn). On pose que ce prédicat P(ω,x) est défini par un programme de niveau 5. On pose que , P(ω,x)=faux lorsque P(ω,x) = FAIL. Et on pose que P(ω,x) = false lorsque P(ω,x) ≠ FAIL. Comme c'est un programme de niveau 5, il se termine nécessairement en un temps fini, et selon une borne donnée par les boucles "for".

Etant donné une structure libre, qui jouera le rôle des entiers, telle que <a,b,f(.),g(.,.)>, l'énumérateur canonique de cette structure y définie une relation d'ordre. La minimalisation suppose qu'il existe un ordre de rangement des éléments, et cet ordre est donné par l'énumérateur canonique, selon la taille d'abord et l'ordre lexicographique selon l'ordre des opérateurs dans la présentation. Ainsi, dans le langage L = {a,b,f(.),g(.,.)}, et selon l'ordre (a,b,f,g), les éléments sont totalements ordonnés comme suit :

a
b
f(a)
f(b)
f(f(a))
f(f(b))
g(a,a)
g(a,b)
g(b,a)
g(b,b)
f(f(f(a)))
f(f(f(b)))
g(a,f(a))
g(a,f(b))
g(b,f(a))
g(b,f(b))
g(f(a),a)
g(f(a),b)
...

La minimalisation de P(ω,x) pour x appartenant à <a,b,f(.),g(.,.)> est la fonction suivante :

ω --> min(x ; x∈<a,b,f(.),g(.,.)> et P(ω,x)=true)

Mais une hypothèse supplémentaire doit être faite, car sans cela il se pourrait qu'il n'y est pas de solution, il se pourrait que pour tout x le calcule aboutisse à P(ω,x) = false, et alors le calcul de la minimalisation ne s'arrèterait jamais. Pour remédier à cela, il faut supposer que : Quelque soit ω, la fonction x -> P(ω,x) définie sur <a,b,f(.),g(.,.)> est un prédicat sûr, c'est à dire qu'on doit être sûr qu'il existe au moins un élément x appartenant à <a,b,f(.),g(.,.)> tel que P(ω,x) = true.

Autrement dit, P est une fonction quelconque de niveau 0,1,2,3,4 ou 5, tel que ∀ω ∃x∈<a,b,f(.),g(.,.)> P(ω,x)=true.

On remarquera que la minimalisation et la programmation µ-récurcive sont ainsi définie indépendament des entiers.

Le niveau 6 regroupe tous les programmes dont l'arret est sûr.

Niveau n°6 (Programmation générale)

contient les opérateurs qu'il est possible de construire à partir des précédents à l'aide de la programmation générale. Mais la programmation générale ne garantie pas l'arrêt du programme. Un programme peut ne jamais s'arréter et ne jamais donner de réponse, ce qui est représenté par l'infini de Turing. On dit abusivement que le programme donne comme résultat l'infini de Turing. Il s'agit en faite d'un oracle, car pour en être sûr, il faudrait attendre indéfiniment. Le sens de ces opérateurs est alors un peu particulier puisque dans certain cas imprévisible, et sans jamais en être sûre, ils valent l'infinit de Turing.

Voici des exemples d'opérateurs pour chaque niveaux :

Niveau 0 (Base) : L'élément 1

Niveau 1 (Termes clos) : L'élément 3 = 1+(1+1)

Niveau 2 (Composition générale) : La fonction f = x-->(x+x)

Niveau 3 (Unification) : La fonction g = (x+1)-->x

Niveau 4 (Alternative) : La fonction h = (x+1)-->x | x->1

Niveau 4.5 (Quotientage de niveau 5) : La fonction g°f où :

f appliqué à x, retourne le terme x en remplaçant toutes les expressions de la forme (1+z) en les expressions (z+1).

g = (x+1)-->x | x->1

Niveau 5 (Programmation primitive récurcive) : La fonction mult = (x,0)-->0 | (x,y+1)-->x + mult(x,y)

Niveau 6 (Programmation µ-récurcuve) : La fonction d'Ackermann

A = (0,x)-->x+1 | (x+1,0)-->A(x,1) | (x+1,y+1)-->A(x,A(x+1,y))

Exemple générale :

A = ω --> min(x / x∈<a,b,f(.),g(.,.)> et P(ω,x)=true)

P(ω,x) est une fonction quelconque (de niveau 0,1,2,3,4,5,6), et où ω = (ω1, ω2, ω3...., ωn), et où ∀ω ∃x∈<a,b,f(.),g(.,.)> P(ω,x)=true ce qui signifie que le prédicat P(ω,x) est sûre quelque soit ω, il y a au moins une solution x appartenant à <a,b,f(.),g(.,.)>.

Niveau 7 (Programmation générale) : Exemple non-trivial à trouver :

Reste à trouver un exemple simple de programme qui sur certaines entrés donne l'infini de Turing, mais un infini vrai, un vrai oracle, c'est à dire qui ne peut pas être deviné avant d'avoir attendu un temps infini.

Les opérateurs sont définie par des programmes. Et le langage de programmation devient un langage de construction d'opérateurs.

 

Structure fondamentale (suite)

 

---------------------------------------------

11) Ce que contiennent les structures

La récursivité est consubstantielle à la notion de structure

Le Semi-groupe `("+")` qui est définie par `"<+>/"{"+"` est associatif`}`, ne contient aucun élément. Mais il contient des opérateurs tel que `g"(.,.)"` définie par la déclaration `g   =    (x,y) -> (x"+"y)"+"(y"+"x)`. Ces opérateurs sont obtenus par composition générale, au sens d'une programmation sans boucle, à partir le l'opérateur `"+(.,.)"`. Ces programmes sans boucles sont énumérables et il existe un énumérateur qui les énumère. Et on peut aussi programmer un calcul au sens d'une programmation avec boucle "for" dont l'arrêt est borné, pour construire de nouveaux opérateurs. Ces programmes avec boucles "for" sont énumérables et il existe un énumérateur qui les énumère. Mais on peut aussi programmer un calcul au sens d'une programmation plus générale dite µ-récurcive dont l'arrêt est sûr mais non borné, pour construire de nouveaux opérateurs. Ces programmes µ-récurcif sont également énumérables et il existe un énumérateur qui les énumère. Mais on peut aussi programmer une recherche, au sens d'une programmation générale pour construire de nouveaux opérateurs, mais ces programmes peuvent pour certaines valeurs ne jamais s'arréter et ne jamais donner de résultat. Ces programmes au sens générale sont également énumérables et il existe un énumérateur qui les énumère.

La description de ces nouveaux opérateurs va nous amener à définir un langage de programmation qui complètera le langage d'opérateurs de base en ajoutant des opérateurs de programmation. Ces opérateurs de programmation respecteront un certain nombre de règles spécifiques, appelés protocoles, qui seront mis en oeuvre au dessus du langage d'opérateurs de base. On définie 7 niveaux de protocole ou de langage de programmation. Ainsi on réunifie le langage de donnée et le langage de programmation.

On prend comme exemple, le semi-groupe commutatif bigène libre :

`S = "<"1, i, "+>/"{"+"` est associatif`, "+"` est commutatif`}`

Cette structure correspond au couples d'entiers naturels en enlevant l'élément `(0,0)`. Nous allons explorer les 7 niveaux de protocole en programmant à chaque fois un exemple d'opérateur.

Les opérateurs constructibles dans cette structure font partie de la structure. La structure est définie par ce qu'elle peut construire à partir de ses opérateurs de base, modulo sa théorie d'égalité. On classifie plusieurs niveaux de construction selon la puissance d'expression du moteur énumérant les programmes, c'est à dire selon le niveau de protocole ou de langage de programmation :

Niveau n°0 (Base)

Ce niveau ne contient que les opérateurs de base, qui sont les éléments et opérateurs générateurs exposés dans la présentation de la structure :

Exemples : `1, i, "+"`

Niveau n°1 (Termes clos)

Ce niveau contient tous les éléments (opérateurs d'arité zéro) qu'il est possible de construire par composition close d'opérateurs de base :

Exemples : `1, i, 1"+"1, 1"+"i, i"+"1, (1"+"i)"+"1, 1"+"(i"+"1)...`

Un même élément de `S` peut avoir plusieurs expressions différentes tel que `(1+1)+1 = 1+(1+1)` et tel que `1+i = i+1`. Cela est dû, ici, à l'associativité et à la commutativité de `"+"` qui introduit une relation d'équivalence sur la structure libre `"<"1, i, "+>"`, faisant que deux expressions distinctes sont équivalentes lorsque la théorie de la structure le démontre, et donc désigne le même élément dans la structure `S`.

Comme l'opérateur `"+"` est associatif et commutatif, par un procédé mécanique, on peut regrouper dans toutes les expressions de `"<"1, i, "+>"`, les `1` et les `i` pour les mettres sous une forme telle que par exemple `(((1"+"1)"+"1)"+"1) + ((((i"+"i)"+"i)"+"i)"+"i)` appelé forme normale que l'on remplace par un couple d'entiers `(a,b)` noté `a+i**b``a` et `b` sont des entiers mais où `a` et `b` ne peuvent pas être nulle en même temps. On a ainsi définie un isomorphisme calculable de `S` vers `NN×NN - {(0,0)}` munie de l'addition vectoriel `"+"`.

L'associatrivité fait que l'on peut enlever les parenthèses. La commutativité fait que l'on peut mettre les éléments de la somme dans n'importe quel ordre.

Niveau n°2 (Termes non clos)

Ce niveau contient tous les opérateurs qu'il est possible de construire par composition non nécessairement close d'opérateurs de base, et où les places libres de gauche à droite et sans changer d'aucune façon l'ordre, constituent l'ordre d'appel des arguments. Cela correspond à la logique polonaise.

Exemple : l'opérateur `(.x+1)+((i+.)+.)` correspond à l'opérateur `(x,y,z)->(x+1)+((i+y)+z)`, et grace à l'associativité et la commmutativité cet opérateur est égal à l'opérateur `(x,y,z)->1+i+x+y+z`

Niveau n°3 (Composition générale)

Ce niveau contient tous les opérateurs qu'il est possible de construire à partir des précédents à l'aide de la composition générale. Cela correspond à la programmation sans boucle ni condition.

On introduit dans le langage le méta opérateur `->` qui prend en premier argument une entête constituée de `n` variables de noms distincts, et qui prend comme second argument un terme clos du langage étendu par ces `n` variables, appelé corps de l'opérateur. Cela produit un opérateur d'arité `n`.

Lors de l'appel de l'opérateur d'arité `n`, l'entête récupère les `n` arguments d'appel dans ses `n` variables locales.

Exemples : `x->x,   x->x+x,   (x,y)->x+y+x+1`

Noter que ce niveau permet de définir la fonction identité `x->x`

L'utilisation de ce protocole de manière imbriquée tel que par exemple `x->(y->f(y))`, va entrainer la définition d'un typage, et un mécanisme de variables locales et de variables masquées.

Masquage

Les variables d'appel, à gauche du méta-opérateur de définition `->`, sont de nouvelles variables locale à la fonction. Et si elles ont été utilisé lors d'appel antérieur, il sagit alors de nouvelle variable portant le même noms. Par exemple l'opérateur d'expression `x->(x->(x+a))` comprend deux niveaux de contexte emboités et la variable `x` du premier contexte est masquée par la variable `x` du second contexte, et cela donne un opérateur constant.

Currification

Puisque qu'un opérateur `f` d'arité `n` est un programme avec `n` entrés, on peut scinder la liste des entrés en deux morceaux contigüs `n_1 + n_2 = n`, et considérer que `f` est une fonction d'arité `n_1` retournant une fonction d'arité `n_2`. Et ce procédé peut être répété. Par exemple nous avons :

`x -> (y -> g(x,y)) = (x,y) -> g(x,y)`
`x -> ((y,z) -> h(x,y,z)) = (x,y,z) -> h(x,y,z)`
`x -> (y -> (z -> h(x,y,z))) = (x,y,z) -> h(x,y,z)`

La currification réduit ainsi le nombre de types différents d'opérateur. Et il y a deux formes normales, la forme série qui n'utilise un opérateur de construction d'application binaire `->`, et la forme liste qui n'utilise qu'une seul fois un opérateur de construction d'application d'arité variable `->`. Par exemple l'opérateur x--> ((y,z) --> h(x,y,z)) admet une forme normale série `x -> (y -> (z -> h(x,y,z)))` et admet une forme normale liste `(x,y,z) -> h(x,y,z)`

Extension implicite

Si on autorise l'utilisation de variables tel que `x,y` dans le corps sans qu'elles n'apparaissent dans l'entête, on se place alors dans le langage étendu par extension élémentaire.

Par exemple l'opérateur `f  =   x->a"+"x` se place dans la structure étendue `S[a]` qui se présente comme Semi-groupe trigène `("+",1,i,a)` c'est à dire `"<+",1,i,a">/"{"+"` est associatif`, "+"` est commutatif`}`

Introduction des listes

On introduit les listes finie, ce qui permet de définir les couples, les triplets, etc..., ainsi que les opérateurs d'arité de sortie supérieur à `1` tel que `x->(x,  x"+"1,  x"+"x)`

il y a deux normales de currification, en liste ou en série. Exemples :

Exemple
Forme normale liste
Forme normale série
`x -> (y -> g(x,y), a)`  `((x,y) -> g(x,y), x->a)`   `(x -> (y -> g(x,y)), x -> a)`  
`x -> ((y,z) -> a, y -> f(y))`    `((x,y,z) -> a, (x,y) -> f(y))` (x -> (y -> (z -> a)), x -> (y -> f(y)))`

Si on s'intéresse à la complexité du calcul des opérateurs, il faut étudier les opérateurs d'arité de sortie supérieur à `1`, car ils mettent en oeuvre des calculs parallèles.

Niveau n°4 (Unification)

Contient tous les opérateurs qu'il est possible de construire à l'aide de l'unification et de la composition générale. Cela correspond à la programmation sans boucle avec unification mais sans alternative.

Ce niveau introduit l'unification, qui correspond à un opérateur inverse, ou autrement dit à une condition, d'être dans l'image de cet opérateur, suivi de l'opérateur inverse. L'unification se déroule lors de l'appel, elle unifie l'appel de l'opérateur avec l'entête de l'opérateur.

On étend l'opérateur `->`. Celui-ci s'applique maintenant à une entête plus sophistiquée, qui n'est plus seulement composée de variables libres mais de termes clos quelconques du langage étendu par n variables, et le corps doit être un terme clos du langage étendu par ces n variables.

Le méta-opérateur `"FAIL"` est ajouté au langage. Un opérateur retourne `"FAIL"` lorsque lors de son appel, l'unification a échoué. Par défaut un opérateur qui prend parmi un de ses arguments, `"FAIL"`, retourne `"FAIL"`.

Exemple : `x+x -> i`

 

---- 1er Juillet 2016 ----

 

 

Ce nouveau protocole permet de construire les opérateurs programmables par composition générale et unification, autrement dit sans boucle et avec une seul condition c'est à dire sans alternative.

Grace au meta-opérateur FAIL, tout opérateur peut être perçu comme un prédicat. Il retourne FAIL pour "Faux" ou un résultat autre que FAIL pour "Vrai". Etant donné un tel opérateur P(u)u représente n arguments u = (u1,u2,u3...,un), nous écrirons P(u)=true pour dire P(u)≠FAIL et nous écrirons P(u)=false pour dire P(u)=FAIL.

Exemples pour la structure :

Dans une structure , les éléments sont implementés comme des mots non vides d'alphabet {a,b}. L'uification d'un mot avec la concatenation de deux mots n'est pas unique !. Nous ne pouvons pas utiliser l'unification sur les classes d'équivalences car elle n'est pas unique, mais nous pouvons utiliser l'unification sur la structure libre sous-jacente en ne traitant que les formes normales pour ne produire que des formes normales. Si on choisie comme forme normale de la somme +(u1,u2,u3,u4...,un) l'expression u1+(u2+(u3+(u4+...un)))... alors on peut définir les opérateurs suivant :

Défini par
constructeur d'application
Défini par
clause d'égalité
Appliqué à deux exemples
Ecrit sous forme
de mots
K : b+x --> x
K(b+x) = x
K(b+(a+b)) = a+b
K(bab) = ab
H : x+(b+y) --> x+y
H(x+(b+y)) = x+y
H(a+(b+(c+a))) = a+(c+a)
H(abca) = aca
M : x+(y+(b+z)) --> x+(y+z)
M(x+(y+(b+z)))= x+(y+z)
M(a+(a+(b+(c+a)))) = a+(a+(c+a))
M(aabca) = aaca

L'introduction des listes et opérateurs d'arité variabiables ne change pas grand chose. L'unification de listes de taille différente échoue.

Niveau n°5 (Alternative)

Contient tous les opérateurs qu'il est possible de construire à partir des précédents à l'aide de l'alternative, de l'unification et de la composition générale. Cela correspond à la programmation sans boucle.

On introduit le méta-opérateur d'alternative noté | qui permet de construire une liste d'opérateurs.

Ce niveau introduit la liste d'alternatives, qui correspond à une liste d'opérateurs possibles, posée dans un ordre précis, et tel que le premier qui ne retourne pas FAIL est choisie pour retourner le résultat.

Exemples pour la structure libre L :

Défini par
constructeur d'application
Défini par
clause d'égalité
Appliqué à des exemples
K : f(x) --> g(x, x) | x --> f(x)
K(f(x)) = g(x,x) | K(x) = f(x)
K(a) = a
K(f(a)) = g(a,a)
K(h(a)) = FAIL
H : (x, f(y)) --> g(y, f(x)) | (x, x) --> x
H(x, f(y)) = g(y, f(x)) | H(x, x) = x
H(a,a) = a
H(a,b) = FAIL
H(a,f(b)) = g(b, f(a))

Exemples pour la structure avec le choix de la forme normale +(u1,u2,u3,u4...,un) = u1+(u2+(u3+(u4+...un)))...

Défini par
constructeur d'application
Défini par
clause d'égalité
Appliqué à des exemples
K : x+y --> y+x | x+(y+y) --> y+x
K(x+y)=y+x | K(x+(y+y)) = y+x
K(a+b) = b+a
K(a+(b+b)) = b+a
K(a+(b+(b+b))) = FAIL

Niveau n°6 (Programmation primitive récurcive) (Arret borné)

Contient tous les opérateurs qu'il est possible de construire à partir des précédents à l'aide de la programmation primitive récurcive, c'est à dire programmés par composition et par récursion primitive, ou dit autrement dans un langage de programmation impératif, programmés uniquement avec des boucles "for" et non avec les boucles "while", et sans modifier les indexes des boucles "for" autrement que par augmentation, ni modifier les bornes des boucles "for" autrement que par réduction, permettant ainsi de garantir l'arrêt borné du programme.

Ce niveau introduit la récursivité primitve. On la définie de manière plus générale appliquée à une structure autre que les entiers. La récursivité générale met simplement en oeuvre le principe de clôture, un principe co-substantiel à la notion de structure. A savoir : Si des éléments a, b satisfont une propriété P(.), c'est à dire si nous avons P(a) et P(b), et que des opérateurs f(.), g(.,.) respectent la propriété P(.) sur la structure <a,b,f(.),g(.,.)>, c'est à dire si pour tout élément x de la structure <a,b,f(.),g(.,.)> nous avons P(x) => P(f(x)) et si pour tout couple d'éléments x et y appartenants à la structure <a,b,f(.),g(.,.)> nous avons P(x) et P(y) => P(g(x,y)), alors nous pouvons déduire par récurrence généralisée que tous les éléments de la structure <a,b,f(.),g(.,.)> satisfont la propriété P(.). Nous déduisons par exemple P(g(b,f(a))).

    P(a)
    P(b)
,
    ∀x∈<a,b,f(.),g(.,.)>, P(x) => P(f(x)),
    ∀(x,y)∈<a,b,f(.),g(.,.)>2, P(x) et P(y) => P(g(x,y))
=>
∀x∈<a,b,f(.),g(.,.)>, P(x)

On note une séquence de n variables comme suit : u = (u1, u2, u3...., un).

Une fonction primitive récurcive r d'arité n+1 se construit à partir de k opérateurs tels que par exemple a, b, f(.), g(.,.), formant implicitement une structure <a,b,f(.),g(.,.)>, et à partir de k fonctions r1, r2, r3...., rk, une fonction par opérateur, d'arité égale à n plus deux fois l'arité de l'opérateur. La fonction r se programme alors comme une suite d'alternative :

r(u, a) = r1(u)
r(u, b) = r2(u)
r(u, f(x)) = r3(u, x, r(u,x))
r(u, g(x,y)) = r4(u, x, y, r(u,x), r(u,y))

Notez que les dernières alternatives sont récurcives. La fonction r est réappelée dans un ou plusieurs arguments. L'opérateur r se note à l'aide du méta-opérateur d'alternative | comme suit, chaque alternative étant passée à la ligne pour plus de clarté :

r = (u, a) --> r1(u) |
      (u, b) --> r2(u) |
      (u, f(x)) --> r3(u, x, r(u,x)) |
      (u, g(x,y)) --> r4(u, x, y, r(u,x), r(u,y))

C'est une liste d'alternatives à prendre dans l'ordre. Lors de l'appel r(w)w est une séquence de n+1 termes clos, la fonction r va tester l'unification de w avec la première entête (u,a). Si l'unification réussi alors la fonction r retourne r1(u), et si l'unification échoue alors on passe à l'alternative suivante, etc...

La récurcivité primitive peut ainsi être construite indépendament des entiers. De tel sorte que les entiers ne sont plus une structure particulière, nécessaire à la récurrence.

---- 6 juillet 2014 ----

 

-----------------------

 

Une variable universelle x se présente comme une mémoire pouvant contenir un élément constructible, c'est à dire un terme clos du langage de base.

Puis on considère une variable un peu plus générale qui contient un opérateur d'arité n définie par un programme µ-récursif, c'est à dire une variable qui contient un programme à n entrés dont l'arrêt est sûr. Le programme appliqué à n éléments va construire un résultat à l'aide d'opérateurs qui, s'ils ne sont pas définis par d'autre programme, ne seront pas évalués mais utilisés comme des légos de construction. Et, il n'y a pas de différence entre donnée et programmme. Une généralisation possible consiste à étendre ainsi le domaine de ces variables afin qu'elles puissent contenir n'importe quel opérateur µ-récursif d'arité fixe, c'est à dire n'importe quel programme agissant sur un nombre fixe d'entrés et dont l'arrêt est sûr. (C'est le principe de finitude que nous mettons en avant. Toute donnée, programme ou théorie, du moment qu'elle est finie, peut être mémorisée dans une mémoire. Et cela constitue le principe de base de la construction informatique.)

 

------------------

 

 

Exemple pour L : r = a--> b |
     f(a) --> g(a, r(a))
Noter l'appelle à r dans la définition de r
Exemple pour N* : m = (x, 1)-->x |
       (x, y+1)--> x+m(y)
Noter l'appelle à m dans la définition de m

Ces opérateurs r et m sont des programmes primitifs récurcifs. La variable r peut être considéré commme contenant un programme. C'est pourquoi on utilise le symbole d'affectation "="

L'opérateur r est perçu comme une variable contenant un programme primitif récurcif d'arité 1, c'est à dire qui s'applique sur une entré.

Niveau n°4.6 (Unification avec une mise en forme normale préalable)

Contient un pré-algorithme de mise sous forme normale avant l'unification. Par exemple, pour tenir compte de l'associativité de l'opération +, il faut mettre sous forme normale une somme telle que l'expression (1+1)+((1+1)+(1+1)) en l'expression (1+(1+(1+(1+(1+1))))).Et cela peut se faire en appliquant une transformation de niveau 6

Niveau n°7 (programmation µ-recurcive) (Arret sûr)

Contient tous les opérateurs qu'il est possible de construire à partir des précédents et à l'aide de la programmation µ-recurcive, c'est à dire programmés comme au niveau précédent mais en ajoutant une opération supplémentaire appelée la minimalisation de prédicats sûrs, c'est à dire programmés dans un langage de programmation impératif, en utilisant des boucles "while" seulement lorsque on est sûr qu'il y aura un arrêt de la boucle "while", un arrêt non nécessairement borné, mais un arrêt garanti du programme. On obtient ainsi tous les opérateurs totalement calculables.

Ce niveau introduit la minimalisation de prédicat sûr.

Etant donné un prédicat n+1 aire, P(ω,x), avec ω représentant une séquence de n arguments ω = (ω1, ω2, ω3...., ωn). On pose que ce prédicat P(ω,x) est défini par un programme de niveau 5. On pose que , P(ω,x)=faux lorsque P(ω,x) = FAIL. Et on pose que P(ω,x) = false lorsque P(ω,x) ≠ FAIL. Comme c'est un programme de niveau 5, il se termine nécessairement en un temps fini, et selon une borne donnée par les boucles "for".

Etant donné une structure libre, qui jouera le rôle des entiers, telle que <a,b,f(.),g(.,.)>, l'énumérateur canonique de cette structure y définie une relation d'ordre. La minimalisation suppose qu'il existe un ordre de rangement des éléments, et cet ordre est donné par l'énumérateur canonique, selon la taille d'abord et l'ordre lexicographique selon l'ordre des opérateurs dans la présentation. Ainsi, dans le langage L = {a,b,f(.),g(.,.)}, et selon l'ordre (a,b,f,g), les éléments sont totalements ordonnés comme suit :

a
b
f(a)
f(b)
f(f(a))
f(f(b))
g(a,a)
g(a,b)
g(b,a)
g(b,b)
f(f(f(a)))
f(f(f(b)))
g(a,f(a))
g(a,f(b))
g(b,f(a))
g(b,f(b))
g(f(a),a)
g(f(a),b)
...

La minimalisation de P(ω,x) pour x appartenant à <a,b,f(.),g(.,.)> est la fonction suivante :

ω --> min(x ; x∈<a,b,f(.),g(.,.)> et P(ω,x)=true)

Mais une hypothèse supplémentaire doit être faite, car sans cela il se pourrait qu'il n'y est pas de solution, il se pourrait que pour tout x le calcule aboutisse à P(ω,x) = false, et alors le calcul de la minimalisation ne s'arrèterait jamais. Pour remédier à cela, il faut supposer que : Quelque soit ω, la fonction x -> P(ω,x) définie sur <a,b,f(.),g(.,.)> est un prédicat sûr, c'est à dire qu'on doit être sûr qu'il existe au moins un élément x appartenant à <a,b,f(.),g(.,.)> tel que P(ω,x) = true.

Autrement dit, P est une fonction quelconque de niveau 0,1,2,3,4 ou 5, tel que ∀ω ∃x∈<a,b,f(.),g(.,.)> P(ω,x)=true.

On remarquera que la minimalisation et la programmation µ-récurcive sont ainsi définie indépendament des entiers.

Le niveau 6 regroupe tous les programmes dont l'arret est sûr.

Niveau n°8 (Programmation générale)

contient les opérateurs qu'il est possible de construire à partir des précédents à l'aide de la programmation générale. Mais la programmation générale ne garantie pas l'arrêt du programme. Un programme peut ne jamais s'arréter et ne jamais donner de réponse, ce qui est représenté par l'infini de Turing. On dit abusivement que le programme donne comme résultat l'infini de Turing. Il s'agit en faite d'un oracle, car pour en être sûr, il faudrait attendre indéfiniment. Le sens de ces opérateurs est alors un peu particulier puisque dans certain cas imprévisible, et sans jamais en être sûre, ils valent l'infinit de Turing.

Voici des exemples d'opérateurs pour chaque niveaux :

Niveau 0 (Base) : L'élément 1

Niveau 1 (Termes clos) : L'élément 3 = 1+(1+1)

Niveau 2 (Composition générale) : La fonction f = x-->(x+x)

Niveau 3 (Unification) : La fonction g = (x+1)-->x

Niveau 4 (Alternative) : La fonction h = (x+1)-->x | x->1

Niveau 4.5 (Quotientage de niveau 5) : La fonction g°f où :

f appliqué à x, retourne le terme x en remplaçant toutes les expressions de la forme (1+z) en les expressions (z+1).

g = (x+1)-->x | x->1

Niveau 5 (Programmation primitive récurcive) : La fonction mult = (x,0)-->0 | (x,y+1)-->x + mult(x,y)

Niveau 6 (Programmation µ-récurcuve) : La fonction d'Ackermann

A = (0,x)-->x+1 | (x+1,0)-->A(x,1) | (x+1,y+1)-->A(x,A(x+1,y))

Exemple générale :

A = ω --> min(x / x∈<a,b,f(.),g(.,.)> et P(ω,x)=true)

P(ω,x) est une fonction quelconque (de niveau 0,1,2,3,4,5,6), et où ω = (ω1, ω2, ω3...., ωn), et où ∀ω ∃x∈<a,b,f(.),g(.,.)> P(ω,x)=true ce qui signifie que le prédicat P(ω,x) est sûre quelque soit ω, il y a au moins une solution x appartenant à <a,b,f(.),g(.,.)>.

Niveau 7 (Programmation générale) : Exemple non-trivial à trouver :

Reste à trouver un exemple simple de programme qui sur certaines entrés donne l'infini de Turing, mais un infini vrai, un vrai oracle, c'est à dire qui ne peut pas être deviné avant d'avoir attendu un temps infini.

Les opérateurs sont définie par des programmes. Et le langage de programmation devient un langage de construction d'opérateurs.

 

 

 

 

 

 

Dominique Mabboux-Stromberg (Septembre 2013)

 

Sujet :

Structures fondamentales
Langage d'opérateurs et structure mathématique.

Sujets liés :

Structures fondamentales 2
Type

 

 

 

Table des matières :

  1. Semi-groupe
  2. Les premières structures dévoilées
  3. La théorie d'une structure
  4. Décomposition en suite d'extensions et de quotientages
  5. Une alternative à la théorie des ensembles
  6. Les théories d'égalité
  7. Les relations d'équivalence
  8. Ce que contiennent les structures
    1. Niveau n°0 (Base)
    2. Niveau n°1 (Termes clos)
    3. Niveau n°2 (Composition générale)
      1. Currification
      2. extension implicite
    4. Niveau n°3 (Unification)
    5. Niveau n°4 (Alternatives)
    6. Niveau n°4.x (Quotientage de niveau x)
    7. Niveau n°5 (Programmation primitive récurcive)
    8. Niveau n°6 (Programmation µ-récurcive)
    9. Niveau n°7 (Programmation générale

 

On enlève cette restriction en développant le concept de variable locale. L'entête de l'opérateur déclare des variables libre dites locales à l'opérateur, dont la portées ne s'étend pas au delà du corps de l'opérateur. Dés lors, ces variables locals peuvent masquer une variable moins locale commme dans l'exemple x-->(x-->f(x)) où l'appel f(x) se fait avec la variable locale déclarée par x-->f(x) et non avec la première variable x qui est moins local.

On peut alors, comme dans la programmation orientée object, utiliser un méta-opérateur spécifique $ pour faire référence à la variable masquée juste au dessus, en remontant d'un niveau. Par exemple x-->(x-->$x) désigne la fonction qui à tout élément associe la fonction constante égale à cet élément.

Mais un tel élément étendu, x ou y, peut aussi être utilisé comme variable dans une entête. Et s'il est utilisé comme variable dans l'entête, il ne peut être utilisé comme élément étendu dans le corps car il est alors masqué par la variable local de même nom.

Puis on convient de nommer la liste vide par .∅ = ( ) = List( )

 

Niveau n°5 (Quotientage)

Contient tous les opérateurs qu'il est possible de construire à partir des précédents à l'aide de transformations de niveau maximum x en une forme normal avant unification et alternative.

Une telle transformation en forme normale est un programme qui appliqué à un terme va produire un autre terme représentant une classe d'équivalence. Deux termes ayant la même forme normale sont équivalents. La transformation correspond à un quotientage. De façon analogue à cette présente classification, Il existe 7 niveaux de quotientage que nous décrirons plus tard. Noter alors que le niveau 4 correspond aux niveaux 4.0, 4.1, 4.2, 4.3, 4.4 et que les niveaux 4.5, 4.6, 4.7 sont à ranger avec les niveaux 5, 6, 7.

T définie une relation d'équivalence sur une puissance de la structure libre L. Deux éléments x, y, de la structure libre L sont dits T-égaux si T démontre leur égalité. On note x T y pour signifier que x et y sont égaux pour la théorie T. Deux couples d'éléments (x1,x2), (y1,y2) de la structure libre L2 sont dits T-égaux si T démontre leur égalité. On note (x1,x2) T (y1,y2) pour signifier que ces deux couples sont égaux pour la théorie T c'est à dire que T démontre x1=x2 et y1=y2.

x T y                                 si et seulemet si        T |- x=y
(x1,x2) T (y1,y2)              si et seulemet si        T |- x1=y1   et   T |- x2=y2
(x1,x2,x3) T (y1,y2,y3)     si et seulemet si        T |- x1=y1   et   T |- x2=y2  et   T |- x3=y3
...

La théorie T possède une dimension définie comme égal au plus petit nombre de noms distincts de variables universelles devant être utilisés pour écrire un ensembles de clause équivalent à T.

 

 

 

-----

---- 2 février 2015 ----

 

 

Forme normales

On appel une forme normale, une forme unique produite par un algorithme, et qui permet ainsi de tester si deux expressions sont équivalentes simplement en calculant leur forme normale. Si deux expressions ont la même forme normale alors elles désignent nécessairement le même élément que l'on représente par la forme normale en question.

La forme normal dans un semi-groupe libre correspond à une séquence d'éléments de base. On peut définir une forme normale sous forme d'une liste lispienne d'éléments de base que l'on peut noter par u1+(u2+(u3+(u4+...un)))... et de façon simplifié par le mot u1u2u3u4...un

Dans , nous pouvons identifier les élements aux formes normales suivantes :

1 = 1
2 = 1+1
3 = (1+1)+1
4 = ((1+1)+1)+1
...

Dans S, nous pouvons identifier les élements aux formes normales suivantes :

(1,0) = 1
(0,1) = i
(2,0) = 1+1
(1,1) = 1+i
(0,2) = i+i
(3,0) = (1+1)+1
(2,1) = (1+1)+i
(1,2) = (1+i)+i
(0,3) = (i+i)+i
(4,0) = ((1+1)+1)+1
...

Dans , nous pouvons identifier les élements aux formes normales suivantes :

a
b
2a = a+a
a+b

Pour pouvoir utiliser les listes, il faut enrichire notre langage de programmation avec des outils de manipulation de listes. On peut s'inspirer de la programmation orienté objet. On définie des opérateurs d'arité variable symbolisé par l'élipse (...) et pour récupérer le i-ième argument transmis dans un appel, on utilise le meta-opérateur a en italique suivie d'une expression entière valant i devant être comprise entre 1 et n. Et on utilise le méta-opérateur n en italique pour retourner sous forme d'un entier la taille de l'appel. Voici quelques exemples d'opérateurs construits dans la structure libre L :

 

 

 

Une somme de 1 correspond à un arbre binaire nu. Et un arbre binaire nu modulo l'associativité se ramène à un arbre aplati en une liste nue uniquement caractérisée par sa taille. Deux arbres nus sont donc égaux modulo l'associativité, si leur nombre de feuilles est le même.

Une forme normale peut être facilement définie en choisissant l'expression sous forme d'une liste lispienne de 1 qui se note 1+(1+(1+(1+...1)))...). Et nous pouvons alors identifier les nombres entiers comme suivant :

1 = 1
2 = 1+1
3 = 1+(1+1)
4 = 1+(1+(1+1))
....

Exemples pour la structure :

a, b,
a+a, a+b, b+a, b+b,
(a+a)+a, a+(a+a), (a+a)+b, b+(a+a),
(a+b)+a, a+(a+b), (a+b)+b, b+(a+b),
(b+a)+a, a+(b+a), (b+a)+b, b+(b+a),
(b+b)+a, a+(b+b), (b+b)+b, b+(b+b),
....

Un même élément peut avoir plusieurs expressions différentes tel que (a+b)+a = a+(b+a). Cela est dû à l'associativité qui introduit une relation d'équivalence sur la strutcture libre <a,b,+>.

Il existe une forme normale, et un algorithme capable de déterminer en un temps fini si deux expressions sont équivalentes ou non.

 

 

Défini par
constructeur d'application
Défini par
clause d'égalité
Appliqué à des exemples
H : (...)-->an
H(...) = an
H(a,b,c,f(a),f(b)) = f(b)
H(a,b) = b
M : (...)-->g(a1, an)
M(...) = g(a1, an)
M(a,b,c,f(a),f(b)) = g(f(b),a)
M(a,b) = g(b,a)

Délors on peut définir l'opérateur List comme l'opérateur (...)--> List(...) c'est à dire un opérateur d'arité variable supérieur à zéro qui n'a pas de définition autre que lui-même. Puis on convient d'une simplification syntaxique consistant à omettre le nom de l'opérateur List. Ainsi nous avons :

(a,b,c) = List(a,b,c)
(a) = List(a)
((a)) = List(List(a))
(a,(b,c)) = List(a, List(b,c))

Noter qu'il y a une ambiguité dans les listes à un seul argument, car les parenthèses peuvent dans ce cas signifier autre chose qu'une liste, elle peuvent signifier une priorité, qui ne doit pas être nécessaire car la priorité syntaxique de la virgule est posée comme la plus basse.

L'introduction de l'opérateur List dans le langage va augmenter considérablement son pouvoir d'expression. Considérons la structure libre <a, b, (...)> qui est engendrée par deux éléments a,b et par l'opérateur List d'arité variable supérieur à zéro. Les termes clos sont :

a,b,
(a),(b),
(a,a),(a,b),(a,(a)),(a,(b)),
(b,a),(b,b),(b,(a)),(b,(b)),
((a),a),((a),b),((a),(a)),((a),(b)),
((b),a),((b),b),((b),(a)),((b),(b)),
((a)),((b))
((a,a)),((a,b)),((a,(a))),((a,(b))),
((b,a)),((b,b)),((b,(a))),((b,(b))),
....

L'énumérateur n'est pas simple à formuler.

A partir de la structure = <a, b, +(.,.)> / { + associatif } on défini un opérateur d'arité variable de même nom + comme suit :

+(u1,u2,u3,u4...,un) = u1+(u2+(u3+(u4+...un)))...

C'est à dire formellement avec i comme variable entière, comme suit :

+ : (...) --> Run( i:=1, s:=a1, While (in) do (s:=ai+s, i:=i+1), Return s)

L'associativité de +(.,.) correspond à la séquentialité de +(...). La propriété de séquentialité, appliquée à un opérateur d'arité variable, c'est à dire pour une liste, se traduit par le fait qu'une liste de liste se ramènent en une liste aplatie. Le concept est simple à penser mais pas simple à écrire. Il convient de trouver un langage adapté pour programmer cette opération mécanique d'aplatissement de liste de listes. Les deux structures suivantes sont isomorphes :

<a, b, +(...)> / { + séquentiel }     -->     <a, b, +(.,.)> / { + associatif }
+(u1,u2,u3,u4...,un)                        -->     u1+(u2+(u3+(u4+...un)))...

La forme normale s'obtient en aplatissant la somme. La propriété de séquentialité permet d'implémenter l'opération de concaténation, qui réunie deux listes en une seul liste. Le concept est simple à penser mais pas simple à écrire. Il convient encore de trouver un langage adapté pour programmer cette opération mécanique de concaténation de listes. Les deux structures suivantes sont isomorphes :

<a, b, +(...)> / { + séquentiel }     -->     <a, b, *(.,.) > / { * est la concaténation }
+(u1,u2,u3,u4...,un)                        -->     u1u2u3u4...un

Les éléments distincts sont les mots distincts de {a,b}* - {ε}* est l'opérateur de Kleene et où ε représente le mot vide. Les éléments distincts sont alors énumérés comme suit :

a, b
aa, ab, ba, bb
aaa, aab, aba, abb, baa, bab, bba, bbb
aaaa, aaab, aaba, aabb, abaa, abab, abba, abbb, baaa, baab, baba, babb, bbaa, bbab, bbba, bbbb,
....

Remarquer que le qualificatif distinct est relatif à l'associativité. En effet, en théorie d'égalité on ne peut pas démontrer que deux éléments sont distincts. Parcontre, si on suppose que deux éléments sont distincts dans la structure libre, c'est à dire qu'ils possèdent deux expressions distinctes, deux constructions distinctes, alors il peut être possible de démontrer que pour une théorie d'égalité simple, ils sont dans des classes d'équivalences distinctes.

 

L'implémentation de H et de +(...) permet de manipuler que des éléments sous leur forme normale.

⓵ = <1, +(.,.)> / {+ associatif}
⓵ = <1, +(...)> / {+ séquentiel}
⓵ = <1, +(.,.) > / {+ est la concatenation}

----------

l'usage des mathématiques pour étudier les mathématiques fait que l'objet de l'étude sont les énoncées mathématique, autrement dit son langage et non directement ce qu'il désigne (s'il y a une distinction à faire). Tout est langage. Et seul ce qui nous intéresse son les objects qui peuvent être énoncé dans un langage, et dont l'énoncé constitue leur définition.

 

 

 

et ce morphisme est bijectif.

Nous devons donc maintenant trouver le langage adéquat pour programmer cet isomorphisme, et officialiser ce moyen de construction qu'est le produit cartésien de structures.

10) Structure nommée et ensemble sous-jacent

Une fois la structure définie, celle-ci peut être nommée par une lettre qui peut alors être utilisée pour exprimer différentes choses selon le contexte.

On généralise la notation par un indice i, désignant une arité, pour représenter l'ensemble des opérateurs d'arité i choisie pour construuire ls structure, ou bien pour représenter l'ensemble des opérateurs d'arité i constructible dans la structure. Ainsi dans notre exmple S nous avons :

S0 = {1+i}
S1= Ø
S2 = {+}
S3= Ø
....

ou selon le contexte :

S ou S0 est l'ensemble des élément constructible de la sructure,
S1 est l'ensemble des opérateurs unaires constructibles dans la structure S,
S2 représente l'ensemble des opérateurs binaires constructibles dans la structure S,
S3 représente l'ensemble des opérateurs ternaires constructibles dans la structure S,
....

L'élément 1+i appartient à S. La fonction x -> x + x + x appartient à S1. L'opération + qui désigne la fonction (x,y)->x+y appartient à S2. La fonction (x,y,z) -> x + y + z appartient à S3.

On retrouve la notation classique (S,+) avec l'ensemble sous-jacent de la structure muni de ses opérations (ici une seul) génératrices (de par ses propriétés) des autres opérations de la structure.

11) Le produit cartésien de structures

Etant donné deux structures A et B, on définie la structure produit A×B comme l'ensemble des couples d'opérateurs de même arité et opérant respectivement sur chaque composante. Le produit cartésien correspond exactement au calcul parallèle. Le calcul d'un terme se fait de façon parallèle pour chacune de ses composantes. Par exemple dans la structure (A,+)×(B,*) le terme (a,b)(+,*)(a',b') se développe en le terme (a+a', b*b'), et correspond exactement au calcul parallèle de a+a' et de b*b'.

Les éléments sont les couples (x,y)x est un élément constructible dans A, et où y est un élément constructible dans B. Les opérateur unaires sont les couples (f,g)f est un opérateur unaire constructible dans A et où g est un opérateur unaire constructible dans B. Les opérateur binaires sont les couples (+,*)+ est un opérateur binaire constructible dans A et où * est un opérateur binaire constructible dans B. Et ainsi de suite...

Si A est engendré par des opérateurs rangés selon leur arité A0∪A1∪A2... et B engendré par B0∪B1∪B2..., alors la structure produit A×B est engendrée par les couples d'opérateurs de même arité A0×B0 ∪ A1×B1∪ A2×B2... (l'opération × est posée prioritaire à ). Et nous avons (A×B)i = Ai×Bi.

Le contexte définie les symboles employés, il peut les renommer comme il le souhaite. Et il peut être judicieux d'utiliser un même symbôle pour désigner des opérateurs distincts opérant sur des domaines distincts. Il n'y a pas d'ambiguité si les domaines sont distincts. Pour deux opérateurs de même noms *, c'est à dire préalablement choisie. On met en oeuvre la simplification d'écriture (*,*) = * en appliquant le paradigme vectoriel distributif. L'opérateur * s'applique sur chaque composante, c'est à dire est distribué sur chaque composante (a,b)*(c,d) = (a*b,c*d). Dans la structure (A,*)×(B,*), le terme (a,b)(*,*)(a',b') se notera simplement (a,b)*(a',b'), et se développera en le terme (a*a', b*b'). La structure (A,*)×(B*) peut donc s'écrire en respectant le paradigme vectoriel distributif (A×B,*) * est l'opération étendue sur les deux domaines distincts A×A et B×B. D'une manière plus générale on peut nommer une opération (+,*) par un symbole . Nous avons alors • = (+,*). L'opérateur s'applique sur chaque composante, c'est à dire est distribué sur chaque composante (a,b)•(c,d) = (a•b,c•d). Dans la structure (A,+)×(B,*), le terme (a,b)(+,*)(a',b') se notera simplement (a,b)•(a',b'), et se développera en le terme (a•a', b•b') qui sera identique au terme (a+a', b*b'). La structure (A,+)×(B*) peut donc s'écrire en respectant le paradigme vectoriel distributif (A×B,•) est l'opération étendue sur les deux domaines distincts A×A et B×B.

---- 11 mai 2015 ----

 

 

/ {1*x=x, x*1=x}

<a,*(.,.)>×<b,*(.,.)> = <(a,1),(1,b),*(.,.)> / {1 est élément neutre pour *}

 

La fonction qui se traduit dans

(x,y)->(y,x)

 

 

à S2 car cette fonction est programmable reste à trouver le langage adéquat (associé à une implémentation mécanique) pour écrire ce programme.

 

 

 

 

 

 

Existe-t-il une forme normale ? cela veut dire existe-t-il un algorithme capable de transformer toutes expressions en une expression image, dite forme normale, qui soit unique pour chaque élément de S.... Unique pour chaque élément, certainement pas, puisqu'il est impossible de démontrer la non équivalence de deux expressions (au cas où l'arithmétique est contradictoire, toutes les expressions sont équivalentes). Mais on peut affiner et trouver une représentation où de nombreuses expressions équivalentes sont représentés par la même expressions image. Mais si deux éléments ne sont pas équivalent, ils doivent avoir une représentation image différente. Il s'agit d'un morphisme mécanique. Le morphisme est qualifié de mécanique car l'image d'une expression est obtenue en exécutant un algorithme..

 

 

Si deux expressions sont équivalentes, alors l'énumérateur de la théorie de S finira par le dire. Parcontre si elles ne sont pas équivalentes, il n'y a pas toujours d'algorithme capable de confirmer cela de façon certaine. Mais ici la structure n'étant pas assez sophistiquée pour contenir l'arithmétique

 

<1, i, +> --> <0,1,+> × <0,1,+>
       1     -->   (1,0)
        i     -->   (0,1)
      1+1  --> (1+1,0)

 

 

 

Il existe pour chaque exemple une forme normale et une forme normale factorisée :

Structure
Exemple
Forme normale
Forme normale factorisée
L
g(h(w),u)...
g(h(w),u)
g(h(w),u)
(1+1)+(1+1)...
((1+1)+1)+1
4
(a*((a*b)*(b*a)))*b
((((a*a)*b)*b)*a)*b
a2*b2*a*b
S
1+(i+((i+1)+i)
(1+1)+((i+i)+i)
2+3i
G
(a*((a*b-1)*(b-1*a)))*b
((((a*a)*b-1)*b-1)*a)*b
a2*b-2*a*b

Lorsque l'opération est associative, on peut enlever les parenthèses, et si c'est le même élément qui est combiné plusieurs fois, alors on le désigne par la nombre de fois qu'il est combiné. C'est ainsi que l'on obtient la forme normale factorisée.

Le langage se perfectionne. Pour une opération binaire associative, + ou * selon la notation additive ou multiplicative, la combinaison de cette opération et remplacé par une opération de même nom mais d'arité arbitrairement agrandit. Exemple +(.,+(.,+(.,.))) = +(.,.,.,.), autrement dit x+(y+(z+t)) = x+y+z+t = +(x,y,z,t). Et si l'opération + est commutative, on utilisera les notations +{.,.,.,.}, +{x,y,z,t}.

Un élément quelconque x combiné n fois par l'opération, se notera de façon factorisée par nx ou xn. Exemple : 4x pour x+x+x+x ou x4 pour x*x*x*x.

Existe-t-il une méthode générale permettant de calculer une forme normale pour chaque structure à partir de sa présentation ? Il est trop tôt pour répondre à cette question.

 

On sépare question de la cohérence, de la réunion des structures proprement dite. Pour cela, on commence par effectuer la réunion des structures en considérants tous leurs opérateurs générateurs comme différents. Puis on ajoute à la théorie les égalités d'opérateurs souhaitées, ce qui peut alors entrainer une incohérence.