Theories egalitaires dans les Langages sur types de graphes

Algebra Universalis, 10 (1980) 300-332 Birkh/iuser Verlag, Basel

Theories egalitaires dans les Langages sur types de graphes*

GEORGES BLANC

O. Introduction

Aprbs que le langage des cat6gories ait enrichi une partie importante des math6matiques, c'est le concept m6me de cat6gorie qui para]t ~tre depuis quelques ann6es d'un apport important en logique alg6brique, logique intuition- niste, fondement des math6matiques. I1 appara~t pourtant que les propri6t6s dites de cat6gorie, ne peuvent ~tre formellement envisag6es d 'une fagon efficace dans les langages et th6ories du premier ordre classiques. La description par langages et theories classiques 6tant de conception ensembliste, alors que l 'essence des propri6t6s de cat6gorie est plut6t de configuration graphique.

L'6tude simple de la th6orie 616mentaire de cat6gorie [G. Blanc, 2] conduit remarquer que la notion d'6galit6 d 'objets est h rejeter sous toutes ses formes, si l 'on veut disposer d'un sens de formules vraiment appropri6 ~ l'utilisation des th6ories de cat6gorie; ce sens de formule est par exemple reconnu par P. Freyd en "Diagrammatic properties" [P. Freyd, 6]. On est donc conduit d~s l 'origine (6tude de la combinatoire d'6criture), ~t consid6rer que les relations de configuration existantes entre ftbches et objets, ne sont pas des propri6t6s de cat6gorie, mais des r~gles de syntaxe, dont il faut tenir compte formeIIement dans l '6criture m6me des propri6t6s de cat6gorie.

Une construction de langage appropri6: les langages sur graphes, se trouve d6finie dans [G. Blanc, 1]; c'est ensuite un syst~me.d6ductif formel des th6ories sur graphes qu'il faut envisager, et qu 'on trouvera darts [C. Rambaud, 9,10] avec en particulier un th6or~me de compl6tude de ces th6ories dans [M. R. Donnadieu et C. Rambaud, 5].

Ces th6ories sur graphes ne sont toutefois pas 6galitaires, et constituent une

* Ce travail doit son origine et son d6veloppement, aux pr6occupations de recherche qui animent le groupe de "Logique et th6orie des cat6gories," dirig6 par le Professeur A. Preller h I'U.E.R. de Luminy (Universit6 d'Aix-Marseille II).

Presented by J. D. Monk. Received February 10, 1978. Accepted for publication in final form October 5, 1978.

300

Vol. 10, 1 9 8 0 Theories egalitaires dans les langages sur types de graphes 301

premiere 6tape dans l 'approche des th6ories g6n6rales sur cat6gorie, que nous nous proposons d'6tudier ici, et qui sera 6galitaire en un sens appropri6. I1 en r6sulte que ce travail ne peut trouver sa place, qu'~ la suite des r6f6rences [1], [9], [10] cit6s ci-dessus. On pourra toutefois trouver une version complete et technique dans [G. Blanc, Th~se de doctorat, 3].

Dans les num6ros 1 et 2, nous rappelons sur l 'exemple des cat6gories cart6siennes closes [Mac Lane, 8] les principales terminologies propres aux langages sur graphes, les principales notions et propri6t6s propres aux th6ories sur graphes, en particulier les axiomes et r~gles logiques. Un cas particulier mais essentiel des th6ories sur graphes, 6tant la th6orie de cat6gorie (n ~ 3).

Les num6ros 4 et 5 abordent eux le cas 6galitaire et beaucoup plus g6n6ral des th6ories sur cat6gorie.

Enfin dans tout ce papier, graphe doit 6tre compris pour graphe orient6; un graphe orient6 6tant la donn6e de deux ensembles disjoints F et S appel6s respectivement ensemble des fl~ches et ensembles des sommets (ou des objets) et de deux applications appel6es source et but de F dans S.

1. Langages Foncfionnels sur Graphes

Ainsi qu'il en est par exemple pour les langages de th6orie des types, la combinatoire formelle des langages sur graphes est tr~s technique, et les r6sultats, souvent intuitifs, ~ obtenir pour la coh6rence des notions sont parfois tr~s laborieux. Nous nous contenterons donc de rappeler en termes simples les notions usuelles des langages sur graphes, sur un exemple.

Un langage sur graphe sera 6videmment d6j~ un langage ~ deux types de variables

Les variables objets: X, X' , X1, Y, Z, etc . . . . Les variables fl~ches: x, x', x~, y, z etc . . . .

1.1 Si un langage fonctionnel du premier ordre classique est la donn6e de symboles fonctionnels f~, auxquels sont attach6es des r~gles d'utilisation: l'arit6, qui n'est en fait qu'un entier ni d6crivant la configuration (la quantit6, darts ce cas) des variables sur lesquelles doit s'utiliser le symbole fl ; un langage fonctionnel sur graphe, est constitu6 de suites fonctionnelles tr = (P1, P2 . . . . . Pm ; f l , f2 . . . . . f,) , couples de suites finies de symboles, les premiers appel6s symboles fonctionnels ob]ets, les seconds symboles fonctionnels fl~ches, auxquelles sont attach6s l'aritd: un graphe _A~ de configuration des variables sur lesquelles ces syrnboles doivent

302 G E O R G E S BLANC ALGEBRA UNIV.

s'utiliser, et le type: un graphe _~,,, extension de A,, ddcrivant la configuration des symboles de tr les uns par rapport aux autres, et par rapport aux 614ments de A=.

Signalons que dans les r6fdrences [1], [3], [9], [10], le graphe ici not6 fi~, est aussi not6 mais pas nomm6, et que ce qui dans ces articles est appel6 type sera ici d6sign6 par prototype (cf. 1.4).

1.2. Consid6rons ainsi l'exemple de la structure de cat6gorie cart6sienne ferm4e [Mac Lane, 8], dans lequel on souhaite utiliser dans le langage: (a) un symbole de produit direct X x Y, ainsi que les projections canoniques, (b) un symbole d'exponentiation X Y, ainsi que la fl~che d'6valuation canonique X v x Y--> X, (c) un symbole d'adjonction cart6sienne, associant h chaque fl6che X x Y--> Z, la fl~che correspondante X--> Z Y, (d) et enfin pour avoir un langage refl6tant suffisamment la complexit6 combinatoire du cas g6n6ral, un symbole de produit fibr6 x * y, avec les projections canoniques.

Le langage fonctionnel sur graphe Se~f correspondant tl cette structure, est donc constitu6 des trois ensembles 2~, N2, "~3 de suites fonctionnelles suivantes:

1~ XI comprend les quatre suites fonctionnelles suivantes: [ x/Y 1

(a) tr~ =( ; o), d'arit6 le graphe A~: .. x X'~Z

avec pour type, le graphe A ~: /'~Z I Xoy et correspondant h la composition des fl~ches.

(b) (r~ = (I ;), d'arit6 le graphe A~ r6duit ~ l'objet ['X'],

avec pour type, le graphe fi~: l• .x, -• et correspondant ~ la fl~che d'identit6.

(c) o'~ = (P; Pl, P2), d'arit6 le graphe A~ r6duit aux deux objets [X[X[~

avec pour type, le graphe fi,~:

P(X,Y)

pI(XY/ ~P2(xY) x Y

et correspondant au produit direct muni des projections.


(d) o'4 ~ = (/-/; "/1"1, "/1"2) , d'arit6 le graphe A4~:

x Y \ / z

avec pour type, le graphe fi~]:

/-/(x.y)

x Y

z

et correspondant au produit fibr6 muni des projections. 2 ~ ~2 comprend une seule suite fonctionnelle:

o-~ = (E; e), d'arit6 le graphe A~ z r6duit aux deux objets

avec pour type, le graphe AlZ:

P(E(X.Y),Y) E(X.Y)

e(X.Y) 1

X Y

et correspondant h l 'exponentiation muni de la flbche d'6valuation.

30- ~3 comprend une seule suite fonctionnelle:

cr~=(;-r) , d'arit6 le graphe A31: t P(X,u x Z l

avec pour type, le graphe f i3: [ x r(x) L E(Z,Y)

I P(X,Y) x Z

et correspondant ~t l 'op6ration d 'adjonction cart6sienne.

1.3. On se doit de remarquer que les graphes A et fi, associ6s h chaque suite fonctionnelle, se compliquent en m6me temps que se d6crit le langage m6me. C'est 6videmment cette difficult6 qui rend la g6n6ralisation tr~s technique. A 3 et fit~ par exemple utilisent en fait des termes du langage r6duit h 21 et 2~ 2. I1 y a

3 0 4 GEORGES BLANC ALGEBRA UNIV.

donc une hi6rarchie n6cessaire dans l ' introduction des suites fonctionnelles, et un langage fonctionnel sur graphe ~ sera ators la donn6e d 'une suite finie (ou infinie, sans que cela pose de s6rieux probl~mes), d 'ensembles 2~t, ~ 2 , - . - , ~n, de suites fonctionnelles; on appelle hauteur de ~, le nombre n d'ensembles de suites fonctionnelles, et si p e s t un entier inf6rieur ou 6gal ~t n, on note ~o le langage fonctionnel rdduit h E l , 2 2 . . . . . Xp, avec m~mes r~gles d'utilisation des symboles.

1.4. En fait la d6finition pr6cise de langage fonctionnel, conduit ~ introduire, non pas comme on l'a fait (dans un but de simplification) l'arit6 A= et le type fi~ pour chaque suite fonctionnelle tr = (P~ . . . . . Pm ; fl . . . . . f ,) , mais plus pr6cis6ment l'arit6 A~, de 00, et le prototype D,~ de o-: un graphe extension de A~, correspondant au type A=, mais dans lequel les nouveaux symboles introduits sont remplac6s par des variables Z1 . . . . . Zm, Zl . . . . . zn, en correspondance biunivo- que par une indexation avec les symboles constituant 00.

Ainsi par exemple dans le langage ~ a envisag6:

0-3 ~ est d'arit6 A~ = A~ d6j~ cit6, et de prototype

D~ = D31 le graphe:

71

Y\ x u

0 ~ est d'arit6 A,, = A 2 d6j~t cit6, et de prototype

D~ = D~ le graphe:

P(ZI.u Z1 z,J • Y

On est conduit g introduire la notion de prototype Do, dans le but de permettre que les r~gles d'utilisation des symboles de o- (d6crites par l'arit6 et le prototype) soient des graphes d 'un langage plus simple que celui dans lequel sera envisag6 00.

1.5 La notion de configurations possibles de variables, qui, dans le cas de langages classiques, se r6duit simplement ~t leur nombre cardinal, est en langage sur graphe ~ repr6sent6e par la notion de ~-graphes, ou graphes du langage. Ces graphes sont intuitivement toutes les configurations graphiques finies que permet

Vol. 10, 1980 Theories egalitaires dans les langages sur types de graphes 305

un tel langage. En notant X x Y pour P(X, Y) , et X v pour E(X, Y) , p o u r rendre

plus expressives Ies expressions, les deux graphes G~ et G2 ci-dessous, sont des

s ~-graphes:

G I :

XxY

y X'~ z

-z

6 2 :

Xx Y x -Z

x ( x , y ) Iy

//(x.y) ~ z x x

Remarquons une n6cessaire hi6rarchie entre les fl~ches libres d 'un ~ -g raphe . Dans G2 par exemple, la fl~che z ne peut 8tre introduite qu'apr~s Ies fl~ches x et y. On appelle rang d'un ~-graphe G, le nombre de variables ft~ches apparaissant

dans G. Pour une variable objet X (resp. variable fl~che x), on dit que X est libre dans

G (resp. x est tibre dans G), si X est un sommet isol6 de G (resp. x est une fl~che de G), qui n 'apparMt dans aucun autre te rme obje t ou fl~che de G.

On appelle ~g-graphe strict, un ~ - g r a p h e dont les fl~ches et les obje ts isol6s ne

sont que des variables. G1 est strict, G : ne l 'est pas, dans notre exemple . On note G~ le graphe strict associ6 & G, par suppression de " te rmes inutiles." 1.6. La notion de terme t(xl . . . . . x~) utilisant des variables prises parmi

{x 1 . . . . . x~} des langages classiques du premier ordre, correspondent en langage sur graphe, ~ la notion de ~-terme objet ou ~-terme fl~che, t(G) sur le 2g-graphe G. Ainsi par exemple les assemblages t~ et tz ci-dessous, sont respect ivement un

~ - t e r m e objet sur G~ et un ~ - t e r m e fl~che sur Gz (exemple de ~ d - g r a p h e s

ci-dessous 1.5):

tl : [ (X x X) m~(~)'y)] x Z

t2 : "r(e(X, X x Z) o T(x))

On est en mesure dans un langage sur graphe, d 'associer ~ chaque ~ - t e r m e fl~che t(G) sur G. ,lcux .~-terrnes objets sur G appel6s respect ivement source et but de t et not6 .~ /~ A2(t).

( J

306 GEORGES BLANC ALGEBRA UNIV.

Ainsi pour l 'exemple ci-dessus, le lecteur v6rifiera qu'on a "naturel lement":

~21(t2) = X ( x x z ) et ~2A2(t2) = (ZY)Xxz

compte tenu des prototypes D~, de chaque syrnbole fonctionnel utilis6s. Ceci permet de consid6rer pour chaque ~-graphe G, le graphe total not~ r

de tousles ~- termes construits sur G qui est, lui, en g6n6ral, infini, et jouant le r61e de la classe Ter (Xl . . . . . x,) des termes construits sur les variables x~ . . . . . x~ dans un langage classique.

1.7. La notion de substitution de termes h des variables, qui dans le cas des langages classiques se traduit par une application d6finie sur {Xl . . . . . x,,} ~t valeur dans Ter (yl . . . . . Ym), se traduit en langage sur graphe par la notion de ~ - homomorphisme entre deux .~-graphes H et G. Un Jg-homomorphisme de H vers G 6tant un homomorphisme h de H dans ~ (G) , graphe de t o u s l e s termes construits sur G, qui doit coincider sur les termes t, objet ou fl~che de H, avec la substitution dans t de h(u) ~ u pour chaque variable fl~che ou variable objet u de H qui figure dans t.

Ainsi par exemple en consid6rant les ~a-graphes G~ et G2 (voir 1.5) l 'homomorphisme h~ d6fini sur G~ par:

ht(X) = X z, h~(Y) = lI(x, y), hi(Z) = II(x, y),

h l ( X x Y ) = X Z x H ( x , y), ht(Zy)=(l-i(x, y))n(x.~).

h~(x) = pa(X z, H(x, y)), ht(y) = r(p~(H(x, y), I-I(x, y)))

hi(z) = t (X z)

est un ~-homomorphisme de G1 dans G 2.

Un ~-homomorphisme h de G~ dans G 2 6tant fix6, il en r6sulte m6me un homomorphisme de ~(G~) dans ~(G2), not6 ~ (h ) el qui est obtenu par substitution dans tous les .~-termes sur G1.

De fagon 6vidente, dans l 'exemple envisag6 ci-dessus:

~(hl)( /70-(x) , y)) = II(r(p2(X z, 1-l(x, y))), ~'(pl(n(x, y),/-/(x, y))))

1.8. A chaque suite fonctionnelle o- d 'un langage sur graphe ~ est associ6 un ~-homomorphisme appel6 a jouer un r61e important et not6 p,, de D,, vers A~, qui correspond en tant qu'homomorphisme, ~ la bijection de D~, sur fi,= d6j~t 6voqu6 en 1.4. p,, coincide en particulier avec l'identit6 sur le s A~ contenu dans D=.


Par exemple (1.4) 0 =P=l est d~fini sur D3 x par

o ( X ) = X, 0 ( Y ) = Y, p(Z) = P(X, Y)

O(ZO = p~(X, Y), O(z2) = p2(X, Y)

1.9. Soit P(resp. f) un syrnbole fonctionnel obje t (resp.fl~che) d e la suite fonctionnelle o-, et h u n .~-homomorphisme de A~ vers G un ~ - g r a p h e . On note alors P(h) (resp. f (h ) ) le terme "cor respondant" sur G. Plus p r rc i s rmen t , si xx . . . . . x~ drsignent les variables fl~ches de A~, X1 . . . . . Xq les variables objets de A , qui sont isol6es en tant que sommets de A~ et n 'apparaissent dans aucun autre terme 616ment de A~ (variables tomlement isol~es de AT, dans [G. Blanc, 1]), alors P(h ) resp. f ( h ) d r s i g n e l 'assemblage:

P ( h ( X O . . . . . h (Xq), h(xO . . . . . h(xv))

(resp. f (h(X1) , . . . , h(Xq), h(x , ) . . . . . h(x~)).

En fait on a:

P(h ) = ~(h ) (P( Id~ . ) ) = ~(h)(p~ (Z))

(resp. f (h ) = fl(h)(P(IdA~)) = o~(h)(p~,(z)))

o~a Z (resp. z) d6signe une variable obje t (resp. fl~che) de D~ non dans A, . On s 'autorisera aussi la notation P(A~)(resp. f(Ar pour P ( I d ~ )

(resp. f(Id,~.)). Rrc ip roquement ~t chaque terme objet T (resp. fl~che t) sur G, au t re que les

variables de G, il correspond un et un seul triplet (cr, P, h) (resp. (o', f, h)) o~a o" est une suite fonctionnelle, P(resp. f) un symbole fonctionnel de o-, h un ~ - homomorph isme de A~ vers G. tel que T = P ( h ) (resp. t = f (h ) ) .

Ainsi par exemple (cf. 1.6):

t2 = r(h2) avec h2 de A 3 vers G2 (cf. 1.4 et 1.5) drfini par:

h2(X) = X (x• ha(Y) = X x Z, h a ( Z ) = Z v,

h2(x) = e(X , X x Z ) o r(x).

Lorsque nous parlerons de te rme sur un ~ - g r a p h e sans autre pr6cision, et nous noterons alors le plus souvent t = P(h) un tel terme, ils s 'agira aussi bien de te rme fl~che que de terme objet.

Cet te ~criture des termes sur (3, permet entre autre de d r t e rmine r une hirrarchie de complexit6 de ces termes, par un entier, le rang de t 6rant ~gal

308 GEO~OES BLANC ALGEBRA UNIV.

n + 1 s i n nest le plus grand rang des termes sur G constituant l ' image de h, lorsque t = P(h).

2. Formules et Theories sur Graphes

DI~FINITION 2.1.1. Un langage sur graphe ~ , est la donn6e d 'un langage fonctionnel ~ (voir w d 'un ensemble ~ de symboles distincts de ceux de ~ ' appel6s symboles relationnels, et la donn6e pour chaque symbole relationnel R, d 'un 2f'-graphe AR appel6 l'aritd de R.

On confondra dans les terminologies Sg et .T', parlant par exemple de ~ -g raphe au lieu de .Le'-graphe.

Si h d6signe un ~-homomorph isme d6fini sur AR, on d6signera par R(h) l'assemblage R(h(XO . . . . . h(Xo), h(xl) . . . . . h(xq)), off les Xi d6signent les variables objets totalement isol6es de AR (eft. 1.9), et x i les variables fl6ches de A~. On appelle alors R(h) formule atomique de ~s

2.2. Une formule dans un langage sur graphe ~ , est au sens le plus pr6cis, un couple (G, 4 ) d ' u n 2e-graphe G e t d 'un assemblage fini �9 de connecteurs logiques v, ], 3X, (3x: T~ ~ T2), et de formules atomiques. Pour des raisons de commodit6s, il sera utile d'utiliser une formule atomique particuli~re: un symbole de "v&it~" not~ V.

I1 va de soi que nous n'utiliserons pas syst6matiquement la notation (G, qb) pour une formule de ~ , nous parlerons plut6t de q~ une formule sur G, ou de G-formule 4, que nous noterons ~ ( G ) ou m6me simplement tp s'il n 'y a pas de risque de confusion lorsque le graphe G sur lequel on souhaite considdrer la formule est 6vident par le contexte.

DI~FINITION 2.2.1. Plus pr6cis6ment par induction sur l 'assemblage 4 : (a) ] ~ est une G-formule si et seulement si ~ est une G-formule (b) ~ v ~2 est une G-formule si et seulement si I ~ 1 e t gt2 sont des G-

formules (c) 3 X ~ est une G-formule si et seulement si X n'apparait pas dans G et gt

est une H-formule , off H est le .~-graphe G + X obtenu par adjonction ~ G d'un nouvel objet X.

(d) (3x: T1 ~ T2) ~ est une G-formule si et seulement si, x n 'appara]t pas dans G, T1, et T2 sont des .~-termes objets sur G, et ~ est une H-formule off H est le ~ -g raphe G + T1 ~ > T2 obtenu par adjonction ~t G des deux objets T1 et T2 (s'ils n 'y 6taient d6j~t), et de la nouvelle fl6che x de source TI et de but T2.


(e) R(h) est une G-formule si et seulement si h est un s de

AR dans G, (f) Enfin V e s t une G-formule quel que soit le graphe G.

2.3. Soit 4 une G-formule , on appelle variables libres de 4 , toutes les variables de G, et variables li~es de 4 , les variables ayant une occurrence dans 4

pr~c~drs du symbole "3" . La drfinition adop t re appelle quelques remarques par rappor t au sens de

formules des langages du premier ordre classique. Ainsi, par exemple , une variable ne peut pas &re libre et l ire dans une formule, de m ~ m e qu 'une occurrence de variable ne peut pas appara] tre sous deux quantifications superposres , comme par exemple dans la formule 3X(R(X, Y )v3XR(X,Z) ) , situation admise formellement en langage classique. Ceci ne constitue toutefois en aucune fa~on un handicap dans l 'utilisation; autant dans l 'utilisation conceptuelle des propr i r t r s , c 'est bien 6vident, que dans l 'utilisation formelle en drduct ion, comme nous le montrerons le plus rapidement possible en thror ie sur graphe. La drmonstrabil i t6 d 'une formule, ne d~pendra pas des noms de variables quantifires. On aura donc tout loisir de changer ~t tout momen t les noms de tetles variables, et nous ne nous embarrasserons, le plus souvent, m~me pas de telle

prrcaution. Cette notation peut aussi pr6senter parfois quelques petites commodi t rs ,

comme par exemple le fait de considrrer ( ( 3 X 4 ) v ~ ) comme une G-forrnule implique nrcessairement que si X apparal t dans gt, il ne peut y &re que li6.

On retrouve toutefois dans notre sens de forrnules, les notions et proprir t~s classiques sur les assemblages formels que constituent les formules, comme par exemple la notion de sous-forrnule.

Nous utiliserons les abrrviat ions classiques:

- - 4 A ~ pour 1(14v1 ) - 4 - - - ~ pour 1 4 v ~ - 4 ~ - - ~ q t pour ( 4 - - - ~ q t ) A ( ~ - - ~ 4 )

- V X 4 pour ] 3 X ] 4

- V ( x : T1 ~ Tz) pour ] 3(x : T1 --~ Tz)] 4

et si I - - { i l . . . . . i.} est un ensemble fini d' indice

- / k 4 i pour 4 i A 4 i 2 A ' ' ' A 4 i .

- V 4 i pour 4 i v 4 i 2 v - . . v4~ .

310 G E O R G E S B L A N C A L G E B R A U N I V .

- 3 L4~, (resp. V s pour 3X~, �9 �9 �9 3 X ~ (resp. VX~ �9 �9 �9 VXt q~)

�9 i i ~ i - 3 (~ : T't ~ T2)q b, (resp. V (~ : T1 T2)4~), pour 3(x~, : T~, ~ Tk) - �9 - i i

3(x,.: T} --> T~)qb (resp. V(x~, : T~, --> T~,) �9 �9 �9 V(x~ : T~- ---> T~)~) .

Ainsi que le fait formellement la logique alg6brique [Halmos 7] nous serons plut6t conduits h utiliser souvent une notation globale de quantification, au lieu de

quantifications individuelles. Soit ainsi H un ~-sous-graphe de G u n 5f-graphe, et 4~ une G-formule . Nous

utiliserons la notation 3HG4~ ~ou 3 ,4~(G) (resp. V~rG4~ ou Vrq4~(G)), pour d6signer ce qui est intuitivement la quantification des variables de G non dans H.

3HG~ ~tant alors une H-formule

Bien 6videmment l 'assemblage 3HG4~ d6pend de la num6rotation (dans l'indice de construction) des variables de G non dans H, et dans cette notation, nous supposerons toujours une num~rotation choisie. Mais nous pourrons aussi, 6videmment, montrer que dans la mesure off l ' interd6pendance des variables dans G est respect6e, les diff~rentes formes qu'on peut obtenir de l 'assemblage 3HG~b restent 6quid6duites dans les theories sur graphes.

2.4. Soient �9 une G-formule et h un ~ -homomorph i sme de G vers H. On montre alors que si aucune des variables de H n'est li6e dans 4 , (on dira alors que h est substituable dans q~), l'assemblage not~ 49(h), obtenu par substitution des termes h(X~) (resp. h(xj)) ~ chaque variable objet Xi (resp. fl~che xj) de G apparaissant dans 4~ est une H-formule.

I1 sera toujours sous entendu lorsque nous utiliserons la notation ~ ( h ) que h est substituable dans ~b.

Nous nous autoriserons aussi comme cas particulier de ces substitutions la notation classique ~ x [ T ] (resp. ~b~[t]) si qb est une G-formule avec G = G ' + X (resp. G = G' + 7"1 -~ 7"2) T (resp. t) un .~-objet (resp. une ~-fl~che de source T1 et de but "/'2) sur G'. La formule ainsi obtenue 6tant alors une G'-formule.

2.5 Thdories sur graphes

Dt~FINITION 2.5.1. On appelle th~orie sur graphe, la donn6e d 'un langage sur graphe, et d 'une classe de formule ~ de ~ , qu 'on appelle axiomes non logiques de ~.


Les formules de s que nous appellerons thror~mes de ~, seront obtenues suivant la mr thode classique par la notion de drmonstrat ion dans ~g, ~ I'aide d'axiomes et de r~gles fixrs, dites logiques que nous allons d6velopper, et des axiomes non logiques de cr

I1 est d~s maintenant tr~s important de percevoir le r r le du ~ -g raphe G de "configuration des variables" dans la notion de drduction. En effet, la situation est comparable ~ celle des Theories de types dans laquelle on n ' impose pas systrmatiquement 'Texistence d'individu" pour chaque type de variable [Boileau, 4], et, ofa dans les Throries "~ la Gentzen" on doit par exemple considrrer les srquents ( ~ ~ ~ ) ....... ~, indicirs par les variables libres sur lesquelles on souhaite considrrer la formule.

Ainsi par exemple, il faudra bien admettre qu 'on puisse avoir pour H c G, c ~ q~ sans avoir ~ ~ pour une H-formule ~ qui soit aussi une G-formule; ce sera en particulier le cas si ~r est G-contradictoire [Rambaud, 9, 10] comme peut l '6tre par exemple la throrie de Topos non d r g r n r r r e (i.e. 0 ~ 1) pour le .~-graphe 1 -~ 0.

Le syst~me d'axiome et de r~gles logiques se distinguera en deux syst~mes (par commodit6 de prrsentation). Le syst~me propositionnel SPL et le syst~me prrdicatif SPF. C'est en fait l 'adaptation au langage sur graphe du syst~me de Henkin [Schoenfield, 11].

I. Syst~me SPL, pour chaque ~ -g raphe G -Ax iome de tiers exctu: (ATE)

~ff ] �9 v �9 pour chaque G-formule ~.

-Rkgle d' extension: (RE) Si ~ �9 alors ~ - ~ v �9 pour chaque G-formule q~ et -R~gle de contraction: (RC) Si ~ - � 9 v q~ alors ~-q~ pour chaque G-formule ~. -R~gle d' associativit~: (RA) Si ~ - q b v ( ~ v 0 ) alors ~ ( ~ v g t ) v 0 pour chaque G-formule ~, ~ , 0 -R~gle de coupure: (RCO) Si ~- �9 v ~ et ~ ] q~ v 0 alors ~ ~ v 0 pour chaque G-formule ~, ~, 0 -R~gle d'extension de graphe: (REG) Si ~ �9 alors ~ ~ pour H c G e t q~ formule sur H et G.

II. Syst~me SPF -Axiome d'existence d'ob]et: (AEO) ~ 3 x v - Axiome d'introduction existentielle: (A!E)


Pour chaque ~ -g raphe H, sous-graphe commun ~t G et G, h : G ~ G u n

~g-homomorphisme coincidant sur H avec l'identit~, et 49 une G-formule .

49(h) ---, 3~G49. - Rkgle d' introduction existentielle: (RIE) Pour chaque H c G, 49 formule sur G, 1/I formule sur H et G,

Si ~G 49 ~ gt alors ~ 3nG49 ~ gt

2.6. Commentaires sur ce syst~me -L ' in t roduct ion de (AEO) est nrcessaire dans la mesure o~a, si la logique du

premier ordre classique peut drduire 3y (x = y) h l'aide de (AIE), il n 'en est pas de mrme dans notre syst~me. (AIE est ici intuitivement plus faible dans la mesure ob la formule 3 ,G49 apparaissant dans l 'rcriture de l 'axiome, y reste considrrre comme une G-formule.

-Nous supposons 6videmment dans l ' rcriture mrme de l 'axiome AIE, que les variables de G non dans H ne sont pas dans 0 , elles sont en en effet quantifires

dans la formule. -Remarquons enfin dans l 'rcriture de (RIE) que le fait que gt soit une

formule sur H et G] nrcessite que les variables de G non dans H n'apparaissent pas dans gr par notre drf ini t ion-mrme de formule.

On dispose de rrsultats essentiellement analogues ~ ceux des throries forrnel- les du premier ordre classique dans les throries sur graphes, comme par exemple un th~or~me de substitution:

THt~ORI~ME 2.6.1. Soit 49 une G-formule et h : G ~ G un ~ -

homomorphisme substituable dans 49. Si q ~ 49 alors ~g~ 49(h).

On dispose 6videmment d 'un thror~me de tautologie pour les formutes sur un graphe G fixr. On dispose aussi d 'un thror~me de complr tude pour les throries sur graphes [M. R. Donnadieu, Ch. Rambaud; 5].

3. Theorie de Categorie

Nous aurons dorrnavant ~ utiliser la thror ie sur graphe particuli~re, qu 'on notera q~, de langage ~f,, et qu 'on appellera th~orie de cat~gorie, la thror ie

suivante: (a) ~c comprend deux suites fonctionnelles o-1, o'2, et un symbole relationnel

dit d 'rgali tr , not6 " = ."

Vol. 10, 1980 Theories egalitaires dans les langages sur types de graphes

o-~ = ( I ; ) d 'ar i t6 le g raphe r6dui t ~ un seul ob je t : [ ]

e t de p ro to type r6duit ~ une seule fl6che: Ix •

o'2 = ( ; ~ le graphe r6duit h deux fl~ches: [x x ~ u

e t de p ro to type le g raphe ~ trois fl6ches :

-• Y -Z[

l

313

I I Le symbole d '6gali t6 . . . . . - 6 tant d 'ar i t6 le g raphe : [ x ~ u [

I I

(b) Les ax iomes non logiques de cr 6 tant :

(Nous ne pr6cisons pas les g raphes 6vidents sur lesquels sont cons id6r6es ces formules , bien que leur r61e reste, rappe lons- le , essentiel syn tax iquemen t ) .

A x i o m e d 'uni t6 (AU) : I ( X ) o x = x /x x o I ( Y ) = x

A x i o m e d 'associat ivi t6 (AA) : x o (y o z) = (x o y) o z

A x i o m e d ' ident i t6 (AI) : x = x A x i o m e d '6gali t6 fonct ionnel le ( A E g F ) :

x = x ' A y = y'---~ (x o y = x ' o y ')

A x i o m e d '6gali t6 re la t ionnel le ( A E g R ) :

x = x ' ^ y = y ' ---~ (x = y ~ x ' = y').

On m o n t r e ~v idemmen t dans cr c que le symbole d '6gali t6 "es t u n e re la t ion ' 6qu iva lence . "

Nous aurons souvent ~t consid6rer dans des extensions de qgc les fo rmules suivantes:

(a) ( x o y = I ( X ) ^ y o x = I ( Y ) q u ' o n no t e r a J(x , y), fo rmule sur le g raphe {X ~ Y}, q u ' o n lira 6 v i d e m m e n t " x e t y sont des i somorph i smes r6c ip roques . "

(b) 3(y : Y---~ X ) J ( x , y) q u ' o n no te ra J ( x ) , fo rmule sur { X - ~ Y}, e t q u ' o n lira 6v idemment : " x est un i s o m o r p h i s m e . "

Enfin dans une extension de qgc nous ut i l iserons les abr6via t ions c lass iques de th6or ie ~galitaires:

3! (x : T1 --~ T2)q b

314 GEORGES BLANC ALGEBRA UN/V.

p o u r

r3(x: T1 ---> T2)~ AV(X : T1 "-* T2) V(x': TI ~ T2)(q ~ A q~x [X'] "-* X = X')]

Plus gdnrralement soit 3(~ : T'I --~ T~2)~ une G-formule. Si chaque y~ n 'apparalt pas darts les sources et but de chaque Yi, nous 6crirons

3!(Yi : Tix "-'> Ti2) r pour:

3(,y, : 7~1 -- , 7-'~)a, ^ v ( ~ , : Z'~ ~ T'~) V ( ~ ' : 7~ --, 7 ~ ) [ ~ ^ a~c~0Ey'] ~ �9 y, = y ' ]

Nous n'aurons dorrnavant dans les paragraphes suivants, qu'~t nous intrresser des throries qg extensions de c@ c.

4. Extensions Fonctorialisees de la Theorie de Categorie

4.1. Apr~s les syst~mes propositionnels (SPL), et pr~dicatifs (SPF) ~tudirs dans les throries sur graphes, c'est surtout l 'aspect de systbme 6galitaire que nous allons devoir envisager darts sa grnrral i t r .

En Iangage classique, de pensre ensembliste, le " rappor t idral" qui puisse exister entre deux situations de variables (xl . . . . . x,,) et (Yl', . . . . Yn) de mrme configuration (c'est-h-dire dans ce cas, toutes deux indexres par n) c'est 6videmment l 'rgalitr, exprimre par la formule A~,~, xi = y,, qu 'on pourrai t con- venir de noter E(xl . . . . . x,, ; Yl . . . . , y,) ou mrme E(n, n'), avec n 'une copie de n ={1, 2 . . . . . n} formule drfinissable dans le langage.

En thror ie sur catrgorie, le " rappor t idral" qui puisse exister entre deux configurations de variables G, et G ' une copie du ~ - g r a p h e G, est 1' "isomorphie naturelle" interne dans la thror ie (comme par exemple l ' isomorphie de deux variables objets pour le catrgoricien), et qui s 'exprimer a donc par une formule drfinissable dans le langage, qu 'on notera E(G, G').

Cette dernibre formule se drfinira essentiellemen]t par l ' idre de base suivante: Dans les throries sur catrgorie, chaque symbole fonctionnel objet , (et done

aussi chaque terme objet sur un ~-graphe) , transporte implicitement avec lui, un nora d' "isomorphisme naturel ," drduit de chaque "isomorphisme naturel" de son

aritr. Malheureusement cet isomorphisme ne peut pas toujours 6tre nomm6 formel-

lement par un symbole du langage. La contrainte d'utilisation n ' r tan t pas purement graphique. I1 faudra done se donner la possiblit6 de caractrriser un tel " isomorphisme naturel ," par des propr i r t rs formulables dans le langage.

En fait les proprir t rs caractrrisant pr rc is rment ces notions d' "isomorphisme naturel ," ne sont pas uniformes. Tan t r t cet isomorphisme n'est pas nomable dans le langage, mais jouit d 'une propr i r t rs de commutativit6 qui le caractrrise, tant6t


il ne jouit d 'aucune propri6t6 particuli~re, si ce n'est d '&re d6j~ nomable dans le

Iangage.

4.2. Illustrons cette remarque h l 'aide de l 'exemple de la structure de cat6gorie monoidale ferm6e [MacLane, 8], exemple que nous utiliserons jusqu'5 la fin de l'article. Une cat6gorie monoidale ferm6e, est la donn6e d 'une cat6gorie C, d 'un bifoncteur not6 | sur C, d'isomorphismes naturels o~, h, 3' permet tan t de d6crire une "associativit6," une "commutativit6 de l 'op6ration" | et le r61e "uni taire" d 'un objet constant e(donn6 dans le langage). On impose enfin de plus pour chaque objet X de C l'existence d 'un adjoint h droite du foncteur ( - | X ) : C ~ C .

I1 est ais6 d'imaginer une langage sur graphe naturel pour cette structure qui r6duise en particulier l 'existence de l 'adjoint au premier ordre par une suite fonctionnelle d' "exponentiat ion."

On notera ~mf ce langage, signalons par exemple les trois suites fonctionnelles

0-1 = ( | ;), 0"2 = (; | 0"3 = (E; e) de .~mf.

o"1 d'arit6 le graphe A 1 r6duit ~ deux objets

de prototype le graphe D1, r6duit aux trois objets I X Y Z[

d ant ,e graphe A2

x

de prototype le graphe D2: X'

x g x '

X"

o-3 d'arit6 le graphe A 3 r6duit h deux objets

z0Y

u x

dans lequel le couple (Z, z) correspond intuitivement an couple universel d6finissant l 'adjoint ~ droite du foncteur ( - | Y).

De marne que nous notons X | Y au lieu de | Y ) nous noterons x | y pour | (x, y), et X v pour E(X, Y).

~me contient 6videmment d'autres suites fonctionnelles. Soit alors clans ~ les graphes G I : X x ~ y e t G~ une copie de

G I : X ' "" ~ Y].


I1 est naturel en th6orie de cat6gorie de consid6rer que ces deux "situations de variables sont 6gales," c'est-h-dire joueront exactement le m6me r61e" dans toutes les propri6t6s envisageables, si existent des isomorphismes Yl et Y2, respectivement de X vers X ' et Y vers Y', qui rendent le carr6 (y~, Y2, x, x') commutatif; rappelons que nous parlons de langages et de th6ories extension de ~c et ~c, th~orie de cat6gorie (voir n~ dans laquelle les concepts d'isomorphisme et de commutativit6 ont le sens classique.

De la m6me fagon consid6rons alors le ~ .~-graphe

J XOy z x " i G2: X z

Y

refl6tant lui aussi une certaine configuration des variables x et z, et consid6rons G~ une copie obtenue en substituant X', Y', Z ' , x', z ' , h X, Y, Z, x, z. On doit donc aussi se poser la question de savoir quand ces deux "situations de variables" doivent 6tre consid6r6es comme "6gales." Naturellement il faut qu'il existe quatre

isomorphismes Yl, Y2, Y3, Y4, entre les quatre objets respectifs de G2 et G~, rendant les deux carr6s construits ~ l 'aide de xx' et zz' commutatifs. Mais 6videmment en th60rie de cat6gorie monoidale ferm6e, ce n'est pas suffisant, il faut de plus que Y4: X | y z __> X ' | y ,z , soit de la forme y~ @ y, si YI : X ---> X', oh y d6signerait l ' isomorphisme de y z dans y,z,, caract6ris6 par la propri6t6 de

rendre commutatif le diagramme:

z| Y3 e-y _ Z.@ y.Z'

le(Y,Z) Y2 [ e(Y;Z')

Y Y

On constate donc qu'~t chaque terme objet du langage est attach6 un nom d'isomorphisme pour des "situations isomorphes" du graphe sur lequel il est

ddfini. Certains de ces isomorphismes ne jouissant d 'aucune propri6t6 caract6ristique si ce n'est d 'e tre d6j~ nomable dans le langage, c 'est dans notre

exemple le cas de Y4 = Yl ~ Y, d'autres n'6tant pas n6cessairement nomables, mais jouissant d 'une propri6t6 de commutativit6 qui les caract6rise enti~rement, c'est

dans notre exemple le cas de y. L 'exemple ci-dessus choisi, n'est peut &re pas des plus 6difiants, dans la


mesure oft on pourrait envisager une extension par d6finition de qgmf [G. Blanc, 3], dans laquelle on pourrait nommer l 'isomorphisme canonique de X v sur X 'v', d6duit d'isomorphismes X ~ X', Y---~ Y'. Un cas ne permettant pas pa r exemple, m6me dans une extension par d6finition, de nommer dans le langage l 'isomorphisme, serait celui de cat6gorie h 6galisateur, o- = (N; n) d'arit6 le graphe

Ix Y(, et de type le graphe

I x I Z z " X ~ Y ,

off N(x, y) doit 6tre pens6 comme l'6galisateur des fl~ches x et y, n(x, y) 6tant la

flbche d'6galisation. Nous devons donc donner la possibilit6, dans notre sens de th6orie g6n6rale

sur cat6gories, de privil6gier certains symboles fonctionnels fl~ches, cornme ayant la possibilit6, ~t l 'occasion de nommer des isomorphismes naturels; pour permettre fi l 'utilisateur, s'il le d6sire, l ' introduction, ~ priori, de foncteur. Plus pr6cis6ment" ce souci correspondra alors dans le texte, ~ la notion de couple fonctoriel formel

(D6f. 4.4.1) Remarquons enfin, que pour ne pas alourdir le texte, nous sommes limit6s

l ' introduction de multifoncteurs covariants. L' introduction plus g6n6rale de multifoncteurs simultan6ment covafiants et controvariants suivant les variables, ne poserait en plus que des probl~mes d'6critures.

4.3. Translat6 de .~-graphe Soit ~ un langage sur graphe, G u n 2g-graphe." On rappelle qu 'on note Ob (G) ou IGI (resp. Obv (G) ou IGI~) la classe des

objets (resp. des objets variables) de G.

DI~FINITIONS 4.3.1. Soit ~ une partie de Ob (G), on appelle translat6 de G sur /2 , tout ~g-graphe H ainsi obtenu:

H est constitu6 par: (a) le graphe G lui-m6me (b) une copie G ' disjointe de G, (on notera syst6matiquement t' le terme

correspondant sur G' t i t sur G), (c) par les fl~ches YT d'une famille {YT} de variables fl~ches index6e par /2,

telle que YT soit, dans H, une flbche de T vers T'.


On parlera de fl~ches de translation sur G pour les fl~ches YT, et de base de translation pour 1"2.

On parlera de translat~ total de G si 12 = Ob (G), et de translat~ variable de G

si Obv(G).

N O T A T I O N S 4.3.2. En vue de ne pas alourdir le texte nous serons oblig6s d'utiliser beaucoup d'abus de notation que nous allons essayer d'envisager d~s maintenant.

- On notera (G, G' ; YT) ou m~me (G; y,) lorsque le contexte le permettra, la base de translation 6tant suppos6e pr6cis6e, un translat~ de G.

On notera alors aussi ~ (G, G'; YT) ou r YT) une formule sur le translat~ envisag6.

- P o u r K c G on pourra noter (G, G'; Yu; zT) ou (G; Yu; Zr) un translat6 total de G avec {Yu} index6e par Ob (K) et {Zr} index6e par Ob ( G ) - O b (K).

Les probl~mes d'6criture pour les substitutions darts des formules sur des translat6s seraient aussi terriblement lourds h pr6ciser.

Si qb(G, YT) est une formule sur un translat6 de G, et h u n ~ -homomorph i sme de G dans H, on notera ( ~ ( G ; yv))h la formule obtenue par substitution de h(x)

x (resp. de h(x') tt x') pour chaque variable x de G (resp. x' de G'). La formule ainsi obtenue est aussi obtenue plus pr6cis6ment par substitution

du ~-hom0morph isme suivant: On consid~re le ~-graphe H = H t..I Im (h), et H ' une copie disjointe de H et

h' la copie correspondante de h, de G ' sur 4 ' ; on consid~re alors le graphe B otenu par r6union disjointe de H et /~' avec en outre des fl~ches YT de source h(T) et de but h'(T'). On consid~re enfin le ~ -homomorph i sme k de (G, YT) dans B d6fini, de fagon 6vidence par h sur G, h' sur G ' et l 'identit6 sur les variables Yr.

La formule que nous notons @(G; yr)h devrait alors exactement se noter �9 (GG'; y)k. Remarquons que le graphe B envisag6 ci-dessus n'est m~me pas un translat6 de / - I au sens oh nous l 'avons d6fini, mais la d6finition plus g6n6rale qu'il nous faudrait donner de translat6 pour ~tre plus coh~'rent, ne pourrai t qu'alourdir le texte. I1 suffira au lecteur d 'e t re vigilant sur les abus de notations, que nous nous efforcerons de pr6ciser.

Illustrons cet abus de notation sur un exemple: Soit G = Gz (notation, 4.2, page 19) un ~fmf-graphe, et soit He le ~mrgraphe

ci-dessous:

AQB B

A A

Vol. 10, 1980 Theories egalitaires darts les langages sur types de graphes

Soit h le ~ m r h o m o m o r p h i s m e de G2 dans / - /2 d6fini par :

h ( X ) = h ( Z ) = A @ B , h ( Y ) = A

h ( x ) = z | x, h ( z ) = u

Soit (G2; y], Y2, Y3, Y4) le translat6 total de G~ ci-dessous:

319

x| x �9 Z

u

et consid6rons enfin sur (G2; y~) la formule q~(G2; y~):

3(I) : Z ----> X ) : l ( w : X'--.--> Z ' ) ( J ( x o 1))A (V o Yl) o W = Y3)

Og J e s t d6fini au n~ page 16 alors la formule d6sign6e par (qb(G2:y~))h est

l 'assemblage:

3(v : A | B ---> A | B ) 3 ( w : A ' B ' .---> A ' B ' ) ( J ( ( z | x ) o v) A (V o Yl) o W = Y3)

consid6r6e c o m m e formule sur le graphe:

A@B (AOB)OA

(A' O ')

AOB B Z@X /

A'OB' II B'

z ' u ' x' A

Y2

A" A,(A'O B')

320 GEORGF_,S BLANC ALGEBRA UNIV.

-Remarquant enfin que les fl~ches de translation sont individuellement libres dans un graphe translat6, nous utiliserons fr4quemment des notations sommaires pour les quantifier. En particulier, nous ne les relativiserons pas ~ une direction, celle-ci sera d6termin6e par l '4criture-m~me de la formule.

Ainsi pour K c G e t q~(G; Yu; ZT) formule sur (G; Yu; ZT) on notera

3zr~b(G; Yu; za-) pour 3 (ZT: T'--> T')q~(G; Yu; zx) t~IGI--IK[

ou encore, avec de plus h un ~-homomorph isme de G dans H.

3~'T(q~(G; Yu; ZT)h) pour 3 (zT : h(T) ---> h'(T'))(dP(G; Yu; ZT)h) T~IGI--IKI

On remarquera dans cette derni~re notation, que bien que ZT soit index4e par un objet de G, c'est le nom d 'une fl~che de source un objet sur H.

DI~FINITION 4.3.3. Dans une extension ~r de cr c, on appelle formule de commutativit~, qu'on note Corn (GG'; YT) OU Corn (G; Ya'), sur le graphe (G; YT) la formule sur ce graphe conjonction g4n6ralis6e des formules

U ~ 1 7 6

pour chaque fl~che u de T1 vers 7"2 dans G lorsque T1 et T 2 sont dans la base de translation du translat6 (G; YT) de G.

4.4. Extension fonctorialis~e de c~c

Soit ~ un langage sur graphe.

DI~.FINITION 4.4.1. On appelle couple fonctoriel formel, un couple (P, f ) constitu6 par:

(a) un symbole fonctionnel objet P d'arit6 A # O (b) un symbole fonctionnel fl~che f d'arit6 B = (A; A ' ; ZT) un translat6 de A

tel que la source (resp. le but) du terme f(IdB) soit P(A) (resp. P(A')) (cf. 1.9)

N O T A T I O N 4.4.2. Nous nous autoriserons l 'abus de notation suivant: Soit toujours avec les notations de la d6finition ci-dessus un ~ -g raphe G extension de A, et (G, G'; YT) un translat6 de G qui soit aussi extension de B = (A, A ' ; ZT), on notera f(YT) la fl~che f(Ids) , lorsqu'il n 'y aura pas de risques de confusion. En particulier on s'autorise donc aussi h noter f(ZT) cette derni~re fl~che.


DI~FINITION 4.4.3. On appelle extension fonctorialis6e de c~c, toute extension c~ de cr dans laquelle on a distingu6 un ensemble F (~ventuellement vide) de couple fonctoriel formel, tel que pour chaque symbole fonctionnel P de ~(~) , l 'ensemble F(P) = {f [ (P, f) ~ b-} des couples fonctoriels formels de F de la forme (P, f) , soit fini.

Ainsi il est naturel par exemple dans la th6orie ~ a (voir 1.2) de cat6gorie cart6sienne ferm6e, de choisir F vide; et tout aussi naturel de choisir dans la th6orie ~m~ de cat~gorie monoidale ferm6e de choisir F = {(| |

Remarquons que l 'on pourrait tout aussi bien d6cider pour cCa que F contient le couple fonctoriel formel (X, _x), off _x d6signe le produit cartesian de fl~ches, mais ceci ne serait d 'aucune utilit6 comme nous le verrons par la suite, celui-ci se d6finissant dans le langage, ~t la difference du symbole @ de CCr~ qui lui est introduit ~ priori.

Remarquons enfin que suivant les observations de la fin d u n ~ 4.2, c'est plus pr6cis~ment de couple fonctoriel formel covariant, et d 'extension fonctorialis6e covariante que nous devrions parler.

Nous aurons souvent ~ utiliser vis-h-vis des couples fonctoriels formels, une formule particuli~re pour chaque suite fonctionnelle ~r d'arit6 A= du langage, sur le translat6 total (fix~; YT) de A= (w

Cette formule exprimera qu'un tel translat6 est "assez naturel" pour Ies couples fonctoriels envisag6s, en exprimant que les fl~ches de translation sont

""calcul6es les unes par rapport aux autres," dans la mesure off le langage le permet.

Posons d 'abord la d6finition:

DI~FINITION 4.4.4. Soit ~r (ou plus pr6cis6ment (~, F)), une extension fonctorialis6e de ~c- On d6finit alors pour chaque suite fonctionnelle cr de d'arit6 A, le formule Can= (YT) sur le translat~ total (fix; YT) de fix(w comme suit: Can= (YT) est la conjonction pour chaque symbole fonctionnel ob je t P de o-, des formules

fJ~r,)YP(A) = f(YT).

(on rappelle que par l 'abus de notation 4.4.2, dans f(YT) n'apparaissent en fait que des variables de translation index6es par des objets de A).

Remarquons que c'est uniquement pour pouvoir consid6rer cette formule que nous avons besoin de nous limiter ~ F(P) ensemble fini dans la d6finition 4.4.3.

322 G E O R G E S B L A N C A L G E B R A UNIV.

Ainsi, par exemple, dans la th6orie ~ de cat6gorie monoidale ferm6e, o0 l'on a distingu6 l'unique couple fonctoriel formel ( | | Si trl d6signe la suite fonctionnelle (@,), Can,, (YT) d6signe sur le graphe (fi,~,; YT)= la formule Y3 =

Y l | Y2-

, , ~ X g Y ,,,"~Y3 y V

x'o~ j ' Jy, .Jy

X' Y'

Mais la forme g6n6rale de la d6finition 4,4.4 permet 6videmment des situations plus complexes; supposons par exemple .~1 une extension du langage ~mf de cat6gorie monoidale ferm6e, et soit <to = (P, Q, R; q, r) une suite fonctionnelle de ,Lel telle que:

I P(x) "z~~ X ,x y q . . ~

Q(x)

P(x) O Q(x) m R ( x )

avec de fa~on 6vidente:

Suppons de plus que les couples fonctoriels formels distingu6s dans ~1, compren- nent outre ( | | les couples (P, f), (R, gl), (R, g2), 00 /, gl, g2 apparaissent

O. tit respectivement dans des suites fonctionnelles o-', tr", d'arit6s respectives:

A , =

I X x _y I

1~ 1 ~ I ~.. x �9 y

A " = X~r - - - -Y"

A " = A'.

Vol. 10, 1 9 8 0 Theories egalitaires dans les langages sur types de graphes

Dans ce cas Can~, (YT) d6signe sur le graphe (fi,~o, Y-r) ci-dessous:

/ X

x/4 X'

P(x) O(x)

~ " ~ O(x' q(x~'~Y) y' r(x) P(x') x ~ Y ' P(x)OO(x)" R(x)

. . q(') P(x')OO(x') r-'-7~--R(x')

323

la formule Y5 = f(xx', Yl, Y2)A Y4 = g~(xx', Yx)/x Y4 = g2( xx' , Y l, Y2)

4.5. Formules d'~quivalenoes en extensions fonctorialis~es

Nous supposons d6sormais disposer d 'une th6orie ~', extension fonctorialis6e de ~'c, on note ~ son langage et F la classe des couples fonctoriels formels distingu6s.

Notre probl~me est maintenant la d6finition dans le langage ~ , pour chaque configuration possible de variables (chaque ~-graphe) , d 'une formule qui tien- dra lieu d.' "6galit6" dans les th6ories g6n6rales sur cat6gorie; formule que nous noterons E q ( G ; y-r) associ6e ~ chaque translat6 total (G, G ' ; y r ) . Une telle formule exprimera que les fl~ches de translation Y'r, d6finissent un "isomorphisme naturel" clans la th6orie, des configurations G e t G'. Ainsi par exemple, dans te cas de la th6orie cr et pour le graphe G2 de cette th6orie envisag6e au w page 19, la formule Eq (G2; y~, .Y2, Y3, Y4) ne fera que formaliser l 'approche conceptuelle que nous avions faite dans ce paragraphe d 'une telle notion d' isomorphie.

Pour cette d6finition de sch6ma de formule Eq (G ; y-r), nous devrons introduire une autre formule associ6e ~t chaque terme objet T sur un Sg-graphe G, exprimant qu 'une fi~che de translation de source T e s t un "isomorphisme d6duit naturel lement" d 'une "translation par isomorphisme" donn6 sur les variables objets de G.

I1 s'agira donc pour chaque translat6 variable (d6f. 4.3.1): (G; y• chaque terme objet T sur G et chaque variable fi~che y, d 'une formule qu 'on notera NatT(G; Yx, Y) sur le translat6 de G U{T}, ayant pour base de translation (d6f. 4.3.1) la classe constitu6e par les objets variables de G, et l 'objet T. Ainsi par exemple si T d6signe le terme objet y z sur le graphe G2 6voqu6 ci-dessus, et si les fl~ches Yl, Y2, Y3 respectivement de X vers X', Y vers Y', Z vers Z' d6finissent un translat6 variable de G2, la formule Nat-r (G2; Yl, Y2, Y3, Y), exprimera que Y2 et Y3 sont des isomorphismes, et que y est l ' isomorphisme correspondant de y z sur y,z, (en terme habituels, il s'agirait de l ' isomorphisme y2 (y3-').


Nous devrons enfm d6finir simultan6ment une formule not6e C,~(yT) pour chaque suite fonctionnelle tr sur le translat6 total (fit~,; YT) de fi~. Cette formule n'est utilis6e qu'artificiellement pour permettre une d6finition inductive des deux types de formules pr6c6dentes, mais n'est d'aucun int6r~t conceptuel nouveau, puisque nous pourrons montrer (proposition 5.2.5) qu'elle est 6quivalente dans les th6ories sur cat6gories, ~ la formule Eq (fi,,~; YT)- N6anmoins ce type de formule est d 'un int6r6t technique fondamental, car il est indispensable pour la d6finition m~me des formules Eq (G; YT), en r6duisant la complexit6 des termes, permettant ainsi une construction inductive.

Nous allons donc, dans la d6finition suivante (4.5.1), construire simultan6ment trois types de formules:

(a) C~(yT) pour chaque suite fonctionnelle o', sur le translat6 total de fi~,

yT). (b) Eq (G; YT) pour chaque ~-graphe G, sur son translat6 total (G; YT)" (C) Natv (G; y• y) pour chaque terme objet T sur G, sur le translat6 de

G + T, avec pour base de translation IGIo t3{T}.

DI~FINITION 4.5.1. La d6finition se fait induction sur la hauteur p du langage (w telle que D~ soit un ~p-graphe, G un 2s T u n .~p-terme sur G.

(a) C~(yT) est la formule:

Eq (D~,; YT)O~ A Can~ (YT)

(b) Eq (G; YT) est la formule:

Corn (G; yT)A A NatT (O; Yx, YT) t~lG[

O~a {Yx} d~signe la restriction de {YT} aux objets variables de G. (c) On d6finit enfin NatT (G; Yx, Y) par induction sur le rang n de T (w

(i) Si T e s t une variable de G, la formule est:

J(y) A y = YT

(ii) Si T = P(h) = h#o(Z) ota P est d'esp~ce r et Z une variable de D~ non darts A~ (cf. 1.9), la formule est:

3 vu((C~(Vu))hA A Nath~y~(G;yx, Vy)Ay=Vz) U~tDI Y~IA~I~


On v6rifie alors facilement que l '6criture-m6me des formules Eq, C,, Nat, ne d6pend pas de la hauteur p du langage consid6re, ni du rang n du terme consid6r6.

Nous allons maintenant devoir d6montrer une suite de petites propositions, dont le but est de rendre l'utilisation de ces formules plus ais6e que ne l'est leur d6finition. Toujours dans un souci de ne pas alourdir un texte, parfois d6j~ tr~s lourd, nous nous autoriserons h ne pas faire figurer le graphe sur lequel les formules seront montr6es 6tre des th6or~mes de cr cela est d 'autant plus licite que la plupart des formules envisag6es contiennent dans leur 6criture m6me, le "graphe naturel" sur lequel elles sont consid6r6es.

Dans une simple extension fonctorialis6e cr de cr c, on v6rifie ais6ment quelques propri6t6s 616mentaires de ces formules d'6quivalences. Ainsi la proposition 4.5.1 ci-dessous qui pr6cise le comportement de ces 6quivalences vis-a-vis des restrictions ou extensions des configurations:

P R OP OS I TI ON 4.5.1. Soit H u n ~-sous-graphe de G, (7.T) u n e famille de variables fl~ches index~e par Ob ( G), (Zx) sa restriction aux objets variables de G, (YT) sa restriction aux objets de H, (Yx) sa restriction aux objets variables de H. Soit enfin U un terme objet sur H, alors:

~ r Z) ~ ~ N a t u ( G ; z x , z)

cr ~ Eq (G; zT) , Eq (H; YT)

I1 r6sulte aussi de la simple d6finition de ces formules, que les fl~ches de translation qui apparaissent dans des formules d'6quivalences sont des isomorphismes:

PROPOSITION 4.5.2

cr ~_ NatT (G; Yx, Y) " J(Y)

C r ' A J(yT) T~IGI

~e~-C~(yT) , A J(yT) TEIDI

Enfin signalons un r~sultat d'int~r~t purement technique, qui pourra ~tre prdcis~ dans les thdories sur categories du chapitre suivant:


PROPOSITION 4.5.3. Pour chaque suite fonctionnelle or de ..~, d'arit6 A:

%' ~ C~(yT) ~ Eq (fix ; YT)-

5. Theories Generales sur Categorie

Nous sommes maintenant en mesure de d6finir les th6ories 6galitaires.

Dt~FINITION 5.1. Une th6orie g6n6rale sur cat6gorie est une extension fonctorialis6e %" de %'c comprenant comme axiomes logiques suppl6mentaires:

(AIG) Axiome d' identit6 g6n&alis6e Pour chaque ~-graphe G, la G-formule

I Eq(G.G; I(T)) I

formule qui est en fait obtenue par une substitution 6vidente dans la forrnule: Eq (G, G'; YT)-

(AEF) Axiome d'6galit~ fonctionnelle Pour chaque suite fonctionnelle tr d'arit6 A de prototype D la formule:

I, Eq(A.A';yu) 3!y'T Eq(A.A': Yu.Yr)

off (Yu) est index6e par les objets de A et (YT) par. ceux de D - A (ou aussi bien fix-A, puisque ft. et D sont isomorphes en tant que simple graphe), formule sur le translat6 total de A.

(AER) Axiome d'6galit~ relationnelle Pour chaque symbole relationnel R d'arit6 A, la forrnule:

Eq(A.A':yu) -,(R(A) ~R(A')) ]

sur le translat6 total de A.

Vol. 10, 1 9 8 0 Theories egalitaires dans les langages stir types de graphes 327

Ces trois sch6mas d'axiomes sont 6videmment ~ rapprocher des sch6mas classiques d'axiomes d'identit6, d'6galit6s fonctionnelles et d'6galit6s

relationnelles.

Nous ne supposons dor~navant ne parler que d'une thdorie cr g~ndrale sur

cat~gorie.

Nous allons maintenant dans les th6odes g6n6rales sur cat6gories, pouvoir pr6ciser des propri6t6s plus fines des formules d'6quivalences Eq, d6finies et ~tudi6es dans le chapitre 4 pr6c6dent.

5.2. Le premier r6sultat important est l'unicit6 de l ' isomorphisme naturel associ6 ~ un terme objet, c'est la proposition 5.2.1 ci-dessous.

P R O P O S I T I O N 5.2.1. Soit G u n s163 et T u n terme objet sur G, alors:

cr ~ Na t r (G; Yx, y )ANat r (G; Yx, Y') > Y = Y'

La d6monstration peut se construire ais6ment par induction sur la hauteur p du langage tel que T soit un ~p- te rme sur le ~p-graphe G, par induction sur le rang de T, et ~t l 'aide des propositions 4.5.1 et 4.5.3.

I1 en r6sulte plus ou moins directement les trois corollaires ci-dessous. Corol- laires d 'un grand int6r6t technique, le premier par exemple permet tant de r6duire la complexit6 des termes objets dans la recherche d ' isomorphisme naturel. Signalons en termes simples de r6alisation une illustration du premier corollaire:

Consid6rons le translat6 ci-dessous, translat6 total d 'un graphe G ayant uniquement quatre objets:

A B A B A B 0 B

B' A'B'o I '

Le corollaire 2.2 atteste que si Y3 est l ' isomorphisme nature1 de A B pour la translation (Yl, Y2), alors y est l ' isomorphisme naturel de A e | pour la translation (Yl, Y2) si et seulement si y est l ' isomorphisme naturel de X @ Y pour la

translation (Y3, Y2), en posant X = A B e t Y = B.

C O R O L L A I R E 5.2.2. Soit h : H---~ G u n .~-homomorphisme, (Yx) (resp. (zv))


une famille de variables fl~ches index~e par les ob]ets variables de H (resp. de G), et T un terme ob]et sur H, alors:

c r A Nath(x~(G;zv, yx) >((NatT(H;yx, y))h~-->Nat,(T)(G;zv, Y))

Dans l'illustration pr6c6dente H d6signerait le graphe r6duit aux deux objets X et Y, et h l'isomorphisme de substitution 6vidente.

On peut aussi 6noncer le corollaire plus g6n6ral.

COROLLAIRE 5.2.3. Soient h:H---~G un ~-homomorphisme, tel que Im ( h ) c G, et (YT) (resp. (Zu)) une famille de variables fl~ches indexde par les objets de H (resp. objets de G), alors:

~ Eq (G; Zu) ) (Eq (H; yT))h.

Ecriture dans laquelle on entend cette fois que Zn(T) est substitu~ it YT dans (Eq (H; YT) pour former (Eq (H; yT))h

Le dernier corollaire ci-dessous, exprimant enfin que les isomorphismes de translation d'un graphe G, sont enti~rement d6termin6s par les isomorphismes de translation des variables objets de G.

COROLLAIRE 5.2.4

~ E q ( G ; y T ) A E q ( G ; y ~ - ) A A Yx=Y~ -----> A YT=Y~r XEIGI~ T E I G I

On est alors en mesure de v6rifier le rSle accessoire jou6 par les formules C,, annonc6 dans le num6ro 4.5

PROPOSITION 5.2.5. Pour chaque suite fonctionnelle ~ de ..~,

~- Eq (~; Yr) , C~(yT).

THI~ORI~ME 5.2.6 (prolongement d'isomorphisme). Soient H c G c g ( H ) deux ~-graphe alors

cr ~ Eq (H; Yu) -"---> 3[fT Eq (G; Yu, ZT).


L'unicit6 du deuxi~me m em bre de l ' implication rrsulte du corollaire 5.2.4.

Pour p rouver l 'existence, on mont re en fait les deux proposit ions suivantes:

5.2.6 (a) Pour tout ~ - t e r m e objet T sur G,

cr v-- Eq (G; Yu) ; 3y NatT (G; Yx, Y)

((Yx) drsignant la restriction de (Yu) aux objets variables de G).

5.2.6 (b) Pour tout ~ - t e r m e fl~che v sur G, de source et but respectif 7"1 et "1"2

dans G, on a:

cr ~ Eq (G; yu) ~ v o yT2= yTlo v '

Remarquons qu 'on retrouve ~ l 'aide de ce th ror~me la "p r r se rva t ion 6galitaire" classique de certains symboles fonctionnels fl~ches, lorsque leur r~gle d'utilisation le permet:

Soit q un symbole fonctionnel fl~che d'arit6 A, x une variable fl~che libre de

A (numrro 1.5), avec A = G + 7"1 '~ :' Z2 , Z 1 et T2 objets de G.

Supposons que les sommets U1 et U2 de q(IdA) = q(X1 . . . . . X,,,; x x . . . x.,,)

soient des termes objets sur G. On drdui t alors du th60r~me ci-dessus que sur le

graphe ( ( G + TI ": ~ Ta)+ T~ ':' ~ T2), la formule:

x = x' ~ q ( X , . . . . . Xm, x , . . . . . x, , x ) = q ( X , . . . . . Xm, x ~ , . . . , x,,, x ' )

est un thror~me de ~'.

La proposit ion suivante justifiera le r61e fonctoriel restreint des fonctions distingures dans les couples fonctoriels formels. Plus pr rc is rment , elle a t tes te que les symboles fonctionnels fl~ches privilrgirs en couples fonctoriels formels, doivent ~tre au moins des foncteurs sur les isomorphismes, plus p r r c i s rmen t sur le groupoide des fl~ches inversibles.

P R O P O S I T I O N 5.2.7. Soit (P, f ) un couple fonctoriel de ~ , P d'aritd A , alors:

(a) ccA t--- f ( I (T) ) = I (P(A)) , of~ ( I (T) ) ddsigne la famit le des fl~ches

d'identit~, index~e par les ob]ets T de A , notation 4.4.2, et IdA le .~-

330 GEORGES BLANC A L G E B R A UNIV.

homomorphisme d'identit~ de A dans A.

(b) r162 ~ Eq (A, A'; y r ) Êq (A'A"; za-)

(c) cr ~ Eq (AA'; yT)Êq (A', A; zr)

' f(YT) o f(zr) = f(Ya" ~ zr)

, (A S(yT, zT) , Jff(yT), f(ZT))).

J(y, z) est rappelons-le la formule d6finie au num6ro 3 exprimant que y et z sont des isomorphismes rgciproques.

Ce rgsultat peut conduire ~t considgrer que les opgrateurs objets (symbole fonctionnel objet) qui ne peuvent 6tre utilis6s dgcemment en th6orie des cat6gories, ne sont que ceux introduits par extension par dgfinition, ou bien alors ceux qui sont "au moins" fonctoriels sur le groupoide des fl~ches inversibles.

5.3. Nous sommes maintenant en mesure de montrer les r6sultats attestant le r61e 6galitaire de formules Eq.

PROPOSITION 5.3.1

it . o (a) ~ ~ Eq (G, G'; ya-)Êq (G', G"; z-r) > Eq (G, G , YT Zr)

(b) ~ ~ Eq (O, O'; yT)A A J(YT, ZT) T

> Eq (G', G; ZT)-

En notant Eq (G G') la formule 3~T Eq (G G'; YT), et compte tenu de l'axiome d'identit6 g6n6ralis6e (n ~ 5.1.), il r6sulte que la relation cr ~ Eq (G', G") entre copies d'un graphe G fix6 est une relation d'6quivalence.

On peut enfin montrer par induction sur la construction des formules, le th6or~me d'6galit6:

THI~ORI~ME 5.3.2. Quelle que soit la G-formule ~,

~' ~ Eq (G G') , (gt(G) ~ gt(G')).

Signalons enfin un r6sultat qui pourra 6tre utilis6 lors de l'extension par d6finition des th6ories g6n6rales sur cat6gorie.

PROPOSITION 5.3.3. Soit cr une th~orie g~n~rale sur categoric, on consid~re cr la th~orie de m~me langage ainsi obtenue:

(a) le schema d'axiome d'identit~, de cr est remplac~ par le schema suivant: Pour chaque couple foncioriel forrnet privil~gi~ (P, f), P d'arit~ A, la formule:

f ( I ( r ) )= t(P(A)) ]


est un axiome. Les axiomes d'~galitds fonctionnelles sont remplac~s par les formules:

I Eq (A, A ' ; ytr) "-~ ::1: y-r(C,~(yu, YT)) [

pour chaque suite fonctionnelle (r. Alors cr est ~quivalente iz ~r

5.4. Nous serons donc en mesure maintenant, dans un prochain article de formuler et de r~soudre te probl~me de l 'extension par d6finition en th6orie des cat6gories. Plus pr6cis6ment donc, de d6montrer l 'analogue du th6or~me classique d 'extension par d~finition de la logique du premier ordre, dans le cadre des th6ories g6n6rales sur cat6gories que nous venons de d6finir.

Soit c8 une th6orie sur cat6gorie de langage ~ . Supposons i : A ~ D u n e injection canonique entre .~-graphe stricts, et qb

une formule de c8 sur le graphe D. On suppose alors que �9 satisfait les deux conditions suivantes:

(a) ~r ~ 3AD@, (b) Si D d6signe une copie de D, co'/ncidant avec D seulement sur A,

c8 ~ 4~(D) A 4~(D') -----* 3!~T Eq (D, D ' ; I ( U ) , YT),

ofa ( I (U) ) d6signe la famille des identit6s de chaque objet U de A, et (YT) une famille des variables fl~ches index6es par les objets de D non dans A.

On note alors ~ le langage obtenu en adjoignant ~ .~ une suite fonctionnelle or d 'ari t6 A et de prototype D, en d6signant par 0 le .~ -homomorphisme canonique

de calcul de D sur le type A de o-. On note @ la th6orie de langage .~, obtenue en adjoignant ~t ~r la A- fo rmu le

q~(p), substitu6e de q~ par 19, comme nouvel axiome non logique. Dans ce contexte on d6crira alors une construction associant ~ chaque formule gt (G) de ~, une formule ~ ' (G) de cr et on mont re ra que gt(G) est un th6or~me de @ si et

seulement si ~z(~) est un th6orbme de ~8.

REFERENCES

[1] G. BLANC, Langage du premier ordre sur graphe, Cah. Math. de Montpellier n~ (1975). [2] G. BLANC, Equivalence naturelle et formules logiques en theorie des cdtegories, Archiv fur Math.

Log. (1979). [3] G. BLANC, Logique des theories ~galitaires sur types de graphes, Th~se de Doctorat, Universit6

d'Aix-Marseille II, (mai 1977).

332 G E O R G E S B L A N C A L G E B R A UNIV.

[4] A. BOILF.AU, Type via Topos, Th~se de Doctorat, Montr6al, 1975. [5] M. R. DONNADmU et Ch. RAMSAUD, [.In th:.or~me de compl~tude en theories sur graphes. Comp.

Rend. Ac. des Sci. Paris (i~ paraRre). [6] P. FREYD, Properties invariant within Equivalence Types of categories, Algebra, Topology and

Category theory, A. Heller. M. Tierney, Acad. Press 1976. [7] P. R. HALMOS, Algebraic Logic, Chelsea, New York 1962. [8] S. MAC LANE, Categories for the working mathematician, Springer, 1971. [9] Ch. RAMBAUD et G. BLANC, Theories formelles sur graphe, Compt. Rend. Acad. Sci. Paris t. 282,

24 Mai 1976. [10] Ch. RAMBAUD, D:.duction formelle en th~orie sur graphe, Compt. Rend. Acad. Sei. Paris. t, 283,

13 Sept. 1976. [11] J. R. SCHOENHELO, Mathematical Logic, Addison Wesley, 1967.

Universite d'Aix-Marseille H Marseille France

Documents

Theories egalitaires dans les Langages sur types de graphes