D IAGRAMMES

R ICHARD M IJOULE
Une généralisation des ensembles énumérés
Diagrammes, tome 21 (1989), exp. no 4, p. M1-M13
<http://www.numdam.org/item?id=DIA_1989__21__A4_0>

© Université Paris 7, UER math., 1989, 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

21

UNE

GENERALISATION
DES
ENSEMBLES ENUMERES

Richard Mijoule

A Armande

INTRODUCTION,

Il y a eu beaucoup d'ouvrages sur une théorie de la récursion,
mais également sur une description algébrique de cette théorie,
Ce que je propose ici est une généralisation de la notion
d1 ensemble énuméré introduite par Ersov (voir par exemple (2)).
Intuitivement, au lieu de se mettre au même niveau que N ou
N** ou N r s J , c'est à dire dans la catégorie E n s
, on
considère les fonctions récursives (ou partielles récursives)
comme des éléments de E n s M
, En effet, les principales
propriétés des fonctions récursives utilisent plus des concepts
provenant de E n s ^
que de E n s
Ainsi toute fonction partielle f; A x B -»N sera identifiée
à une famille (f*)««A de fonctions partielles de B dans N en
posant fm(b) = f(a«b) , pour tout b c B ,

PRELIMINAIRES.

Si
E
est une catégoriel on rappelle qu'une
catégorie
Eî.-indexée
A
est la donnée, pour chaque objet I de E ,
d'une catégorie A 1
et pour tout morphisme oc;J 4 I de E ,

A . M. 3.

Sut».

Cl«iss.

03

D

75

UNE QENCRALZSATION

DES

C N S E M B L C f i CNUMGRCfl

d'un foncteur oc*; A 1 4 A J
appelé substitution
le long de es ,
Ces données doivent vérifier les égalités suivantes:
<lx>**l«r
et
(ft.a)* » a*8&* .
En particulier! E devient elle-même une catégorie
E-indexée
z
E
en posant E
• E / I et oc* étant le changement de base le
long de oc .
Pour tout objet
K
de
E 1 on a une catégorie
E-indexée
1
discrète
[ K ]
* où
[K3
= Homard,K)
et où les
substitutions le long de oc sont les compositions avec oc ,
Un foncteur E-indexé de
A
vers
B
est la donnée, pour
chaque objet
I
de
E , d'un foncteur
F X ; A X -> E?x , ces
foncteurs devant commuter avec les substitutions. Pour tout
complément sur ces notions voir (3).
Pour la suite , on se fixe une catégorie
E
à
limites
finies, munie d'un objet e et d'une flèche
i\\ e -* fi qui
classifie les flèches partielles de codomaine e e
Les notations que l'on prend sont celles de (1).
Soit S
une sous-catégorie de E
à produits finis.
On suppose que n:& -* 8 est élément de S ,
Soit A un objet de S .
Pour chaque objet
I de S , on note S(A, 8 ) x
la catégorie
discrète ayant pour objets les flèches de I* A vers I* 8 dans
S/I .
Si «:J •* I est dans S , le foncteur a* se restreint en un
foncteur de
S (A, S ) 1
dans
S ( A , 8 ) J , que l'on note encore
oc* . On obtient de cette manière une catégorie
S-indexée
S(A,S) .
Il est à noter que la donnée d'un élément de
S(A,ff) ï
est
équivalente à la donnée d'une flèche dans S
de I x A dans
S v Donc tout élément de
S(A,S)1
représente une flèche
partielle de I x A dans S ,
Avec ces données, on se donne les hypothèses suivantes:
- pour tout objet A de S
, A * 3 , il existe un foncteur
S-indexé
VA: [e] -> S(A, S)
et un foncteur
S-indexé
S A : S (A, 3) -» [e] tels que le composé <pA, S A
soit le foncteur
identité sur S(A,8) ,
La donnée du foncteur <pA est équivalente, par un argument du
type Yoneda, à la donnée d'un élément XA de S(A, S ) " appelé
élément générique.
La donnée de XA est donc équivalente à la donnée d'une flèche

UNE

QCNCRALXSATXON

DES

CNfiCMOLCS

CNUMERE9

partielle de e x A dans 8 que nous noterons encore <pA ou
encore { } A .
L'élément XA
possède la propriété suivante:
- pour tout objet
I de S
et toute flèche h; I -* e dans
x
S , on a <pA (h) = h*(XA) f
La donnée de S A
permet alors d'avoir:
Proposition,
Pour tout élément
f : I x A -• 8 de S , il
existe
h: I -> e dans S
tel que * A . (h x 1A> = f . C'est à dire que le
diagramme ci-dessous est commutâtif]

