On s'intéresse à la structure des entiers naturels, et au concept d'infini potentiel qu'elle porte. Mais nous n'allons pas rentrer dans le vif du sujet tout-de-suite. On commencera par décrire des objets plus généraux, que sont les structures de type fini, c'est à dire engendrées par un nombre fini d'opérateurs générateurs d'arité fixe.
L'étude de ces structures fait partie des fondements de l'informatique. Le procédé d'engendrement de la structure constitue un programme écrit dans un langage augmenté des opérateurs générateurs de la structure.
On parcourera la voie tracée par Giuseppe Peano (1858 Coni - 1932 Cavoretto, près de Turin), mathématicien du Royaume d'Italie, qui développa une axiomatisation de l'arithmétique. Et nous explorerons à tâtons d'autres voies, décrivant les structures de type fini d'un point de vue informatique.
Le principal frein au développement de ces recherches reste causé par les nombreux préjugés, dont pour la plus part nous n'avons pas conscience, qui sont ancrés en nous plus ou moins profondément, et qui nous mettent des oeillères, et dont nous sommes incapables de nous en défaire dans la vie quotidienne.
À partir d'un ensemble d'opérateurs générateurs libres d'arité fixe, appelé présentation ou langage `L`, on définit l'ensemble des arbres engendrés par `L`, noté `"<"L">"` en entourant de crochets `"<"...">"` la séquence d'opérateurs générateurs et/ou d'ensembles d'opérateurs générateurs. Par exemple :
`"<"a,f"(.)",g"(.,.)>"= {a,f(a), g(a,a), f(f(a)),g(a,f(a)),g(f(a),f(a)),f(g(a,a)),...}`
Les opérateurs générateurs libres servent de brique de construction, tels des legos qui s'emboitent les uns dans les autres. Seul compte leur arité que l'on déclare dans leur première apparition à l'aide d'un suffixe, `"(.)"` pour désigner un opérateur unaire, `"(.,.)"` pour désigner un opérateur binaire, `"(.,.,.)"` pour désigner un opérateur ternaire, etc., ou par absence de suffixe pour désigner un élément. Ils sont nouveaux car ils ne désignent pas d'opérateur préexistant. Et ils sont libres dans le sens que, l'ensemble commun dans lequel ils sont définis correspond au domaine de Herbrand c'est-à-dire à un ensemble qu'ils engendrent eux-même. C'est le principe de l'infini potentiel général, qui est à la base du principe de récurrence général. Jacques Herbrand (1908 Paris - La Bérarde en Oisans 1931), mathématicien et logicien français, démontre en 1930 le théorème qui porte son nom et qui décrit le domaine de Herbrand.
Les opérateurs libres se définissent par eux-même. C'est-à-dire qu'ils produisent des éléments correspondant à l'expression même de la composition qu'ils mettent en oeuvre :
`a=(|->a)`
`f=(x|->f(x))`
`g=((x,y)|->g(x,y))`
On considère donc qu'il y a une représentation brute des éléments sous forme de composition close finie d'opérateurs générateurs appelée terme ou arbre. On appelle valeur cette représentation brute. Ainsi l'élément `a` a pour valeur le terme `a`. L'application de `f` sur un élément `x` a pour valeur le terme `f(x)` où l'on a remplaçé `x` par sa valeur. L'application de `g` sur `x` et `y` a pour valeur le terme `g(x,y)` où l'on a remplaçé `x` et `y` par leur valeur respective. Délors il est possible de les appliquer à tout élément qui est identifié par sa valeur. On adopte la notation des opérateurs étendus aux ensembles, faisant que, si `A` et `B` sont des ensembles d'éléments identifiés par leur valeur, nous avons :
`f(A) = {f(x) "/" x "∈" A}`
`g(A,B) = {g(x,y) "/" x "∈" A, y "∈" B}`
Le langage `L={a,f,g}` définit la structure libre notée `"<"L">"`. Le rappel des arités des opérateurs en adjoignant à leur nom les suffixent `"(.)"`, `"(.,.)"`, `...` est facultatif si celles-ci ont déjà été définies. Les structures libres de type fini sont caractérisées à isomorphisme près par la signature de leur langage. C'est le nombre d'opérateurs générateurs pour chaque arité et que l'on présente sous forme de liste. Dans notre exemple, la signature du langage `L` est `(1,1,1)` car il y a `1` opérateur nullaire, `1` opérateur unaire et `1` opérateur binaire.
` f_1"(.)",f_2"(.)",..., f_m"(.)>"`
`f_1"(.)",f_2"(.)",...,f_m"(.)",`
` g_1"(.,.)",g_2"(.,.)",...,g_r"(.,.)>"`
`m` types de noeud à un fils et `r` types de noeud à deux fils.
Les structures ainsi engendrées, comprenant une infinité d'éléments, matérialisent le concept d'infini potentiel général, une matérialisation contestable car pour se faire il faut se placer à la fin des temps. Elles sont décrites par leur procédé d'engendrement qui sont des programmes, de taille finie par principe, écrit dans un langage augmenté des opérateurs générateurs de la structure.
Le langage de programmation s'adapte en fonction de ce que l'on veut résoudre. On le perfectionne en utilisant la technique des grammaires. On utilise pour cela des symboles non-terminaux qui sont autant de nouveaux éléments libres, et cela correspond à une extension élémentaire ajoutant ces symboles comme de nouveaux éléments libres. Les termes non-terminaux sont des compositions close finie d'opérateurs générateurs et de symbole non-terminaux comprenant au moins un symbole non-terminaux. Les termes terminaux sont des compositions close finie d'opérateurs générateurs ne comprenant aucun symbole non-terminaux.
La définition d'une grammaire se fait à l'aide du meta-opérateur `"↣"` qui prend comme premier argument, un symbole non-terminal et comme second argument, un ensemble de termes terminaux ou non-terminaux. Considérons par exemple la grammaire `R` qui engendre la structure libre `R="<"a,f,g">"`.
`R"↣"{a,f(R),g(R,R)}`
Cette grammaire signifie que chaque occurrence du terme brut `R` peut être substitué par les termes brutes `a` ou `f(R)` ou `g(R,R)`. Le programme associé à cette grammaire va engendrer un ensemble de termes terminaux et non-terminaux en partant du seul terme `R`, mais seul les termes terminaux seront proposés comme résultat pour l'extérieur.
Le symbole `R` est identifié à la fois comme la grammaire proprement dite, comme le symbole d'entrée de la grammaire, comme l'ensemble des termes (terminaux et non-terminaux) qu'elle produit, et comme l'ensemble des éléments (que sont les seuls termes terminaux) qu'elle produit. Et c'est le contexte qui détermine le rôle. L'ensemble des éléments engendrés par la grammaire `R` est :
`R={a,f(a), g(a,a), f(f(a)),g(a,f(a)),g(f(a),f(a)),f(g(a,a)),...}`
Voici une autre façon de programmer l'engendrement des éléments de `E="<"a,f,g>"` :
L'avantage de se second procédé et que les termes produits sont évalués en même temps, faisant que la méthode s'applique d'une manière plus générale pour des opérateurs générateurs non nécessairement libres.`E := {}`
répéter tant que `a"∉"E` ou `f(E)"⊈"E` ou `g(E,E)"⊈"E`
`| E:= E uu {a} uu f(E) uu g(E,E)`
La notation classique déclare une structure de manière plus générale, par un ensemble muni d'opérateurs internes c'est-à-dire définis dans cet ensemble. Ces opérateurs constituent le langage de la structure. Considérons l'exemple suivante :
` (A, a,f"(.)",g"(.,.)")`
Cette déclaration signifie exactement :
`a in A`
`f in (A->A)`
`g in (A^2->A)``ccL(A)={a,f,g}`
Où le méta-opérateur `ccL` appliqué à la structure `A` retourne son langage. La structure `A` est l'ensemble `A` muni du langage `{a,f,g}`. Par défaut, le même nom est utilisé pour désigner la structure et l'ensemble, laissant au mécanisme d'inférence de type, le soin de déterminer le type de la variable, à savoir si c'est un ensemble ou une structure. L'ensemble `A` est aussi appelé l'ensemble sous-jacent de la structure `A`.
Le langage de la structure est `{a,f,g}` de type `(1,1,1)`. Et dans le cas général, les éléments calculables par composition close finie d'opérateurs du langage ne forment qu'une partie de l'ensemble sous-jacent.
`"<"a,f"(.)",g"(.,.)>"⊆A`
L'extension élémentaire généralise le concept de structure libre, en permettant d'ajouter de nouveaux opérateurs libres à une structure quelconque, et ainsi de l'agrandire librement sans contrainte d'aucune sorte.
Reprenons l'exemple de la structure ` (A, a,f"(.)",g"(.,.)")` de langage de type `(1,1,1)`. Et ajoutons lui trois nouveaux opérateurs libres `b, u"(.)", v"(.,.)"`. On obtient une structure plus grande, dite structure étendue, notée en adjoingnant à `A` la liste entre crochet droit `[...]` des opérateurs ajoutés, après les avoir déclaré comme étant libres :
`b=(|->b)`
`u=(x|->u(x))`
`v=((x,y)|->v(x,y))``A[b, u, v]`
Cette structures possède donc un ensemble sous-jacent, désigné par défaut par le même nom que la structure `A[b, u, v]`, et qui est plus grand que `A` :
`A[b,u,v]= A"+"N `
Le signe `"+"` entre deux ensembles désigne l'union disjointe. L'ensemble `N` regroupe tous les nouveaux éléments engendrés par l'extension élémentaire, et voici ce qu'il contient :
Ce processus d'engendrement se décrit facilement à l'aide d'une grammaire comme suit :
`R=A[b, u, v] `
`R"↣"{A,N}`
`N"↣"{b, u(R),v(R,R),f(N),g(A,N),g(N,A),g(N,N)}`
Chaque symbole `A,N,R` désigne à la fois une grammaire et l'ensemble des éléments qu'elle engendre. Le symbole `A` désigne une grammaire générant les éléments de la structure `A`. Le symbole `N` désigne une grammaire générant les éléments de la structure `A[b, u, v]` qui n'appartiennent pas à `A`. Le symbole `R` désigne une grammaire générant les éléments de la structure `A[b, u, v]`.
On a simplement retiré du processus d'engendrement, les ensembles `f(A)` et `g(A,A)` qui produisent des éléments de `A` déjà pris en compte.
La grammaire d'un ensemble `A` est notée implicitement `A"↣"{A}`, où le symbole `A` dans le second membre `{A}` est remplacé par la séquence de ses éléments. Et lorsque `A` est de cardinalité infinie, la séquence des éléments de `A` devient transfinie, et les algorithmes qui traitent ces séquences doivent itérer un nombre de fois transfini. Leurs existences nécessitent alors l'axiome du choix et l'existence du bon ordre.
Le langage de la structure `A` est `{a,f,g}` de type `(1,1,1)`.
Le langage de la structure `A[b,u,v]` est `{a,b,f,u,g,v}` de type `(2,2,2)`.
Les éléments de la structure étendue correspondent exactement aux termes produit par la grammaire `R`. Et deux termes distincts désignent nécessairement deux éléments distincts car les opérateurs générateurs qui composent ces termes que sont `{A,b,u,v}` sont définis comme étant libre.
On peut déclarer une structure libre `E` de langage `L={a, f"(.)", "g(.,.)"}` comme une extension élémentaire par l'ajout d'opérateurs libres à partir de la structure vide notée `Ø` et du symbole d'extension élémentaire `[...]`. La structure libre se note alors `E=Ø[a,f,g]`, mais il est toujours nécessaire de préciser que `a,f,g` sont des opérateurs libres.
Il existe deux mécanismes pour diviser une structure sans changer son langage, que sont la division par une théorie et la division par un morphisme.
Etant donné une structure `(E, a, f"(.)", g"(.,.)")` et une théorie `T` qui tranche complètement l'égalité entre éléments de `E` c'est-à-dire vérifiant :
`AA(x,y)"∈"E^2, (T|-- x"="y) "ou" (T|-- x"≠"y)`
Alors la théorie `T` définit dans la structure `E`, une relation d'équivalence notée `"≃"` comme suit :
`AA(x,y)"∈"E^2, (x"≃"y) <=> (T=>x"="y)`
Et cette relation d'équivalence respecte nécessairement les opérateurs générateurs, c'est-à-dire :
`AAxAAyAAx’AAy’`
`x"≃"y => f(x)"≃"f(y)`
`x"≃"y "et" x’"≃"y’ => g(x,x’)"≃"g(y,y’)`
En effet, si `x"≃"y` cela signifie que `T=> x"="y` et donc `T=> f(x)"="f(y)` et donc `f(x)"≃"f(y)`. Et de même pour les opérateurs générateurs d'arité supérieur. Ce respect des opérateurs est garanti par la propriété fondamentale du prédicat d'égalité dans la logique.
Dés lors, la structure `E` peut être divisée par cette relation d'équivalence. Les éléments d'une même classe d'équivalence sont regroupés en un seul élément dans la structure quotient notée `E"/≃"` ou notée directement `E"/"T`.
La théorie `T` définissant la relation d'équivalence comme une égalité, l'adoption de `T` transforme de faite la structure `E` en la structure `E"/"T` sans qu'il y ait besoin de renommer quoi que ce soit. L'adoption de `T` représente une restriction de la structure, c'est à dire l'ajout à la structure d'une théorie, et correspond à l'opération de quotientage passant de la structure `E` à la structure `E"/"T`.
6) Théorie des modèles
Etant donnée une théorie `P` qui est tranchée complétement par toutes structure `E` de langage `{a,f(.),g(.,.,)}`, c'est à dire tel que :
`(E|==P) "ou" (E|=="¬"P)`
--- 17 mai 2022 ---
Considérons une proposition `P` d'égalité entre des éléments de `E`. Alors la proposition `T"⇒" P` désignera une proposition d'égalité entre des éléments de la structure `E"/"T`. La proposition `T"⇒" P` s'appellera la proposition `P` modulo `T`. Ainsi l'égalité de deux classes d'équivalences se traduit en l'égalité modulo `T` de deux éléments de `E`. Quelque soit `x` et `y`, les trois assertions suivantes sont équivalentes :
`T"⇒" ((x,y)"∈"E^2 "et" x"="y)`
`((x,y)"∈"E^2 "et" x"="y)` modulo `T`
`(x,y)"∈"(E"/"T)^2 "et" x"="y`
Les classes d'équivalence se définissent comme suit :
`AAx "∈" E,`
`(x mod T) = {z "/" T|-- z "="x}`
`(x mod T) in E"/"T`
Et une définition analogue existe pour les opérateurs non-nullaires :
`AAf "∈" (E->E),`
`(f mod T) = ((x mod T)|->(f(x) mod T))`
`(f mod T) in (E"/"T->E"/"T)``AAg "∈" (E"×"E->E),`
`(g mod T) = ((x mod T, y mod T)|->(g(x,y) mod T))`
`(g mod T) in ((E"/"T)"×"(E"/"T)->E"/"T)`
Etant donné une classe d'équivalence `u` :
`u in E"/"T`
`u= {x "/" x "∈" u}`
On utilise la notation étendue des fonctions aux ensembles. La fonction `f` appliqué à un ensemble `u` inclus dans `E`, produit l'ensemble suivant :
`f(u) = {f(x) "/" x "∈" u}`
Si `a` et `b` appartiennent à `f(u)` alors il existe `x` et `y` appartenant à `u` tels que `a"="f(x)` et `b"="f(y)`. Les éléments `x` et `y` étant dans une même classe, on a `x"≃"y` c'est-à-dire `T|--x"="y` et donc `T|--f(x)"="f(y)` et donc `T|--a"="b` c'est-à-dire `a"≃"b`. On en conclut que `f(u)` forme bien une classe d'équivalence :
`f(u) in E"/"T`
De même, la fonction `g` appliqué à deux ensemble `u,v` inclus dans `E`, produit l'ensemble suivant :
`g(u,v) = {g(x,y) "/" x "∈" u, y "∈" v}`
Si `a` et `b` appartiennent à `g(u,v)` alors il existe `x_1,y_1` appartenant à `u` et `x_2,y_2` appartenant à `v` tels que `a"="g(x_1,x_2)` et `b"="f(y_1,y_2)`. Les éléments `x_1` et `x_2` étant dans la même classe `u`, on a `x_1"≃"x_2` c'est-à-dire `T|--x_1"="x_2`, et les éléments `y_1` et `y_2` étant dans une même classe `v`, on a `y_1"≃"y_2` c'est-à-dire `T|--y_1"="y_2` et donc `T|--g(x_1,x_2)"="g(y_1,y_2)` et donc `T|--a"="b` c'est-à-dire `a"≃"b`. On en conclut que `g(u,v)` forme bien une classe d'équivalence :
`g(u,v) in E"/"T`
La structure quotient peut donc se déclarer comme suit:
`(E"/"T, a mod T, f, g)`
Où les opérateurs `f` et `g` s'appliquent de façon étendue aux classes de `E"/"T` pour produire des calsses de `E"/"T`.
On reprend la division de `E` par `T`, et on définit l'application `varphi` permettant de passer de l'élément à sa classe, c'est à dire de passer de `x` à `x mod T` :
`varphi in (E->E"/"T)`
`varphi(x) = x mod T`
`varphi(x) = {y "/" T|--x"="y} `
L'application `varphi` est un morphisme surjectif de `(E,a,f,g)` vers `(E"/"T, a mod T,f,g)`, c'est-à-dire :
`AAxAAyAAx’AAy’`
`varphi(a) = a mod T`
`varphi(f(x)) = f(varphi(x))`
`varphi(g(x,y)) = g(varphi(x), varphi(y))`
Il existe une dualité entre `T` est `varphi` :
`varphi(E)=E/T`
`AAx "∈" E, varphi(x) = x mod T`
On a diviser une structure `E` par une théorie `T` tranchant l'égalité entre éléments de `E` ce qui nous à permis de définir le morphisme surjectif `varphi`, divisant pareillement la structure. Réciproquement, étant donné un morphisme surjectif `varphi` de `(E, a, f, g)->(E’, a’, f’, g’)` c'est-à-dire :
`AA(x,y) in E,`
`varphi(a) = a’`
`varphi(f(x)) = f’(varphi(x))`
`varphi(g(x,y)) = g’(varphi(x), varphi(y))`
Le morphisme est soit injectif auquel cas il dénote un isomorphisme, ou soit il n'est pas injectif et il existe au moins deux éléments distincts `x,y` tels que `varphi(x)"="varphi(y)`. Et dans ce cas, `varphi` définit une relation d'équivalence non trivial qui respecte les opérateurs générateurs comme suit :
`AA(x,y)"∈E"^2, (x"≃"y) <=> (varphi(x)"="varphi(y))`
On a diviser une structure `E` par un morphisme `varphi` ce qui nous permet de définir la théorie `T`, divisant pareillement la structure.
`T <=> (AAxAAy, varphi(x)"="varphi(y) <=> x"="y)`
Une structure `E` peut être agrandie en `F` par l'ajout d'opérateurs, et réduite en `G` par l'ajout d'une théorie. Le premier niveau d'implémentation formalise une telle extension suivi d'un tel quotientage.
On part d'une structure `E` engendrée par le langage `L_0`.
`E = "<"L_0>`
Puis on procède à l'extension de la structure `E` en ajoutant un ensemble de nouveaux opérateurs `L1` apriori non-libres pour engendrer une structure `F` plus vaste que `E` avec un ensemble sous-jacent plus vaste et un langage plus vaste. Pour définir ces nouveaux opérateurs, il est nécessaire de se placer dans une structure plus vaste indéterminée notée `(W,L_0,L_1)`.
`F = "<"L_0, L_1">"`
Cette proposition constitue la théorie d'engendrement de la structure `F`. Notez que les opérateurs de `L_1` ne sont apriori pas libres, c'est pourquoi on les définit dans une structure plus vaste indéterminée `W`.
Puis on restreint la structure `F` en ne considérant que celle satisfaisant une théorie `T` tranchant l'égalité entre éléments de `F`, c'est à dire satisfaisant :
`AA(x,y)"∈"F^2, (T|-- x"="y) "ou" (T|-- x"≠"y)`
Le langage étendue `L_0uuL_1` regroupe les opérateurs générateurs qui engendre la structure `F`, tandis que la théorie `T` définit dans la structure `F` une relation d'équivalence `"≃"` comme suit :
`AA(x,y)"∈"F^2, (x"≃"y) <=> (T|-- x"="y)`
La structure quotient obtenue, noté `G`, qui regroupe les classes d'équivalence se note `G=F"/≃"` ou directement :
`G=F"/"T`
La structure `G` possède le langage `L_0 uu L_1` où les opérateurs nullaires sont considérés modulo `T`, et les opérateurs non-nullaires s'appliquent à des ensembles (que sont les classes d'équivalences) selon la notation des fonctions étendue aux ensembles.
La structure `G` possède trois théories :
--- 15 mai 2022 ---
On adopte la notation impérative, l'instruction d'affectation `:=` qui permet de redéfinir une variable. Par exemple, considérons la déclaration suivante :
`E:="<"a,f,g">"`
Cette déclaration redéfinie la structure `E` comme étant engendrée par les opérateurs `a,f,g` définis dans la structure initiale `E`. La représentation d'un élément de `E` se fait par un terme de la strutcture libre `"<"A,F"(.)",G"(.,.)>"`. Et pour savoir si deux éléments `x,y` de `E` sont égaux, il faut évaluer les deux termes en remplaçant `A` par `a`, `F` par `f` et `G` par `g`, pour calculer deux termes dans la structure initiale `E` et reposer la question de leur égalité dans cette structure initiale.
Dans notre paradigme, une structure de type fini possèdent trois théories, sa théorie d'engendrement, sa théorie intérieur du premier ordre, et la conjonction des deux qui est identifiable à la strucure elle-même.
Considérons des opérateurs `{a,f"(.)",g"(.,.)"}` agissant sur un ensemble `E`, c'est à dire de type `E` ou `E"→"E` ou `E^2"→"E`..., ou `E^n"→"E`. Ainsi, dans l'exemple, `a` est un élément de `E`, `f` est une application unaire de `E"→"E`, et `g` est une application binaire de `E^2"→"E`.
On s'intéresse à l'ensemble des éléments de `E` qu'il est possibles d'obtenir par composition closes finie d'opérateurs générateurs `a, f"(.)", g"(.,.)"`, et qui est appelé la cloture par composition close finie. On note cette cloture en entourant les opérateurs générateurs ou ensembles d'opérateurs générateurs par des crochets `"<"a,f,g">"`.
`"<"a,f,g">" = {a,f(a), g(a,a), f(f(a)),g(a,f(a)),g(f(a),f(a)),f(g(a,a)),...}`
Si `E` est engendré par `{a,f"(.)",g"(.,.)"}`, ce qui se note `E="<"a,f,g">"`. Alors cela crée une nouvelle notation des éléments de `E`. Un élement `x` appartenant à `E` pourra toujours être désigné par une composition close finie d'opérateurs générateurs, qui en logique polonaise se traduit en une chaine d'opérateurs tel que par exemple : `g(f(a),g(a,a)) = 'gfagaa'`. La chaine d'opérateur est déclarée entre quote. Puis l'ensemble `E` étant lui-même déjà une structure de type fini, il propose déjà une représentation de ses éléments. Il y aura donc au moins deux niveau de représentation des éléments.
---- 8 mai ----
possédera une représentation initiale
Les entiers naturels `bbbN` sont engendrés par deux opérateurs générateurs `{0, s"(.)"}` où `s` est l'opérateur d'incrémentation : `s= (x"↦"x"+"1)`. Dans cette définition, les opérateurs `{0,1,+}` sont préalablement définis par la structure des entiers naturels posée comme une strate logiciel de base. En reformulant la définition de structure `bbbN`, on masquera cette strate logiciel de base par une structure de même ensemble sous-jacent mais ne possèdant que deux opérateurs générateurs :
`bbbN="<"0, s"(.)>"`
Cette structure correspond à la l'expression des entiers sont forme de termes de `"<"0,s"(.)>"` sont appelés des entiers sous forme de batons. Par exemple `s^4(e) = s(s(s(s(e))))` que l'on note en logique polonaise par `sssse`. La complexité de ce terme est le nombre d'opérateurs non-nullaires qu'il met en jeu pour effectuer le calcul. Dans cet exemple, la complexité est `4`. La complexité d'un entier `n` écrit sous forme de batons est de complexité `n`.
Mais comment spécifier logiquement que la structure est libre ?
Les entiers naturels `bbbN` peuvent être engendrés par deux opérateurs générateurs `{0, s"(.)"}` comme une structure libre où `s(x)` désigne le successeur de `x`, où `s` est appelé l'opérateur d'incrémentation. Mais comment spécifier logiquement que la structure est libre ?
Considérons une structure `E` engendrés par deux opérateurs générateurs `{e, s"(.)"}` :
`E = "<"e,s"(.)>"`
La théorie d'engendrement n'est pas une théorie du premier ordre. Elle se décrit comme un processus récurcif construisant `E`, et donc comme un programme récurcif produisant petit à petit tous les éléments de `E`. Autrement dit, quelques soit un élément de `E`, celui-ci sera produit en un temps fini par le programme.
`E:={}`
`x:=e`
tant que `x"∉"E`
`| E:=E "+" {x}`
`| x:=s(x)`
Le symbole `:=` signifie une affectation. Ainsi, l'instruction `E:={}` initialise la variable `E` en la mettant égale à l'ensemble vide. L'instruction `x:=e` initialise la variable `x` en la mettant égale à l'élément `e`. L'instruction tant que `x"∉"E` va exécuter le bloc constitué des deux instructions suivantes tant que `x"∉"E`. L'instruction `E:=E "+" {x}` va modifier la variable `E` qui est un ensemble en lui ajoutant l'élément `x`. Le symbole `"+"` entre deux ensembles désigne l'union disjointe.
L'énumération étant particulièrement simple, nous avons :
`E = {e,s(e),s^2(e),...,s^n(e),...}`
Et en prenant comme convention que `s^0"=id"`, nous avons :
`E = uuu_(i in NN) s^i(e)`
Il existe donc un morphisme surjectif de `NN "→" E` qui est `i"↦"s^i(e)`. C'est un morphisme car la fonction d'incrémentation `x"↦"x"+"1` dans `NN` est transporté par ce morphisne en la fontion d'incrémentation `s` dans `E` comme on peut le voir ici : `i"+"1"↦"s(s^i(e))`. Et il est surjectif car tous les éléments de `E` sont ainsi désignés. On adopte cette désignation, faisant que par exemple, un élément supposé de `E` dont l'expression est `7`, désignera l'élément `s^7(e)`.
Deux cas peuvent se produire : Soit le programme va énumérer des éléments toujours nouveaux de `E` et ne s'arrètera jamais auquel cas la structure `E` sera isomorphe à la structure `bbbN`. Sinon il produira à un moment donné un élément appartenant déja à `E` et s'arrêtera. On obtient alors une structure de poêle, se traduisant par l'équivalence entre deux entiers distincts `m">"n`, notée `P_(m=n)` :
`P_(m=n) = ("<"e,s"(.)>")/{s^m(e)"="s^n(e)}`
Un élément `y` de `E` est appelé un antécédent de `x` si et seulement si `s(y)"="x`. On remarquera que l'élément de `E` désigné par l'entier `n` est le seul élément à possède deux antécédents distincts, qui sont `m"-"1` et `n"-"1`.
Dans notre paradigme, une structure de type fini possèdent trois théories, sa théorie d'engendrement, sa théorie intérieur du premier ordre, et la conjonction des deux qui est identifiable à la strucure elle-même.
Si nous ajoutons dans la théorie de la structure `E` la clause que l'opérateur `s "∈" E"→"E` doit être injectif, c'est à dire que les éléments de `E` ne peuvent avoir soit aucun ou un seul antécédent selon `s`. Cela restreint les possibilités. Seul deux cas peuvent se produirent : Soit le programme va énumérer des éléments toujours nouveaux de `E` et ne s'arrètera jamais auquel cas la structure `E` sera isomorphe à la structure `bbbN`, sinon il produira à un moment donné un éléments appartenant déja à `E` mais qui n'a pas encore d'antécédent c'est-à-dire l'élélement `e`, et s'arrêtera. On obtient alors une structure cyclique, se traduisant par l'équivalence entre un entier `m` et `0`, notée `P_(m=0)`, et qui est notée `C_m`.
`E = ("<"e,s"(.)>")/{s(x) "≠" s(y) "ou" x"="y}`
Notez que toute nouvelle variable apparaissant au dénominateur est implicitement quantifiée universellement sur `E`.
Quelle clause, écrite dans la logique du premier ordre, faut-il ajouter à la théorie pour s'assurer que `E` n'est pas cyclique ? On ajoute simplement l'interdiction pour l'élément générateur `e` d'avoir un antécédent. La structure des entiers naturels peut donc se définir par une structure à deux opérateurs générateurs :
`E = ("<"e,s"(.)>")/{((s(x) "≠" s(y) "ou" x"="y),(s(x)"≠"e))}`
La structure `E` définie une représentation particulière des entiers naturels.
Une autre façon de procéder pour évincer les structures poêliques ou cycliques consiste à introduire une relation d'ordre satisfaisant :
`AAx, x"⩽"s(x)`
On agrandit ainsi le langage de la structure en ajoutant un prédicat binaire, qui servira de relation d'ordre.
Avec l'ajout de prédicat, différente conception de structures apparaissent. Les structures dite constructives impose que leur prédicats doivent être calculable. Un programme doit pouvoir construire le prédicats n-aire c'est à dire calculer sa valeur booléenne pour chaque n-uplet d'élément de la structure, ou autrement dit, doit pouvoir énumérer tous les n-uplet d'éléments satisfaisant le prédicat, et un autre programme doit pouvoir énumérer tous les n-uplet d'éléments ne satisfaisant pas le prédicat.
Dans notre exemple, le calcul du prédicat `"⩽(.,.)"` se fait en calculant l'ensemble `R_0` des couples ne le satisfaisant pas, et en calculant l'ensemble `R_1` des couples le satisfaisant. Et ce calcul se fait en même temps que l'énumération des éléments de `E`.
`E:={}`
`R_0:={}`
`R_1:={}`
`x:=e`
tant que `x"∉"E`
`| R_0:=R_0 + {(x, u) "/" u "∈" E}`
`| E:=E + {x}`
`| R_1:=R_1 + {(u,x) "/" u "∈" E}`
`| x:=s(x)`
Avec la définition limite `R_0"="{(x,y) "/" x">"y}` et `R_1"="{(x,y) "/" x"⩽"y}`.
On note les prédicats ajoutée à une structure de type finie en les regroupant en un ensemble à droite de la structure libre et en précisant leur arité, proposant ainsi une composition en notation française, un prédicat parmi l'ensemble des prédicats, prenant comme arguments des termes parmi l'ensemble des termes placès à sa gauche. La structure des entiers naturels peut donc se définir par une structure à deux opérateurs générateurs et à un prédicat binaire :
`E = ("<"0, s"(.)>" {"⩽(.,.)"})/ ( ((x"⩽"s(x)),(x"⩽"x),(x"⩽"y "et" y "⩽"x => x"="y),(x"⩽"y "et" y "⩽"z => x"⩽"z))`
La structure `E` définie la même représentation des entiers naturels que celle précédente, mais avec un langage enrichie d'une relation ordre canonique.
Les entiers `NN` écrit sous forme de termes de `"<"e,s"(.)>"` sont appelés des entiers sous forme de batons. Par exemple `s^4(e) = s(s(s(s(e))))` que l'on note en logique polonaise par `sssse`. La complexité de ce terme est le nombre d'opérateurs non-nullaires qu'il met en jeu pour effectuer le calcul. Dans cet exemple, la complexité est `4`. La complexité d'un entier `n` écrit sous forme de batons est de complexité `n`.
La fonction de décrémentaion noté `d"(.)"` n'est pas défini pour `e`. Cette particularité complique l'écriture en interdisant l'écriture `d(e)`. On préfère autoriser toutes les écritures et compléter la structure par un méta élément `"FAIL"`. Ainsi nous avons :
`d(e) = "FAIL"`
`d("FAIL") = "FAIL"`
`s("FAIL") ="FAIL"`
On définie la fonction de décrémentation `d"(.)" comme suit : `d(e)="FAIL"`, et `AAx, d(s(x))"="x`. La définition `AAx, d(s(x))"="x` permet de programmer directement `d`, car les entiers sonts exprimés par des termes de `"<"e,s"(.)>"` qui sont des succesions de `s` se terminant par `e`, et qui s'appelle l'écriture baton des entiers.
Le programme `d` consiste à enlever un `s` à la forme baton de l'entier passé en argument. Cela se note par un programme de la forme tête`"→"`corps où la tête est une forme d'appel de fonction et où le corps est le résultat de la fonction :
`d(s(x))"→"x`
Ce programme `d` appliqué à l'entier exprimé par `s(s(s(e)))` va unifier l'appel fonctionnelle avec sa tête `d(s(s(s(e)))) ∿ d(s(x))` ce qui affectera `x:=s(s(e))`. Puis le programme `d` retournera son corps `x` c'est à dire `s(s(e))`. Et si au départ l'unification échoue, le programme retournera `"FAIL"`.
On définie récurcivement la fonction d'addition `"+(.,.)"` de syntaxe centrée, comme suit.
`x"+"s(x) -> s(x)"+"x`
`x"+"e->x`
La complexité d'un calcul est le nombre d'appel à un programme. La complexité du calcul `m"+"n` est de l'ordre de n.
On définie récurcivement la fonction de multiplication `"*(.,.)"` de syntaxe centrée et de priorité supérieure à celle de `"+"`, comme suit :
`s(x)"*"x ->x"*"x"+"x`
`s(e)"*"x->x`
`e"*"x->e`
La complexité du calcul `m"*"n est de l'ordre de `mn`.
On définie une écriture des entiers en base 2 comme suit : On note
`0"="e`
`1"="s(0)`
Puis on définit la composition `"°"` comme suit : `x"°"y = x"+"x"+"y`. On remarquera que l'opérateur `"°"` est associatif. Puis si l'expression commence par le symbole `"%"` suivi par une succession de chiffre `0` ou `1`, alors on autorise l'absence de symbole pour désigner cette composition simplement en juxtaposant les arguments `0` ou `1`. Par exemple : `%1001= 1°0°0°1=9`
Ce nouvel opérateur `"°"` offre une nouvelle représentation des entiers sous forme de développement en base 2. Délors, il existe des programmes d'addition et de multiplication de complexité beaucoup plus faible opérant sur cette seconde représentation.
---- 8 mai 2022 ----