Une manière concrète de définir ce que sont les catégories, consiste à les construire par étapes d'abstraction successives.
On commence par un cas très générale que sont les algèbres, puis les algèbres multi-sortes, de type fini, c'est à dire engendré par un nombre fini d'opérateurs. C'est l'approche la plus simple des ensembles énumérables.
Et cela met en avant le mécanisme d'unification de termes qui est de complexité linéaire, et qui constitue l'opération fondamentale de tous raisonnement.
Puis on la complète avec une notion très générale de lien entre ensemble, qu'est la relation. Celle-ci à l'avantage d'être parfaitement symétrique contrairement à la notion de fonction.
Puis on procède à l'abstraction finale en ne retenant que les liens entre objets de la catégorie, pour définir la catégorie.
On définit un langage algébrique en présentant ses éléments générateurs et ses opérateurs générateurs entre crochet `"<...>"`. Chaque opérateur possède une arité. Elle est indiquée occasionnellement par le suffixe `(".")` pour unaire, `(".,.")` pour binaire, `(".,.,.")` pour ternaire. Exemple :
`L = "<"a,b,f("."), g(".,."),h(".,.,.")">"`
Les éléments générateurs sont considérés comme des opérateurs générateurs d'arité nulle. Le langage algébrique L est l'ensemble de toutes les compositions closes d'opérateurs générateurs :
`L = {a,b,f(a),f(b),g(a,a),g(a,b),f(f(a)),g(a,g(a,f(b))),...}`
Puis il y a une distinction entre les opérateurs générateurs engendrant l'ensemble dit sous-jacent, et les opérateurs structurels définissant la signature de la structure. La structure `L` muni de ces opérateurs structurels se note :
`(L,a,b,f("."), g(".,."),h(".,.,."))`
On appelle terme clos une composition close d'opérateurs structurels. Exemple : `g(f(a),a)`
On appelle terme une composition close d'opérateurs structurels et de variable désigant un élément inconne de `L`. Exemple : `g(g(x,a),g(y,x))` où `x,y` sont des variables
Une structure est dite complète si elle est engendrée par ses opérateurs structurels.
Une structure complète est libre si et seulement si chaque terme clos désigne un élément distinct.
L'algèbre peut se définir complètement en donnant une procédure de calcul pour chacun de ses opérateurs structurels. Dans notre approche constructive on ne s'interesse qu'aux opérateurs calculables. Il y a trois type d'opérateurs :
Lorsque l'algèbre est incomplète, elle est dite libre si et seulement si chaque terme désigne une application injective. La composition d'applications injectives produisant nécessairement une application injective, la condition se ramène à : Si et seulement si chaque opérateur structurel est une application injective.
Considérons par exemple l'algèbre `(L,"*")` où `L` est engendré par `a,b,f("."), g(".,."),h(".,.,.")`. L'algèbre `L` est libre si et seulement si l'opérateur `"*"` est une application injective :
`AA(x,y,u,v) (x"*"y = u"*"v) => ((x = u),(y = v))`
Le vecteur correpond à un `"et"` logique.
On voit donc que cette définition de la liberté s'applique davantage aux opérateurs qu'à la structure proprement dit. On dira qu'un opérateur est libre si et seulement si il constitue une application injective interne à la structure. Notez que la composition d'opérateurs libres crée necessairement un opérateur libre.
On note les n-uplet d'éléments sous forme de vecteur, `vec x=(x_1,x_2,...,x_n)`, et on laisse l'inférence de type déterminer `n`. Ainsi la propriété que `L` soit libre s'écrit formellement comme suit :
`lambda "libre" <=> AAvecx,AAvecy, (lambda(vecx)=lambda(vecy) )=>(vecx=vecy)`
`AA lambda "∈" "sign"(L), lambda "libre"`
Une algèbre non-déterministe est complète si chaque élément appartient à un terme clos de la structure. Et dans ce cas, elle est libre si et seulement si chaque terme clos désigne une partie disjointe.
...
---- 20 juillet 2026 ----
Si elle n'est pas complète elle est dite libre si et seulement si chaque terme `lambda` désigne une application de L^n-->L vérifiant :.
`AAvecx AAvecy lambda(vecx) = lambda (vecy) => (vec x = vec y)`
La composition d'applications injectives produisant nécessairement une application injective, la condition se ramène à : Si et seulement si chaque opérateur structurel est une application injective. Considérons par exemple l'algèbre `(L,"*"(".,."))` où `L` est engendré par `a,b,f("."), g(".,."),h(".,.,.")`. L'algèbre `L` est libre si et seulement si l'opérateur `"*"` est une application injective :
`AA(x,y,u,v) (x"*"y = u"*"v) => ((x = u),(y = v))`
une application injective. La composition d'applications injectives produisant nécessairement une application injective, la condition se ramène à : Si et seulement si chaque opérateur structurel est une application injective. Considérons par exemple l'algèbre `(L,"*"(".,."))` où `L` est engendré par `a,b,f("."), g(".,."),h(".,.,.")`. L'algèbre `L` est libre si et seulement si l'opérateur `"*"` est une application injective :
Lorsque l'algèbre est incomplète,
Dans le cas d'opérateur non-déterministe, la condition devient :
`AA(x,y,u,v) => (x"*"y nn u"*"v ≠ Ø) => ((x = u),(y = v))`
La signature de `L` est l'ensemble des noms cours de ses opérateurs structurels :
La structure `L` est libre si chaque terme composition d'opérateurs structurel distinct désigne un élément distinct. La signature de `L` est l'ensemble des noms cours de ses opérateurs structurels :
`"sign"(L)={a,b,f("."), g(".,."),h(".,.,.")}`.
Le type d'une structure est la liste des arités des opérateurs dans l'ordre. Ainsi `"type"(L) = (0,0,1,2,3)`
Une algèbre comprend un ensemble sous-jacent muni d'opérateurs internes qui définissent la signature de l'algèbre. Par exemple la structure `(L, g(".,."))`
L'algèbre L est libre
La signature est la liste des opérateurs définissant la forme de la structure. Le type est la liste des arités dans l'ordre des opérateurs définissant la forme de la structure.
Lorsque les seuls éléments et opérateurs de forme de la structure n'engendrent pas à eux seuls la structure, celle-ci est dite incomplète.
Par défaut, toute algèbre est supposée incomplète, ceci afin d'atteindre un niveau de généralité plus grand. Par exemple, la structure de groupe ne possède qu'un opérateur binaire définissant sa forme.
On considère une seconde algèbre de même signature. On reprend donc les même noms d'opérateurs de forme qu'il faut indicer par `H` ou par `L` pour exprimer leur nom complet. Les opérateurs se comportent commme des objets de la structure `H` ou `L` que l'on peut noter informatiquement comme suit :
`H"."a, H"."b, H"."f, H"."g, H"."h`
Ou, comme suit, les deux écritures étant valables :
`a_H, b_H, f_H, g_H, h_H`
Et lorsque la structure est nommée ou soumise à une affectation de définition, il n'est alors plus nécessaire d'utiliser les noms complets des opérateurs :
`H = "<"a,b,f("."), g(".,."),h(".,.,.")">"`
Rappelons que les opérateurs étant des objets de classes distinctes `L` et `H`, ils sont donc distincts :
`a_L≠ a_H`
`b_L≠ b_H`
`f_L≠ f_H`
`g_L≠ g_H`
`h_L≠ h_H`
Une relation `R` de `L` vers `H` est un morphisme relationnel si et seulement si :
`R sube L"×"H`
`AA(x,y,z)"∈"L^3, AA(u,v,w)"∈"H^3,``aRa`
`bRb`
`xRu => f(x)Rf(u)`
`xRu "et" yRv=> g(x,y)Rg(u,v)`
`xRu "et" yRv "et" zRw => h(x,y,z)Rg(u,v,w)`.
Le prédicat binaire `R` utilise une syntaxe infixe. Le connecteur `"et"` est prioritaire sur le connecteur `=>`. L'opération `"×"` est prioritaire
On utilise l'inférence des types pour omettre l'appartenance des arguments, et omettre les noms de classe des opérateurs :
`AAxAAu xRu` signifie `AAx "∈" L AAu "∈" H xRu` puisque `R sube L"×"H`
L'inférence peut s'oppérer sur plusieurs niveaux d'emboitement :
`AAxEEy f(x)Rf(y)` signifie `AAx"∈"L EEy"∈"H f_L(x)Rf_H(y)`
puisque `R sube L"×"H` et que `f"∈sign"(H)` et `f"∈sign"(L)` et que c'est la seul inférence cohérente.
La relation inverse notée `R^-1` est celle obtenue en inversant les arcs :
`AAxAAu, uR^-1x = xRu`
La notation ensembliste de `R^-1` est celle d'une application de `H` vers `ccP(L)`. L'ensemble `R^-1(u)` est l'ensemble des éléments `x` de `L` tels que `xRu`.
`R^-1(u) = {x "|" xRu}`
Supposons que `R` soit un morphisme relationnel. Que pouvons nous dire de `uR^-1x` ? il est égal à `xRu` qui implique `f(x)Rf(u)` qui est égal à `f(u)R^-1f(x)`. Il en est de même pour les autres opérateurs de forme de la structure. Ainsi l'inverse d'un morphisme relationnel de `L` vers `H` est un morphisme relationnel de `H` vers `L`.
Lorque le morphisme relationnel `R` est biunivoque, c'est à dire vérifie :
`AAxEE!u xRu`
`AAuEE!x uRx`
Où `EE!x P(x)` signifie qu'il existe un unique élément `x` satisfaisant `P`. Autrement dit :
`(EE!x P(x)) <=> ((EEx P(x)),(EExEEy P(x) "et" P(y) => x"="y))`
Le vecteur correpond à un `"et"` logique. La portée des quantificateurs dans une composante est limitée à celle-ci.
La propriété `EE!x P(x)` se décompose deux propriété ;
Les morphismes relationnels `R` biunivoques sont les isomorphismes.
Lorque le morphisme relationnel `R` vérifie :
`AAuEE!x uRx`
Il définit une application de `L` vers `H` notée sous forme d'un opérateur unaire `R(".")` qui admet un fantôme libre et qui est de même nature que ceux définis dans une algèbre multi-sorte.
Lorque le morphisme relationnel `R` vérifie :
`AAuAAxAAy, uRx "et" uRy => x=y`
Il définit une fonction de `L` vers `H` notée aussi sous forme d'un opérateur unaire `R(".")` qui à la différence de l'application, peut ne rien produire si l'argument s'avère hors domaine de définition de la fonction `R`. L'opérateur unaire `R(".")` admet un fantôme libre qui est de même nature que ceux définis dans une algèbre multi-sorte.
On ajoute au langage `L` des variables muettes `L1, L2, L3,...` qui ont comme nom, celui du langage suivit d'un entier strictement positif. Elles sont dites muettes car elles ne correspondent pas à de nouveaux éléments générateurs, ce sont juste des inconnues appartenant au langage `L`, et qui donc jouent le rôle de terme quelconque de `L`. Exemple de terme avec variable : `g(L2,g(L1,g(a,L2)))`.
On utilise le nom de la structure seule pour désigner une variable toujours libre appartenant à la structure, faisant que :
`g(L,L)` désigne `{g(x,y) "|" x "∈" A, y "∈" A}`
`g(L1,L1)` désigne `{g(x,x) "|" x "∈" A}`
Si ces variables n'ont aucune contrainte, elles représentent chacune l'ensemble `L` entier. Mais celles numérotées désignent une instanciation précise, permettant de définir des diagonales tel que `g(L1,L1)`. La notation ensembliste définit des variables contraintes à rester dans une partie inconnue de `L` auxquels ont donne un nom sans numéro, le même nom avec numéro désignent une instanciation précise.
Considérons des éléments `x,y,...` et des parties `A,B,...` de la structure `L`.
`r in L`
`s in L`
`A sube L`
`B sube L`
Nous avons les égalités suivantes :
`f(A)` `=` `{f(x) "|" x "∈" A}` `g(A,B)` `=` `{g(x,x) "|" x "∈" A}` `h(A1,B,A2)` `=` `{h(x,y,x) "|" x "∈" A, y "∈" B}` `g(r,A)` `=` `{g(r,x) "|" x "∈" A}`
Les définitions étant faites en terme de production, elles restent valables pour des fonctions, l'expression d'une fonction appliquée à des arguments hors domaines désigne le rien, c'est à dire l'ajout à l'ensemble de rien.
On appelle sous-structure de `L`, une partie `A sube L` stable par les opérateurs générateurs de `L` :
A sube L
On appelle une structure incluse dans `L`, le même ensemble `L` muni d'une partie de la signature de `L`
stable par les opérateurs générateurs de `L`.
Considérons un morphisme relationel R de L vers H
Quand R est une fonction, l'image notée `R(L)` forme une sous-structure. Les lois de compositions sont transportées par l'application `R`.
Dans une algèbre complète, c'est à dire où les opérateurs générateurs engendrent complètement l'algèbre, un morphisme relationel contient l'isomorphisme de base, mais il peut contenir d'avantage d'arcs.
Supposon un lien supplémentaire `lambdaRtheta`
---- 18 juillet 2026 ----
Les opérateurs de mêmes arités peuvent être interverti. Et les opérateur d'arité superieure à 1 peuvent permutter leurs arguments. L'ensemble engendré de ces transformations bijectives sont appelé les symétries de premier niveau. Exemple :
De la même façon que le regroupement de tous les ensembles ne constitue pas un ensemble (car cela entraine le paradoxe de Russel "L'ensemble des ensembles ne se contenant pas se contient-il ?"). Le regroupement des algèbres de signature {a,b,f(.,.),g(.,.),h(.,.,.)} se constitue pas un ensemble. On parlera de catégorie des ensemble. De m^me on parlera de catgérie des algèbres de signature {a,b,f(.,.),g(.,.),h(.,.,.)}.