Les catégories

1. Introduction
2. Le monoïde
3. Les entiers naturels
4. La construction d'une forme normale pour les entiers
5. Les algorithmes de calcul
6. Exemple de programme
7. Langage propositionnel du premier ordre
8. Meta-ensemble
9. Principe de construction des fonctions et prédicats
10. Le groupe
11. Le corps
12. Construction de nouvelles structures

1) Introduction

Une catégories est une structure vue d'une façon plus générale, en faisant abstraction des objets possédant cette structure, et en ne retenant que ce qui est générale et s'applique à tous ses objets.

Nous allons construire plusieurs structures, et essayer de mettre à jour un procédé de construction implémentable informatiquement. Une structure possède deux versants, l'un théorique comprenant son langage et sa théorie, l'autre algorithmique comprenant son implémentation.

On définie au départ le méta-ensemble W de tous les éléments. Une fonction f faisant parti d'un langage que l'on ajoute à W, est définie sur W selon le principe de construction des structures libres. A savoir en l'absence d'algorithme de calcul, on choisie par défaut la structure libre. Par exemple, si la variable x, contient l'élément d'expression développée g(a,h(b)) dans l'univers de Herbrand, alors f(x) se développe, et est égale à l'élément f(g(a,h(b))) dans l'univers de Herbrand.

2) Le monoïde

Une structure est définie par un langage et une théorie du premier ordre. Par exemple, la structure de monoïde est définie par le langage {K,*} constitué de :

• Un prédicat unaire K, fonction caractéristique qui appliqué à un élément x, retourne vrai si x est dans K ou faux sinon.
• Un opérateurs binaires nommés * . C'est à dire une fonctions qui, appliquée à un couple d'éléments de W, donne un élément de W.

La théorie est : {K(a*b), (a*b)*c = a*(b*c)}

La théorie est constituée par la conjonction des propriétées suivantes :

Pour tout a,b,c tel que K(a) et K(b) et K(c) nous avons :

L'autre versant de la structure, le versant algorithmique, contient une implémentation des éléments. Les éléments d'un monoïde sont implémentés sous forme de suite. Par exemple, étant donné trois éléments a,b,c appartenant au monoïde, la suite (a,b,a,a,c,b) désigne l'élément a*b*a*a*c*b. Cette implémentation intègre les deux axiomes du monoïde, le fait que l'operation * soit interne et associative.

Nous voulons programmer des algorithmes sur cette structure. Il nous faut une matière pour faire des algorithmes, et cette matière s'appelle les entiers naturels. C'est une structure incontournable qui est à la base de la programmation.

3) Les entiers naturels

La structure de péano est définie par le langage {N,0,s} constitué de :

• Un prédicat unaire N, fonction caractéristique qui appliqué à un élément x, retourne vrai si x est dans N ou faux sinon.
• Un opérateurs zéro-aires nommés 0 désignant un éléments, qui à cette étape du raisonnement n'est pas nécessairement présents dans N.
• Un opérateurs unaire nommés s. C'est à dire une fonctions qui appliquée à un éléments de W donne un élément de W.

La théorie est constituée par les 5 propriétées suivantes :

Pour tout a,b tel que N(a) et N(b) nous avons :

Le versant algorithmique de cette structure est la base de la programmation. Les entiers possèdent une implémentation, une forme normale (représentation binaires par exemple), et l'opérations successeur s possède un algorithmes de calcul qui s'appliquent à cette forme normale.

4) La construction d'une forme normale pour les entiers

On construit une représentation des entiers (en binaire), et on construit l'operation successeur s par son algorithme de calcul sur les entiers binaires (ajout d'un bit avec retenue). Puis on construit de même l'opération + par son algorithme de calcul sur les entiers binaires (ajout bit à bit avec retenue), et de même pour l'opération * avec un algorithme de calcul un peu plus compliqué.

On construit l'élément 1 comme égale à s(0).

Les opérateurs 1, + et * sont définie par leurs algorithmes.

Les propriétés relatives à ces nouveaux opérateurs sont recherchées.

Pour tout a,b,c tel que N(a) et N(b) et N(c) nous avons :

5) Les algorithmes de calcul

