D IAGRAMMES R. M IJOULE L’universalité des semi-fonctions récursives universelles Diagrammes, tome 12 (1984), exp. no 2, p. M1-M12 © 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, Volume 12, 1984, A.M.S. Sub. Class. 18 A 15 , 03 D 75, 03 G 30, L'UNIVERSALITE DES SEMI-FONCTIONS RECURSIVES UNIVERSELLES. par R. Mi joule Soit E une catégorie k limites finies. Sur la théorie des catégories indexées, le lecteur pourra consulter l'article de Paré et Schumacher (6). Voici cependant quelques notions indispensables à la compréhension du texte. Une catégorie E-indexée objet I de A est la donnée, pour chaque E , d'une catégorie phisme J — - — > I de A , et pour tout mor- E , d'un foncteur a : A ^ A , appelé substitution le long de a • Ces données doivent être fonctorielles, i.e. vérifier les égalités suivantes: (1 I* = 1 AI (e ' 'a)* = a *e* ' En particulier, E devient elle-même une catégorie E-indexée £ , en posant £ = E/I et a étant le changement de base le long de a • Pour tout objet rie E-indexée discrète [K] K de , où [K] E, on a une catégo= et HOIÏL_,(I,K) où les substitutions le long de a sont les compositions avec a • Un foncteur E-indexé de pour chaque objet I de B F , ces foncteurs tions. A vers B_ est la donnée, E , d'un foncteur F de A vers devant commuter avec les substitu- M 2 Soient f et g buts respectifs deux flèches de même source A et B et de , dans une catégorie où le produit A x B est défini. On désigne par vers A x B (f ,g) la flèche de D qui s'en déduit (ceci suppose bien évidemment que les projections de Si D 1 A x B vers A et B sont spécifiées), est objet final d'une catégorie, et si I est un autre objet de cette catégorie, on désigne encore par I l'unique flèche de I vers 1 . La catégorie E sous-jacente à la théorie a été supposée à limites finies. On fait sur elle une autre hypothèse : c'est le choix d'une flèche particulière CU -f ^ UJ qui a la propriété de classifier les flèches partielles de codomaine U). Bien sur, la flèche °? est nécessairement un monomorphisme, puisqu'elle représente la flèche partielle "identique" de UJ vers UJ , correspondant à Id I - Une théorie abstraite de la récursivité. Soit S une sous-catégorie de On suppose que UJ et W A on note S(A, uj) un obiet de ~ I "Los floches de est dans de S S et que les sont composables dans S . Pour chaque objet I de S , la catégorie discrète ayant pour objets I*A vers S , le foncteur S(A,LO) h produits finis. sont des objets de flèches partielles de but CO dans S . Soit E vers I*uu dans S/I . Si J —^—> I a se restreint en un foncteur S(A,aj) , que l'on note encore d . On obtient de cette manière une catégorie S-indexée S(A,uu). Nous pouvons alors énoncer l'axiome de base de notre théorie: AXIOME. Pour tout objet A de tondeur S-indexé U : IM-U S , A ^ 1 , il existe un > S(A,UJ) et un foncteur M3 S-indexé soit SA: ) S(A,UJ > [ u / } t e l s que l e composé U .S le foncteur i d e n t i t é de S(A,cu). En u t i l i s a n t l e lemme de Yoneda, l a donnée de U de- v i e n t é q u i v a l e n t e à l a donnée d'un élément g é n é r i q u e X de S(A, u i ) S qui est . Notons CP l e composé de : U) x A p 2 e t de projection d e c o x u j > UJ l a f l è c h e de X A> où p 2 d é s i g n e l a deuxième d a n s u!) . On o b t i e n t donc q u e , pour t o u t o b j e t f e x i s t e une f l è c h e dans h f de I v e r s eu, S(A, Cu) 1 , de il S , telle que S-semi-calculable tout c/.(h,lA) = . Définition 1 . On a p p e l l e f o n c t i o n é l é m e n t de S de but uj , e t f o n c t i o n é l é m e n t de S de b u t CO. S-calculable tout A Théorème 1 . (3 e s t une f o n c t i o n s e m i - c a l c u l a b l e u n i v e r s e l s l é . Pour t o u t e f o n c t i o n S-semi-calculable f : co x A » uj i l e x i s t e une f o n c t i o n h Cp - ( , l A ) pour f A h : co >uu t e l l e A . En d ' a u t r e s x Ç UJ e t Corollaire. de = S-calculable termes, q> (h(x),y) - que f(x»y) y Ç A. Cp onumère l e s f o n c t i o n s S-semi-calculables d a n s uj . On s u p p o s e que l e s f o n c t i o n s S-semi-calculables sont compo- sais l e s . Théorème 2 . Soit h : eu l a b l e . Pour c h a q u e o b j e t Loi que pour CP ( t P (e,x),30 ^ (A) une f o n c t i o n A = de S A S-semi-calcu- i l e x i s t e un é l é m e n t e f eu (i> (h(x),y) pour x € u) et y Ç A . Preuve. Si h est S - s e m i c a l c u l a b l e , p a r c o m p o s i t i o n on d é - duit que Ci) ( h ( x ) , y ) est S-semi-calculable, Cu . 1 1 e x i s t e donc 9 : UJ >uJ de eu x A S-calculable telle dans que M 4 Cf> A (9(x),y) Comme CP C|?A(h(x),y) , = pour énumère l e s f o n c t i o n s dans u> , i l e x i s t e pour x € UJ . O n o b t i e n t x f uj donc l e (/^(ejx) Avec un bon c h o i x de S-semi-calculable. - tP ( e , y ) = Y(e,y) Cp ( f ( x ) , y ) = Il existe pour ^ et, il existe A t e l que Soit un o b j e t A on n o t e (^ dans - LP ou d'après = tf A de S et cp . ( e f l y e A, on a ip (y) A Théorème 4 . Pour c h a q u e o b j e t = S-calculable eu le théorème = f I x A > tu ; L UJ ci-dessus, A UJ t e l l e pour de termes, S , il existe et Preuve. I l s u f f i t l e composé u n i v e r s e l l e . Si la fonction A [S^(e,x)}A(y) que h (f ( ( ^ ( n . n ) ) , ? ) iP par fonction que (n,n). {e} LU d é f i n i e > 1 , \ Cj> ( ^ ( n . r O . y ) Ip^C^Cn.rO.y) telle y £ A . Soit > UJ x UJ — » h est S-semi-calculable, » OU une y f A, ^ (x,y) e . e f eu t e l > uJ S - c a l c u l a b l e de p o s e r y € A, CO x A : uj UJ D'où M/ : pour t o u t suivant n 0(x) h , on a l e fonction A f pour Cj?A(h(e),y) Théorème 3 ( d e r é c u r s i o n ) . S o i t Preuve. Soit = de UJ résultat. On r e m a r q u e que l ' o n a en p a r t i c u l i e r , = y f A. S-semi-calculables e f UJ t e l que lj>A((^(e,e),y) et à M 5 Exemples. 1) Soit E la catégorie dont les objets sont les en- sembles de la forme IN de ces ensembles et p G IN, les sous-ensembles , pour ]N U {u*} . Les flèches de applications entre ces ensembles. On pose UJ - IN U {u} • Soit S sont les 6J = IN et la sous-catégorie de E ayant P pour objets les ensembles E IN et IN U {u} . Les flèches de S S vérifie bien les propriétés énoncées ci-dessus. Pour cha^ que sont les fonctions semi-récursives . On remarque que A = IN , V est une fonction sem^-récursive univer- selle à (p+l)-places, Si S(A,CO) ves I = IN f de représente une famille de fonctions semi-récursi- (f.) indexée par I . Alors S (f) est la fonction Pi L récursive de méro de , un élément ]N dans IN qui à i f IN associe le nu- f. • 2) Soit tu l'ensemble des entiers naturels et posons: T (0) = Uû , T ( J + 1 ) = T tj) dans Soit E UU , pour l'ensemble des fonctions totales de jf W . la catégorie dont les objets sont les T , les produits de ces ensembles, les sous-ensembles de ces ensembles et UJ = UJ U {u} . Soit S la sous-catégorie de pour j f UJ , les produits de ces objets et UJ . Les flèches âo sont les fonctions partielles récursives au sens de S Kleene. La description de U E ayant pour objets les T et de S est la même qu'au 1), Si l'on revient à nos définitions initiales, on a UJ c E , en désignant encore par E l'ensemble des flèches de intéresse donc aux fonctions partielles de E E . On s' dans OU et en particulier à une certaine classe de ces fonctions que l'on code par UJ . M 6 Cette remarque permet de faire un peu le parallèle avec les fonctionnelles J -récursives définies dans (5), les fonctions S -computables définies dans (3) et les BRFT définies dans (4). Notre point de vue se rapproche plus de ceux de Fenstad et de Friedman. Définition 2. Soient —,—, „.,,,.„ A, Al9..,,A 1 " *n des objets de S . Soit Gf une application de l'ensemble produit des fonctions semi-calculables de lions S- dans UJ vers l'ensemble des fonc- A. S-semi-calculables de A dans UJ . On dit que Gf est représentable s'il existe une fonction S-calculable f :u/ i > CU telle que G ^ O j } , ...,0)) = £f (ex,. . . ,e )} pour tout e.,...,e dans U) . Théorème 5, Si • i G G G ' J= S(A,,OL>) X ... X S(A , Qj) et de but S(A,Çu), n est représentable. Si indexé S-indexé de source la ca- •, tégorie produit 1 alors est un foncteur G 1 G Preuve. Gc de est représentable, il existe un foncteur S(A , Çu) x...x S(A ,UJ) vers S- S(A,cu) tel que n • Considérons le diagramme c i - d e s s o u s : tu)nJ«[u)]x . . . x[uu] — > S(A1,U)) x . . . x S(An,0>) G S V [uj]< où H = U S(A,UJ) x ... x U 1 te f f S , Comme F est S-indexé, il exis- F . Donc G est repréaentable. n tel que Réciproquement, si on a un foncteur [fj= G 1 est représentable par f : UJ S-indexé [f] tel que: Gf.(U^ x ... x U* ) =« U*. [f] . —*UJ, M 7 En u t i l i s a n t le lemme de Yoneda, on c o n s t r u i t l e f o n c t e u r S-indexé t e l que G = G G' . Proposition 6. 1) L ' a p p l i c a t i o n qui à (f.f ... , f ) associe f. est repré- sentable. £ ) Les a p p l i c a t i o n s r e p r é s e p t a b l e s sont s t a b l e s par composition. On en décjuit a l o r s l e r é s u l t a t Théorème 7 . (du pqint f i x e ) . de S(A,CO) calculable vers Soit G un foncteu^ S-indexé, I l e x i s t e une f o n c t i o n S(A,UJ). f : A-, "classique": l > UJ t e l l e que G (f) = S-semif . Preuve. D'après le théorème 5 , i l e x i s t e une f o n c t i o n S - c a l culable g :W^ » ^ t e l l e que G ({e}) le théorème de r é c u r s i o n , i l e x i s t e e [et] , I l suffit de poser II - Sous-objets S-semi-calculables. So}.t S A' A un o b j e t de e s t un objet de Définition 3. , • • • f : A A = [ g ( e ) } . D'après Ç OU t e l que {g(e')}= un s o u s - o b j e t de A . f = {e'} . et A' E , mais pas nécessairement de On d i t que A' e s t un s o u s - o b j e t , ,-. culable de u 1 s'il existe une fonction S. S-semi-cal- , , • "1 '•! S-semi-calculable '•• • ' > UJ <\e domaine P r o p o s i t i o n 8. Les o b j e t s A' . S - s e m i - c a l c u l a b l e s sont stables par changements de b a s e . Soit A uri objet de t r u i t une c a t é g o r i e si I S . Grâce à c e t t e p r o p o s i t i o n , on consS-ir)dexée e s t un qbjet de S , S(A) S(A) est la catégorie d i s c r è t e dont l e s o b j e t s sont l e s s o u s - o b j e t s 1 x A , et, si a î J ———^ 1 t o n d e u r qui à A'> S - s e m i - c a l c u l a b l e s de est dans S , a est le > I ^ A a s s o c i e B')—71—> J x A , où où IP' est l'image réciproque de bré)t de l a manière s u i v a n t e : A* par a x 1. (produit fiA M 8 Proposition 9. Il existe un foncteur source S(A,OJ) S(A,u>) et de but LU , notons objet S(A) qui à aspocie le domaine de En particulier, si ~^ A P ({> f de élément de est universelle, de A A de dom p^.f . l e domaine de S-semi-calculable S-indexé CP . p^ 6U x t\ dans e s t donc un s o u s - u) x A . A Théorème 9 . P vérifie jet et tout sous-objet I de S la propriété suivante I X A , i l e x i s t e une f o n c t i o n t e l l e que et S-calculable h : I F P ( h ( 3 ) , 7 ) pour x Ç 1 y Ç A . Le diagramme c i - d e s s o q s e s t donc Lfn p r o d u i t F , , ^ p A ]f I x A h x 1A f : I x A > UJ F . Il existe donc 0(x)](y) = f(3,y) fibre: vj/ ;> u) x A S-semi-calculable de domai-r h : I pour de t * •• > U> A F(5c,50 s i et seulement s i Preuve. Soit ne ; pour t o u t o b - S-semi-calculable x 6 I > OU S-calculable telle que et y e A . Par produit fi- bre, on en déduit le résultat. A Corollaire. P est un sous-objet S-semi-calculable universel de UJ x A qui énumère les sous-objets S-semi-calculables de A . III - Structures récursives, péfinition 4. On appelle structure récursive la donnée dfune catégorie E E à limites finies, d'une sous-catégorie vérifiant les conditions du paragraphe plus que le foncteur S-indexé S S de I . On impose de •> S x S admet un adjoint M 9 à gauche en (l,u>) et que sa valeur e s t W , On obtient en particulier deux fonctions CU ", ' ") UJ telles que S-calculables 1 -> uj et . OU OU soit une somme dans S . On retrouve à présent toutes les théories faites sur la ré T cijrsivité. On obtient ep particulier la Proposition IQ, Il exista une fonction a : UJx UJ x UJ S-calculable r-r-* OU telle que si = 0 si t a(a,x,y) = Preuve. tions 0 On u t i l i s e l ' u n i v e r s a l i t é de l a somme avec l e s f o n c S-calculables uuxuj -r^ujet Théorème 1 1 . I l e x i s t e un f o n c t e u r S-indexé S(A,uJ) x S(A,Co) p : et de but si h : A on ait c a l c u l a b l e s , et s i f S(tU x A,uj) -> t u et g : A = C (h,g) h(y) SI g(y) 51 p 3 : oOxiOxuJ CA de source t e l que, en 1 , - ^ CU sont S-semi- alors: f(y7 = Preuve. En effet, pour tout \ ions S-semi-rcalculables, de * I , soient 0 h. et h des f o n c - I x A dans 00 , car I U C U Ï x I ) . Posons a l o r s Théorème 12, " et et 0- # de I dans h2 . p ? ; c'est une flè- C O x I vers U ) . On en déduit alors unç fonction calculable = bj 0- • Supposons que UJ x I ^(h^t^) E = = U^ S- (lLJu-OxI X J (0) . s o i t une s o u s - c a t é g o r i e de r et que UJ soit l'ensemble des entiers naturels. Alors Ens les fonctions semi-récursives sur u) sont des fonctions ST semi-calculables• Preuve. La démonstration est classique. Je rappelle simples ment les constructions: 1) Soit f réoursive à application H : F - (n+l)-*places . Considérpns 1' -^ F définie par: si f(y,x xî ...,x n ) H(g)(y,x lf ...,x n ) ~ s(g(^(y),x T , f ..,x n ) si f(y,x 1 ,...,x n ) + Par le théorème du point fixe, il existe soit égale à re H 2) Soient F n+1 0 h telle que H(h) h . Posons /^f(x,,...,x ) = h(0,x, ,...,x ) • g € Fn -> et h Ç F n * récursives. Soit encoF n+1 définie par: gvX-,•.•, X ) SI n+1 = 0 H(k)(x.I.I.,X ,.) = 1 n+1 h(x1,...,xr)+1,k(x],,.. f .,xn,x^+1 - D ) si Si 1 est un point fixe de H , alors f n+1 * est définie par 0 M 11 récurrence à partir de g et de h . Le résultat ci-dessous afferme que, sous certaines conditions, A U> est un NNO Théorème 13. Soit dans S/A , pour tout objet A un objet c}e S . Si dans te des éléments 1 iX > A*CU existe un élément m : A u> et m s = ^ A CO x A* h k S( e u x A,CL)) S-indexé de f g.p^ » x S-serçi^calr* A g * S* x I S ( c o x A,u)) dans de S , soit = u n objet b . On remarque dfabord que la fonction pré- décesseur p est S-calculable en utilisant rant m 0 est associé une fonction £((^ x AfUJ) . Pour tout objet b il e x p - k . F Posons S/A tel que h : U) x A ——^-> 60 telles que On construit un foncteur de S . A*OU , il est associé une fonction g : A — « — ^ CO et à semi-calculjable et A*tU——» de k m • Preuve . A l'élément culable et A b.(l ,p,l ) 1 > u) <'• •» (x) f et soit h.(b ,p 2 ). En considé- et cette dernière fonction, on arrive à une fonc- I x UJ x A dans uj . I /^ I On obtient ainsi une application G de S(CU x A,eu) dans /v i tion S-semi-calculable de S( a; x A, ou) . Il est facile de voir que l'on construit de cette manière un foncteur S-indexé de S( UJ x A, u)) dans S( co x A,ou) . D'après le théorème 7 , G que (f,p~) admet un point fixe f . Mpntrpns répond à la question, c'est-à-dire satisfait les deux égalités voulues. On utilise pour ce faire le fait que Co x A est une somme de Définition 5. Soit spus-objet de A et de U)x A , Il existe une fonction calculable (jj x (jJ -r- Corollaire. ble de A A un objet de A . On dit que A 1 S et A' > ^ A ^OJ* un est un sous-objet S-calcula- s'il existe une fonction S-calculable f :A > OJ M 12 t e l l e que A1 s o i t le produit f i b r e de f et de 0 . P r o p o s i t i o n 14. Les o b j e t s S - c a l c u l a b l e s sont s t a b l e s par changements de b a s e . S i A' e s t un s o u s - o b j e t b l e de ^A e s t dans A et h : B« produit fibi^é de b l e de Af e t de h S-calcula- S t a l o r s l ' o b j e t A" e s t un s o u s - o b j e t Sr-calcula^ B . a suivre.•, 1) J.P.AZRA et B.JAULIN, Récursivité, Collection Programmation, Gauthier-Villars (1973) 2) S.KLEENE, Recursive functionals and quantifiera pf finite types, I, Trans. Amer. Math. Soc. 91 (1959),1-52, 3) J.FENSTAD, Genaral recursion theory, Perspectives in m^thematical logic, Springer-Verlag (1980). 4) H.FRIEDMAN, Axiomatic recursive function theory, Logic colloquium °69, North-Holland (1971) 113-137. 5) A.KECHRIS and Y.MOSCHOVAKIS, Recursion in higher types, Handbook of mathematical l o g i c , North-Holland, (1977) 681-737. 6 ) R.FARE et D.SCHUMACHER, Abstract f a m i l i e s and t h e a d j o i n t f u n c t o r theorems, Lectures n o t e s i n mathematics, 6 6 1 , (1978) 1-125.