h x 1A
I x A

Définition,
On appelle fonction
de S
de but 8 et fonction
S
de but e .

S-semi-calculable
toute flèche
^-calculable
toute flèche de

Par convention, si t:l 4 « est une flèche de S , on notera
6ctt . Pour deux flèches
f«g;A -* 8 de S , si
f = g , on
écrira souvent: f(x) = g(x) pour xcA .
Exemple, Soit E » E n s
et S
la catégorie des fonctions
p
récursives partielles de N
dans N
où p parcourt N . Un
P
Nq
élément de S ( N , N w { u } )
est donc un triangle commutatif:
f

>N^ x (Nu{u})

et par conséquent,
f est une fonction indexée
(fk)k«N<31 où
p
p
f*:N -» Nu{u} . Dans ce cas, <p,^
est une fonction récursive

M

3

UNE QENCRALXSATXÛN

D E S BNSEMfiLE9

CNUHCRCS

partielle universelle à p+1 places,
Dans (1) on démontre le résultat suivant:
Théorème, Pour tout objet
A
S-semi calculable
universelle
S-semi-calculables
de A dans

de S , fA est une fonction
qui
énumère les
fonctions
8.

On en déduit:
Corollaire,

Il existe

(piia 4 8

universelle,

Preuve, Soit <p«;e x e 4 8 universelle, Il suffit de prendre
pour 91 le composé
û
9«»
e
^ exe
^ 8
La vérification est simple. Fin de la

preuve,

On obtient également (voir(l)):
Théorème de récursion,
Pour tout
calculable,
il existe ftee tel que
y€A .

f:e x A 4 8
9A(9,y) » f(ô,y)

S-semi pour tout

Définition,
Soient A, Ai, A2, ... , A„ des objets de S . Soit
G1
une application de l'ensemble produit des fonctions
S-semi-calculables de
A±
dans
8
vers l'ensemble des
fonctions S-semi-calculables de A vers 8 . On dit que 6'
est représentable
s'il existe une fonction
S-calculable
ô:e° 4 e telle que, pour tout &i, ,,,,en
dans 0 , on a:
6l({tti}Au...f{e.i}An) * { « ( e l l , i 0 l e „ ) } A .

En d'autres termes, le diagramme ci-dessous est commutatif,
H1
[e*1]1 s [[e]"]1

> S ( A , , 8 ) 1 x f i f x S(A T ,,S) 1

[e]1

? S(A,8)'
^

1

UNE QENCRALISATXÛN

DES

CNSEMOUCd

CNUMCRCS

où H est le foncteur S-indexé
fA1 x. ,.x <pA„
foncteur S-indexé composition le long de 0 .
En récursivité, cette notion correspond
fonctionnelle récursivement représentable.
Théorème, Si
G;S(A,,8)
foncteur
S-indexé, alors

à

et

la

x,,.x S(A„,8) 4 S(A,8)
G1 est
représentable,

[e]

le

notion

de

est

un

On généralise donc de manière simple (par des foncteurs indexés)
deux notions: d'une part celle de fonctionnelle récursivement
représentable et d'autre part celle de morphisme entre deux
ensembles énumérés défini par Ersov dans (2),
Corollaire,
Si 6:S(A, S) 4 S (A, 8) est un foncteur
il existe une fonction
^-semi-calculable
f;A 4 8
GMf) = f ,

S-indexé,
teJJe que

On retrouve donc le théorème du point fixe,

STRUCTURES RECURSIVES.

Considérons le foncteur S-indexé diagonal û: S 4 S x S ,
Soit l'objet
(l,e) de ( S x S ) 1 . On suppose que û admet un
adjoint à gauche en (1,e) et que la valeur de cet adjoint en
(1,e)
est
e . On en déduit l'existence, dans
S , de deux
flèches o: 1 4 e et s;e 4 e . On a la condition d'adjonction
(voir(3)):
I*e 4 a
dans S/I

!*(!,*) 4 ûxa

dans

S/I x

S/I

pour tout objet I de S
et tout objet a de S / I .
En particulier, le diagramme ci-dessous est une somme dans

UNE QCKERALXSATZOM

o
1

Proposition, Il
a:exttxe4e

DES ENSCMBLCS

CNUHCRCfl

S

4

existe
teiJe que:

une
"x

fonction
si

a =O

si

a * 0 .

i-calculable

oc (a, x, y)

La fonction oc trouvée est une donnée de base dans (4),
Nous allons à présent redémontrer deux notions de récursivité,

à savoir: la définition par cas et le schéma de
L'originalité de ces démonstrations
réside
formalisations en termes de foncteurs indexés,

récurrence.
dans

leurs

DEFINITION PAR CAS.

Théorème. Soient
g: A 4 8 et
h:e x A 4 8 deux fonctions
S -semi-calculables,
Il existe une fonction
S-semi-calculable
f;e x A 4 8 telle que les diagrammes ci-dessous commutent:

[o]

Preuve. Par l'universalité de <pA i l existe ô€» et 0 : e 4 0
S-calculable t e l s que ?A. # s g et <pAi © » h .
Il existe aie 4 0 S-calculable t e l l e que les diagrammes c i dessous commutent:

w 6

UNE OBNERALISATION D E S CNSCHOLfS B N U M B W 8

Posons f = <<pA)- . Ainsi f : [*] -» S<A,8> ,
De oc.o a e on déduit que <M<*.o,y) a fA<ô,y) » g ; d'autre part
<pA(a.o,y> • fA(a,y).o « o*f , D'où o*f » g et par conséquent
f.fo] = g .
De
mené
««(cc.s^)
=
<pA<e,y)
=
h
et
•A<cc.s,y> * ««(ot.y^s = s*f .
Donc h - s*f et par suite h • f,[s] , Fin de la preuve.
On remarque qu'en

1 le diagramme ci-dessus se traduit par:
^g<y)