A partir d'une structure, c'est à dire d'un langage et d'une théorie, on construit de nouvelles fonctions en programmant des algorithmes de calcul utilisant les fonctions et prédicats préalablement définis dans de la structure. Le langage de programmation comprent le langage de la structure et les opérations de programmation.

Noter que ces nouvelles fonctions sont une émanation de la catégorie. Il sont propre à la catégorie, et ne sont pas propre à un objet particulier de la catégorie. Il s'applique donc à tous les objets de la categorie.

6) Exemple de programmation

Par exemple définissons l'opération externe, d'élévation à la puissance, d'un élément du monoïde par un entier, notée sous forme fonctionnelle P(x,n) = x^n. Cette fonction a un type, un schéma qui précise la structure des éléments de départ et la structure des éléments d'arrivé. La construction des types se fait en parallèle à la construction des structures et des fonctions. Le type de la fonction P est le suivant :

(K, N) --> K

La fonction P(x,n)=x^n peut se programmer en ruby comme suit :

def P(x,n)
  s=1
  loop do
    break if n==0
    s=s*x
    n=n-1
  end
end

L'opération ^ est ainsi programmée dans le langage de la catégorie des monoïde, c'est à dire programmé à partir de la seul fonction * de la catégorie des monoïdes et sans utiliser aucune propriété du monoïde spécifique tel que l'ensemble sous-jacent K. Mais elle utilise les opérations de récursion propre à la programmation des fonctions récurcives et appartenan à la structure des entiers.

L'opérateur ^ possède des propriétés que l'on décompose en skolèmes :

(x^n)*(x^m) = x^(n+m) ou ¬K(x) ou ¬N(n) ou ¬N(m)
(x^n)^m = x^(n*m) ou ¬K(x) ou ¬N(n) ou ¬N(m)
(x^n)*(y^n) = (x*y)^n ou ¬K(x) ou ¬K(y) ou ¬N(n)

On appellera émanations de la structures, les nouvelles fonctions et prédicats construits de cette façon. Toute sorte de construction sont délors possible, et nous devrons définir un critère de pertinence.

7) Langage propositionel du premier ordre

Le langage de Herbrand de la structure contient toutes les constantes obtenues par emboitement clos de fonctions de base de la structure.

Le langage propositionnel de la structure contient toutes les propositions du premier ordre utilisant les prédicats et fonction de base de la structures et utilisant le prédicat d'égalité.

Le langage propositionnel admet une forme normale, dite de skolème, dans laquelle les propositions ont la forme suivante :

• Tous les quantificateurs existenciels sont placés en premier et portent sur des fonctions d'arité pouvant être supérieur à zéro, constituant en cela des variables existentiels d'ordre supérieur, et sont suivis par tous les quantificateurs universelles. Ils constituent une extension du langage.
• Le corps de la proposition est constitué d'une seul conjonction globale, opérateur multi-aire "et", appliquée à des disjonctions.
• Les disjonctions, opérateurs multi-aire "ou", sont appliquées à des littéraux.
• Les littéraux sont négatifs ou affirmatifs c'est à dire avec ou sans l'opérateur "¬" devant, et sont constitués, soit d'un prédicat ou soit d'une égalité, appliqué à des termes de l'univers de Herbrand étendu.
• Les termes de l'univers de Herbrand étendu sont les termes clos que l'on peut construire par emboitement de fonction à partir de trois sources de fonctions que sont ; les fonctions du langage de la structure, les fonctions d'arité zéro correspondantes aux variables universelles, et les fonctions correspondantes aux variables existenciels (Voir algorithme de skolémisation).

Par exemple la proposition suivante :

∀x ∃y  K(x) et K(y) => K(x+y)

Admet comme forme normale de skolème :

∃f(.) ∀x  K(x+f(x)) ou ¬K(x) ou ¬K(f(x))

La théorie de la structure se met sous forme normale de skolème. On définie alors le langage de la structure en y ajoutant les variables existancielles postulées dans sa théorie. Et on supprime les quantificateurs existentiels qui délors n'ont pu lieu d'être puisque leur variables sont maintenant définie dans le langage. Les axiomes ne contiennent alors que des quantificateurs universelles, les variables existentiel ayant était enlevées de la théorie et rajoutées au langage, de tel sorte que toute variable qui ne figure pas dans le langage de la structure est obligatoirement une variable universelle.

