Fondant l'algèbre par l'informatique, on redonne à la notion de langage sa première place, avant mêmes les objects désignés par le langage. Le langage formel se concrétise lorsqu'il s'exécute en tant que programme. C'est pourquoi nous reprenons la démarche initiale du groupe N. Bourbaki, dans la présentation d'un langage mathématique formel, en lui donnant une autre direction davantage vers la linguistique et l'informatique que vers la notion d'ensemble.
L'isomorphisme de structure est la clé d'entrée pour séparer l'objet de la propriété. Nous commençons par en exposer les raisons profondes pour ensuite procéder à une construction rigoureuse du langage.
La signature d'une structure est une listes d'arités. L'isomorphisme transporte toutes les propriétés d'une structure de même signature à une autre.
En plaçant ce principe en premier, cela nous permet de circonscrire ce que l'on entend par propriété propre à une structure. C'est une propriété qui doit être transportée par tout isomorphisme.
L'isomorphisme s'étend au domaine des propriétés et de leurs expressions, transformant l'expression logique en remplaçant l'ensemble sous-jacents et les éléments par leur images, et en remplaçant les lois de la première structrure par les lois de la seconde structure.
On se place dans une structure de magma `(M, "*")`. Les propriétés écrites concernant exclusivement cette structure, utilise le langage de la structure. Si on ne précise pas le type d'un élément, par défaut, il appartient à l'ensemble sous-jacent de la structure, `M`.
Exemple de propriété du premier ordre : Tout élément admet une racine carré :
`AAx,EEy, x"="y"⁎"y`
Exemple de propriété du second ordre : La structure est infinie :
`EE f "∈" (M"↪"M),f(M)"≠"M`
Si `(A,"⁎")≅(B,"•")` alors la propriété :
`AAx "∈" A,EEy "∈" A, x"="y"⁎"y`
aura la même valeur logique que la propriété :
`AAx "∈" B, EEy "∈" B, x"="y"•"y`
et la propriété :
`EE f "∈" (A"↪"A),f(A)"≠"A`
aura la même valeur logique que la propriété :
`EE f "∈" (B"↪"B),f(B)"≠"B`
la traduction se faisant par un isomorphisme.
En mathématique, une structure se déclare souvent par un couple où le premier argument est l'ensemble sous-jacent et où le second argument est une loi de composition binaire interne, telle que `(M,"⁎")`. S'il découle de cette loi `"⁎"` des éléments singuliers et d'autres lois, ceux-ci sont définis après coup à partir de la loi `"⁎"` ce qui explique pourquoi ils n'apparaissent pas dans la déclaration initiale de la structure.
La structure, comme en informatique, définit un espace de noms. De telle sorte que le même symbole d'opérateur `"⁎"` peut être utilisé dans plusieurs structures, par exemple `(A,"⁎")` et `(B,"⁎")`. Et lorsque une expression peut être interprétée de deux façons possibles, on lève l'ambiguité en mettant en indice la structure à laquelle l'opérateur appartient, par exemple : `x "⁎"_A y` ou `x "⁎"_B y`. Dans le premier cas cela entraine que les variables `x` et `y` sont de type `A`, et dans le second cas cela entraine que les variables `x` et `y` sont de type `B`.
La loi `"⁎"` peut dans certain cas être définie sur des ensembles plus grand que la structure, couvrant `A` et `B`. Dans ce cas, la loi de la structure est implicitement celle réduite à l'ensemble sous-jacent ce qui se note explicitement par `(A,"⁎|"_A)` et `(B,"⁎|"_B)`, et elles doivent être internes, autrement-dit `(A "⁎|"_A A) sube A` et `(B "⁎|"_B B) sube B`.
Les structures peuvent utiliser le même ensemble sous-jacent, elles doivent alors se distinguer par un symbole d'opérateur distinct, par exemple `(M,"⁎")` et `(M,"•")`. Chaque structure est définie par sa loi :
`"⁎" in (M"×"M->M)`
`"•" in (M"×"M->M)`
Le fait qu'elle partage un même ensemble sous-jacent permet de donner plusieurs rôle à un même élément. On peut séparer les deux sructures en deux magmas disjoints tout en les liant par une bijection. On crée une copie de `M` que l'on nomme `N` :
`(M,"⁎")`, `(N,"•")`, `f "∈" (M"↔"N)`
Une structure peut comprendre plusieurs lois et éléments singuliers. Le cas précédent peut se résumer en une structure de double-magma `(M,"⁎","•")`.
Considérons par exemple la structure `(M, a,b, s("."), "⁎"(".,."))`. Les suffixes `(".")` ou `(".,.")` notés facultativement rappelle l'arité des opérateurs internes à `M`. Cette notation comprenant un ensemble et une liste d'éléments et d'opérateurs est utilisée à titre de définition initiale dans un but unificateur. Elle doit être minimale. Cela signifie que ces éléments et opérateurs ainsi prédéclarés ne doivent pas être définissables dans la structure réduite d'eux-mêmes. Ainsi, il ne doit pas exister de définision de l'élément `a` dans la structure réduite `(M, b, s("."), "⁎"(".,."))`, De même, il ne doit pas exister de définision de l'opérateur `s(".")` dans la structure réduite `(M, a,b, "⁎"(".,."))`, etc..
Comme le langage alpha comprend toute l'algèbre, on a souvent à faire à une structure définie par une unique loi binaire.
La signature de la structure permet de définir précisément ce que l'on entend par isomorphisme.
`(M,"⁎")` `(2)` `(M,"⁎","•")` `(2,2)` `(M, a,b, s("."), "⁎"(".,."))` `(0,0,1,2)`
L'isomorphisme de structure de signature `(0,0,1,2)` se décrit ainsi :
`(A, a,b, s("."), "⁎"(".,.")) ≅ (B, a,b, s("."), "⁎"(".,."))`
si et seulement si :
`EEfAAxAAy, ((f"∈"(A"↔"B)),(f(a)=a),(f(b)=b),(AAx̦ f(s(x))=s(f(x)) ),(AAxAAy̦ f(x"⁎"y)=s(f(x)"⁎"f(y)) ))`
Les types de `x` et de `y` ne sont pas précisés explicitement, mais implicitement par inférence en tant qu'argument de la fonction `f` de type `(A"↔"B)`, comme éléments de type `A`. Pour la même raison, `f(a)` signifie `f(a_A)` par principe du langage, et aussi `s(f(a))` signifie `s_B(f(a_A))`. L'application prototypée `(A"→"B)` ou `(A"↪"B)` ou `(A"↔"B)` impose le type `A` à son argument, et le type `B` au résultat.
Un morphisme entre deux structures de même signature est une application qui respecte les opérations de la structure. On note l'ensemble des morphismes de `A` vers `B` de signature `(0,0,1,2)` comme suit :
`((A,a,b,f,"⁎")"→"(B,a,b,f,"⁎"))`
L'application prototypée `((A,a,b,f,"⁎")"→"(B,a,b,f,"⁎"))` impose l'espace de noms de la structure `A` à l'expression de son argument, et l'espace de noms de la structure `B` à l'expression dont il est l'argument. Et si on utilise le symbole `"↪"` à la place du symbole `"→"`, on obtient l'ensemble des plongements, et si on utilise à la place le symbole `"↔"`, on obtient l'ensemble des isomorphismes.
` f ∈ ((A,a,b,f,"⁎")"→"(B,a,b,f,"⁎"))`
si et seulement si :
`((f"∈"(A→B)),(f(a)=a),(f(b)=b),(AAx̦ f(s(x))=s(f(x)) ),(AAxAAy̦ f(x"⁎"y)=s(f(x)"⁎"f(y)) ))`
Ainsi l'isomorphisme se définie ainsi :
`(A, a,b, s("."), "⁎"(".,.")) "≅" (B, a,b, s("."), "⁎"(".,.")) <=> EE f "∈" ( (A, a,b, s,"⁎")"↔"(B, a,b, s,"⁎"))`
Le regroupement entre crochet d'éléments et d'opérateurs désigne toute les compositions closes qu'il est possible de composer avec autant d'occurences que voulues. Le magma libre `(L,"⁎")` et dit monogène s'il est engendré par un élément `alpha` :
`L = "<"alpha, "⁎>"`
Un magma quelconque peut être engendré par un élément ou deux ou trois ou ... ou un infinité énumérable d'éléments :
Magma monogène`(M,"⁎")` `EEa, M="<"a, "⁎>"` Magma bigène`(M,"⁎")` `EEaEEb, M="<"a,b, "⁎>"` Magma trigène`(M,"⁎")` `EEaEEbEEc, M="<"a,b,c, "⁎>"` Magma `oo`gène`(M,"⁎")` `EEf "∈" (NN"↪"M), M="<"f(NN) , "⁎>"`
En engendrant la structure, on renoue l'algèbre avec l'informatique. Puis, on construit une nomenclature des structures engendrées, présentant leurs éléments et opérateurs générateurs.
L'engendrement utilise deux concepts clés que sont :
L'extension absolument libre par un élément consiste à ajouter un nouvel élément générateur `e` à la structure `M` de façon absolument libre. L'élément `e` est dit absolument libre vis-à-vis de la structure et va se comporter comme une graine en se démultipliant.
On définie la structrure étendue `M⟨e⟩` par un procédé d'engendrement récurcif : Pour chaque opérateur unaire générateur `f(".")` de la structure, `f(e)` est un nouvel élément libre qui relance ce procesus d'extension absolument libre. Pour chaque opérateur binaire générateur `g(".,.")` de la structure, `g(e,e)` est un nouvel élément libre qui relance ce procesus d'extension absolument libre, et pour chaque `x "∈" M⟨e⟩` l'élément `g(e,x)` est un nouvel élément absolument libre qui relance ce procesus d'extension absolument libre, et l'élément `g(x,e)` est un nouvel élément absolument libre qui relance ce procesus d'extension absolument libre.
L'extension absolument libre par un opérateur unaire consiste à ajouter un nouvel opérateur unaire générateur `s(".")` à la structure `M` de façon absolument libre. L'opérateur `s(".")` est dit absolument libre vis-à-vis de la structure et va se comporter comme un légo en s'emboitant, de tel sorte que pour chaque `x "∈" M⟨s(".")⟩`, l'élément `s(x)` est un nouvel élément absolument libre qui relance ce procesus d'extension absolument libre.
L'extension absolument libre par un opérateur binaire consiste à ajouter un nouvel opérateur binaire générateur `g(".,.")` à la structure `M` de façon absolument libre. L'opérateur `g(".,.")` est dit absolument libre vis-à-vis de la structure et va se comporter comme un légo en s'emboitant, de tel sorte que pour chaque `x "∈" M⟨s(".")⟩` et chaque `y "∈" M⟨s(".")⟩`, l'élément `g(x,y)` est un nouvel élément absolument libre qui relance ce procesus d'extension absolument libre.
La première structure engendrée est le singleton `"<"e">"`.
Puis vient la structure de `"Peano<"e,s(".")">"` que l'on obtient à partir du singleton par extension absolument libre par un opérateur unaire. Les éléments de cette structures sont identifiés à `NN` comme suit :
`0 = e`
`1=s(e)`
`2=s(s(e))`
`3=s^3(e)`
...
`n = s^n(e)`
...
En langage informatique, cela signifie la mise en place d'une conversion implicite entre le type `NN` et le type `"Peano<"e,s(".")">"`. On nomme la structure à l'aide d'une égalité de définition :
`P = "Peano<"e,s(".")">"`
Après cette déclaration la sructure `P` est définie et possède un espace de noms, faisant que l'on peut préciser pour chaque opérateurs, à quelle structure il appartient en l'indiçant par le nom de la structure, `e_P` et `s_P"(.)"`.
Les éléments de la structure sont engendrés comme les mots d'une grammaires. Ils sont donc désignées par les mots d'un langage. Et cette désignation est biunivoque parceque la structure est libre. Ils sont donc identifiable aux mots du langage. La grammaire de ce langage se présente comme une inclusion récurcive :
`P←{e,s(P)}`
Puis vient la structure de `"M = Magma monogène<"e,"⁎"(".,.")">"` que l'on obtient à partir du singleton par extension absolument libre par un opérateur binaire. Sa grammaire se note :
`M←{e, (M"⁎"M) }`
Notez que les grammaires ici sont toutes algèbriques, et que les mots ici doivent être considérés comme des emboitements d'opérateurs, et non comme des chaines de caractères.
Une des motivations de l'exploration tient dans la recherche à minimiser l'effort de démonstration. Ce qui est donc recherché sont des propriétés de définition simple à écrire et à mettre en oeuvre, qui soient plus complexe à démontrer, marquant de ce fait une avancé dans ce pouvoir de démonstration à moindre effort.
La structure de Peano, qui représente les entiers naturels, possède de nombreuses propriétés simples à écrire en logique du premier ordre et également en logique du second ordre (Cela couvre toute l'arithmétique). Difficile de savoir dans quelle ordre il faudrait les annoncer. On définit les entiers naturels `NN` comme suit :
`NN = "Peano<"0,s(".")">"`
Il existe une relation d'ordre naturelle et une opération d'addition définissable. Sa définition nécessitent un recours à la récurrence et met en oeuvre quelques mécanismes de base propre à la notion de calculabilité. On définit l'opérateur binaire `+(".,.")` de syntaxe centrée, par un jeux de règles de simplification : `AAx,`
`x"+"0 = x`
`x"+"s(x) = s(x)"+"x`
Il faut d'abord prouver qu'une telle opération existe, puis présenter le programme récurcif qui procède au calcul de l'addition : L'opérateur `(x,y|->0)` est une solution vérifiant ces deux propriétés. Le programme de calcul s'écrit dans un langage informatique qui pourrait ressembler à cela :
`"Op"("+") = (`
`x,0 |-> x`
`x,s(y) |-> s(x)"+"y`
`)`
La relation d'ordre `"⩽"` se définit comme suit : `AAxAAy,`
`x"⩽"y <=> EEz, x"+"z"="y`
Peano est une structure libre (extension absolument libre par `s(".")` de la structure singleton), de ce fait on peut définir une injection de `NN` dans `NN-{0}`, ce qui prouve l'infinité du cardinal de `NN`.
Ce sont là, les débuts de l'arithmétique. C'est donc à partir de cette base qu'il convient d'établir le langage mathématique le plus adapté pour faire ces démonstrations avec le moindre effort.
Etant données des éléments et opérateurs tels que par exemple `a,b,f("."),g(".,.")`. Où le domaine de définition de l'opérateur n'est pas complètement défini. On demande seulement qu'ils soient définis pour `a` et `b` (c'est à dire que `f(a)` et `f(b)` soient définis, et que `g(a,a),g(a,b),g(b,a),g(b,b)` soit définis), et qu'ils soient définis sur leurs images. Cela engendre une structure `E="<"a,b,f("."),g(".,.")">"`. Etant donné un prédicat `P(".")` défini sur `E`. Le principe de réccurence générale se déroule dans la structure `E` comme suit :
`((P(a)),(P(b)),(AAx̦ P(x)=>P(f(x))),(AAx̦AAy̦ P(x) "et" P(y) => P(g(x,y)))) => AAx, P(x)`
Notez que la priorité syntaique du `"et"` est plus forte sur celle de`=>`. Le langage doit être étendu pour pouvoir formuler de façon plus générale ce principe de réccurence. On commence par définir la variable séquencielle notée vectoriellement, `vec v`. Elle représente une séquence finie quelconque d'éléments, mais dont la taille est contrainte par l'inférence de type. Ainsi l'expression `AA vec v, g(vecv)"="a` signifie `AAxAAy, g(x,y)"="a` car l'opérateur `g` possède une arité fixée à 2.
Le `i` ième élément de `vec v` se note `v_i`.
La séquence se comporte aussi comme un ensemble, `AAx"∈" vecv, P(x)`, signifie que tous les éléments de la séquence `vec v` satisfont le prédicat `P(".")`
Une séquence `vec v` peut être vide et égale à `vec v "="()`.
Les éléments générateurs sont considérés comme des opérateurs générateurs d'arité nulle, qui appliqué à une séquence vide retourne l'élément considéré.
On note, `cc"G"`, l'ensemble des opérateurs générateurs de la structure `E`.
Le principe de récurrence générale s'écrit alors formellement comme suit :
`(AAf"∈" cc "G", (AA vecv, (AAx"∈" vecv, P(x) ) => f(vec v))) => AAx, P(x)`
Si on se place dans une algèbre monogène `"<"alpha, "⁎>"` alors le principe de récurrence générale s'écrit :
`(P(alpha) "et" AAxAAy, P(x) "et" P(y) =>P(x"⁎"y)) => AAx, P(x)`
Elle se définit formellement dans la structure de Péano `NN``=``"<"0,s(".")">"` et sépare les fonctions en deux groupes, les fonctions primitives récursives, et les fonctions µ-récurcives qui nécessitent une minimisation non-borné.
L'étude de la calculabilité donne une définition formelle des fonctions récurcives primitives dans la structure de Peano, `NN``=``"<"0,s(".")">"`. Ce sont toutes les fontions constructibles à partir des procédés suivant :
1- La fonction zéro `0()`, elle n'a pas d'argument et à toujours la valeur `0`. C'est l'élément générateur de la structure de Peano. Et comme les éléments sont des fonctions sans argument qui les retournent tel quel, nous pouvons la définir comme suit :
`0=(|->0)`
2- Les fonctions de projection `AAvecx, p_i(vecv ) = v_i`
`p_i=(vec v |->x_i)`
3- La fonction successeur `s(".")`, c'est la fonction unaire génératrice dans la sructure de Peano, une extension absolument libre donc `s` est injectif.
`s = (n|->s(n))`
4- La fonction `F(".,...")` définie par récurrence primitive à partir de deux fonctions quelconques `G("...")` et `H(".,.,...")` d'arité `k` et `k"+"2`, comme suit :
`AAvecvAAn,`
`F(0,vecv) = G(vecv)`
`F(s(n),vecv)=H(n,F(n,vecv),vecv)`
Cela s'écrit sous forme d'un programme ressemblant à du Haskel :
`F= (".,...|" `
`0,vec v |-> G(vecv)`
`s(n),vecv|-> H(n,f(n,vecv),vecv)`
`)`
Les fonctions récursives primitives sont les fonctions construites à partir de la composition d'application et de ces 4 procédés, répétés un nombre quelconque de fois.
De par la définition constructive des fonctions récurvcives primitives, celles-ci sont énumérables. On utlise lors la méthode de la diagonale de Cantor pour prouver qu'il existe des fonctions calculables qui ne sont pas récursives primitives.
Considérons donc une énumération de toutes les fonctions récursives unaires, `f_1,f_2,f_3,...` Considérons maintenant la fonction `AAn, g(n)"="s(f_n(n))` qui est calculable en tant que composition de fonctions caculables. Celle-ci, en tant que composée de fonction récursive, est récurcive et doit donc être énuéméré `EEm, g"="f_m` donc `g(m)"="s(f_m(m))` donc `f_m(m)"="s(f_m(m))`, ce qui est impossible. Il existe donc des fonctions calculables non primitive récurcive.
Les fonctions µ-récursives sont les fonctions construites à partir de la composition d'application et des 4 procédés pour définir les fonctions récurvives primitives, aux quels on ajoute un cinquièmes procédé qu'est la minimisation non-bornée.
5- La fonction `F(".,...")` se définie par minimisation non borné d'un prédicat `P(".,...")` comme suit :
`AAvecvAAn,`
`F(n,vecv) =` le plus petit `n` tel que `P (n, vecv)`, ou `0` s'il n'y a en a pas.
Pour que la fonction `F("...")` soit calculable, on se restreint aux seuls prédicats dit sûre c'est à dire vérifiant :
`AAvecxEEn, P(n,vecx)`
La fonction s'écrit alors sous forme d'un programme :
`F= (vec x | `
`"para" n in NN`
`"si" P(n,vecx) "entonces devolver" n`
`)`
---- 17 novembre 2025 ----
9.4) Calculabilité
Voir Turing
Il n'existe pas de prédicat calculable `K(P,vecv) ` capable de déterminer pour tout prédicat `P` définissable et pour tout paramètre `vecv` s'il existe ou pas, un `n` tel que `P(n,vecv)`. On le démontre par l'absurde
---- 16 novembre 2025 ----