si n » o

h<n,y)

si

f(n,y)
n 4 0

et qu'en
I
il se traduit par l'existence d'une fonction
S-semi-calculable f telle que:

f'(i,y) »

où

k : N a

est

"g<y)

si

k(i) = o

_h(k(i),y)

si

k(i) * 0

-

S-calculable.

LE SCHEMA DE RECURRENCE.

Théorème. Soit fl»:S<A,S) •• S<A,8)
un foncteur
S-indexé
et
g: A -» S une fonction
S-semi-calculable.
Il existe une fonction
S-semi-calculable
f : « x A •» 8
telle
que les diagrammes
ci-dessous soient commuta tifs;

M

r

UNE QENCRALXâATIûN

DES CNâCMBLCâ

CNUMCRCâ

[s]
+ [«3

[•]

[i]

S(A,S)

i(A#«)

0
Preuve, On trouve la preuve en (1), Fin de là preuve,
un rentarque que

[0]

se comporte comme un

Exemple. Soient g: A 4 S et
Alors la fonction f:e x A 4 S

NNO

dans un topos,

h:e x A 4 S
définie par;

S-semi-calculables,

g(y)

si

n = 0

h(f(n-l#y),y>

si

n^O

f(n,y>

est S-semi-calculable,
Pour voir cela, il suffit de considérer le foncteur
S-indexé
a>,S(A,8)
4
S(A,S) ,
défini
en
I
par
z
<t> (k)(i,y) » h(k(i,y),y) , et d'appliquer le théorème ci-dessus,

OBJETS

S-CALCULABLES

Soit A un objet de
1
A
est un objet de

ET

S-SEMI-CALCULABLES.

et A1 un sous-objet de A . Alors
mais non nécessairement un objet de

Définition,
On dit que A1 est un sous-objet
S-semi-calculable
de
A
s'il existe une fonction
S-semi-calculable
f:A 4 8
telle que le diagramme ci-dessous soit un produit fibre:

ENCRAI. XSkATIQM D E S

ENâCMBLCS

CNUMERC8

A'
Y

A
Dans ce cas. on pose A1 = dom f ,
Cette notion
énumérable,

coïncide

avec

celle de prédicat

récursivement

Définition,
De même, on dira que
A* est un
sous-objet
S-calculable
de
A
s'il existe une fonction
S-calculable
f:A 4 0 telle que le carré ci-dessous soit un produit fibre:

Plusieurs propriétés de ces sous-objets sont établies dans (1),
En particulier«
Théorème, Si
Ai
et
S-semi-calculables
de
A
sous-objet
S-semi-calculable

A2
sont
des
alors
Ai o A 2
est
de A ,

sous-objets
encore un

Pour chaque objet
A
de
S , on construit une catégorie
S-indexée
S(A)
, en considérant pour
S(A) 1
l'ensemble
ordonné des sous-objets
S-semi-calculables de
I x A . On
démontre que pour chaque objet
A
de
S , il existe un

UNE QCNERALXdATZÛN

DES CN&CHBLCS

ENUHCRCfi

sous-objet S-semi-calculable P de 0 x A universel,
Le théorème ci-dessus dit simplement que le foncteur
S-indexé
diagonal û: S ( A ) 4 S(A> x S ( A ) admet un adjoint à droite que
l'on note n ,
Le but à présent est de montrer que les sous-objets
S-semi-calculables de 0 x A sont stables par projection sur A
i, e, 1 si P(n, y) est S-semi-calculable alors 3n P(n,y) est
S-semi-calculable,
On remarquera que la démonstration ne fait pas appel à un
théorème de sélection mais utilise un théorème d'existence
d'adjoint à gauche.
On supposera que E
est un topos et on reprend les notations de
(1) et (3).
Définition.
Soit
B
un objet de
S , On dira que
B
est
S-fini
si:
(i) sub(B) est un objet de S ,
(ii) € B >
> sub(B) x B est S-calculable,
(iii) l'universabilité de sub(B) se restreint à S ,
(v) l'égalité sur
sub(B)
est
S-calculable (et on notera
EB
la fonction caractéristique de cette égalité),
Cette notion correspond à la notion de finitude définie dans (5),
Lemme 1, Soit
A
un objet de S
et
I
un objet S-fini
de
S , Alors
S(A>
est À
l-produits,
i, e, le
foncteur
S-indexé
diagonal
A Z :S(A) 4 S ( A ) Z
admet un adjoint à droite
noté

irz .

Preuve, La preuve se trouve dans (1), Fin de la preuve,
Lemme 2, Soit S
une catégorie
S-indexée
et
un foncteur S-indexé,
Alors F satisfait
SSO ,

F: S(A,S) 4

Preuve, Soit B un objet de £?z et XA l'élément générique de
S ( A f 8 ) . Alors, pour tout f objet de S ( A , a ) x t il existe d
tel que
9*XA = f . Par conséquent»
pour toute flèche
a:B 4 Fxf , on a:

M

10

O

ZNEAAl- X S A T X ON

DES

CNfiCK

F*f

B

F2**X«
Fin de la preuve,
Théorème, Si

0

Û:S(A) 4 S C A ) 1 ^ 1

et

A

sont

admet un adjoint

S-finis

alors

le

à gauche en 1 noté

foncteur

3~ ,

Preuve, Soit
f
un élément de
(S(A)i>3)i
^ soit
p
l'élément générique de S ( A ) " . On obtient ainsi deux éléments
e*f et Û~P de (S(A>«>3)-;
AS(A)-

^, ( S(A)C-3 )-

S(A) 1

-$> ( S ( A ) 0 3 ) 1

0"

Par l'universalité de sub(e x A) 1 à 0*f et A~P sont
associées, dans E , deux flèches f^P'je 4 sub(0 x A) ,
Considérons alors 0' le noyau de f et «.(f',?') ,
La catégorie HT-indexée a des cotenseurs par mono (voir (6)); on
en déduit donc l'existence d'un objet Q de S ( A ) " tel que
0*f soit inclus dans û"Q , En utilisant le lemme 1, on obtient
un élément g de S ( A ) 1 qui n'est autre que 3~f , Fin de la
preuve.

Mil

UNE

«MENERAL.XSATXON

OCfi

CNfiCMOUCÔ

ENUMEAEA

CONCLUSION,

L'utilisation des fonctions indexées et ensembles indexés se
révèle être un outil puissant en récursivité. De plus, il paraît
intéressant d'utiliser ces notions pour avoir une formalisation
mathématique de la programmation parallèle; ceci sera fait dans
un autre article.

BIBLIOGRAPHIE,

(1) R, Mijoule:
La théorie des fonctions indexées en récursivité,
Archivum Mathematicum, Vol, 23, n*4, 1987.

(2) Yu, L .Ersov:
La théorie des énumérations, Actes du Congrès
International des Mathématiciens, Vol, 1, pp. 223227, 1970.

(3) R, Paré et D, Schumacher:
Abstracts fami lies and the adjoint functor theorem,
Lectures Notes in Mathematics 661, pp. Ï-Î25,
Springer, 1978,

(4) H, Friedman;
Axiomatic
recursive
function
théorie,
Logic
Colloquium 69, pp. 113-137, North-Holland, 1971.

(5) J, Fenstad:
General
recursion
theory,
Perspectives
Mathematical Logic, Springer-Verlag, 1980,

M 12

in

UNE QCNCRALXSATXON

D E S CNSCMOUZfi

ENUMEREfi

(6) R. Paré:
Indexed
catégories
and
generated
topologies,
Journal of Pure and Applied Algebra 19 , pp. 385400, 1980,

(7) R. Mijoule:
L'universalité
des
semi-fonctions
récursives
universelles, Diagrammes 12 , Paris, 1984,

INSTITUT D'INFORMATIQUE

la A L L E S

D'ENTRCPRISe

JEAN

ROSTAND
B. P. -r?

9 1 0 0 2 E*VRY

CEDEX