La théorie d'une structure après skolémisation ne comprend que des variables universelles. Mais la théorie admet plusieurs représentations possibles équivalentes.

Repartons des fondements pour construire nos structures.

8) Meta-Ensemble

On définie le méta-ensemble W de tous les éléments. On considère qu'un élément peut avoir plusieurs représentations et que l'ensemble N des représentation est identifiable aux entiers naturels. De plus on considère que le prédicats Ident : (N,N) -->{vrai, faux} décidant si deux représentations représentent le même éléments est totalement calculable, et que nous possèdons un algorithme calculant Ident(x,y) toujours en un temps fini. Le choix de ce prédicat Ident est arbitraire. Nous avons :

W = N / Ident

9) Principe de construction des fonctions et prédicats

Une fonction f, ou un prédicat, faisant parti du langage, est définie de fait sur W selon le principe de construction des structures libres. A savoir en l'absence d'information sur l'algorithme de calcul, on choisie par défaut la structure libre qui permet de définir l'image de n'importe quel élément x par f comme suit : Par exemple, si la variable local x, telle qu'elle est mentionnée dans ce paragraphe, contient l'élément d'expression "g(a,a,h(b))" dans l'univers de Herbrand, alors f(x) est égale à l'élément qui admet comme représentation "f(g(a,a,h(b)))" dans l'univers de Herbrand.

La fonction, ou le prédicat, n'à de sense mathématique commun que définie sur un ensemble. Or W n'est pas un ensemble, c'est un méta-ensemble qui transporte des choix de constructivité arbitraires, des méthodes arbitraires, que nous avons choisie pour construire notre mathématique. Aussi toute propriété fonction ou prédicat relative à W est entachée d'arbitraire. Ce n'est que lorsque le domaine de définition est circonscrit à un ensemble, que la propriété, la fonction, le prédicat ainsi construit, peut prendre un sense commun.

A partir d'une structure, c'est à dire d'un langage et d'une théorie, on peut programmer de nouvelles fonctions en utilisant les fonctions et prédicats de la structure, c'est à dire écrit dans le langage de la structure et complété par les opérations de récursion propre à la programmation des fonctions récurcives. Ces programmes définissent, par des moyens effectifs, de nouvelles fonctions et prédicats que l'on ajoutent au langage de la structure. Néamoins pour chaque fonction et prédicat programmée ainsi, il faut fixer le sense de l'Infinit de Turing, à savoir un autre calcul, tel une valeur particulière par exemple, ou bien l'absence de calcul c'est à dire par défaut l'élément de la structure libre associée. La théorie de la structure enrichie par ces nouvelles fonctions devra pouvoir déduire des propriétés les concernant. On peut construire de nouvelles structures en construisant leurs éléments de la même manière. Et on peut construire dans ces nouvelles structures des fonctions et prédicats de la même manière.

La création de structure généralise la création d'un ensemble. Un ensemble énumérable est créé par une machine qui l'énumère. Un ensemble décidable est créé par un ensemble mère et un prédicat calculable. L'ensemble mère est une structure libre engendré par un nombre fini d'éléments, c'est donc un ensemble énumérable.

10) Le groupe

On ajoute dans le langage toutes les variables existentiels mentionnées dans les axiomes initiaux de la catégorie des Groupes. Cela consiste à ajouter un élément 1, un prédicat unaire G(.), une fonction binaire *(.,.) et une fonction unaire inverse inv(x). La structure de groupe utilise le langage {G,*,inv,1}. Ces fonctions ou opérateurs, que nous appelons également méthodes en analogie à la programmation object, n'ont aucune implémentation autre que celle par défaut de la composition libre non évaluée.

Nous complétons la structure de groupe en implémentant ses opérateurs. Cela constitue une sorte de conctrétisation de la structure. Mais les algorithmes, pour pouvoir s'effectuer, doivent obligatoirement s'appuyer sur des structures de base sous-jacente préexistantes. Prenons un exemple simple de produit directe. On suppose que le groupe est le produit directe de deux groupes A et B, et on implémente alors ses différentes méthodes comme suit :

