D IAGRAMMES L. C OPPEY Catégories de Peano et catégories algorithmiques, récursivité Diagrammes, tome 12 (1984), exp. no 1, p. LC1-LC47 © Université Paris 7, UER math., 1984, tous droits réservés. L’accès aux archives de la revue « Diagrammes » implique l’accord avec les conditions générales d’utilisation (http://www.numdam.org/legal.php). Toute utilisation commerciale ou impression systématique est constitutive d’une infraction pénale. Toute copie ou impression de ce fichier doit contenir la présente mention de copyright. Article numérisé dans le cadre du programme Numérisation de documents anciens mathématiques http://www.numdam.org/ Diagrammes, Vol.12, 1984. A.M.S. Sub. Class. 18 A 99 , 18 B 99, 18 C 99. CATEGORIES DE PEANO et CATEGORIES ALGORITHMIQUES REÇUESIVITE par L.COPPEY Les classes usuelles de fonctions récursives (au moins primitives) fournissent "évidemment" des exemples typiques pour ce qui va suivre (voir § 3 par exemple). Il nous semble toutefois que les procédés classiques (particuliers et généraux) de l'algèbre ont été quelque peu négligés par les "récurseurs" (au profit d'autres points de vue.,.). Notre intention, ici, est donc de donner quelques définitions et quelques résultats de nature bien algébrique, destinés à suggérer, sur des exemples relativement simples, que l'algèbre des catégories a certainement un rôle à tenir en matière de récursivité. Nous ne prétendons pas, pour l'instant, rentrer dans toutes les subtilités usuelles concernant les fonctions ou les fonctionnelles récursives. Dans un autre ordre d'idées on pourra se reporter aussi à (R.E.C.S.) et à (U.S.R.U.) pour des approches catégoriques des fondements de la récursivité. A l'origine de cet article, il y a une question d'A.Burroni concernant la triplabilité des catégories de Peano sur les graphes; la réponse à cette question est donnée en (A.M.E.N.) et est seulement suggérée ici. Les quatre parties du texte sont relativement indépendantes. C'est#à notre avis*la dernière (engendrements par structures partielles de plus en plus totales.,.) qui tient la place la plus importante. LC 2 I. CATEGORIES DE PEANO. Soit £ une catégorie et soit C un objet de £ • Définition 1. Un objet de Peano engendré par est constitué d'un triplet C , dans C , (NC, ip, s c ) , où - NC est un objet de £ , - i est une flèche de £ , de source C et de but NC , - s p est une flèche de £ , fermée en NC , ce triplet devant satisfaire la propriété universelle suivante: quel que soit le triplet ( C , f, t) où - C est un objet de £ , - f est une flèche de £ , de source C et de but - t est une flèche de £ , fermée en C , il existe une unique flèche f.i = f et f = f.sc C , [f,t] telle que : = t.f Remarques. (i) Soit 1_ la catégorie à un seul objet, noté 0, une seule flèche Id0 ; soit N la catégorie libre engendrée par le gra- phe suivant : ^ ^ ; soit teur possible défini par engendré par C Kan inductive de où u : 1^ ^ N l'unique fonc- u(0) = 0. Alors, un objet de Peano s'identifie naturellement à une extension de C :1 > £ le long de u : 1^ > N, C(0) = C . u » N cW \ * C'(0) = NC , c, <*> = s c ' KO) = ic . (ii) La terminologie est suggérée par l'exemple classique t si X est un ensemble, alors ( 1N.X, L., s„) est un objet de LC 3 Peano engendré par X , dans Ens , où on a posé: ^ ( x ) = (x,0) et s x (x,n) = (x,n+l) . Définition 2. On dit que C = (£ , i, s) est une catégorie de Peano si l'on s'est donné, pour chaque objet C de C, un objet de Peano (NC, i c , s ) engendré par C . Soit L = (£> i> s) un ^ catégorie de Peano. Si f est une flèche de £ , de source C et de but C , on pose : Nf = [ i C f f f s c ,] ; c'est l'unique flèche de £ telle que: Nf.i c = icf.f et Nf.s c = scf.Nf . Ainsi, N détermine un endofoncteur de C et i : Idr et s :N > N > N sont des transformations naturelles. Si C est un objet de £ , on pose encore JLL = [icLp, s S] ; c'est l'unique flèche de £ telle que : ^ C ^ N C = Id NC et V corres- D • On peut dire, de manière équivalente, que l'évaluation en 0, N N soit V : £ > £ , a un adjoint à gauche S : £ > £— défini par S(C)(cO = s et que V est triplable . Ce n'est alors qu'un cas particulier de la situation suivante: soit CP : 1^ ^J un foncteur bijectif sur les objets. Supposons que le foncteur £' : £— >£— tion par (p ait un adjoint à gauche (T, i, p.) le triple dans £- F à L , et soit 0 : TF >F F , la structure de prolongement J , correspondant à = est une F de 0-p.(LF)(j).ip j . Voici encore le point de vue des D-algèbres. Soit D = 0 , est définie ainsi : pour j: I — » I' , on a : F (j) tégorie ; soit T qui s'en déduit ; alors £ i est triplable ; de plus, si T-algèbre sur de composi- £ une ca- le graphe multiplicatif trivial obtenu en attachant à chaque objet C de £ une boucle formelle ou $ sans aucune équation particulière. Alors une D-algèbre sur C de s'identifie naturellement à un élément et un homomorphisme entre D-algèbres à un triplet tel que f.v = morphe à C— et son oubli naturel vers V v v'.f . La catégorie des End(C) , (v', f, v) D-algèbres est iso£ est isomorphe à . Dire que cet oubli a un adjoint à gauche revient exac- tement à dire que C peut être muni d'une structure de caté- gorie de Peano . Si tel est le cas, on sait (cf. proposition n°l, page 28 de (T.A.E.P.), ou la version postérieure de cette même proposition, page 17 de (S.B.D.S.)) que à l'isomorphisme près. V Q est triplable LC 5 Remarque. On ne confondra pas une catégorie de Peano avec un objet catégorie de Peano dans avons vu que , si alors par Cat , d'autant plus que nous (£ , i, s) est une catégorie de Peano, (NIdp, i, s) est un objet de Peano dans £— Id . Un objet de Peano dans est la donnée du triplet désigne la somme de engendré Cat , engendré par C , ( 1N.£ , i , s ) dans lequel IN copies de la catégorie injection canonique définie par IN.£ C , ip est 1' i (f) = (f,0) et s est l'endofoncteur défini par s (f,n) = (f,n+l). Plus généralement, si K est une catégorie à sommes dénombra- bles (cf. par ex. : Ens et long de se calculent point par point, ce qui u : JL >N signifie que tout objet Cat) K de ( IN.K , i^, s ) trivial, où les extensions de Kan le K engendre un objet de Peano 1N.K est la somme IN copies de K , et si (i ) ^ désigne la famille des coprojections n n ^0 de K vers ]N.K , alors i = i et s__ n'est autre que K le crochet de la famille (i ) U K. ^ . , i . e . l'unique flèche H n n ^ 1 s__.i = i ..s., . K n n+1 K Définition 3. Un foncteur de Peano est un homomorphisme en- telle que n tre catégories de Peano , c'est-à-dire un foncteur préservant les objets de Peano choisis. Donc, si C = (C , i, s) et —cr — C' = ( C , i', s') —a catégories de Peano, F_ : C cr sont deux — >C est un foncteur de Pe- -a -a ano si et seulement si F : £ ^ £• est un foncteur, et pour tout objet C de £ , on a les égalités suivantes : ^FCC) * F(i C} et S *F(C) = Dans ce cas, si C est un objet de £ ple de flèches ainsi dispodées : C que F([f,t]) = et si F(S C} * (f,t) est un cou- > D<^pt » o n voit [F(f),F(t)] , par unicité du crochet . LC 6 En particulier, F commute avec les endofoncteurs sous-jacents à C et C Nous désignons par Cat- —C N et N' . —C la catégorie ayant pour objets les catégories de Peano et pour morphismes les foncteurs de Peano. Le foncteur d'oubli naturel U.: Cat^ > Cat a un adjoint à gauche et est triplable. Répétons (une nouvelle fois) l'argument (général) : (i) £at_ peut être décrite comme catégorie de dessus de Cat , relativement à un graphe multiplicatif D surgraphe d'un sous-graphe de a) D-algèbres au- et b) , et (S.B.D.S.) , Cat , assez simple (cf.(T.A.E.P.) pour les généralités sur les D- algèbres, et le § suivant pour une description explicite de D ). (ii) Cat est une catégorie de réalisations d'une esquisse pro- jective (esquisse de catégories) . Il s'en suit que £at_ est elle-même une catégorie de réalisations d'une esquisse projective, ayant un "étage" de cônes supplémentaire par rapport à l'esquisse de catégorie. (iii) Il s'en suit que U a un adjoint à gauche et que U est triplable (cf. (T.A.E.P.), (S.B.D.S.), (E.D.S.A.), (C.T.F.A.)). Venons-en à la description de D . Il se trouve que, plus gé- néralement, il y a moyen de décrire la catégorie des catégories à extensions de Kan choisies le long d'un foncteur q , à 1' aide d'un graphe multiplicatif : seules les D arités des lois (i.e. les objets de isomorphe à Cat D et D sont greffés) et les lois naturelles (i.e. les flèches de Cat qui interviennent dans la description de fèrent ; ceci étant, D auxquels D —q et de D D ) dif—u aura, dans tous les cas, 5 objets , 8 lois naturelles, 3 lois formelles et 7 équations non triviales. LC 7 II. CATEGORIES A EXTENSIONS DE KAN COMME Soit q : I >J D-ALGEBRES SUR Cat . un foncteur ; on lui associe les trois catégories suivantes : - La catégorie Q. . Elle a pour classe d'objets la réunion, supposée disjointe, des classes d'objets de 1^ et de ^ . Ceci étant, nous la décrivons par générateurs et relations : Soit, pour chaque objet I de q(I) , que nous notons q1 . Posons puis X = FI I U FI J U L I_ , une flèche reliant L I à CQj3]; ç ob I f = . L a catégorie Q- est la ca- tégorie quotient de la catégorie libre des chemins propres de X , soit L[X] 9 Par les relations suivantes: (i)" h I ou dans = J g.f " , chaque fois que et vaut justement (ii) " q If .f = g.f est défini dans h , q(f).q-r " > P°ur toute flèche f : I —> I ' dans 1^ . Donc, Q- = L[X[] / r où r est la relation d'équivalence bicompatible sur l[X~] engendrée par les relations ci-dessus. On dit encore que Q.. est le gnerons par a "cylindre de q " . Nous dési- le foncteur injection canonique de - La catégorie Q^ . Il est clair que la catégorie que q est le foncteur Id I_ dans Q. , lors- , est canoniquement isomorphe à la catégorie produit J x 2_ où La catégorie se décrit aisément comme un recollement de £9 deux copies de £- £.. 2_ = ( 0 et d'une copie de ^ 1 )• J x 2^ , . d'une part selon le schéma suivant, qui précise les principales notations et les foncteurs injections canoniques dont nous avons besoin : LC 8 Q A < (q(D , D D Q2 ai J x 2 . d'autre part, en tenant compte des équations génératrices suivantes: j((q(I)fD).ai(qI) = b'(qj) . (2)Vl€0bI Bien sûr, on peut décrire, de plusieurs manières naturelles, la catégorie Q- comme limite inductive dans Cat de catégo- ries "plus simples" , mais ceci est sans intérêt pour la suite. - La catégorie Q 3 . C'est un recollement de 3 copies de Q~, . d'une part selon le schéma suivant, qui précise les principales notations et les foncteurs injections canoniques dont nous avons besoin : LC 9 . d'autre part , en tenant compte des équations génératrices suivantes : (3) V J Ç Ob J c"(J,i).b"(J,l) = a"(J,t) . Bien sûr, on peut décrire, de plusieurs manières naturelles, la catégorie ^ comme limite inductive dans Cat de catégo- ries plus simples, mais ceci est sans intérêt pour la suite. On remarquera, de ce point de vue, que les limites inductives en question ont un aspect purement graphique (recollements des graphes orientés sous-jacents à £, £, (L, Q« e t c . ) et natu- rel (c'est le sens des dessins ci-dessus) et_ aussi un aspect purement équationnel (cf. les égalités (2) et (3),etc..) tout aussi naturel, et, de toute manière, inévitable pour ce que nous allons dire ensuite. Soit e le foncteur naturel de J x 2^ dans le cylindre sur la base de son image par Q~ qui écrase j . Nous pouvons alors décrire le graphe multiplicatif D , qui est donc une "syntaxe catégorique" des catégories à extensions de Kan le long de q - ses objets sont les choisies: 5 catégories suivantes : I = % ' 9,i ' Q2 ' ^3 et - X - ' - ses lois "naturelles" sont les 8 foncteurs (entre ces caté- gories) ci-dessous désignés : a , a' , b' , a" , b" , c" , j , e , - ses lois "formelles" génératrices sont au nombre de a x '• 2.1 -—> <* 2 ! 22 > JSb -Si a 2.2 3 ! Q3 > 3 : ' les autres lois formelles à ajouter étant celles qui figurent (implicitement) dans les équations ci-dessous, - les équations non triviales de D sont au nombre de 7 : LC 10 Otj^a = Id Cat au sens des triples, (cf. la fin du § précédent). Il est clair que, plus généralement, si Cat désigne la catégorie des catégories à extensions de Kan choisies le long de foncteurs q Ç R , elle est algébrique au dessus de Cat , pour les mêmes raisons, à la condition toutefois que R soit un ensemble ; le graphe multiplicatif n —R à considé- rer, dans ce cas, n'est autre que la somme (éventuellement amalgamée sur certains objets et sur certaines flèches) des différents D , où q Ç R . Plus généralement encore, on peut aussi considérer les catégories à extensions de Kan liées choisies, les liaisons étant spécifiées par des équations supplémentaires imposées entre les diverses lois génératrices a. données. Nous proposons d'appeler de telles structures des catégories algorithmiques0 Peut-on faire plus général ? Absolument oui ! Considérons un sur-graphe multiplicatif de Cat tel que la "différence" Nous obtenons alors des D' = D D - Cat soit petite. D-algèbres qu'on pourrait qualifier d'hyper-algorithmiques. En fait, puisque D est générique maintenant, le seul point commun entre ces algèbres réside en ce que leurs syntaxes contiennent toujours Cat ; aussi pour- rait-on les appeler (génériquement) des algèbres catégoriques, rappelant ainsi que les arités des lois formelles qui les définissent dans chaque cas particulier (i.e. pour un D donné) sont toujours des catégories. Ainsi on peut dire que les algèbres catégoriques (ou hyper-algorithmiques) sont algébriques sur Cat, dans le sens précis suivant : quelle que soit la syntaxe catégorique type D D donnée , les algèbres catégoriques de sont triplables au-dessus de Cat . LC 12 Dans le même ordre d'idées, on peut concevoir une extension de cette notion, qui consiste à envisager pour les arités des lois formelles des objets d'une catégorie £ arbitraire. Ce point de vue n'est pas sans rappeler celui de (T.A.E.P.), a) et b ) . Ainsi, pour un sur-graphe multiplicatif a la notion d'algèbre de type • jD , ou de £ , et si D D de £ , on D-algèbre , au-dessus est donné génériquement, on peut tout à fait parler d'algèbres £ / iques . Avec des conditions (non nécessaires d'ailleurs) concernant (i) la taille de l'esquissabilité de D - £ et (ii) £ , on peut énoncer un résultat du genre : "les algèbres £ / iques sont algébriques sur £ " , ce qui jus- tifie pleinement le choix des mots puisque nous disposons maintenant de l'équation de commutation : algèbres £ / iques = algébriques / £ . Nous avons tenu à écrire ce paragraphe pour bien mettre en évidence le fait que les catégories à extensions de Kan choisies se décrivent le plus naturellement du monde comme des algèbres catégoriques (i.e. les arités naturelles qui s'imposent dans la définition naturelle sont bien des catégories !) ce qui ne veut pas dire qu'il soit interdit, ou impossible a priori d'en donner une définition en termes d'algèbres rie £ ï £ / iques, avec une catégo- Cat. Il est cependant établi en (A.M.E.N.) qu'il n' est pas toujours possible de les décrire en termes d'algèbres graphiques (i.e. £ = Gra): notamment pour les catégories de Peano. Nous pensons aussi qu'il est utile à certains de se convaincre de la simplicité, de l'élégance, de la généralité (non gratuite) de certaines notions en examinant des cas particuliers. Ils en ont donc ici tout le loisir. Le point de vue des D - algèbres issu de la théorie des triples est très naturel dans la mesure où on ne se fixe pas a priori la catégorie de base £ une fois pour toutes, c'est-à-dire dans la mesure où on tourne le dos au point de vue des algèbres C / iques (cf. le commentaire ci-dessus qu'il convient de ne pas réduire à un simple amusement !) LC 13 III. L'EXEMPLE DES FONCTIONS PRIMITIVES RECURSIVES. L'ensemble PR des fonctions (totales) primitives récur- sives admet beaucoup de présentations équivalentes. Elles ne diffèrent pas fondamentalement les unes des autres, mais il est bien nécessaire de s'en convaincre dans chaque cas, avec quelque précision. Si donc on propose une présentation de l'ensemble PR "légèrement différente" (au moins en apparence) de celles qu'on trouve dans la littérature, on doit s'astreindre, quand bien même cela paraît "évident" à montrer l'équivalence avec une des définitions précises que fournit la littérature. Le bavardage autour de la "thèse de Church" n'est scientifiquement d'aucun secours ! Commençons par remarquer que PR comme ensemble de fonctions de IN est défini en général dans IN , où r > 1 est va- riable. Reprenant le point de vue développé par Eilenberg et Elgot dans (R.E.C.S.), nous associons tout d'abord à catégorie PR la PR suivante: - ses objets sont les ensembles IN , avec, n > 0 ; on pose IN° = 1 ; - ses flèches sont les applications que f : ]N ^ IN telles p . .f = f. : IN > IN soit dans PR , pour i = ' ème r l,2,...,r, p . désignant la i projection naturelle de IN r,i dans IN , et les applications z : 1 > IN et C : IN •1 définies par z n (0) = 0 et C (n) = 0 (de sorte que PR est une catégorie à produits finis quelconques, y compris le 0-produit 1) Ceci étant, nous allons préciser une définition qui n'est pas très éloignée de celle qu'on trouve dans (R.E.C.S.) , puis nous montrerons qu'elle est équivalente à celle qu'on trouve dans le livre de Jaulin et Azra (R.E.C.U.) à la page 191, exercice I 11 . Nous utiliserons largement des faits simples, qu'on ren- LC 14 contre un peu partout dans la littérature. Donc, peu d'originalité dans ce qui suit, mais quand même un tout cohérent qui peut éviter au lecteur consciencieux d'avoir à se noyer dans les romans-fleuves de la récursion primitive! 1. La catégorie de Péano K . . Ses objets sont les ensembles finissons alors K IN , avec n > 0. Nous dé- par récurrence comme suit : on part de l'ensemble K' constitué des applications suivantes: les i r : lNr les s lN r+1 » : IN r+1 > , où i r (V) = (V,0) , IN r+1 , où s (V,n) = (V,n+1), l'entier r prenant toutes les valeurs > 0 K^ est la catégorie d'applications engendrée par K' . Supposons définie la catégorie K . Nous définissons alors: —m . l'ensemble K1.- comme réunion de K et de l'ensemble m+1 m ("K ,K "] des crochets |~f#al d'applications de K : L m mJ L q !N -i-^ ' J 3N^Qa . la catégorie d'applications La catégorie *^ ; [f,a](V,n) m = a n (f(V)), K.-. engendrée par K' - . K est la réunion des catégories emboitées K . — —m Cette présentation montre aussitôt que (K , i, s) est une catégorie de Peano. 2. La catégorie PR (cf. (R.E.C.U.)) . Comme convenu, on définit en fait l'ensemble PR : c'est le plus petit ensemble d'applications contenant : .s . p : IN > r . : lN . z r : ]Nr ^ IN , où > ]N s(n) = n+1 , où ]N , où , p r .(n ,n ,...,n ) = n z (V) = 0 , r > 0 , , 1 < i < r LC 15 et qui est stable pour les opérations de composition et de récurrence simple. 3. L'égalité PR = K . Commençons par établir que certaines applications bien naturelles sont effectivement dans K • . tl . : IN » IN2 n |—>(n+l,0) 2 s. .: IN* , comme composée t- = i..-s0 ; 2 IN > If J* (m,n) | — > (m+l,n) , comme crochet s. - = Ct,fS-] ; . par récurrence, on obtient les applications successeurs : s P>q : »1*1 (n- ,. •. ,n si si N**1 > ^) | — > (n 1# .. ,n +1,.. ,n ^) ; q = p+1 , on v o i t que s , - = s est dans ^ p,p+l P q ï p+1 , on remarque que : s - „ = ^i , . s . , s ] *q P-l P-l q K' 0 , ; . par récurrence, on obtient les applications nulles : z : INr ^ IN r V h-» o si r = 0 , on v o i t que z si r î 0 , on remarque que = i Q est dans K , z = \JL ,$ Id TM-I » . par récurrence, on obtient l e s projections : p . . ]Nr > IN r,i ( n l f . . . , n r ) J—» n t si r = 1 , on v o i t que si r £ 1 , ou bien ou bien ,avec l < i £ r p- , = I d ^ ' i = r i # r ; e s t dans K, r n e t , dans ce cas P r r = ' - z r - 1 > s 0 J et a l o r s p r ^ = C p r - l i * I d i N ^ LC 16 . par récurrence, on obtient les insertions de 0: s lNr j ]Nr+1 > K r, i i < r+1 , — — (nlf...,nr) |—> (n lf .. f n i-lf 0 f n if .. f n ) si r = 0 , on voit que si r î 0 , ou bien r,i = - = i est dans K, i = r+1 et, dans ce cas, j ,, = i r,r+l r i ^ r+1 et a l o r s : est dans K, ou bien j j ; E V j r - l , i ' SiP ; • par récurrence, on obtient les permutations: â : lNr > lNr (nlfn2,..,nr) (—> ^na(l),na(2 V " ,na(r P permutation de l,2,...,r ; 9 °" ° est une (i) d'abord la permutation des 2 dernières variables (r > 2) détaillons une procédure possible: (nlfn2,...,nr-1,nr) | > ( n ^ n ^ ... f n'est autre que le crochet suivant: Ûr-l,r-l ' sr-l,r-l^ (ii) ensuite, la permutation circulaire (n^,n2,...,n^) |—> (n ,n^,...,n n ,n ,n r . 2 r r-l^ ' (r > 2) ,) n'est autre que le crochet suivant: Ejr-l,l ' s r-l,l^ 5 2 d : IN > IN n j—> (n,n) . la diagonale est le crochet suivant: [ i r i 0 , slj2.slfl] ; . par récurrence, on obtient les diagonales dr : INr > INr x INr , pour r> 1; indiquons une procédure possible pour récupérer d : r d'une part, d d - à partir de suivie de deux insertions convenables de 0 fournit l'application h suivante : V (—• (V,0,V,0),où V € !Nr; LC 17 a = s 2 r r + 1 « s 2 r 2r+l d'autre part, on prend on obtient alors d - =£h,a]]; toujours par récurrence, on obtient les diagonales générales: lNr >> lNrq (v,v,...,v) . la catégorie K e s t à produits. S o i t f : IN ^ IN une a p p l i c a t i o n , élément de K ; a l o r s , quel que s o i t q > 0 , l'application ]NP x ment de INq > (Vx , V 2 ) |—> K . En effet, pour INr x INq (f(V x ), V 2 ) est encore élé- q = 0, il s'agit simplement de f, et on poursuit par récurrence sur la "longueur de V " . De même, soit g : INP l'application ^q x > ^p IN ^ (V lf V 2 ) |—^ dans K ; quel que soit ^q x q > 0, ^t (Vx, g(V 2 )) est encore dans K, comme compée des trois applications suivantes: (Vlf V 2 ) h-»(V2, Vx) h-»(g(V2), Vx) (permutation , cas précédent , on obtient alors, pour INP, l'application f et g (f ,g) ; permutation ) données dans K, de même source : INP V t — » ( V 1 # g(V 2 )) > | ^ INr x Ttf (f(V),g(V)) , en composant les trois applications suivantes: V I—> (V, V) |—» (f(V), V) (diagonale , cas précédent , h-> (f(V), g(V)) ; cas précédent ) on généralise facilement au cas d'un nombre quelconque d'applications de même source. Ainsi K est une catégorie à produits. C'est une théorie de Lawvere particulière qui jouit d'une remarquable propriété universelle par rapport à toutes les théories de Lawvere finiment présentables (nous en reparlerons dans un travail ultérieur, et nous laissons à la sagacité du lecteur la découverte de ce que sont les K-algèbres !) LC 18 • A p a r t i r du moment où l ' o n dispose de l ' o p é r a t i o n de j u x t a p o s i t i o n au but : ( f l f f 2 , . . . , f k ) ( v ) = (f x (v), f 2 ( v ) , . . . , f R ( v ) ) dans K , il est licite de reprendre (les yeux fermés) les nombreux engendrements décrits dans les ouvrages spécialisés en récursivité ; on obtiendra, par exemple, la fonction caractéristique de l'ordre, le prédécesseur, la valeur absolue de la différence, les fonctions caractéristiques des ensembles sur lesquels Inégalité f = g qui signifie que est à noyaux virtuels,etc... K entre deux éléments de K a lieu, ce . Pour prouver l'inclusion tenant que K Soit donc g : INP K => PR , il reste à établir main- est stable par le schéma de récurrence simple. > IN applications, éléments de et h : ïïr K , et soit > IN deux f : IN ^ IN l'application définie par: f(V,0) = g(V) , f(V,y+1) = h(V,y,f(V,y)) . Introduisons l e s deux a p p l i c a t i o n s s u i v a n t e s : i INP v INP+2 5> | » (V, 0 , g(V)) h : IN**2 > (V, y , z ) ^ , 2 I—» (V, y+1, h ( V , y , z ) ) . En composant avec les projections convenables, on trouve des éléments de K ; donc, d'après la possibilité établie de juxtaposition au but, on voit que Le crochet n f = Cs » 3 est g et h sont éléments de donc élément de K . K, et l'on vérifie A par récurrence que bien dans f(V, y) = (V, y, f(V,y)) , donc que K comme composée de aux égalités suivantes: PR est f et de la dernière projection. . Reste à établir l'inclusion inverse On voit tout d'abord qu< que f K cz PR. contient K' , et donc KQ grâce LC 19 p r,i"lr - pr-l,l si p r . r ' l r = Z r-1 p r+l,i'sr • pr+l,i P r+l,r+l,sr = V P r + l , r + l i l suffit alors d'établir que de crochetage si 1 1 T << X 1 l < r ' PR est stable par l'opération [_ , ] . Or ceci résulte des deux points suivants ( i ) Soit mP —£—> l N < ^ | l a » avec f, a dans PR ; alors [f"»aD n'est autre que l'application h définie par le schéma de récurrence simple suivant: h(V,0) = f(V) , h(V, n+1) = â(V, n, h(V,n)) , où (ii) Soit 1NP â(V,n,m) = a(m) . $> K s T 7 ) *avec f> a dans PR et r > 2- Choisissons une bijection récursive primitive y de IN (il y en a beaucoup !) et posons f et a donc que sont dans PR f = y.î , a sur IN = Y»*«Y » et on est ramené aucas (i) ; on sait [f , a 1 est dans PR , et comme la conclusion en résulte aussitôt. [f, a] = Y «tX,*^]]* LC 20 IV. DES STRUCTURES VOISINES PLUS FAIBLES. (Méthode d•engendrement par structures partielles) On peut chercher à affaiblir la structure de catégorie de Peano en y remplaçant l'axiome d'unicité du crochet [ , ] par un ensemble plus ou moins tiche d'axiomes, qui seraient des conséquences de l'unicité, si celle-ci était réalisée. Ceci peut conduire, par exemple, à une connaissance plus précise de ce que sont les algèbres du triple induit dans Gra par l'adjonction Cat-, ^ > Gra décrite en (I). On voit un autre intérêt possible : celui de la classification algébrique d*un certain nombre de classes de fonctions récursives, utilisant les résultats généraux de la théorie des esquisses ou des D-algèbres. Cependant, l'intérêt premier de ce paragraphe est la présentation, sur des exemples significatifs, d'une méthode d'engendrement de structures libres, à l'aide de structures partielles de plus en plus totales, dont l'originalité est double: - elle colle à la réalité de 1•engendrement tel qu'il est pratiqué usuellement, plus ou moins consciemment, - elle montre que la totalisation peut s'effectuer en rattrapant le(s) retard(s) sur les domaines partiels de définition des lois, afin de contrôler au mieux l'injectivité dans la structure totale. A. Les SC-monoïdes. Quel que soit l'objet monoïde End(NC) C d'une catégorie de Peano, le est naturellement muni d'une structure de SC-monoïde. La définition proposée ici de cette structure est volontairement "un peu" compliquée, pour qu'à son sujet nous puissions expliquer la technique de partialisation. LC 21 Définition 1. Un monoïde à succession cohérente, en abrégé un SC-monoïde, est constitué par un triplet (M",s,c) dans lequel M* est un monoïde d'élément neutre e, s est un élément distingué, appelé "succession", et c est une loi binaire dans M, dite de "cohérence", satisfaisant les axiomes suivants: SCX V(y,x) € M2 x SC2 \/(y> ) C M SC3 \f(z,y,x,x') z x c(y,x).s = x.c(y,x) c(y,x).c A ° = y.c 6 M* ç M3 SC4 V< >y' ) SCJS c(s,s) = s , où ° c(z.c(y,x),xf ) = c = c(e,e) ° c(z.y,x') c(y,x).c(z,s) = c(c(y,x).z,x) , c(e,s) = e , c(e,c ) = c o o Citons quelques conséquences immédiates de ces axiomes: CQ et C C(S ,S) = s P . (par convention, s = e) VP — ° 1 c ^o = c ^o V(x',x) € M 2 C 2 \/(z,x) € M c(x',s).c(c x,s) = c(x'.c .x , s) o o c(e,x).c(z,s) = c(c(e,x).z , x) La con équence C^ résulte de SC2 et SC., et elle rend compte de la fonctorialité du crochet, quand les boucles sont prises égales à s, tandis que C^, cas particulier de SC., rend compte du changement de boucle seul ( s I > x ) . En fait, SC. , en présence de SC2, équivaut à : C. V(z,x) € M2 J c(z.c ,x) = c(z,x) . o Mais C- et C 2 , même assorties de SC-,SC2 et SC. n'entraînent pas en retour la validité de SC0 et SC, ! Définition 2. Un monoïde de Peano est un triplet (M*,s,c) dans lequel M' est un monoïde, s est un élément distingué de M, et c est une loi binaire dans M ayant la propriété suivante, où c o désigne toujours c(e,e) : 2 P (y#x) € M c(y,x) est l'unique élément z possible tel que z.s = x.z et z.c = y.c J o o LC 22 On vérifie sains peine que tout monoïde de Peano est un SCmonoïde. La réciproque n'est pas vraie, comme nous aurons 1' occasion de le voir plus loin. Les SC-monoïdes s'esquissent avec des cônes distingués à bases discrètes de cardinal ^ 4 . L'esquisse en question engen- dre une théorie de Lawvere. L'exemple typique. Soit Peano, et soit un objet de C C = (£, i, s) une catégorie de £ ; on lui associe naturelle- ment le SC-monoïde (M*, s , c p ) suivant: M* est le monoïde des endomorphismes de l'objet NC , sr est la valeur de la transformation naturelle s en C , c'est donc bien un élément distingué dans M c , c (y,x) n'est autre que le crochet [y.i c #x] • L'unicité du crochet dans une catégorie de Peano fait que ces divers SC-monoïdes (M", s , c ) sont des monoïdes de Peano. On est donc déjà assuré de l'existence de SC-monoïdes non triviaux. On verra plus loin des exemples de SC-monoïdes qui ne sont pas des monoïdes de Peano. Notons enfin que la terminologie que nous employons ne doit pas entretenir une confusion possible: un monoïde de Peano (définition 2 cidessus) n'est pas une catégorie de Peano à un seul objet (définition 2 du § I ) . B. Les SC-monoïdes partiels. Plusieurs descriptions classiques du engendré par un monoïde SC-monoïde libre M' sont possibles. Nous allons en pré- senter une ici, sans doute moins classique, mais dont l'intérêt théorique ne peut pas échapper au catégoricien attentif; nous lui demandons donc d'envisager ce qui suit d'un point de vue LC 23 générique; nous développerons ces idées de façon plus systématique dans un article séparé. Nous partirons de la définition de SC-monoïde partiel suivante. Définition 3. est un On dit que ( M ^ S j c ) ^ n 7 où P c ZxZ c Q c MxM, SC-monoïde partiel de domaines P,Q,Z lorsque: M* est un monoïde d'élément neutre e, s est un élément distingué de M, c est une loi binaire partielle dans M, de source Q, satisfaisant les axiomes SC SC? (i = 1,2,...,5) suivants: n'est autre que l'énoncé SC. dans lequel les égali- tés sont conditionnées, pour i = 1,2,3,4,5, au fait qu'elles soient bien définies (i.e. appartenance à Q de tous les couples voulus) et surconditionnées, pour i = 3,4, au fait que (y>x) Ç P, et en plus, pour i = 3, au fait que Définition 4. Par homomorphisme entre z Ç Z . SC-monoïdes partiels il faut entendre la donnée suivante: (M *' S ' C ) P,Q,Z où f: M* " > (M "'S,'C,)p.,Q'fZ' ' > M'* est un homomorphisme entre monoïdes, f(s) = s» , (f x f)(P) c P' , c'(f(y),f(x)) f(c(y,x)) , pour tout (y,x) dans Q . = (f x f)(Q) c Q' et f(Z) c Z' , On peut imaginer bien des variantes de "partialisation de la structure de SC-monoïde" : l'une d'entre elles consisterait, par exemple, à partialiser aussi la structure de monoïde sous-jacente. Cependant, il convient de dégager nettement, sur cet exemple, le trait caractéristique souhaité pour la structure de l'opération de partialisation (esquisse de partialisation d'esquisses !) : c'est l'inclusion des domai- LC 24 nés de "deux" lois (par ex.: P c — > Q) qui se trouvent être superposées dans l'égalité axiomatique requise (par ex.: ici c se superpose à elle-même dans les expressions c(z.c(y,x),x') et c(c(y,x).z,x) . Bien sûr, si on avait voulu partialiser, par exemple, aussi, la loi de monoïde k(y,x) = y.x , on aurait fait apparaître une chaîne d'inclusions de domaines plus longue: en rendant partielle l'expression c(k(z,c(y,x)),x') on pour- rait introduire trois domaines inclus les uns dans les autres, comme suit : p c—> P- É — > P, serait le domaine du " c P 2 le domaine de p 9 où intérieur " , k , P 3 le domaine du " c extérieur " . C'est sur cette structure de "retard entre les domaines" que nous voulons attirer l'attention principale. Encore une fois, il n'y a aucune "obligation a priori" de partialiser comme ceci ou comme cela. Le rôle de Z dans SC' apparaîtra clairement plus loin. Revenons alors à la définition 3 de SC-monoïde partiel proposée ci-dessus. Ecrivons, à titre d'exemple, les axiomes SC' et SC' avec précision: [(e,e) Ç Q SC£ V(y,x) € Q — > SCj \/(z,y,x,x') [(y,x) € P, (z.c(y,x),xf) € Q , (z.y,x') Ç Q , — > Lorsqu'on construit le dré par un c(y,x).c(e,e) = y.c(e,e)] z € Z c(z.c(y,x),x') = c(z.y,x')] SC-monoïde libre (M',s",ïï) engen- SC-monoïde partiel (M*,s,c) r,Q,£ , on doit ajou^ ter, si nécessaire, librement, les valeurs particulières de c pour les couples de constantes comme (s ,s) , avec p ^ 0 , (e,e), puis (e,c ) ..., qui ne figureraient pas dans la source de c • LC 25 On peut convenir que cette adjonction s'effectue en premier. Nous allons traiter en détail le cas de l'adjonction de (e,e) à Q , pour mettre en évidence un procédé qui est en fait général. Soit donc (M',s,c) n nés P,Q,Z, tel que dans Z . On veut adjoindre attribuer à _ ,un SC-monoïde partiel de domai- (e,e) c(e,e) ne soit pas dans (e,e) à Q et e soit Q . Le problème est d' une valeur convenable. On commence par aggrandir M sans trop se préoccuper de la o structure partielle : soit L(M') par M* M' = M U { C Q } et soit le monoïde libre engendré le monoïde quotient de L(M')° par les relations suivantes, dans lesquelles on a identifié à une partie de L(M'), et où. Q 1 = Q U {(e,e)} M c o s = c , o o * V ( y > x ) Ç Q-. c(y,x)ocQ = yoC Q \/(y,x) Ç M yox = y.x , , = e on distingue par : s dans M- et on définit Cj^y,x) = c(y,x) , pour tout c- , de domaine (y,x) dans Q Q- , , c 1 (e,e) = C Q . Le problème est maintenant de savoir si (M" , s, c. ) bien un P-jQ^Z , où on a posé si SC-monoïde partiel de domaines est P 1 = P U {(e,e)}. Ce problème équivaut au fait de savoir (M\S,C)P^Z homomorphisme entre i—> (M i»8»ci>PlfQl,z est bien un SC-monoïdes p a r t i e l s . S i c'en e s t un, on peut poursuivre l e s adjonctions (par exemple, c e l l e de ( e , c ) o à P 1 et Q.) . Si ce n'en est pas un, on doit procéder à un quotient de M* , ce qui peut éventuellement détruire l'injec- tivité de j ; on connaîtra alors une raison précise de la non LC 26 injectivité dans la structure libre. A cet effet, examinons les axiomes (M^,s,c 1 ) p z satisfait en ce qui concerne SCj et SC . Par construction , SC' , SC£ , SC£ . Par contre , SC' , cela va dépendre de la struc- ture initiale (M*,sfc)1> n „ . 9H9& " Supposons, par exemple, qu'il existe t e l s que x , y , z , dans M , (y .x ) Ç P , (z .c(y ,x ) , e ) Ç Q , z Ç Z et z .y = e. o o o o o o o o (on ne peut pas avoir z .c(y ,x ) = e , puisque, par hypothè- se, (e,e) tf Q) . Comme (M^,s,c-) est obligé d'identifier c et doit satisfaire SC' , on c' = c(z .c(y ,x ),e) dans M.. - Pour abréger, nous dirons qu'il existe dans (M ,s,c) D une occurence simple de c , à savoir c' (via (z ,y ,x )). o o o o o On définit aisément les occurences doubles, triples, e t c . . mais nous ne nous y attarderons pas ici. Soit E(c ) l'ensemo ble des occurences simples de c dans (M*,s,c) . On o voit que l'adjonction de (e,e) à P,Q,Z Q et à P conduit à deux possibilités qui s'excluent mutuellement: . ou bien E(c ) = 0 et, dans ce cas, c a du être ajouté formellement ; (M*,s,c,)_ n „ est un SC-monoïde partiel de domaines P ,Q-,Z ; . ou bien de Mj^ E(CQ) £ 0 ; dans ce cas, on doit faire le quotient par la plus petite relation d'équivalence, compatible avec la structure partielle, engendrée par la relation qui identifie c o aux divers éléments de est réduit à un seul élément E(c ) . Même si o c* , il se peut fort bien que ce quotient identifie entre eux des éléments de ici, à cause de l'axiome E(c ) o M , notamment SC' . Pour la suite des constructions, nous supposons qu'on dis- LC 27 pose maintenant d'un SC-monoïde partiel (M.",s,,c-)_ 1 1 1 P^,Q^,Z^ dont les domaines contiennent les "constantes" , i.e. (e,e) et les (s 1 ,s 1 ) , pour p ^ O , appartiennent à P- , et posant toujours C Q = c1(e,e) , (e,cQ) appartient à P ^ Ainsi, les axiomes où figurent c et s- sont efficients. o Supposons déjà c o n s t r u i t e une s u i t e d'homomorphismes entre SC-monoïdes p a r t i e l s JM = (M* s. , c , ) p ft _ , l^i< k : J^ l Wx J. > M2 2 =-» M 3 .... J. l , x lf k-1 £-* ^ 1 , ayant les propriétés suivantes: (i) Q 1 + 1 = j.(M.) x j^M.) P 1+ l = (JiXJ.KQ.) Z i+1 = W ' pour 1 < i < ^ , (ii) pour tout homomorphisme ]M> ]M' dont le but est un SC-monoïde total (i.e. de domaines M'xM' , M'xM' , M ' ) , il flr existe un unique homomorphisme Iti f , i.e. tel que f k « j k-l" j k-2 ## ' j l > = f ]M' qui prolonge • Construisons alors l'homomorphisme au rang k : M — > ]M de la manière suivante : Soit ^ l e m o n o " d e libre engendré par la somme, supposée disjointe, ^ + C M ^ M ^ 9 où [)^,M^ est écrit pour une copie du produit cartésien VL x K ; on convient d'écrire les mots sans parenthèses, identifiant canoniquement M. à une partie des générateurs de L ; pour plus de précaution, nous écrirons les éléments de [j^,^]] sous la forme [y9x] , réservant ainsi la notation (y,x) pour les éléments de L x L tels que y et x soient dans K ! La composition dans L est notée par simple juxtaposition, alors que celle de M/ est notée "." Enfin, [ , ] est regardé comme une loi partielle définie jus- LC 28 tement pour les couples (y,x) éléments de K x ML et à valeurs dans D^fMjJ] . Le crochet a donc ici une nouvelle signification. On désigne par M ^ le quotient de K par la relation d' équivalence compatible avec la composition de L et la loi £,] engendrée par les relations élémentaires (r.) ci-dessous : (rQ) V(y#x) Ç M^ y.x = yx , et 0 = e V(y>*) ? Q k ck(y,x) = [y,x] (rx) V(yfx) € M^ [y,x]sk = x[y,x] (r2) V(y,x) 6 M^ !>.*>0fk = ycQfk (r3) V(y,x) Ç Qk \/(z,xn (V V W ) € Qk \/z € MR Ç^ ,où c ^ = ck(e,e) [z.ck(y,x),x'] = [z.y,x'] ck(y,x)[z,sk] = [ck(y,x).z,x] La classe d'équivalence de m est alors notée <3n> . On définit, dans Mjç+1 , la loi de monoïde suivante: <3n'>. = . L'application canonique j : K ^ M - , donnée par Jk(x) = Oc> , définit clairement un homomorphisme de monoïdes. On pointe M^+1 par l'élément s R+1 = jR(sk) ; on pose: Vi = W x w Vi = ( \ x V,) = < y , x > . Par construction, les conditions de domaines sont satisfaites à l'ordre k+1 . Ensuite j k (s k ) = sk+l et (y ' x) Ç j est un homomorphisme satisfaisant % j k(ck(y'x)) = ,) € Q k + 1 ; on a : ck+1(,). SC:£. Soit = <[y,x>. (déf.) = (déf.) = (rx) = .< (y,x> (déf.) = .ck+1(,) (déf.) (,) € Q R + 1 , avec (y,x) Ç MjJ ; on a : c k+1 (»). c R + 1 (,) SCJ. = <[y.x]>.<[e,e]> (déf.) = <[y»x]>. (r0+comp.) = <[y»x>.k> (déf.) = <[y»x]c o > k > (déf.) = k>' (déf.) = . (déf.) = . c R+1 (,) ( déf. ) . , avec zÇ K , et (,) € P R + 1 , avec (y,x) € Qk , Supposons que € Z (.,) € Q R + 1 , (,),) € Q k + 1 ; alors: LC 30 C k+l ( < z : > C k+l ( < y > # < X > : ) # < x , > ) = c k+1 ( # ) (déf.) = ck+1(#<:x'>) (rQ+comp.) = = <&-ck(y,x),x']> <&.y, x']> (déf.) (r3) = ck+1(,) ' (déf.) = cR+1(<>r>Kx'>) (rQ+déf.) Il était important ici de conditionner le domaine de la variable z (par Z) . Si nous n'avions pas pris cette précaution, on aurait du établir un résultat du genre: " Soit avec m Ç L^ ; si l'on a = , (y,x) Ç QR , t, t' € ^ , alors = m € K ". Ce résultat, s'il est exact, nécessite une démonstration bien redoutable ! Il se trouve que le plongement dans la structure de SC-monoïde total ne dépend pas en fait de la validité de cet énoncé. SC£. Supposons (Cy>,) Ç P R + 1 , avec (y,x) Ç QR , «Cz>*Csk>) ç Q k + 1 , avec x, y, z € M ^ (ck+1^y>,)cz>|c:x>) € Q k + 1 . On a: ck+1(ck+16C y>,< x > * z>*C x>) = ck+1£c[y,x]z>|Cx>) (déf.+comp. ) = ck+1(|c:x>) (rQ+Comp.) = <[ck(y,x).z,x> (déf.) = ^(y.xtz,^ (r4) = = < &f x ] x i , s R > = ck+1«y>!Cx».ck+1«z>,sk+1) (déf.+comp.) (rQ+comp. ) (déf.) Déf. = par définition, Comp. = par compatibilité r. = d'après la relation (r.). LC 31 Contrairement à ce qui s'est passé pour SC' , il n'est pas utile ici de conditionner z • Cela provient du fait que la compo- sition du monoïde ne figure pas à l'intérieur dans les deux expressions égalisées de SC. , mais seulement à l'intérieur de 1' une d'elles, à savoir L'axiome SC" Soit enfin se vérifie sans difficulté. f : 11 monoïde total <ïn> =< z n z n - i , , , z i > > i = f > M un homomorphisme de but un SC Ç M* (M,3","S) . Soit où chaque [y^x^ Ç C soit de la forme = <[y. ,x.]> ^ + 1 ^ 3 ^ ^ 3 ¾ ^ ) • s * i:L existe un homomorphisme f. tel que i°J k = f , on doit avoir: f1() = f(Xi) f fe = l V° si < 2 i > = jk(x.) , VW^i^i^ = c(f(yi),f(Xi)) si < Z i > = <[yi,xi]> . Donc f^ est déterminé de manière unique par l ' é g a l i t é suivante: f1fem>) = f 1 <).f 1 <)...f 1 () , et c'est évidemment un homomorphisme. On passe alors à la limite inductive (filtrante !) des j dans la catégorie des monoïdes pointés. Soit (M*,s") cette limite; désignons par i R : (M^,s R ) # > (M */3T) l'homomorphisme canonique. On dispose sur (M /s) soient en effet y et x Ç M" ; pour x et y tels que On pose alors d'une structure de y = i R (y) c et k SC-monoïde total : assez grand, on trouve Y = i k (x), et c R (y,x) défini. ^(7,x) = i k k (y»x) . Cette définition de T? ne dépend pas des représentants choisis; la vérification du fait que (M'/g-,^" ) est bien le SC-monoïde (total) libre engendré LC 32 par le SC-monoïde partiel (M* , s-, c.X, L'engendrement à partir d'un monoïde n est aisée. 7 M" d'élément neutre e s'effectue de la manière suivante : on adjoint librement un élément un monoïde cie le M* "contenant" c P-IJQ-I* Z T » = c(e,e) E(c ) SC-monoïde partiel (M' , s, c) ï\ e t z i hien choisis, et Q- est alors (s ,s) , pour (e,c ) . La loi de cohérence c , de domaines vi- est formelle puisque constitué des seuls couples suivantes: c(s P ,s) = s P M , ce qui fournit (M* , s, c) ^ „. n 0 9*0*9 est vide ; on obtient alors un de domaines à M" comme sous-monoïde. On lui asso- SC-monoïde partiel des. L'adjonction de s p > 0, (e,e) et est définie par les égalités c(e,e) = C Q , c(e,c Q ) = C Q . L'engendrement général peut alors s'effectuer comme plus haut. On voit que M* s'injecte dans M* , et on peut établir alors, par récurrence (reprenant les étapes de la construction générale ci-dessus), que sous-jacent au M* se plonge bien dans le monoïde SC-monoïde total engendré par M" M". Ce dernier fait peut s'établir plus rapidement en remarquant que M* se plonge bien dans le monoïde sous-jacent à un SC-monoïde particulier. Soit E* le monoïde des applications de M x i , On le pointe par l'application de succession par s(m,n) = (m,n+l) ; enfin, à tout couple fait correspondre M xlN dans s définie (g,f) Ç E x E on c(g,f) € E , définie par : c(g,f)(m,n) = f n (g(m,0)) . Il est trivial de constater que total. D'autre part, si l'on pose (E*, s, c) est un j(m')(m,n) on définit un homomorphisme injectif j de = SC-monoïde (m'.m,n) , M* dans E* . LC 33 B. Les SCL-catégories. Les SCL-catégories sont aux catégories de Peano ce que les SC-monoïdes sont aux monoïdes de Peano. Définition 1. Une catégorie à successions cohérentes libres , en abrégé une SCL-catégorie, est la donnée d'un quadruplet C. = (£ , i, s, k) dans lequel: (i) £ est une catégorie, (ii) pour tout objet C de C , (i ,s ) est un couple de flèches ainsi disposées : „ „„ ^ v (iii) k est une loi de composition qui fait correspondre à tout couple (f,a) de flèches ainsi disposées: T-» c *0 une flèche k(f,a) : NC > C soumise aux axiomes suivants: SCL. V C f , cette correspondance étant > C»^J, a k(f,a).sc = a.k(f,a) et SCL2 V c — £ - » NC c c k(f,a).ic = f k(f',a).k(f,sc,) = V '~^> "LL et les foncteurs d'oubli naturels Çatc Catn„T des SCL-catégories, > Cat et > Gra , qui sont évidemment algébriques ! Toute catégorie de Peano est une SCL-catégorie , i.e. Çat_ est une LC 34 sous-catégorie pleine de exemple typique de Cat POT • Nous verrons plus loin un oCL SCL-catégorie qui n'est pas une catégorie de Peano. La technique d'engendrement à partir de structures partielles est applicable à la construction de la C • Nous ne donnerons pas ici de dé- engendrée par une catégorie finition particulière de SCL-catégorie libre SCL-catégorie partielle, les mêmes re- marques et les mêmes constructions qu'au paragraphe précédent pouvant être conduites. Nous ne décrirons pas non plus l'engendrement complet de la SCL-catégorie libre, mais seulement une pre- mière étape possible, dont l'intérêt est de permettre d'appréhender la seule difficulté dans la question de la non triplabilité des catégories de Peano sur les graphes (cf.(A.M.E.N.) à ce sujet). Avant cela, nous devons modifier un peu le début des constructions du paragraphe précédent pour la raison suivante: soit £ une ca- tégorie ; si l'on veut construire la SCL-catégorie (resp. la ca- tégorie de Peano) libre engendrée par £ , la "première idée qui vient à l'esprit" est d'adjoindre formellement , pour chaque objet C de £ , le couple (i : C en posant formellement: c c (y,x) = k(y.i c ,x) > NC , s (resp. [y.i c ,x]) : NC •> NC) ; , on voudrait pouvoir décrire M = (End(NC) , s f , c p ) à partir du SC-monoïde (resp. monoïde de Peano) libre engendré par M = End(C) et profiter ainsi des constructions précédentes. A cet effet, les deux premières étapes consistaient en l'adjonction formelle à M des deux éléments s et c ; ces deux premières étapes doivent être modifiées ici, pour une description correcte de End(NC) , de la manière suivante : il faut adjoindre librement à M deux éléments s et c effet, le plongement qui commutent avec les éléments de End(C) — r — > End(NC) M ; en sera représenté corn- LC 35 me restriction du foncteur N : x | alors, d'une part » N(x) = k(i c .x , s c ) = k(N(x).ic , s c ) = c c (N(x) , s c ) $ N(x) commute avec s_ ; d'autre part , c = C C ( I d NC ' I d N C ) = k ( i C ' I d N C ) ' d ' ° Ù N ( x ) ' C o = V * * * = k(i .x , IcL r ) (axiomes SC. ou unicité !) Notons aussi que la valeur de cp est fixée sur les couples (N(x) , s c ) par 1' égalité cc(N(x) , s c ) = N(x) . En résumé, on doit partir avec le SC-monoïde partiel M- = (M* , s, c-)., n „ dans lequel: (i) M' est le monoïde libre engendré par M", s, c et les équations suivantes : x.s = s.x , x.c = c . x co 2 = co *, co. s °= co °, (ii) P.. et Z des : ,où x € M ( « End(O) sont choisis convenablement et Q. est l'ensemble (s P ,s) , pour p > 0, (e,e) , (e,c Q ) , (x,s) , x Ç M, (iii) c, est définie par les égalités suivantes: c 1 (s P ,s) = s P , pour p > 0 , c1(e,e) = C Q , c 1 (e,c Q ) = C Q , c1(x,s) = x , pour x dans M • On peut alors engendrer le SC-monoïde libre fï = ( M , s , c ) à partir de ]M- comme on l'a fait au paragraphe A. Les modifications à faire ne portaient donc que sur le passage de M" à H, • Gardant des notations similaires, voici la première étape de la construction de la SCL-catégorie libre engendrée par une catégorie £ , utilisant pour chaque objet C de £ la construction de M . p à partir de M„ « End(C) , puis celle de W à par1,L L ^ tir de M .i,u . LC 36 On constitue la catégorie £. de la manière suivante : (i) On dispose de deux copies de £ : l'une est même; l'autre, notée de N £ , a pour objets les £ , et pour flèches les che de C elle- NC , C objet N(x) , ou simplement x , x flè- C • (ii) On relie ces deux copies, dans le sens £ > N £ , en adjoignant des flèches i : L» C > NC , pour chaque objet de £ , dans le sens NC N £ > £ , en adjoignant des flèches k : $> C , pour chaque objet de £ . (iii) Pour chaque objet C de £ , on dispose du monoïde M* ( « End(C)) des boucles fermées en NC de la forme x , x Ç End(C) ; on constitue alors M. = (M* n, sn, c ) comme 1,L 1»C C C indiqué plus haut , et on aggrandit End(NC) d'au moins M ; A la notation — " x " — — — — (J permet de distinguer les éléments de M ; (iv) Disposant alors d'assez de générateurs: . flèches de £ et de . flèches i c et kc . flèches x des M N C , , C variable , , C variable , et disposant déjà des relations existant dans les £ ,N C , et Mç , C variable , on ajoute les relations suivantes: (s x ) k c .i c = Idc VSC = kC (s2) i c . k c = CQ , pour tout objet C de £ k , pour tout objet C de £ c«x = x.k tout (s3) x de et pour End(C) , f.ic = ic,.f f.sc = scl.f , pour t o u t e f l è c h e f : C >C de £ . Ces r e l a t i o n s sont n é c e s s i t é e s par l e choix de l ' o p é r a t i o n k , choix qui sera opéré plus l o i n . La c a t é g o r i e défi- nie par générateurs et r e l a t i o n s . £. est a i n s i LC 37 Nous avons besoin des lemmes suivants, dans lesquels nous reprenons les notations et définitions précédentes. Lemme 1. Quel que soit l'objet élément de C de £ , quel que soit , il existe un unique élément x = g(x) de - . p . et un unique entier p > 0 tel. que x.i r = s .ip.x • © M On supprime l'indice C > Mj >... M' >M^ dans les notations. Soit : >M^ >... >M la chaîne d'inclusions de monoïdes intervenant dans la construction de M (paragraphe A ) , la première inclusion M" >M* prenant en compte les modifications apportées au début du paragraphe B. . Tout élément de M- s'écrit de manière unique sous l'une ou l'autre formes s .c .x , s .x . o . De là résulte déjà l'unicité, car si x.i = s .i.x = sq.i.y , il vient d'abord : sP.x.i = sq.y.i , puis en composant par k sP.x.c = sq.y.c , ou encore o o p = q et x = y . à droite : d'où s .c .x = s .c .y , o o . De là résulte aussi la validité de l'énoncé pour P P P s .c .x.i = s .c .i.x = s .i.x o o P A OU . k = 1 , car (s 3 + 2 fois s ) * *• P . S .X.I = S .I.X . Supposons le lemme établi à l'ordre k et soit z un élément de M. - ; il existe, par construction, des éléments z i ' z 2 ' , , f Z n tels que z = zn ••••z^.z. , où z. est soit de la forme _ _ _ ^ A i c(y.,x.) , avec y. et x. éléments de M. , soit élément de M. , auquel cas il est licite de supposer que z. - n'est pas élément de "k- Faisons alors une récurrence sur n • - Si avec n = 1 , le seul cas à examiner est celui où x,y éléments de z = c(y,x) M. ; on a alors: I.i = c(7,x).i = 7.i (SC 2 + k épi.) et l'hypothèse de récurrence à l'ordre k s'applique . LC 38 - Si le résultat est vrai jusqu'à n-1 , deux cas restent à examiner: 1ercas. z"x Ç Mj^ et z 2 = c ^ , ^ ) , avec y2, 3^ € MR ; il existe un entier p ^ 0 et un élément x- de M tels que zf ••••z^.z-.i n 2 1 = z ••••z-.s .i.xn 2 1 (Réc./k) i ....z .x2.c(y2,x2).i.x1 (SC 1) = z" . ...70.xP.y0.i.xn 3 2 2 1 = z ....z3.s .i.xi.x- = s .i.y.x'.x- = q 2 cas. z x = c(y1,x1) , avec y ^ xx € ^ z" ... .z"2.c(y- #x,).i = x9 et y9 Ç K (Réc./k) s .i.x (Réc./n) ; on a : z ....z2.y-.i et on est ramené au premier cas si (SC 2 + s ) 1 (SC 2 + s^) z 2 = c ^ ^ x ^ , avec , ou à l'application directe de l'hypothèse de récurrence au rang k si C de peut s'écrire d'au moins une façon de la ma- vers NC C ^ Lemme 2. Soient NC et z 2 Ç VL ! deux objets de £ . Toute flèche x nière suivante : X où x. € M c = X .1 n :K , f i«t_ .X n n-1 i * . . . X-i i l - «X-* n-1 > ^ NC. . , 1 1 V provient d'une f l è c h e 1 f. : C. i î-l > C. de 1 C , Cn = C — © En effet, ces flèches k_ et les relations et 0 x C = C . n , celles de £ , les (s.). ,0 « ic , les définissent une sous ca- tégorie de £, ; c'est donc, par définition de 1'engendrement, la catégorie £- elle-même ! Lemme 3. Pour tout objet il existe un unique C Q de £ , et pour tout x € End(C) , soit x Ç End(NC) x = g(x) et un unique LC 39 entier p^O t e l s que = s p . i .x x.i . rv fi) En e f f e t , x s ' é c r i t , en vertu du lemme 2 dont nous reprenons l e s notations : A i — A — , A _ A _ x = x .f . x ., .f .. • •. .X- .f. . x~ ; n n n-1 n-1 1 1 x) on a alors : A*. X#1 C = — £ ~" X ,f , n A n Vl ,f — n-l M,,X l A ,f l — ,x O,iC = x . f .x^ - . f - . . . . f . . s P l . i r , . x r k n n n—i n—i l C u = A — X .t — = A . ... ... A . ... ... A ... = s n#i (s^J p 1.1. .f-«x~ (s-} P9 f 0 . s ^ z . i . . x ' . f , . x _ (lemme 1) 2 Ci 1 1 0 = x .f n n = ^ ...t^.X.«S A ~~ A p • • • t ^ . X - i . S 1 . 1 . . • 1_ .X_ A X .1 — (lemme 1) x .x . . . . C# n n .X- . i * «x,-, 1 1 0 , qui est bien de la forme voulue. L'unicité s'établit comme dans le lemme 1. © On établit de la même manière le lemme suivant. Lemme 4. Pour toute flèche que flèche f = g(¥) : C ? Ç Hom(NC,NC), il existe une uni> C et un unique entier q > 0 tels que ?.ic = s^.i^.f . Lemme 5. £ che h:C est une sous-catégorie pleine de £- et toute flè- > N C s'écrit de manière unique sous la forme h = s£f.i t.f , où f :C > C est une flèche de £ . A priori, une flèche de source et but dans £ sée d'un certain nombre de flèches de la forme est la compokrt.¥.ir.y , C où x et y sont dans C et où ? est dans flèche, on a les égalités suivantes: L» N£ . Pour une telle LC 40 k C''^ #i C* y = k c»#sq,ic',6^'y (lemme 4) = k c ,.s q " .ict.g(f).y (sx) = kct.ict.g(?).y (Sl q-1 fois) = g(f).y (encore s.) qui est bien une flèche de £ . La seconde partie du lemme s' établit tout aussi facilement. ^ © On est maintenant en mesure de définir sur la catégorie C^ une structure de SCL-catégorie partielle , en choisissant convenablement les valeurs de k(f,a) pour certains couples (f ,a) ainsi disposés : C Tout d'abord, les lois > *<^D i et dans £i • s ne sont définies que partiel- lement ; seulement pour les objets de £ : ce sont les i et les kc Ensuite, sées : C ajoutés plus haut, pour constituer soit C . (f,a) un couple de flèches de £ C ^ 'C k(h,b) = dans , où ainsi dispo- b€Mc,, h=sj,.i c ,.f, C ; nous poserons: ^.(s^,, b).f . On trouve alors: k(h,b).sc k(h, b).i = cc,(sj?,, b).f.sc = c r i(s3„ b).s ,.f C' v C " "'•"£*"• v(s_) o 3' = b.cc,(s2,, ^'* (SC X) = b.k(h,b) (déf.) = c ,(sj?,, b).f .1 = c = sj?,.ic,.f C t(s£,, b).ic,.f = h (s 3 ) (SC 2 + s ) Ainsi se trouvent bien satisfaites les égalités qui figurent dans l'axiome SCL . Nous allons vérifier maintenant l'égalité figurant dans 1' axiome SCL2 , en distinguant deux cas. 1 cas. Soit h : C > N C , avec h = s£,.i ,.f et soit C LL-^c"<^7)a dans C . , Nous calculons séparément les deux membres de l'égalité figurant dans SCL_. k(f,a).k(h,s c .) = kc„.c(IdNC„,â).f'.c(s^,,sc,).f = ^.0(1^,,,4).1^.8^,.1 (déf.) (C Q ) LC 42 = et = k(k c „.0(^,,,4).1^.8^,.^,^,a) = k(kc„.aq.ic„.f'.f,a) = k(kc„.ic„.aqif' .f,a) (s3) = k(aq.f.f,a) (s ) = kc„.c(IdNC„,â).âq.f'.f c(Id,l).sq - = (s3, SC][, SC2, s^) . (déf.) c(Id,â)âq j c(Id,â).c(sq,s) (CQ) q c(c(Id,â).s ,â) (sc4) = c(âq.c(Id,â),â) (SC = = q fois) q (C3) q (sc2) (c 3 ) c(â .c(Id,a).co,â) c(â .co,â) c(âq,â) c(Id,â).âq = c(Id,â)c(âq,s) (struc.de M ) = c(c(Id,â).âq,l) (SC4) c(c(Id,â).â .c ,â) o (C,) 3 = c(c(Id,â).c .âq,â) (struc.de M.,) = cas. q = = 2 c(Id,â).sq (déf.) = = et 3^ k(k(f',a).h,a) Reste à établir que or (s ^,,.0(1(1^,,,1).82,,.1^ q c(co.â ,a) (SC2) q (struc.de M.) q (C3) h = s q , . i , ,f , c(â .c ,â) = c(â ,â) Soit toujours h : C > N C , avec et s o i t C » NC " V _ l b ' a v e c h ' = s C " , i C , , , f ' e t * Ç **C"' Nous calculons de nouveau, séparément, les deux membres de l'égalité figurant dans SCL_. k(h',b).k(h,sc,) = cc„(s^„,b).f'.cc,(sq,,sc,).f (déf.) = cct,(s£„,b).f'.sqt.f (C Q ) LC 43 = cr„(s£„,b).sq„.f.f (s3) e t , d'autre part, on v o i t que : k(h',b). h = cc„dsl„,b).h.S^,.ic,.f = "b^.sP.i^.f.f ; posons alors, en vertu du lemmé 4, avec b ^ s ^ i „ = s£„.i .g g € C ; on peut donc calculer : k(k(h',b).h,b) = c(s*„b).g\î'.f (déf.) et il reste à prouver l'égalité : c(sP,,b).sq„ = Laissons tomber l'indice C" pour alléger les écritures: —N A , r ,b).c(g,s) —. c(s_r,b).| = c(s (struc.de M ) r = c(c(s ,b).g,b) (SC^) = c(c(sr,b).i.co,b) (c3) = c(c(s ,b).co.|,b) (struc.de M.) = c(sr.co.g,b) (SC2) r = c(s .i.g.k,b) (sx + s 2 ) = c^.sP.i.k.b) (déf.) q et c(s£„,b).g . P = c(b .s .co,b) (Sl) = cCB^.s^b) , (c ) c(sP,b).sq = c(sP,b).c(sq,s) P (c ) q = c(c(s ,b).s ,b) (SC^) = ctfâF.ctfs^b).!)) (scx) = c^.sPjb) (c ce qui achève l a preuve de v a l i d i t é de l'axiome deux fois) SCL- pour l a loi partielle k ( . , . ) . La v é r i f i c a t i o n de SCL3 e s t immédiate, l e passage de c ( . , . ) à k ( . , . ) n'offrant aucune d i f f i c u l t é au niveau des "constantes" des t h é o r i e s en q u e s t i o n . On v o i t que (C^ , i , s , k) e s t une SCL-catégorie p a r t i e l l e en un sens qu'on peut préciser maintenant : non seulement l e s LC 44 lois i et s sont partielles (définies objets C de £ ) , mais encore la loi uniquement pour les k , qui est "doublement" partielle, d'abord à cause de la limitation aux objets C de £, puis, pour ces objets, à certains couples (f,a) qui en sont issus, et non pas a priori à tous, car nous n'avons pas défini k(f,a) , lorsque tible à une boucle a est une boucle bouclée dans "a (d'un N£ non réduc- M p !) . Nous voyons que s'amorce ici une autre étape de la construction récurrente de la catégorie libre engendrée par n F, SCL- C • b ^ V NC. "*«C2 ^ - * = b ,. .f .b •••.f~.b~.f- .b. • n+1 n n 2 2 1 1 Nous terminerons en donnant un exemple de SCL-catégorie (totale) qui n'est pas une catégorie de Peano , ce qui nous assurera aussi de l'existence de de Peano. Appelons L SC-monoïdes qui ne sont pas des monoïdes cette catégorie, à définir. sont les INP , avec p > 2. p+1 On convient de désigner un élément de IN par (V,n) où V Les objets de la catégorie nommée est un élément de ]N L et n un entier. LC 45 On décrit alors par récurrence l'ensemble des flèches de L . Considérons l'ensemble L' des applications suivan- tes : ^JN^1 i : KP P V I—» (V,l) et : M1*1 s > IN**1 P (V,n) f—» (V,n+2) On c o n s t i t u e l a catégorie d ' a p p l i c a t i o n s L^ engendrée par L' . Supposons c o n s t r u i t e l a catégorie d ' a p p l i c a t i o n s L et u —m indiquons comment s ' e f f e c t u e l e passage de L à L.1 • On c o n s t i t u e l'ensemble d ' a p p l i c a t i o n s L t o u t e s l e s arrp p l i c a t i o n s m d i t i o n s suivantes : (i) L (h,a) et a i n s i ( i i ) k en ajoutant à s a t i s f a i s a n t l e s con- e s t un couple d ' a p p l i c a t i o n s appartenant à disposées : IN (h,a)oip = h (h,a)° s p = a k L'ensemble k!. ( h , a N) LV- > ]N q ^^^ , °Vh.a) * L' - engendre alors une catégorie d'applications L . .La catégorie L —m+1 — est la réunion des catégories Voyons ce que les conditions (i) et L . —m (ii) imposent à k (h,a) ' . Si (V,2n+1) Ç U 1 * 1 , on a : k (h,a)(V'2n+1) donc la valeur de kï. = "(h.a)-8^'1* = k = anok' a x«i(V) (h,a) p = an(h(V) ; (h,a)«Vip(V) <.(V,2n+l) est bien déterminée, pour v.h,aj tout V et tout n , par la donnée du couple (h,a) . LC 46 (V,2n) € IN1*"1 , on a : . Si k (h,a)(V'2n) = k = an et on peut choisir la valeur de (h,a)° S p ( V ' 0 ) °k(h,a)(V'0) kï, ' v(V,0) arbitrairement, a priori ! Pour définir la loi binaire partielle k qui fera de (L^ , i, s, k) une SCL-catégorie, on choisit,parmi les applications kï, x possibles,les suivantes : (h,a) .si (h,a) k^ N(V,0) n'est pas de la forme = \Llp3.) k (h,a) (h,a)(V'0) (p,h(V),0) , où l'on convient que si 1 h(V) = (W,q) , .si (s oi ,s ) , alors = p x h(V) = W (s oi ,s ) , alors P P P = (V 2m) ' La v é r i f i c a t i o n du f a i t que (L , i , s, k) est bien une SCLcatégorie est laissée au lecteur : e l l e est longue, mais ne présente pas de d i f f i c u l t é p a r t i c u l i è r e . Bien sûr, i l ne peut s ' a g i r en aucun cas d'une catégorie de Peano puisque, pour un même couple ( h , a ) , i l y a une multitude de kï, v possibles ! . . . Ch,a; LC 47 Bibliographie. T 'A*E'P* (a) L.COPPEY, Théories algébriques et extension de préfaisceaux, Cahiers de Topologie et Géométrie Différentielle, Vol.XIII,l (1972) T *A.E.P. (b) L.COPPEY, Compléments à l'article "Théories algébriQ u e s e t extension de préfaisceaux" , Cahiers de Topologie et Géométrie Différentielle, Vol XIII,3 (1972) S.B.D.S. L.COPPEY, Sur quelques structures de base pour définir les structures, Diagrammes, Vol.7(1982) E «D*S»A. C.LAIR, Thèse d'Etat, Esquissabilité des structures algébriques, Multigraphié, Amiens (1977) C.T.F.A. CLAIR, Condition syntaxique de triplabilité des foncteurs algébriques esquissés, Diagrammes, Vol.l, Paris 1979. A.M.E.N. L.COPPEY, CLAIR, A l g é b r i c i t é , M o n a d i c i t é , E s q u i s s a b i l i t é , Nona l g é b r i c i t é , à paraître dans Diagrammes, V o l . 1 3 , J u i l l e t 1985 . R.E.C.S. S.EILENBERG, CELGOT, Recursiveness, Académie press, New York and London, 1970. JP.AZRA, B.JAULIN, Récursivité, Collection "Programmation", Gauthier-Villars, Paris,Bruxelles,Montréal, 1973. R.E.C.U. U *S.R.U. R.MIJOULE,L'universalité des semi-fonctions récursives universelles, Diagrammes, Vol.12 (1984)