1 = (1_A, 1_B)

x  *  y = ( P_A(x)  *_A  P_A(y), P_B(x)  *_B  P_B(y))

inv(x) = ( inv_A(P_A(x)), inv_B(P_B(x)) )

La représentation d'un élément x du groupe G est décomposé en un couple d'éléments (x_A, x _B) où x_A∈ A et x_B∈ B. Les projections sont définies par :

P_A((x_A, x _B)) = x_A

P_B((x_A, x _B)) = x_B

L'implémention constitue le lien effectif entre les deux structures de groupes A et B, et la structure de groupe G. Si les méthodes des groupes A et B sont calculables et possèdent une complexité, alors l'implémentation rend les méthodes du groupe G calculables et de complexité évaluable. On dira que l'implémentation est paramétrique, qu'elle possède deux parmètres d'entré que sont les groupes A et B.

Et il peut y avoir plusieur implémentions différentes calculant la même chose. La même chose signifiant un lien isomorphique appelé une traduction. Une autre complexité apparait alors, qui est celle des traductions passant d'une implémentation à une autres, et toutes ne sont pas forcement possibles.

11) Le corps

La structure de corps est définie par le langage {K,+,-,*,inv,0,1} constitué de :

• Un prédicat unaire K, fonction caractéristique qui appliqué à un élément x, retourne vrai si x est dans K ou faux sinon.
• Deux opérateurs zéro-aires nommés 0 et 1 désignant deux éléments, qui à cette étape du raisonnement ne sont pas nécessairement distincts, ni présents dans K.
• Quatres opérateurs binaires nommés +,-,*,inv. C'est à dire quatres fonctions qui chacune appliquée à un couple d'éléments de W donne un élément de W.

On peut construire à partir d'une ou plusieurs structures, de nouvelles structures. Les éléments de la nouvelle structure sont calculés à l'aide d'une fonction qu'il faut programmé dans le langage des structures initiales. Et le opérateurs de la nouvelle structure peuvent être programmés également dans le langage des structures initiales. La nouvelle structure est alors une émanation des structures initiales.

Par exemple définissons la structure des matrices 2 fois 2 sur un corps K. Les éléments sont des quadruplet d'éléments du corps K tel que par exemple :

(x₀₀, x₀₁, x₁₀, x₁₁)

L'opérations d'adition est définie par :

  (x₀₀, x₀₁, x₁₀, x₁₁) + (y₀₀, y₀₁, y₁₀, y₁₁) = (x₀₀+y₀₀, x₀₁+y₀₁, x₁₀+y₁₀, x₁₁+y₁₁)

L'opérations de multiplication est définie par

   (x₀₀, x₀₁, x₁₀, x₁₁) * (y₀₀, y₀₁, y₁₀, y₁₁) = (x₀₀*y₀₀ + x₀₁*y₁₀, x₀₀*y₀₁ + x₀₁*y₁₁, x₁₀*y₀₀ + x₁₁*y₁₀, x₁₀*y₀₁ + x₁₁*y₁₁)

Les opérations matriciels + et * sont programmés dans le langage de la catégorie des corps, et plus exactement programmés à partir de la seul fonction * et + de la catégorie des corps et sans utiliser aucune propriété du corps, mais par contre utilise la structure (Z/2Z)² et d'une manière plus générale, utilise la structure des entiers. La programmation utilise nécessairement la structure des entiers, et cette structure contient l'arithmétique effective et donc contient toutes les mathématiques effectives.

Par contre pour que la nouvelle structure possède les propriétés suivantes :

• L'associativité : M1*(M2*M3) = (M1*M2)*M3
• La distributivité à gauche de * sur + : M1*(M2+M3) = M1*M2 + M1*M3
• La distributivité à droite de * sur + : (M1+M2)*M3= M1*M3 + M2*M3

Il suffit d'avoir dans la structure K, l'associativité de *, l'associativité de +, la distributivité à droite de * sur + et la distributivité à gauche de * sur +. Et cela est contenue dans la catégorie des corps.

On appellera émanations de la structures, les nouvelles structures construites de cette façon. Toute sorte de construction sont délors possible, et nous devrons définir un critère de pertinence.