D IAGRAMMES

C. H ENRY
Propriétés de permanence et existence de réalisations
minimales pour les algèbres multisortes
Diagrammes, tome 27 (1992), exp. no 3, p. CH1-CH53
<http://www.numdam.org/item?id=DIA_1992__27__A3_0>

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

OlAORAHMCfi

VOLUME

PROPRIETES DE

27

PERMANENCE

ET
EXISTENCE DE REALISATIONS
POUR
ALQEBRES

C.

MINIMALES

LES

MULTISORTES

Henry

On sait qu'on peut toujours concrétiser un comportement
M

entrées/sorties" comme étant le comportement effectif
d'au moins
un automate, minimal (en nombre d'états),
En (I.I.A.C.), J, A, Goguen et J, Meseguer ont montré comment
replacer ce résultat, très classique, dans la systématique des
algèbres de signatures multisortes,
Dans le présent travail, nous montrons comment il est naturel
d'élargir cette systématique jusqu'à celle des algèbres de
théories multisortes (d'ailleurs suggérée en (I.I.A.C,), mais non
utilisée dans le passage concernant justement les "machines
abstraites" - §5, pp. 485 à 490), Ainsi, tant la construction de
l'automate minimal, ayant même comportement qu'un automate donné,
que la construction du monoïde syntaxique
de cet automate,
apparaissent comme deux cas particuliers (l'un "au dessus des
comportements" et l'autre "au dessus des états") d'une même
procédure générale de minimalisation,

Nous avons cru devoir rappeler, dans la PARTIE 0, les quelques
éléments, indispensables pour la compréhension de la suite,
concernant les théories multisortes, Dès lors, il nous a semblé
utile d'y rappeler aussi, très rapidement, quelques rudiments

8ub.

Cl«s*.

18 C

10 , O S A 3 0

. 09 B 20 , ÔO O

30

assez techniques de théorie des catégories (concernant le lemme
de Yoneda ou, surtout, une construction particulière d'adjoints à
gauche ,.,) constamment utilisés dans le reste du texte, Bien
entendu, le lecteur averti pourra ne voir dans cette partie que
le catalogue des notations systématiques utilisées,
La PARTIE I est consacrée à la propriété de "suffisante
complétude" (i, e, lorsque les algèbres d'une théorie "forte",
engendrées par les algèbres d'une théorie plus "faible", sont
obtenues par quotient de ces dernières), puis à la propriété de
"cohérence hiérarchique" (i, e. de plongement des algèbres d'une
théorie "faible" dans les algèbres d'une théorie plus "forte"
qu'elles engendrent) et, enfin, à la propriété de "permanence"
(i, e, quand les algèbres d'une théorie "forte", engendrées par
les algèbres d'une théorie plus "faible" les ont encore - à
isomorphisme près - pour algèbres faibles sous-jacentes). Dans
chaque cas la règle du jeu est d'établir des conditions
nécessaires et/ou suffisantes syntaxiques,
i, e, portant
exclusivement sur les théories (les syntaxes) concernées.
La PARTIE II adapte et complète les méthodes de J, A, Goguen et
J, Meseguer concernant 1'indiscernabilité, l'accessibilité et
l'existence de réalisations minimales. Dans chaque cas, il s'est
agi de passer du concept de "sortes invisibles" de (1,1,A,C,) à
celui d'homomorphisme entre théories multisortes (possédant
éventuellement la propriété de permanence). Cela a d'ailleurs
également imposé le passage d'un traitement "ensembliste" des
algèbres à un traitement "catégorique et interne aux catégories
concernées" de ces algèbres. Cette partie s'achève par un retour
à l'exemple des automates (minimalisation des états, puis du
monoïde des transitions) et par un autre exemple (inspiré de la
construction du monoïde syntaxique) concernant les groupes
d'opérations,

PARTIE 0
TERMINOLOGIE

Si

I

ET

NOTATIONS

est un ensemble, nous désignons évidemment par

I*

reniemble d@ §@§ mis U § mi vide étint neté 1 , s'il n'y § eài
risque d'ambiguïté), Alors, si M est un tel mot, nous notons
A(M) sa longueur et, pour tout entier Ki<A(M) , nous désignons
par M(i) sa i*-"* lettre,

Si n * 1 est un entier, on note
représentée ci-dessous:

z„

la catégorie (triviale)

1 t- 2 4 3 <- .., 4 2n-l f- 2n 4 2n+l ,

Supposons que C est une catégorie,
Nous notons
Gro(C)
le graphe orienté (sans identités
sélectionnées) sous-jacent à C ,
Si
C
est une autre catégorie et si
F: C 4 C
est un
l
foncteur, on note <F(C)> l image pleine de F , i, e, la souscatégorie pleine de C
dont les objets sont les images par F
des objets de C ,
Enfin, si n > 1 est un entier, un foncteur Z ; z„ 4 C sera
appelé un zigzag (de longueur 2n+l) de C ,

On dit que T » (T.,TC,( (PMi)1<i<A<M> )w « x* est une théorie
multisorte si, et seulement si;
- T. est un ensemble, dit des sortes de T ,
- Te
est une catégorie, dite sous-jacente à
T , ayant
T.*
pour ensemble d'objets,
- pour tout mot
M € Tm*
(i, e. pour tout objet), la famille
(PM±: Il 4 l1(i))1<i<Acn> définit un produit, dit distingué, dans
Te
(ainsi, en particulier, le mot vide 1 est un 0-produit,
i,e un élément final).
Dans la suite, si K est un "constructeur" prenant en argument

CH

3

TCRMINOUOeXE ET NOTATIONS

une catégorie, on notera indifféremment
K(TC) a K(T) , Par
exemple, Ob(T) = Ob(Tc) est l'ensemble des objets de T c
ou
encore de T ,,.

On dit que H = (T, H., HC,T' ); T 4 T' est un homomorphisme de
théories multisortes si, et seulement si;
- T et T' sont deux théories multisortes,
- H, : T. 4 T'.
est une application (entre les ensembles de
sortes de T
et
T'
et dont on note
H.* : T.* 4 T' m *
le
prolongement aux ensembles de mots),
- Hc: T c 4 T'c
est un foncteur (entre les catégories sousjacentes), injectif sur les objets et tel que:
4 pour tout mot (i, e, pour tout objet) M e T.* = Ob(T) , on a
A(HC(M)) = A(H) ,
4 pour tout mot (i, e. pour tout objet) M € T m * • Qb(T) , et
pour tout entier Ki«A(M> , on a Hc(M(i)) = Hc(M)(i) ,
4 pour tout mot (i, e. pour tout objet) Il e T.* = Ob(T) , et
pour tout entier Ki<A(M) , on a H c (P M i) » P^<M\
,
(autrement dit, la restriction de He aux objets est H m * et
He
transforme les produits distingués de T en des produits
distingués de T' ),
Dans la suite, si K est un "constructeur" prenant en argument
un foncteur, on notera indifféremment, K(HC) • K(H) , Par
exemple, la resricion de K= aux objets sera encore notée H ,
De même, on notera <H(T)> l'iaiage pleine
de Hc ou encore de
H ... D'ailleurs, on ne fera aucune mention, le plus souvent, des

Si T est une théorie multisorte, on dit que A: T 4 Ens est
une algèbre de T , ou encore une T-algèbref si, et seulement si:
- A: Te 4 Ens est un foncteur,
- pour tout mot 11 € T m * (i, e, pour tout objet M de T ), la
famille
(A(P"i); A(tl) 4 A(M(i)) )I<I<A<M>
est un produit dans
Ens (en particulier, A d ) est un ensemble à un élément).
Dans ces conditions, on note Alg(T) la sous-catégorie pleine de
(la catégoie de foncteur s)
Ens Tc ( = EnsT ) dont les objets
sont ces algèbres et les flèches les transformations naturelles,
Alors, on sait (ou on voit facilement) que le plongement de
Yoneda (relatif à la catégorie Tc
sous-jacente à
T )
ÏT« = ÏJ T 4 (£nsT)0fD
admet une restriction (évidemment pleine
et fidèle)
YT: T 4 Alg(T)op> et on peut vérifier que (voir

TERMXNOLOQZE CT

NOTATIONS

(C.F.W.M. )):
Lemme de Yoneda, Naturellement en tout objet
toute algèbre A: T 4 Ens , on a;
HomAlacT>(YT(M),A) s, A(M) ,

M

de

T

et en

Si
H: T 4 T'
est un homomorphisme entre deux théories
multisortes, son foncteur sous-jacent
Hc: T c 4 T f c
induit un
foncteur ("composition par H " ) ;
EnsM - Ens Hc : EnsTi 4 EnsT
(F'; T'e 4 Ens) 4 (F'.He! Tc 4 Ens) ,
qui admet évidemment une restriction:
Alg(H): Alg(T') 4 Alg(T)
(A': T 4 Ens) 4 (A',H: T 4 Ens) ,
Mieux, on sait que Ens M admet un adjoint à gauche (le foncteur
"extension de Kan induetive le long de H ", voir (C,F, W.M, ));
SH! EnsT 4 EnsT' ,
qui, lui aussi, admet une restriction:
fî„: Alg(T) 4 Alg(T') ,
Dans ces conditions, s'il n'y a pas rique d'ambiguïté, on notera
encore;
- 1 = ÏT ,
- I' - *T- ,
- Y = YT ,
- Y' = YT- ,
- fi

s

fin 1

- S = 6H ,
- e(A); A 4 Alg(H)(6(A))
l'homomorphisme canonique
d'adjonction
associé à toute T-algèbre A: T 4 Ens ,
- c(M) = e(«) : Y(«) 4 Alg(H)(6(Y(M)) * Alg(H)(Y'(H(M))
1'homomorphisme canonique d'adjonction associé à tout mot
M € T.* (i, e, à tout objet M de T ),
De même, si A: T 4 Ens est une T-algèbre, si A'; T1 4 Ens est
une
T'-algèbre et si
m: A4Alg(H)(A')
est une flèche de
Alg(T) , on désignera par fact(m): 6(A) 4 A' l'unique flèche de
Alg(T')
(dont l'existence et l'unicité sont assurés par
l'adjonction de G à gauche de Alg(H) ) telle que:
Alg(H)(fact(m)).e(A) = m ,
Enfin, pour achever de préciser les notations et pour fixer un
peu mieux les idées, rappelons (le plus brièvement possible!)
comment est construite la T'-algèbre G(A); T' 4 Ens , librement
engendrée par une T-algèbre
A: T 4 Ens , et l'homomorphisme

TERHXN0L06XE ET

NOTATIONS

canonique associé e(A): A 4 Alg(H)(6(A)) = G(A),H ;
- on commence par associer au foncteur
A : T c 4 Ens
la
catégorie 1/A telle que:
4 ses objets sont les (x, M) , où 11 est objet de
T et x élément de ACM) ,
4 ses flèches sont les;
((x^M, ), t, (x 2l M 2 )): (Xi,Mi) 4 (x2, M 2 ) #
où t;Mi 4 M 2 est une flèche de T telle que:
A(t)(x,) » x 2 ,
- on dispose alors du foncteur "de projection":
1//A :1/A 4 T
(x,M) H M ,
- ensuite, à tout objet M1 de T' , on associe la catégorie
H/M' telle que:
4 ses objets sont les (M, t' ) , où 11 est objet de
T et t':H(M) 4 PI' est flèche de T' ,
4 ses flèches sont les;
((Ni.t , ,) l t ( (H a( t , a )):(h ll t , 1 ) 4 ( M 2 , f 2 ) ,
où t:Mi 4 M 2 est une flèche de T telle que;
t'2.H(t) » t', ,
- de la sorte, on dispose d'un nouveau foncteur "de projection":
H/ZM-îH/W 4 T
(W,t') H M ,
- on peut alors construire la catégorie produit fibre des deux
foncteurs 1//A-.1/A 4 T f- H/M1 : H//M' :
1/A/H/M' = (1/A) x T (H/M1) ,
(c'est, à isomorphisme près, la catégorie telle que:
4 ses objets sont les (x, M, t') , où (x, 11) est
objet de 1/A et (11, t 1 ) est objet de H/ri1 ,
4 ses flèches sont les
((x 1 ,M 1 ,f 1 ),t,(x ai M 2 ,t , 2 ):(x 1 ,l1 1 ,f 1 ) 4 (x 2 ,M 2 ,t' 2 ) ,
où ((x,,M,), t,(x2,M2)) est flèche de 1/A et
((HnVJ.t.tlt.t'a)) est flèche de H/M' ,
autrement dit, et de manière plus concrète, les objets de
1/A/H/M' peuvent être représentés comme des couples de flèches
formellement consécutives de la forme suivante - où 1 = { 0 } :
1

$>A(«)

M

CH

H(M)

6

>«'

PART. O : TERHINOL.MIK ET NOTATIONS

et, de nême, les flèches de 1/A/H/M' peuvent être représentées
comme des couples de triangles commutatifs
formellement
consêcuti fr.
A(M,)

H<M,)

Mi

A(t)

M'

A(M 2 )

M*

),

- dans ces conditions, il est facile de vérifier que:
+ pour tout objet
M'
de
T' , l'ensemble
G(A)<M'> = TT0< 1/A/H/M')
a pour éléments les
composantes connexes
<<x,M, t')•
des objets
1
<x,M,t'> de la catégorie 1/A/H/M ,
+ pour tout objet
M
de
T , l'application
e(AXM):A(M) -» Alg(H)(8(A))CM)
associe à tout
élément x la composante connexe 4<x, M, 1H<M>)r de
<x,M, lH<n>) dans la catégorie 1/A/H/HCM) .
En particulier, on voit aisément que:
- naturellement en tout objet M de T , on a:
6<Y<M)> S Y'(H(M)) ,
(on supposera même qu'on a l'égalité),
- pour toute flèche t;M -+ N de T , on a:
c(MXN)

;

Y(N)(N> -» Alg(H)CG(Y(M)))(N)
•

S

HoiMM,N>

Alg(H)(Y'(H(M)))(N)

S

S

Hooh-CM.N)

Y'(H(M))(H(N))

HOMT(M,N)

HO»T.CH(M),H(N))

t t* H(t) .

De ces constructions résulte, entre autre, que:
Lemme de commutation. Si
deux théories multisortes,

H: T -» T" est un homomorphisme entre
les trois diagrammes ci-dessous

PART.

O

t

TERfIXNOLOeiE

ET

MOT A T X OMS

commutent:
Alg(T') c_

Ens"

^

Alg(T')

Ens H

Alg(H)

6
Ens1

Alg(T)

Alg(T)

T'

_> Ens"1

c

->

Alg(T* )«
/S

->

Alg(T)«

>

Ens T

H

Pour conclure cette PARTIE 0, énonçons le lemme qui suit, utile
dans la suite (et qui se démontre immédiatement):

Lemme de transition.

Si

x, y;Xi 4 X a , m':X 2 -» X 3

C est une catégorie à sommes finies,
et

t: X 4 X 2

en sont

des

si

flèches

telles que m'.x * m> ,y , alors
m'.]x, tC = m'. ]y, tC (si l'on
désigne par
3x, tC, 3y, tC: X,+X 4 X2
les flèches obtenues par
transition relative à t , i, e. les uniques flèches telles que:
3x, tC.s, » x et 3x, tt.s » t ,
]y, tC.s, « y et ]y, tC.s • t ,

où Si: Xi 4 X,+X et s: X 4 X,+x sont les

co-projections).

PARTIE
SUFFISANTE
COHERENCE

1.

Suffisante

I

COMPLETUDE
ET
HIERARCHIQUE

complétude.

On d i t qu'un homomorphisme de théories multisortes
H;T 4 T'
est sectionnable s i , et seulement s i , i l existe un homomorphisme
de graphes orientés K;Gro(<H(T)>) 4 Gro(T) t e l que:
( i ) pour tous objets M et Mi de T et pour toute flèche
f : H(M) 4 H(M,) de T' ( i . e. de <H(T» ), on a:
H(K(t')) = f ,
( i i ) pour tous objets M , M, e t M2 de T , pour toute flèche
t':H(M) 4 H(M,) de <H(T)> et pour toute flèche t:M, 4 M2 de
T , on a;
K(H(t),t') = t.K(t') ,

Montrons que:
Proposition 1. Si H;T 4 T' est un homomorphisme entre
théories
multisortes,
alors les assertions suivantes sont équivalentes :
(1) H est sectionnable,
(2) pour tout objet
M de T et naturellement en tout objet
Mi de T , il existe (et on peut choisir) une
application
X(M)(M,): Alg(H)(G(Y(M)))(M,) 4 Y(M)(M,)
telle que:
€(M)(Mi ), X(M)(Mi ) =

(où

IdAlg(H)(QCY(M>>XMU

c(M):Y(M) 4 Alg(H)(G(Y(M)))

associée à l'adjonction
du foncteur
Alg(H) - voir la PARTIE 0>.

est

la

G

à gauche du

flèche canonique

[Remarque. On peut, évidemment, remplacer la
précédente par
la condition
(3) suivante,
trivialement équivalente;

foncteur

condition
qui
lui

(2)
est

PART.

I : 9UFFZ3ANTE CQMPLETUOE ET COHERENCE HIERARCHIQUE

(3) pour tout objet M de T , il existe (et on peut
une transformation naturelle :

choisir)

X(M)): Alg(H)(G(Y(M))) 4 Y(M)

telle que :
C(M),X(M)) a IdAlg(H>(aCYCMJ?> .

Nous avons préféré faire figurer la condition (2), plutôt que la
(3), dans l'énoncé de la proposition 1 pour rendre immédiatement
explicite le parallèle à faire avec la proposition 3 - voir la
remarque qui suit cette dernière, ]
Preuve, a) Montrons tout d'abord que (1) implique (2) .
Pour tous objets M et Mi de T , considérons l'application:
X(M)(M,) : Alg(H)(6(Y(M)))(M,) 4 Y(M)(M,)
HOBIT- (H(M), H(M, ) )

HooMM, M, )
-> K(f )

Alors, pour toute flèche
commute:

t;M, 4 M 2

de

T , le diagramme suivant

X(M)(MT)

Alg(H)(G(Y(M)))(M,)

-T> Y(M)(M,)

HomT.(H(M),H(M1))

Hom-r(M, Mi )

Alg(H)(G(Y(M)))(t)

Y(M)(t)

Homr-(H(M),H(t))

HomT(H, t)
•V

HomT-(H(i1),H(H2))

HomrtM, M 2 )

Alg(H)(G(Y(M))XM2)

Y(M)(M2)
X(M)(M2)

puisqu'en effet, pour toute flèche
nous avons:

C H IO

t':H(M) 4 H(MT)

de

T1

I : SUFFISANTE

COMPLETUOE ET COHERENCE

HIERARCHIQUE

Y(M)(t)(X(M)(M1)(f)) * Y(M)(t)(K(t'))
• HomT(H,t)(K(t'>)
= t.K(t')
= K(H(t).f)
(d'après (ii) )
= X(M)(Ha)(H(t).t')
= X(l1>(^!2)(HomT.(H(M),H(t))(t,))
= X(M)(M2)(Alg(H>(Q(Y(M)))(t) ( f ) ) .
Par conséquent, pour tout objet
11
de
T , la famille
(X(M)(M1))t,)«0bcT> est "naturelle en M, ".
Enfin, pour tous objets M et M, de T et pour toute flèche
t':H(M) -» H(M,) de T1 , nous avons:
€(M)(M,)(X(M)(M1)(f)) » €(M)(M,)(K(t'))
= H(K(f )>
(d'après les propriétés de c - voir la PARTIE 0)
= f
(d'après (i) ) ,
b> Montrons maintenant que (2) implique (1) ,
Par hypothèse, pour tout objet M de T , nous disposons de la
transformation naturelle, i, e. de la flèche de Alg(T) :
X(M) : Alg(H)(G(Y(M))) -» Y(M) ,
de sorte que;
€(M),X(M) » IdAig(H}.e<Y<n>> .

Par conséquent, pour tous objets M et M, de T et pour toute
flèche
t':H(M) -» H(M, ) de
T' , nous disposons du diagramme
(évidemment) commutâtif suivant;

Alg(H)(Y'(H(M,))>

Alg(H)(Y'(t'))
5> AlgCHXY' (H(M))>

a

a

Alg(H)(S(Y(«,)))

Alg(H)(6(Y(M)))

c(M,)

X(M)

4/
Y(M,)

>

Y(M)

X(«),Alg(H)(Y,(t')).c(M1)
et, puisque

Y;T •* Alg(T)0'»

est un foncteur plein et fidèle, il

CH 1 1

SUFFISANTE

PART.

COHPLSTUK

ET COHCRCNCC

HIERARCHIQUE

existe donc une unique flèche K(t'):M -» M, de T telle que:
Y(K(t')) = X(M).Alg(H)(Y'(t')).c(N,) .
Clairement, on définit bien ainsi un homomorphisme de graphes
orientés:
K:Gro(<H(T)>) -» 6ro(T) .
Alors, pour tous objets 11 et M, de T et pour toute flèche
t':H(M) -» H(Mi) de T' , on a:
e(M),Y(K(t')) * e(M),X(M).Alg(H)(Y'(t')).e(M,)
(par définition)
= Alg(H)(Y'(f )).€(«,)
(puisque, par hypothèse, c(M),X(M) = IdAig<H>.a<v«M>» ) ,
autrement dit Y' ( f >: Y'(H(I1, )) •» Y' (H(M>) est, par l'adjonction
du foncteur G à gauche du foncteur Alg(H) , l'unique flèche de
Alg(T') rendant le diagramme ci-dessous commutatif:
Alg(H)(Y'(t'))
Alg(H)(Y'(H(M))>

Aig(H)(Y'(H(M,)))

A

/i

e(M)

«(M,)

Y(M)

Y(M,>
Y(K(f))
d'où il résulte que:

(puisque

Y'(t') » 6(Y(K(f)))
(par unicité)
= Y'(H(K(f )))
op
Y',H a G ,Y - comme rappelé dans la PARTIE 0) ,

mais, Y' étant fidèle, on en déduit que t' » H(K(t')) , i. e.
que K vérifie la condition (i) .
Maintenant, pour tous objets M , Mi et M 2 de T , pour toute
flèche
t';H(M) -» H(M, )
de
<H(T)>
et pour toute flèche
t;Mi -» Ma de T , on voit que;
- le diagramme suivant commute (le rectangle de gauche, grâce à
l'adjonction de G à gauche de Alg(H) , et celui de droite, en
vertu de la définition de K ):

C H 12

PART.

I

SUFFISANTE

COHPLETUOE ET COHERENCE

HIERARCHIQUE

Alg(H)(Y'(H(t))
Alg(H)(G(Y(t)))
Alg(H)(Y'(t'))
Alg(HH6(Y(M2))>
> Alg(H)(G(Y(M, )))
*Alg(H)(G(Y(M)))
A
A
e(M 2 )
e(M,)
X(M)
Y(M 2 )

-> Y(M,)
Y(t)

-5» Y(M)
Y(K(t'))

- le diagramme suivant commute, par définition de K :
Alq(H)(Y'(H(t).t'))
~Alg(H)(Y'(H(t)))
Aig(H)(Y'(t'))
Alg(H)(6(Y(M2)))
> Alg(H)(G(Y(M,)))
> Alg(H)(G(Y(M)))
A

X(M)

e(M 2 )
-*• Y(M)

Y(M 2 )
Y(K(H(t).t'))

d'où on déduit que:
Y(K(H(t).f)> » Y(K(f)).Y(t) » Y(t.K(f)) ,
et donc, puisque Y est fidèle, que;
K(H(t).f) = t.K(t') ,
autrement dit que K vérifie (ii), Fin de la preuve.
Etablissons maintenant la condition syntaxique de
complétude suivante:

suffisante

Proposition 2, Si H: T -» T* est un homomorphisme sectionnable
entre
théories
multisortes,
alors,
pour
toute
algèbre
A; T -» Ens , la flèche canonique (associée à l'adjonction du
foncteur G à gauche du foncteur Alg(H) - voir la PARTIE 0)
e(A):A -» Alg(H)(G(A)) est un épimorphisme point par point (donc
un épimorphisme) : autrement dit, pour tout objet M, de 1 ,
l'application
e(A)(M1 ): A(Mi ) -» G(A)(H(Mi )) est surjective.

[Remarque. Si H

est sectionnable, la proposition 1 indique -

PART,

I : SUFFISANTE COHPLETUOE ET COHERENCE

HIERARCHIQUE

voir la remarque qui la suit - que, pour tout objet M de T
(i, e, pour tout objet de Alg(T) die la forme Y(M) ), la flèche
canonique d'adjonction particulière
e(Y(M)) = c(M) possède une
section (i. e. est naturellement
sectionnable point par point),
Par contre, la proposition 2 indique seulement
que, pour un
quelconque
objet
A
de
Alg(T) , la flèche canonique
d'adjonction e(A) est certainement point par point sectionnable

mais, en général, non naturellement. ]
Preuve, Supposons que Mi est un objet de T et y est un
élément de 6(A)(H(M,>) .
Par construction (voir la PARTIE 0), y = *(x, M, t')•
est la
composante connexe d'un de ses représentants (x,M, t') , comme
figuré ci-dessous:
-?-A(M)

1

M

H(M)

-^ H(M, )

Alors, dans le schéma ci-dessous, le diagramme de gauche est
trivialement commutâtif dans Ens et celui de droite commute
dans T' (puisque, par hypothèse, H est sectionnable par K );
M,
-t.

Id

A(K(t')).x

M,

A(Mi)

A(K(t')).x
1

I Id

Id

, A(Mi)
A(K(f)).x
A
A(K(t'))

M,
K(f )

H(K(t'))

A(M)

Id

Id
H(M)

•^ A(M)

C H 1-4

PART.

I : SUFFISANTE COMPLETUOE ET COHERENCE HIERARCHIQUE

Par conséquent, (x, M, t 1 ) et (A(K(f )),x,Mi, IHCMI >)
la même composante connexe de 1/A/H/HCM,) , On a donc:

sont dans

e(A)(M1)(A(K(t,)),x) = <(A(K(t' )).x, M,, IHCMI >)•
= *(x,M, t' )•
= Y*
d'où la surjectivité annoncée, Fin de la preuve.

2.

Cohérence

hiérarchique.

On dit qu'un homomorphisme de théories multisortes
H;T -» T1
est rétractable
si, et seulement si, il existe un homomorphisme
de graphes orientés K;Gro(<H(T)>) -+ Gro(T) tel que:
(j) pour tous objets M 2 et M! de T et pour toute flèche
t: M* -f M, , on a H(K(t)) = t ,
(jj) pour tous objets M , Mi et M 2 de T , pour toute flèche
t:M2 4 M, de T et pour toute flèche t':H(M1) -• H(M) de T' ,
on a K(t\H(t)) = K(t').t ,

Montrons que:
Proposition 3, Si H: T -» T1 est un homomorphisme entre
théories
multisortes,
alors les assertions suivantes sont équivalentes:
(l)H:T-»r
est
rétractable,
(2) pour tout objet
M die T et naturellement en tout objet
Mi de T , il existe (et on peut choisir) une application::
v(M,)(M):Alg(H)(fî(M,))(M) 4 Y(MT)(M)
telle que:
V(M,)(M),€(M,)(M) « Idv<Mi>CM> i

(où
€(M,):Y(M,) 4 Alg(H)(Q(Y(M,)))
associée à l'adjonction
du foncteur
Alg(H) - voir la PARTIE 0).

est la flèche canonique
G
à gauche du foncteur

[Remarque, Si H est rétractable, on déduit de la proposition 3
que la transformation naturelle
«(M,): Y(M,) -» Alg(H)(G(M1 ))
est
point
par
point
rétractable,
mais en général non
naturellement:
ainsi, la famille
(v(Mi )(M))M«ot><T>
ne définit

RART.

I : SUFFISANTE

COMPLETUDE ET COHERENCE

HIERARCHIQUE

pas une transformation naturelle
v(M,):Alg(H)(G(M,)) 4 Y(M,)
(qui serait rétraction de c(M,) ) - re-voir la remarque qui suit
la proposition 1. ]
Preuve, a) Montrons tout d'abord que (1) implique (2) ,
Pour tous objets M et Mi de T , considérons l'application;
v(M, )(M) : Alg(H)(G(Y(Mi)))(M) 4 Y(M,)(M)
Hom T -(H(Mi),H(M))

Hom T (M,,M)
-»

Alors, pour toute flèche
commute:

t;M 2 4 Mi

de

K(t')

T , le diagramme suivant

v(Mi)(M)
*

Alg(H)(G(Y(Mi)))(M)

Y(M,)(M)
s

Hom-r(M,,M)

Hom T .(H(Mi),H(M))

Y(t)(M)

Alg(H)(6(Y(t)))(M>

3

Horo-r(t, M)

Homr-(H(t),H(M))

Hom T (M 2 , M )

Hom T -(H(M 2 ),H(M))

3

3

->

Alg(H)(6(Y(M a )))(M)

Y(M a )(M)

v(M 2 )(M)
puisqu'en effet,
nous avons:

pour toute flèche

V ; H(M, > -» H(M)

Y(t)(M)(v(M,)(M)(t')) = Y(t)(M) ( K ( f ) )
= Homr(t,M) (K(f ))
a K(t').t
= K(t',H(t))
(d'après (jj) )

de

T' ,

PART.

I ; SUFFISANTE COMPLETUDE ET COHERENCE HIERARCHIQUE

» v(M2)(M) (t',H(t)>
= v(M2)(M) ( HomT.(H(t),H(M))(t') )
= v(M2)(M)(Alg(H)(Q(Y(t)))(M>(t')) .
Par conséquent, pour tout objet
M
de
T , la
(v(M,)(M))M)«0bcT> est "naturelle en M, ",
Enfin, pour toute flèche t;M, -» M de T , nous avons:

famille

v(Mi)(M)(€(M,)(M)(t)) • v(M,)(M)(H(t))
(d'après les propriétés de c - voir la PARTIE 0)
= K(H(t))
= t
(d'après (j) ) .
b) Montrons, maintenant, que
Pour tous objets
M
et
hypothèse, de l'application:
v(M,)(M)

:

(2)
Mi

Alg(H)(Q(Y(M,)))(M)
3

implique (1) ,
de
T , nous disposons, par

T.Y(M,)(M)
S

Alg(H)(Y'(H(M,))(M)

HomT(M,,M)

Y'(H(Mi))(H(M)>

HomT(M,,M)

Homr-(H(M,),H(M))

HomT(M,,M) .

Autrement dit, si, pour tous objets M et M, de T et toute
flèche t':H(Mi) -» H(M) de T', nous posons:
K(t') = v(M, )(M)(f) ,
nous définissons bien un homomorphisme de graphes orientés:
K : <H(T)> -» T .
En particulier, pour toute flèche
t;Mi •• M
de
T , on a
successivement:
K(H(t)) » v(Mi)(M)(H(t))
(par définition de K )
« v(M,)(M)(c(M,)(M)(t))
(en vertu des propriétés de e - voir la PARTIE 0)
= t
(d'après (2)),
par conséquent, la condition (j) est vérifiée.
Enfin, si
M , Mi
et
M2
sont trois objets de

T , si

RART.

I

SUFFISANTE CQMPLETUDE ET COHERENCE

HIERARCHIQUE

t:M2 4 Mi est une flèche de T et si t':H(Mi) 4 H(M) est une
flèche de T' , on voit que:
- tout d'abord, le diagramme suivant commute, en vertu de
l'hypothèse de naturalité contenue dans (2):
v(M,)(M)
HomT-(H(Mi),H(M))

* HomT(Mi,M)
HomT(t,M)

HomT-(H(t),H(M))
if

HomT.(H(M2),H(M))

> HomT(M2,M)
v(M2)(M)

- ensuite, on a successivement:
K(t\H(t)) » v(M2)(M)(t',H(t))
(par définition de K )
» v(M2)(Homr.(H(t),H(M))(t'))
- HomT(t,M)(v(M,)(M)(t'))
(puisque le diagramme précédent commute)
= HomT(t,M)(K(t'))
(par définition de K )
= K(f).t ,
autrement dit, la condition (jj) est vérifiée, Fin de la preuve.

Etablissons maintenant la condition
cohérence hiérarchique suivante:

syntaxique

suffisante

de

Proposition 4, Si
H: T 4 T1
est un homomorphisme rétractable
entre
théories
multisortes,
alors,
pour
toute
algèbre
A: T 4 Ens / la flèche canonique (associée à l'adjonction
du
foncteur
G à gauche du foncteur
Alg(H) - voir la PARTIE 0)
e(A):A 4 Alg(H)(G(A)) est un monomorphisme point par point (donc
un monomorphisme) : autrement dit, pour tout objet
Mi die T ,
l'application
e(A)(M):A(M,) 4 G(A)(H(M,)) est
injective.
Preuve, On sait qu'une condition syntaxique suffisante pour que,
pour toute algèbre A: T 4 Ens , la flèche e(A):A 4 Alg(H)(G(A))
soit un monomorphisme est que (voir (C.S.D.P,)):
(CS) pour tout objet
Mi de T , pour tout entier
n>1 , pour
tout zigzag
Z:z„ 4 T
fermé en
Mi
(i,
e,
tel que

C H 13

PART.

I

SUFFISANTE COMPLETUOE ET COHERENCE HIERARCHIQUE

Z ( l ) s Mi • Z(2n+1) ) , alors s'il
de T' tel que le diagramme ( * )

(*)

1 <k

2

Z(l)

Z(2)

Mi «

M2

existe un diagramme commutatif
ci-desous:

2n-l «*— 2n — > 2n+l

> 3

Z(2n)
,, ,

. t . M2r%

i a

=>. Mi

. ,,H(M 2 T ,)->H(Mi)

H(Mi)<-H(M 2 ),,,

t

Z(2n+1)

Idnchii >

t

2n+l

3

IdHCMl>

alors
il existe
un entier
m)l
, il existe
un foncteur
N: z« 4 z„
, tel que IM(1) » 1
e t N(2m+1) » 2n+l , et il
existe un diagramme commutatif de 1 tel que le diagramme ( * * )
ci-dessous:

(**)

1<—

2

2n-l <— 2n

^3

^ 2n+l

Z.N
Mi ^ —

gi a IoV,,

MM< 2 >

MN<2IN>

• • •

g2

g2E M

M,

> Mi

g3m*i

a

Idni

SUFFISANTE

COMPLETUOE ET COHERENCE

HIERARCHIQUE

Comme en (S.Q.P.A, ),
il nous suffit donc d'établir que
1'homomorphisme rétractable H;T 4 T' vérifie la condition (CS)
(avec n = m et N = Id ),
Pour ce faire, supposons que l'on dispose d'un diagramme
commutatif de T' tel que (*) , Si, pour tout Kp<2n+1 , on
pose g R • K(t'p,) , on voit que;
- on a tout d'abord:
g, » K(t',)
= K( Idncm >)
= K(H(Id m )
= Id„i
(puisque H est rétractable),
- on a ensuite:
g2r«-*-i a K(t 2n-^i )
s
KddncHi >)
= K(H(Id m )
= IoV.1
(puisque H est rétractable),
- pour tout

Kp*n , on a également:
92p^-l 1 b2p s K(t

= K(t'2^i.H(t2|,)
est rétractable)
= K(t'2|,)
(*) est un diagramme commutatif)

(puisque
(puisque

2p^l)«t2p

H

• g**

(par définition),
- pour tout

0€p(n-l , on a enfin:
g2p-»-i • t2p-»-1 S
s

(puisque
(puisque

K(t

2pr^.l ) , t2f>^.1

K ( t' 2v»*.i, H(t^pjH-i )

H

est rétractable)
= K(t' 2p * 2 )
(*) est un diagramme commutatif)
s

g2i>^2

(par définition).
Au total, on dispose donc d'un

diagramme commutatif dans

T

de

SUFFISANTE

la forme
preuve.

3,

(**)

COMPLETUOE ET COHERENCE

recherchée (où

n » m

et

HIERARCHIQUE

N • Id ), Fin de la

Permanence.

Etablissons la condition
permanence suivante:

syntaxique

nécessaire et suffisante

de

Proposition S, Si H: T 4 T' est un homomorphisme entre
théories
multisortes,
alors les assertions suivantes sont équivalentes:
(1) H est sectionnable et
rétractable,
(2) (permanence) pour toute algèbre
A:T 4 Ens , la flèche
e(A):A 4 Alg(H)(G(A))
est
un isomorphisme (où la
flèche
e(A):A 4 Alg(H)(G(A))
est
la
flèche
canonique associée à
l'adjonction
du foncteur G à gauche du foncteur
Alg(H) - voir
la PARTIE 0).
Preuve, Clairement, si
H est sectionnable et rétractable, en
appliquant les propositions 2 et 4 on voit que, pour tout objet
M, de T , e(A)(Mi):A(Mi) 4 G(A)(H(M1)) est un épimorphisme et
un monomorphisme de Ens ; c'est donc une application inversible.
En conséquence e(A) = e(A)(-): A(-) 4 G(A))(H(-)) = Alg(H)(G(A))
est une
transformation naturelle
inversible et donc un
isomorphisme.
Inversement, supposons que, pour toute algèbre A: T 4 Ens , la
flèche
e(A): A 4 Alg(H)(G(A))
soit un isomorphisme. Cela
signifie en particulier que, naturellement en tout objet N de
T , la flèche
e(Y(N)) • c(N)
est un isomorphisme. Par
conséquent, naturellement en tout objet
N
de
T
et
naturellement en tout objet
P
de
T , l'application
c(N)(P): Y(N)(P) 4 Alg(H)(G(Y(N)))(P) est inversible:
- de la proposition 1, il résulte que H est sectionnable (si
l'on pose X(N)(P) = [cdMHP)]-1 ),
- de la proposition 3, il résulte que H est rétractable (si
l'on pose v(N)(P) = [e(NMP)]-1 ).
Fin de la preuve,

On

peut

"présenter",

c'est-à-dire

énoncer,

la

proposition

FART.

I ; SUFFISANTE

COMPLETUOE ET COHERENCE

HIERARCHIQUE

précédente un peu différemment, Etablissons tout d'abord que:
Lemme 1, Si
H: T 4 T'
est un homomorphisme entre
théories
multisortes, alors les assertions suivantes sont équivalentes:
(1) H est sectionnable et
rétractable,
(2) H est un isomorphisme sur son image pleine.

Preuve, Supposons que H
est un isomorphisme sur son image
pleine
<H(T)> . Notons
K = H'""1
le foncteur inverse du
1
foncteur
H : T c 4 <H(T)> , restriction de H , Clairement, H
est rétractable et sectionnable par K ,
Inversement, supposons que H
est sectionnable par K et
1
rétractable par K , Alors, on voit que:
- si M et Mi
sont deux objets quelconques de T et si
t': H(Mi 4 H(M) est une quelconque flèche de T1 , nous avons
H(K(t')> = f et donc H est plein,
- si M 2 et Mi sont deux objets quelconques de T et si
s, t: M 2 4 Mi sont deux quelconques flèches de T , telles que
H(s) = H(t) , on a s = K'(H(s)) » K'(H(t)) =t et donc H est
fidèle.
Ainsi, H étant plein et fidèle, mais aussi injectif sur les
objets (puisque c'est un homomorphisme entre théories), c'est un
isomorphisme sur son image pleine. Fin de la preuve.
Tenant compte maintenant de la proposition
5 et du lemme 1,
nous obtenons
immédiatement
l'autre
condition
syntaxique
nécessaire et suffisante de permanence suivante:
Proposition 6. Si H: T 4 T' est un homomorphisme entre
théories
multisortes,
alors les assertions suivantes sont équivalentes:
(1) H est un isomorphisme sur son image pleine,

(2) pour

tout

algèbre

A: T 4 Ens ,

e(A); A 4 Alg(H)(6(A))

est un isomorphisme (où
e(A):A 4 Alg(H)(G(A))
est la
flèche
canonique associée à l'adjonction
du foncteur
G
à gauche du

foncteur

Alg(H) - voir

la PARTIE 0),

PARTIE
INDISCERNABILITE,
ET
REALISATIONS

1.

II
ACCESSIBILITE
MINIMALES

I n d i s c e r n a b i l i t é ,

Supposons que
H ;T 4 T'
est un homomorphisme entre deux
théories multisortes, que
M'
est un objet de
T'
et que
A':T' 4 Ens est une algèbre de T' ,
On note
£A*.M*
la r e l a t i o n binaire (dont i l est f a c i l e de
prouver que c'est une r e l a t i o n d'équivalence) définie sur
l'ensemble
Hom(Y'(M'),A 1 )
(ou sur l'ensemble M'(A 1 ) qui l u i
est isomorphe - voir la PARTIE 0) t e l l e que, pour tous
x,y e Hom(Y'(M , ),A') , on a:
x

SA-.M-

y

s i , et seulement s i ;
- pour tout objet
M de T et pour toute flèche u;M' 4 H(M)
(ou encore, pour toute flèche v;Y'(H(M>) 4 Y'(M 1 ) de A l g ( T ' ) ,
nécessairement de la forme v » Y ' ( u ) - voir la PARTIE 0 ) , on a;
x.Y'(u) = y.Y'(u) ,
comme représenté sur le diagramme commutatif suivant:
Y'(u) = v
Y'(M') *

Y'(H(M))

Ceci fait, on note maintenant
=A*.Mla relation binaire
définie sur l'ensemble Hom(Y'(M*),A') et telle que, pour tous
éléments x,y € Hom(Y((M'>, A') , on a:
x 2 A . M- y

CH 2 3

PART.

II

INOISCERNABIL.ITE.

si, et seulement si:
- pour tout objet N' de T'
(ou encore, pour tout élément
a:

ACCESSIBILITE

et tout élément te Hom(Y'(N'), A')
t e A'(N') - voir la PARTIE 0), on

]x, t[ SA'.M-*N-

]y#t[

,

(pour la notation ] , [ , voir la PARTIE 0)
comme représenté sur le diagramme commutatif suivant;
Y'(M')

Y'(M') + Y'(N')

Y'(N')
Dans ces conditions, on vérifie facilement que = A . # „. est une
relation d'équivalence, dite d' indiscernabilité
: ainsi, si on a
x 3A.,M. y , on dit que x et y sont indiscernables
(dans
1
A , relativement à M' , du point de vue de T ),
Mieux, les lemmes 1 et 2 et la proposition 3 qui suivent
établissent que
( s A . (M , )„.« 0t><T- >
est une famille de
congruences (i. e, de relations d'équivalence compatibles avec
les "lois de composition"),
Lemme 1, Si
H:T 4 T'
est un homomorphisme entre
théories
multisortes,
si
A';T' 4 Ens est une algèbre de T' , si
M'
est un objet de
T'
et si
x,y 6 Hom(Y'(M'), A')
sont deux
éléments de
Hom(Y'(M1 ), A1 )
(ou de
A'(M') ;
tels que
x 2 A . #M . y , alors, pour tout objet
P' de T' et toute flèche
h: M' 4 P'
de
T' (ou
encore,
pour
toute
flèche
k:Y'(P') 4 Y'(M1)
de
Alg(T' ) , nécessairement de la forme
k = Y'(h) ) , on a x.Y'(h) S A -,R. y. Y'(h) .
Preuve, Il nous faut prouver (par définition) que :
- pour tout objet N' de T1 et tout t e Hom(Y'(N'), A'>, on a:
]x.k,t[ 2A-,R--MM- ]y.k,t[ ,

PART.

IX

| INOISCCRNABILITE,

ACCESSIBILITE

c'est-à-dire encore que;
- pour tout objet M de T et tout veHom(Y' <H(M)>, Y' (P' )+Y' (N' )),
on a:
]x.k,t[,v = ]y.k,t[.v ,
(on pourra se reporter au diagramme suivant:
Y'(h)
Y'CP')

Y'(P') + Y'(N')

).

Mais, par raison d'unicité, on a :
]x.k,t[ » fc.tMm'.k.n' [
et
]y.k.t[ - ]y»t[,]m\k,n'[
(en notant m': Y'(M 1 ) -» Y'(M'>+Y'(N'> et n':Y'(N') -» Y'(M1 )+Y'(N* )
les co-projections),
D'où l'on déduit
]x.k,t[,v = Ox.ttJm'.k.n'n.v
= ]x,t[.(]»'.k,n'[.v)
a
]y.t[.(]m'.k,n'[,v)
(car,par hypothèse, ]x, t[ sA-. «•**«• ]y, t[ )
- (]y.t[.]m',k,n'[).v
• ]y.k, t[.v .
Fin de la preuve.
Lemme 2, Si
H;T •» T'
est un homomorphisme entre
théories
multisortes, si A';T' -» Ens est une algèbre de T' , si M' et
N' sont deux objets de T , si x,y€Hom(Y'(«'),A') sont deux

PART,

IX : INOI3CCRNADILITE, ACCESS IS11-1 TC

éléments de
Hom(Y' (M' ), A' )
(ou de
A' (M' ) ; tels
que
,
x aA.#M. y
et si
r,s€Hom(Y (N'),A')
sont deux éléments de
Hom(Y'(N'>,A' ) (ou de A ' ( N ' ) ) tels que r s A . . N . s , alors on
a
] x , r [ =»•+»• ]y#s[
(en reprenant
les notations
de la
PARTIE 0).
Preuve, I l nous faut prouver (par d é f i n i t i o n ) que:
- pour tout objet P' de T' e t tout t e Hom(Y'(P'), A ' ) , on a:
] ] x . r [ , t [ Ct«-*N- >**>• ] ] y i s [ , t [ ,
c ' e s t - à - d i r e encore que:
- pour tout objet
n
de
T
et tout v appartenant à
HortY'CHOUMY'Cn' >+Y'(N' ))+Y'(P' ) ) , on a:

]]x,r[,t[,v = ]]y,s[,t[.v ,
(on pourra se reporter au diagramme suivant:

Y'(H(M))
Y* (M') + Y ' ( N ' )

(Y'(M') + Y'(N')) + Y'(P')

^ Y ' ( M ' ) + (Y'(N') + Y'(P'))

*

. - Y ' ( N ' ) + (Y'(W') + Y ' ( P ' ) )

?3

(Y'(M') + Y ' ( N ' ) ) + Y ' ( P ' ) ).
Hais, s i on note successivement:

CH 2 «

RART.

II

INOIâCERNABILITE,

A C C E S S I B i t . ITE

-» Y'(M')+(Y'(N')+Y'(P')) ,
Ya:Y'(M )+(Y'(N')+Y'(P')) -» Y'(N'>+(Y'(M')+Y'(P')) ,
Y . î Y ' d H ' W Y ' W )+Y'(P')) -» (Y'(M')+Y'(N'))+Y'(P') ,
les isomorphismes canoniques, il est facile de voir que;
(1)
]]*,r[,t[ = ]x,]r,t[[.ti ,
<2)
]y*]r,t[[ = ]r.]y,t[[,v2 .
(3)
]s,]y,t[[ = ]]y,s[,t[.t3 ,
Ï.IIY'W'JTY'IH'IM'IP')
,

(4)

Y3t Y:2i Y1

=

W < Y * (M» > * V CN' ))•¥• CP' > t

D'où l'on déduit ;
]]x,r[,t[.v • ]x, ]r,t[[.?i.v
(d'après (1) )
3
]yJr,t[[.Yi.v
(car x sA.,„. y )
s
]r, ]y,t[[.Y2.Yi.v
(d'après (2) )
s
]s* ]yit[[.t*.Yi.v
(car

r =A«,N-

s

)

= ]]y#s[,t[.Y3.Y2,Yi.v
(d'après (3) )
- ]]*•[. t[.v
(d'après (4) ) .
Fin de la preuve.
Proposition \,Si
H: T 4 T' est un homomorphisme entre
théories
multisortes,
alors, pour toute algèbre
A';T' 4 Ens' de T' , la
famille
2 A . • ( s A . tM . )M-«ot><T->
est une famille
de
congruences, i, e, de relations
d'équivalence
compatibles avec
les lois de composition (de T' ) ,
Preuve, En effet, si x,y€Hom(Y'(M'), A') et r,s€Hom(Y'(N'), A')
sont tels que x 3 A . f „. y
et si
r 2 A .. M . S , alors on voit
(d'après le lemme 2) que ]x, r[ Sn-**.- ]y*s[ d'où l'on déduit
(en utilisant le lemme 1) que, pour tout objet P' de T' et
pour toute loi (i. e, toute flèche) h : M' x N' 4 P' de T1 ,
on a bien ]x, r[.Y'(h) s A . -R . ]y, s[.Y'(h), Fin de la preuve.

Supposons que
H : T 4 T'
est un homomorphisme entre deux
théories multisortes et que A' : T' 4 Ens est une T'-algèbre.
Pour tout objet M1
de Ta , on dispose de l'ensemble quotient
A'/sA-(M") = A'(M')/=A«.M«
et de l'application (surjective)
"passage au quotient" pA- ,M«: A'(M-) 4 A'(M')/=A.,M. ,
Puisque (d'après la proposition 1 précédente)
=Aest une

INOISCERNABIL.ITE,

A C C E S S ISIL. I T E

famille de congruences, il est facile de vérifier qu'on définit
ainsi un foncteur
A'/sA. : T'c 4 Ens
(de source la catégorie
T'c
sous-jacente à
T' ) et une transformation naturelle
p A . : A' 4 A'/sA. surjective "point par point".
Plus précisément encore, il est clair que:
Proposition 2, Si
H: T 4 T'
est un homomorphisme entre deux
théories multisortes
et si
A': T' 4 Ens
est une algèbre de
T' , alors
A'/sA.; T' 4 Ens est une algèbre de T'
(appelée
l'algèbre
des classes d'indiscernabilté
de A' , du point de vue
de T ) et le "passage au quotient"
pA-: A' 4 A'/sA.
est un
homomorphisme surjectif
point par point.

2.

Accessibilité.

Supposons que
T'
est une théorie multisorte et que
A': T' 4 Ens en est une algèbre,
Si
B': T' 4 Ens
est une autre T'-algèbre et si
m': A' 4 B'
est un homomorphisme de
A'
vers
B'
(i. e. une flèche de
Alg(T' ) ), on dit que
m1
présente
B'
comme une algèbre
l
{\ -accessible si, et seulement si:
-pour tout objet M' de T' , m'M.: A'(H') 4B'(M' ) est une
application surjective,
(autrement dit, si m' est un épimorphisme point par point),
Supposons que
H: T 4 T'
est un homomorphisme entre deux
théories multisortes et que A'; T1 4 Ens est T'-une algèbre,
On désigne par C'(A() la catégorie définie comme suit:
- ses objets sont les flèches m': A' 4 B1 de Alg(T' ) telles
que:
+ m1 présente B' comme une algèbre A1-accessible,
+ m'.H : A'.H 4 B'.H est un isomorphisme dans Alg(T) ,
- ses flèches sont les triplets:
(m',: A' 4 B',,n': B', 4 B'2,m'2: A' 4 B' 2 ): m', 4 m 2
où
n':B'i4B' 2
est une flèche de
Alg(T')
telle que
n'.m', • m'2 ,
(autrement dit, C'(A') est la catégorie des algèbres de T' qui
sont A'-accessibles et qui ont, à isomorphisme près,
la même
T-algèbre sous-jacente que A' ),

RART.

II : XNOZSCERNABZLZTE,

ACCESSIBILITE .

Dans ces conditions (et en reprenant
notations du §1 ), montrons que:

la terminologie et les

Lemme 3, Si H: T 4 T' est un homomorphisme entre deux théories
multisortes et si
A': T' 4 Ens
est une J1-algèbre,
alors la
flèche
"passage au quotient
vers
l'algèbre
des
classes
d'indiscernabilité"
pA-: A' 4 A'/sA. est un objet de C'(A') .
Preuve, D'après la proposition 2 du §1, on sait déjà que
pA.
présente effectivement A'/sA. comme une algèbre A1-accessible.
Comme, pour tout objet n de T (en particulier), l'application
PA..H<«>: A'(H(M)) 4 A'(H(M))/5A.,H<ri>
est
évidemment
surjective, pour conclure il suffit de montrer qu'elle est
injective.
Pour ce faire, supposons que x,y e Hom(Y'(H(M)), A') sont deux
éléments (de A'H(II)) ) tels que
x =A-.H<M> y
(on pourra se
reporter aux deux diagrammes ci-dessous:
Y'(H(M))
X 2A.,H<M> y

m'

Y'(H(M)) + Y'(N')-*

£ A - , HCrDxN*

— ] y > t[

Y'(H(N))
v

Y'(N')

et
Y'(H(M))
/
x a A .. MCM> y

\
\ v

]x,t[

^
Y'(H(M)> + Y'(l) <

»A..M<M>«,

]y,t[
Y'(l)

yf

Y*(H(M>>

v
).

II

:

INOISCERNABILITE,

ACCESSIBILITE

Ainsi, pour tout objet
N'
de
T' , pour tout élément
t e Hom(Y'(N'),A') , pour tout objet
N de T et pour toute
flèche
v:Y'(H(N>) 4 Y*(H(M))+Y'(N')
de
Alg(T') , on a (par
définition) ]x,t[.v * ]yit[,v .En particulier, on peut prendre:
- N' = 1 ,
- pour t , l'unique flèche t: Y'(1) 4 A' de Alg(T' ) , puisque
Y'(l) est initial dans Alg(T' ) car 1 est terminal dans T'
(voir la PARTIE 0),
- N = M,
- pour
v: Y'(H(N)) = Y'(H(«)) 4 Y'(H(M)) + Y'(l) , la première
co-projection,
d'où l'on déduit que:
x • ]x, t[.v
(puisque v est la première co-projection)
• ]y>tl>
(par hypothèse)
s
y
(puisque v est la première co-projection).
Fin de la preuve,
Etablissons,
maintenant,
que
la
T'-algèbre
des
classes
1
d'indiscernabilité d'une T'-algèbre donnée A
est la T'-algèbre
accessible "minimale" ayant même T-algèbre sous-jacente que A1 ,
Plus précisément, on a:
Proposition 3, Si
H; T 4 T'
est un homomorphisme entre deux
théories multisortes
et si
A': T' 4 Ens
est une
T'-algèbre,
alors la flèche identité
IdA.; A' 4 A* est un objet initial
de
la catégorie
C'(A')
et la flèche "passage au quotient
vers
l'algèbre
des classes d'indiscernabilité"
pA.; A1 4A'/s A .
en
est un objet terminal,
Preuve, Il est évidemment trivial de constater que IcU-: A1 4 A'
est bien un objet initial de la catégorie C'(A') ,
Pour prouver que
pA.; A' 4 A'/s A .
est un objet terminal de
C'(A') , supposons que
m1; A* 4 B1
est un (autre) objet de
C'(A') : il nous faut donc établir qu'il existe une unique flèche
n': B' 4 A'/sA.
de sorte que
n'.m' • p A . , Mais, pour tout
objet
M' de
T' , l'application
pA..«.: A' (M' ) 4 A'/s A . (M' )
est une surjection, il nous suffit donc de montrer que:
- si x,y e Hom(Y'(M1),A') sont tels que m'.x • m'.y , alors on
a x sA.,M. y ,
ou encore que:

CH 3 0

PART.

II

INDISCERNABILITE,

ACCESSIBILITE

- s i x,y e Hom(Y'(M'),A') sont tels que m'.x • m \ y , alors,
pour tout objet N' de T' et tout t € Hom(Y'(N'), A') , on a
]x, t[ KA-.«.*M-

]y, t[ ,

autrement dit, que;
- s i x,y € Hom(Y'(M'),A') sont tels que m'.x = m'.y , alors,
pour tout objet N' de T' , tout t e Hom(Y'(N'), A') , tout
objet M de T et tout v € Hom(Y' (H(M)>, Y' (W )+Y' (N' )) , on a
l'égalité
]x,t[,v = ]y,t[,v ,
(on pourra se référer au diagramme ci-dessous;
Y'(M')

Y'(M') + Y'(N')

Y'(N')
fact(z)

Y'(H(M))

Aig(T')
Alg(H)
)

Alg(T)
Alg(H)(fact(z))
Alg(H)(A')-*

Alg(H)(Y'(H(M>)>

z = Alg(H)(]x,t[.v).€(M)

e(M>
Y(M>

),

Mais, grâce au lemme de transition (voir la PARTIE 0), de
l'égalité m ' , x = m ' . y , on déduit que m \ ]x, t[ = m \ ]y, t[ d'où
m'.]x,t[,v = m'.]y, t[. v
et, par conséquent, en appliquant le
foncteur Alg(H); Alg(T') -» Alg(T) , on voit que;

RART.

II

: INDISCERNABILITE,

ACCESSIBIL.I T E

Alg(H)(m' ). Alg(H)(]x, t[. v) » Alg(H)(m'). Alg(H)(]y, t[, v) ,
et donc que:
Alg(H)(]x,t[.v) = Alg(H)(]y,t[.v) ,
puisque Alg(H)(m') est un isomorphisme, m'; A' 4 B' étant un
objet de C'(A') .
Or Y'(H(M)) est l'algèbre de T' , librement engendrée par Y(M)
(voir la PARTIE 0), en conséquence il existe une unique flèche
fact(z): Y'(H(M)) 4 A' de Alg(T') telle que:
Alg(H)(fact(z)).€(M) = Aig(H)(]x, t[. v). €(M) = Alg(H)(]y, t[. v). c
(en posant z = Alg(H)(]x,t[.v) = Alg(H)(]y, t[.v) ),
donc, par unicité, on conclut que:
]x,t[.v = fact(z) = ]y,t[.v .
Fin de la preuve.

3,

Réalisations,

Supposons que
H: T 4 T'
est un homomorphisme entre deux
théories multisortes et que A: T 4 Ens est une algèbre de T .
Si B'; T' 4 Ens est une algèbre de T' et si m: A 4 B'.H est
un isomorphisme de A vers B'.H (i. e, une flèche inversible
dans
Alg(T) ), on dit que
m
présente
B'
comme une
réalisation
de
A
si, et seulement si (en reprenant les
notations de la PARTIE 0);
- pour tout objet M' de T' , fact(m)„.«. G(A)(M' ) 4 B'(H') est
une application surjective,
(autrement dit, si fact(m): 6(A) 4 B* est un épimorphisme point
par point).
Alors, s'il n'y a pas risque d'ambiguïté, on dira plus simplement
que
B'
est une
A-réalisation;
ainsi, B'
est une
Aréalisation si, et seulement si, B' est 6(A)-accessible - au
sens du §2 précédent - et admet A pour T-algèbre sous-jacente
(à isomorphisme près),
Supposons que
H; T 4 T'
est un homomorphisme entre deux
théories multisortes et que A: T 4 Ens est une algèbre de T .
On désigne par C(A) la catégorie telle que:
- ses objets sont les (B',m: A 4 B'.H) vérifiant:
+ B': T' 4 Ens est une algèbre de T' ,
4 m: A 4 B'.H est un isomorphisme de Alg(T) présentant B'

CH 32

RART.

II

INDISCERNABILITE,

ACCESSIBILITE

comme une réalisation de A ,
- ses flèches sont les triplets;
( (B', .ihsA-tB'i. H), n':B' ,48'*, (B'2, m2: A4B'2. H)); (B',, m, )4(B'2, m 2 ) ,
tels que Alg(H)(n').mi = tht #
(autrement dit, C(A) est la catégorie des algèbres de T' qui
sont des A-réalisations),
Montrons maintenant que toute algèbre de
T
permanente
(relativement à H ), i. e. qui est aussi la T-algèbre sousjacente à la T'-algèbre qu'elle engendre, possède une réalisation
"minimale". Précisément, établissons la proposition suivante:
Proposition 4. Si
H; T 4 T'
est un homomorphisme entre deux
théories multisortes
et si
A: T 4 Ens
est une algèbre de T
permanente, i, e, telle que:
- la flèche canonique
e(A); A 4 Alg(H)(G(A))
(associée à
l'adjonction
du foncteur
G; Alg(T) 4 Alg(T*)
à gauche de

Alg(H); Alg(T') 4 Alg(T) ) est un isomorphisme dans Alg(T) ,
alors:
- la catégorie

C(A)

a un objet

initial

et un objet

terminal.

Preuve, D'après la proposition 3, il suffit de montrer que la
catégorie C(A) est isomorphe à la catégorie C'(G(A)) .
Pour ce faire, construisons tout d'abord un foncteur:
« : C(A) 4 C'(G(A)).
Dans cette optique, supposons que (B',m) est un objet de C(A)
(on pourra se référer au diagramme ci-dessous;

fact(m)
B' <

G(A)
Alg(H)
)

Alg(H)(B' )<*
Alg(H)(G(A))
Alg(H)(fact(m)>
m
^
I e(A)
).

Alors, on voit que;

CH 33

RART.

II

INDISCERNABILITE,

ACCESSIBILITE .

- Alg(H)(fact(m)) » m.e(A)" 1
est un isomorphisme, puisque
Alg(H)(fact(m)).e(A) = m et puisque m et e(A) sont, par
hypothèse, inversibles,
- fact(m) est, par hypothèse, un épimorphisme point par point,
par conséquent, fact(m); G(A) 4 B1 est un objet de C'(G(A)) ,
De même, supposons, que ((B' ltm^ ),n' :B' i4B'2, (B'2,m^)) est une
flèche de C(A) (on pourra se référer au diagramme ci-dessous;

actdta)
Alg(T')

. JAlg(H)

(•
Alg(T)
Alg(H)(B',)

*

Alg(H)(n')

Alg(H)(B'a>

).

Alors, on voit successivement, que:
- Alg(H)(n'),ffli = «a , par hypothèse,
- Alg(H)(n').m,.e(A)-\e(A> = m a .e(A)-\e(A) , puisque e(A) est,
par hypothèse, inversible,
- Alg(H)(n').Alg(H)(fact(m,)).e(A) = Alg<H)(fact(m2)).e(A) , car
e(A) est, par hypothèse, inversible et puisque, pour i = 1,2 ,
on a, par définition, Alg(H)(fact(mi>),e(A) = m± ,
- Alg(H)(n'.fact(m1)).e(A) - Alg(HXfact(m 2 )).e(A) , car Alg(H)
est un foncteur,
- n'.fact(mi) s fact(m2) , par unicité, puisque la flèche

INDISCERNABILITE,

ACCESSIBILITE

e(A): A 4 Alg(H)(G(A))
est la flèche canonique associée à
l'adjonction de G à gauche de Alg(H) ,
d'où il résulte que:
((B',,fact(m1)),n',(B'2, fact(m2))):(B',,fact(m,))4(B,2,fact(m2))
est bien une flèche de C'(G(A)) ,
Dans ces conditions, il est trivial de vérifier qu'on dispose
bien d'un foncteur:
0 : C(A) —*C'(G(A))
(B',m) j—> (B\fact(m))
((Bl,lmi),nfl#(Bl2,n2>) l > ((B',, fact(m, )), n', (B'2, fact(m2))) ,
Inversement, construisons maintenant un foncteur;
V : C'(G(A)) 4 C(A) .
Pour y parvenir, supposons que m1: G(A) 4 B' est une flèche de
Alg(T*) qui soit aussi un objet de C'(6(A))
(on pourra se
reporter au diagramme ci-dessous;

m'
B' «-

G(A)
iAlg(H)

Alg(T)
Alg(H)(G(A))

Alg(H)(B')
Alg(H)(m' )
ct(m')

e(A)
).

Alors, il est clair que:
- oc(m') = Alg(H)(m').e(A): A 4 Alg(H)(B') « B'.H
est
un
isomorphisme de Alg(T) , puisque Alg(H)(m') et e(A) sont,
par hypothèse, deux isomorphismes,
- fact(Alg(H)(m'),e(A))
est un épimorphisme point par point,
puisqu'on
vérifie
facilement
(par
unicité)
que
fact(Alg(H)(m').e(A)) = m' et puisque m' est, par hypothèse,
un épimorphisme point par point,
d'où il résulte que (B', Alg(H)(m').e(A)) = (B',<x(m')) est bien
un objet de C(A) .
De même, supposons que
(m'i;G(A)4B'i,n':B'i4B'2,m'2:G(A)4Bl2)
est une flèche de C'(G(A)) (on pourra se référer au diagramme
suivant;

RART.

II

: INOISCERNABILITE,

ACCESSIBILITE

B\

Q(A)

n'

Alg(T')

B':
Alg(H)
)

(•
Alg(T)
Alg(H)(B',) *
Alg(H)(m',)
Alg(H)(n')

Alg(H)(Q(A)) <Alg(H)(m'2)

Alg(H)(8'a>

oc(m'2)
).

Alors, il est clair que:
Alg(H)(n').(Alg(H)(ma1).e(A)) = Alg(H)(n«.m'i).e(A)
(puisque Alg(H) est un foncteur)
= Alg(m'2).e(A)
(puisque, par hypothèse, n',»1, » m' 2 )
ce qui signifie que:
((B'1,oc(m'1)),n',(B'2,a(m'2))):(B'1,<x(m,,))4(B'2,a(m'2))
est bien une flèche de C(A) .
Dans ces conditions, il est trivial de vérifier qu'on dispose
bien d'un foncteur:
¥ : C'(G(A))-»C(A)
l
m >^(B l Alg(H)(m').e(A))
( m ' ^ G ^ ^ B ' ^ n ' ^ ' a î G ^ ^ B ' ^ y ^ U B ' ^ o r t m ' , )),n', (B'2,«(m,2))) .
Finalement, un calcul élémentaire montre que les foncteurs
« ; C(A) 4 C'(G(A))
et
V : C'(G(A)) 4 C(A) , ainsi définis,
sont bien inverses l'un de l'autre. Fin de la preuve,
Evidemment, dans le cas où
H
a la propriété
de permanence,
i, e. quand toute T-algèbre est permanente (relativement à H ),

CH 3«

RART.

II

INDISCERNABILITE,

ACCESSIBILITE

et compte tenu de la proposition 6, §3, PARTIE I, et du lemme 1,
§3, PARTIE I, on déduit immédiatement de la proposition 4
précédente que;
Corollaire 1. Si
H: T 4 T'
est un homomorphisme entre deux
théories multisortes et si:
- H: T 4 T' est un isomorphisme sur son image pleine,
alors:
- pour toute algèbre
A; T 4 Ens de T , la catégorie
C(A) a
un objet initial
et un objet
terminal,
et;
Corollaire 2, Si
H: T 4 T'
est un homomorphisme entre deux
théories multisortes et si:
- H: T 4 T' est un homomorphisme rétractable
et sectionnable,
alors:
- pour toute algèbre
A; T 4 Ens de J , la catégorie
C(A) a
un objet initial
et un objet
terminal,

Supposons que
H ; T 4 T'
est un homomorphisme entre deux
théories multisortes.
Si A1 ; T' 4 Ens est une algèbre de T' , on note (en reprenant
les notations introduites dans la PARTIE 0):
- F(A') = G(Alg(H)(A')) la T'-algèbre librement engendrée par la
T-algèbre sous-jacente à A' ,
- f(A') = fact(Id(Alg(H)(A'))) ; F(A') 4 A' , l'unique flèche de
Alg(T') telle que:
Alg(H)(f(A')).e(Alg(H)(A'>) = Id(Alg(H)(A')) ,
et on dit que A' est librement accessible (relativement à H )
si, et seulement si:
- Alg(H)(A') est permanente (relativement à H ),
- f(A') ; F(A') 4 A'
présente
A'
comme une algèbre
F(A')accessible,
Alors, vérifions que:
Lemme 4. Si H; T 4 T1 est un homomorphisme entre deux théories
multisortes
et si
A': T' 4 Ens
est une algèbre,
librement
accessible, de T' , alors:
- on dispose d'un foncteur ("composition - des triangles
-par
f(A') "):

RART.

II

: INDISCERNABILITE,

ACCESSIBILITE

Û' ; C ' ( A ' ) - » C , ( F ( A ' ) )
m':A'4B'H*m'.f(A')
(m,1,n',m'2)i^(m'1.f(A'),n',m'2.f(A')) ,
- on dispose d'un foncteur ("trace de Alg(H) sur les côtés des
triangles"):
fl : C ' ( A ' ) ^ C ( A l g ( H ) ( A ' ) )
m , :A'4B'r^(B',Aig(H)(m'))
(m'1:A'4B'1#n',m'2:A'4B'2)>»(B',,Alg(H)(m'1),n',(B,2,Alg(H)(m'2))
Preuve, Le composé de deux épimorphismes point par point de
Alg(T') étant encore un épimorphisme point par point de Alg(T*)
et le composé de deux isomorphismes de Alg(T) étant encore un
isomorphisme, Û' est trivialement un foncteur (bien défini).
Enfin, il est facile de vérifier que
Q = V.Û'
est bien un
foncteur (puisque, d'après la preuve de la proposition 4 et
Alg(H)(A')
étant permanente, on dispose des deux foncteurs
inverses l'un de l'autre:
0> : C(Alg(H)(A')) 4 C'(F(A'))
et
V : C'(F(A')) 4 C(Alg(H)(A')) ).
Fin de la preuve.
Ainsi, compte tenu de la preuve de la proposition 4 (dont nous
reprenons les notations) et du lemme 4 qui précèdent, si
A' : T1 4 Ens
est une algèbre librement accessible, nous
disposons d'un diagramme commutatif:
C'(A')

(*)

—

C(Alg(H)(A' ))

—

J C (F(A' ))

(où
4
et
V
sont inverses l'un de l'autre), Dans ces
conditions, nous pouvons établir que ces foncteurs "font
coïncider" les trois T1-algèbres suivantes:
- la réalisation minimale de Alg(H)(A') , i. e, de la T-algèbre
sous-jacente à A' ,
- la T'-algèbre des classes d1indiscernabilité de A' ,
- la T'-algèbre des classes d'indiscernabilité de F(A') (i, e.

CM 3 3

RART.

II

INDISCERNABILITE,

ACCESSIBILITE

de la T'-algèbre librement engendrée par la T-algèbre sousjacente à A' ). Précisément, nous avons en effet;
Proposition 5. Si
H; T 4 T'
est un homomorphisme entre deux
théories
multisortes
et si
A' ; T1 4 Ens
est une algèbre
librement accessible,
alors dans le diagramme commutatif
(*)
ci-dessus, tous les foncteurs créent (voir (C.F.W.M, ) ) , et donc
préservent et reflètent,
les objets terminaux,

Preuve, Comme Q et ¥ sont des isomorphismes (puisqu1inverses
l'un de l'autre - d'après la preuve de la proposition 4), il est
trivial de voir qu'ils créent les objets terminaux.
Comme * et V sont inverses l'un de l'autre, pour montrer que
fi et fi' créent les objets terminaux, il suffit de montrer que
c'est fi (par exemple) qui les crée,
Pour ce faire, supposons que (B',m: A',H 4 B'.H) est un objet
terminal de la catégorie C(Alg(H)(A')) = C(A'.H) (on pourra se
reporter au diagramme suivant;
B-

f(A')

m"

F(A')

A'
fact(m)

Alg(H)

Alg(H)(m")
Alg(H)(f(A'))
Alg(H)(B"><
Alg(HMA') *
Alg(H)(F(A'))
Alg(H)(n")

Alg(H)(fact(m))
e(A'.H)

).

RART.

II

INDISCERNABILITE,

ACCESSIBILITE

Il est clair que;
- Id(A'.H) : A'.H 4 A'.H est un isomorphisme de Alg(T) ,
- fact(Id(A'.H)) = f(A') ; G(A'.H) = F(A') 4 A'
est un épimorphisme point par point, puisque A' est, librement accessible,
par conséquent, (A1, Id(A'.H); A'.H 4 Alg(HMA')) est un objet de
la catégorie C'(A'.H) et donc, puisque (B',m) en est un objet
terminal:
(1) il existe une unique flèche n':A' 4 B' de Alg(T' ) telle
que Alg(H)(n').Id(A'.H) = m , i. e. telle que AlgCHHrV ) = m .
On voit que;
Alg(H)(n\f(A')).e(A'.H) = Alg(H)(n'). Alg(H)(f (A* )).e(A'.H)
= Alg(H)(n' ). Alg(fact(Id(A',H))).e(A', H)
(par définition de f(A') )
= Alg(H)(n,).Id(A'.H)
(par définition de fact )
= Alg(HMn')
= m
(d'après (1))
= Alg(H)(fact(m)).e(A'.H)
(par définition de fact )
d'où l'on déduit, par unicité, que:
(2) n'.f(A') = fact(m) .
Maintenant, il est clair que:
-Alg(H)(n') est un isomorphisme de
Alg(T) , d'après (1) et
puisque m en est un, par hypothèse,
- n' est un épimorphisme point par point de Alg(T') , d'après
(2) et puisque f(A') et fact(m) en sont deux, par hypothèse
(i. e, A' étant librement accessible et (B',m) étant un objet
de C(A'.H) ),
d'où il résulte que la flèche n' : A' 4 B' de Alg(T' ) est
aussi un objet de C'(A') et, d'après (1), que c'est l'unique
objet de C'(A') tel que fi(n') » (B',m) .
Pour conclure, il nous reste donc à prouver que n' est bien
terminal dans
C (A* ) . Mais, si
m": A' 4 B"
est un (autre)
objet de C'(A') , on voit que:
Alg(H)(m',,f(A')).e(A'.H) » Alg(H)(m"). Alg(H)(f (A')).e(A'.H)

PART.

II

INDISCERNABILITE,

ACCESSIBILITE

= Alg(H)(mH).Alg(H)(fact(Id(A'.H))).e(A'.H)
(par définition de f(A') )
= Alg(H)(m")
(par définition de fact )
d'où l'on déduit, par unicité, que;
(3) m".f(A') = fact(Alg(H)(m")) .
Alors, il apparaît que:
- Alg(H)(m"> est un isomorphisme de Alg(T) , puisque m" est
objet de C'(A') ,
- fact(Alg(H)(mH))
est un épimorphisme point par point de
Alg(T' ) , d'après (3) et puisque f(A') et m" en sont deux,
par hypothèse (i. e. A' étant librement accessible et m" étant
objet de C'(A') ) ,
d'où l'on déduit que (B-,Alg(H)(m")) est un objet de C(A'.H)
et, par conséquent, que:
(4) il existe une unique flèche n": B" •» B'
que Alg(H)(nu).Alg(H>(m"> = m .

de

Alg(T')

telle

liais on voit que:
Alg(H)(n".m^f(A, )).e(A'.H> » Alg(H)(n".m">.Alg(H)(f(A' )).e(A\H>
* Alg(H)(n".m">. Alg(H)(fact(Id(A<.H))),e(A'.H)
(par définition de f(A') )
= Alg(H)(n".mM)
(par définition de fact )
= AlgŒHn^.AlgŒXm")
= m
(d'après (4))
= Alg(H>(fact(m)).e(A'.H>
(par définition de fact )
- Alg(H)(nl.f(A')).e(A'.H>
(d'après (2)>
d'où il résulte, par unicité que:
n".m".f(A'> = n'.f(A') .
et, comme
f(A')
Alg(T'), il vient:

est

un épimorphisme

point

par point

de

RART.

II

INDISCERNABILITE,

ACCESSIBILITE

(S) n".m" = n' .
De (5) résulte que (m N ,n M ,n'): m" 4 n'
est une flèche de
C'(A') . C'est
manifestement
la seule,
puisque,
si
(mH,nHi,n'); m" 4 n en est une autre, on a:
n ii

n i, iim «.— ni
(par définition)
= n\m"
(d'après (5))
m

n

et donc
n", = n"
puisque
m"
est, par hypothèse, un
épimorphisme point par point de Alg(T' ) . Fin de la preuve,

4.

Automates:

le

retour.

Désignons par Aut la catégorie des automates (déterministes,
complètement spécifiés), i, e. la catégorie dont les objets sont
les ((S,,, 1S)#E, S',e, T,<T) tels que:
- (S, ,,ls) est un monoïde (dit des signaux d'entrée
et dont la
loi de composition est " . " et l'élément neutre l s ),
- E est un ensemble (dit des états
internes),
- S' est un ensemble (dit des signaux de
sortie),
- e e E est un élément (dit état initial)
distingué dans
l'ensemble E ,
- T: E x S 4 E
est une opération (dite de transition)
du
monoïde (S, ,,13) » à droite, sur l'ensemble E ,
- <r: E 4 S* est une application,
et dont les flèches sont les homomorphismes (aisés à définir
naturellement) entre ces structures.
Il est, alors, facile de construire une théorie T' à 3 sortes
(Ent , Etat
et
Sor ) et une équivalence de catégories
r A : Alg(T') 4 Aut , Plus précisément, T1 contient au moins le
diagramme (*) ci-dessous;

CH 42

P«RT.

II

: INDISCERNABILITE,

ACCESSIBILITE

comp
Etat x Ent
proje^-t

trans
-> Sor

sor

et les équations suivantes y sont valides:
projet, q =» Id(Ent)
projet*, q a init, est ,
De la sorte, si

A' ; T' 4 Ens

est une algèbre, alors;

- A'(l) = {0} (à une bijection près),
- A'(neutrMO) = 1A. est un élément de A'(Ent) ,
- A'(initKO) = eA. est un élément de A'(Etat) ,
- A'(Ent x Ent) = A'(Ent) x A'(Ent) (à une bijection près),
- A'(Etat x Ent) = A1 (Etat) x A'(Ent) (à une bijection près),
et on a;

ra(A')
((A,(Ent),A'(mult),lA. ), A'(Etat), A'(Sor), eA., A'(trans), A'(sor)),

Désignons par Comp la catégorie des comportements, i, e, la
catégorie dont les objets sont les ((S,,, 1S)»S', X) tels que:
- (S,,,1S) est un monoïde (dont la loi de composition est " , "
et l'élément neutre est l s ),
- S' est un ensemble,
- X ; S 4 S* est une application,
et dont les flèches sont les homomorphismes (aisés à définir
naturellement) entre ces stuctures.
Il est alors facile de construire une théorie T à 2 sortes (Ent

CH 43

RART.

II

INDISCERNABILITE,

ACCESSIBILITE

et
Sor ) ainsi qu'une équivalence
rc; Alg(T) 4 Comp
entre
catégories , Plus précisément, T contient au moins le diagramme
(**) ci-dessous:
comp

Sort
neutr

De la sorte, si A ; T 4 Ens est une algèbre, alors:
- A d ) = {0} (à une bijection près),
- A(neutr)(0) = 1 A est un élément de A(Ent) ,
- A(Ent x Ent) = A(Ent) x A(Ent) (à une bijection près),
et on a:
T C (A)
((A(Ent),A(mult),lA),A'(Sor),A(comp)).
Si on désigne par Ens* la catégorie des ensembles pointés, il
est encore plus facile de construire une théorie T* à une sorte
(notée ici
Etat - pour les besoins de la cause) et une
équivalence de catégories T*: Alg(T«) 4 Ens* . Plus précisément,
T* contient au moins le diagramme (X**) ci-dessous:
(***)

Etat
init

1
De la sorte, si A ; T* 4 Ens est une algèbre, alors on a;

r*(A) = A(Etat) ,

INDISCERNABILITE,

ACCESSIBILITE

Les deux catégories Aut et Comp ne sont évidemment pas
étrangères l'une à l'autre, On dispose, en effet, du foncteur
"comportement sous-jacent";
comp ; Aut 4 Comp
((S, ,,U),E,S',e, T,<T) 4 ((S,., U>, S', or(f(e, -))) ,
Alors, il est facile de construire un homomorphisme H; T 4 T*
(dont une restriction est l'injection canonique du diagramme (**)
dans le diagramme (*) ) de sorte que Alg(H); Alg(T') 4 Alg(T)
et comp: Aut 4 Comp
soient "équivalents", i. e, tel que le
diagramme ci-dessous commute:
Alg(T')

> Aut

Alg(H)
Alg(T)

comp
> Comp

On en déduit immédiatement (voir la PARTIE 0) que comp admet un
adjoint à gauche, Une vérification rapide montre, en effet, que
tout
comportement
A = ((S,., U>, S', X)
engendre librement
l'automate 6(A) = ((S,,, ls)iS,S', 1s*., X) .
Alors, on constate que, pour tout comportement A , l'automate
6(A) a encore A pour comportement sous-jacent (c'est donc une
réalisation particulière de A , au sens du §3 précédent), Par
conséquent, H
a la propriété de permanence et, d'après le
proposition 6, §3, PARTIE I, H est un isomorphisme sur son image
pleine,
Maintenant, si B' = ((S,,, 1S)#E,S',e, Ï,cr) est un automate, de
comportement
A = ((S,., U>#S', X) ,
et si
m'; G(A) 4 B'
présente
B' comme étant
6(A)-accessible, au sens du §2
précédent, alors m ' e ^ ^ S 4 E est une surjection "compatible
avec l'opération du monoïde": c'est exactement dire que tout
état, élément de E , est dans l'orbite de l'état intial e de
E et donc que A' est accessible au sens usuel,
Enfin, tout automate (ou plus, généralement, tout comportement)
engendre, d'après la proposition 3 (ou la proposition 4)
précédente, un automate minimal (en nombre d'états) de même
comportement, Supposons que
((S,., ls)# E, S', e, T, cr)
est un
automate, associé (par l'équivalence entre Alg(T') et Aut ) à
une algèbre
A': T1 4 Ens et interprétons-en les classes
d'indiscernabilité, au sens
du §1 précédent, (on pourra se

CH 46

RART.

II

INDISCERNABILITE,

ACCESSIBILITE

reporter au diagramme ci-dessous;
Y'(Etat)
Y'(projEiJ.^)
jx,t[
lt/\x>

A/
Y'(sor. trans)
W% ZZV (Etat)+Y' (Ent)=Y' (EtatxEnt)^
Y' (Sor)
]y.t[

Y'(H(Sor))

Y'(proJEo-t)
Y'(Ent)

).

Si
x,y C E » A'(Etat)
sont deux états, ils s'identifient
(d'après le lemme de Yoneda - voir la PARTIE 0) à deux flèches
(encore notées) x, y : Y1 (Etat) 4 A' , Alors, si on a;
(1)
x s*.,,-.^ y ,
on voit que, nécessairement (par définition):
(2) pour toute flèche t: Y'(Ent) 4 A' , on a:
]x,t[.Y'(sor.trans) = ]y, t[, Y'(sor. trans) .
Réciproquement, on peut établir que (2) implique
(1) , donc
que (1) équivaut à (2), i. e. que c'est (2) qui est la partie

consistante

ou significative

de la relation (1),

Nais, une flèche t;Y'(Ent) 4 A' s'identifie (d'après le lemme
de Yoneda - voir la PARTIE 0) à un élément (encore noté)
tes
et, de même;
- ]x,t[ : Y'(Etat) + Y'(Ent) » Y'(Etat x Ent) 4 A'
s'identifie
au couple (x, t) c E x S ,
- ]y#t[ ; Y'(Etat) + Y'(Ent) = Y'(Etat x Ent) 4 A'
s'identifie
au couple (y, t) e E x S ,
- ]x,t[,Y'(sor, trans) s'identifie à:
A'(sor)(A'(trans)(x, t)) = or(-c(x, t)) ,
- ]yit[.Y'(sor, trans) s'identifie à:
A'(sor)(A'(trans)(y, t)) = <r(T(y, t)) ,
par conséquent, on a;
(»)

x = A -,e±m*. y #

si, et seulement si:
(3) pour tout signal d'entrée t e s , on a;
<r(*(x, t)) • *(f(7, t)) .
Ainsi, la relation d1indiscernabilité, au sens général du §1,
s'interprète
exactement
comme
étant
la
relation

CH 46

RART.

II

: INDISCERNABILITE,

ACCESSIBILITE

d'indiscernabilité usuelle (pour les automates). Si l'on préfère,
à l'objet terminal de C'(A') correspond, par l'équivalence de
catégories entre
Alg(T')
et A u t , l'automate à ensemble
d'états minimal, de même comportement que ((S,., l s ), E, S' ,e, T,<J),
Les deux catégories Aut et Ens* ne sont pas non plus
étrangères l'une à l'autre. On dispose évidemment du foncteur
"ensemble (des états) pointé (par l'état initial) sous-jacent";
état ; Aut 4 Ens*
((S,.,l3),E,S',e,T,*) 4 (E,e) ,
Alors, il est facile de construire un homomorphisme H*: T* 4 T'
(dont une restriction est l'injection canonique du diagramme
(***)
dans
le
diagramme
(*) ),
de
sorte
que
Alg(H*); Alg(T') 4 Alg(T*)
et
état; Aut 4 Ens*
soient
"équivalents", i. e. tel que le diagramme ci-dessous commute:

r.
Alg(T' )
AlgCH*)
Alg(T*)

> Aut
état
>Ens*

On en déduit immédiatement (voir la PARTIE 0) que état admet un
adjoint à gauche G* . Une vérification rapide montre, en effet,
que tout ensemble pointé (E,e) engendre librement l'automate
6*((E,e)) » (({1}, ,,l),E,E,e,proj:lxE4E, Id(E);E4E) .
Alors, on constate que, pour tout ensemble pointé
(E, e) ,
l'automate 6*(E,e) a encore (E,e) pour comportement sousjacent (c'est donc une réalisation particulière de (E,e) , au
sens du §3 précédent), Par conséquent, H* a la propriété de
permanence et, d'après le proposition 6, §3, PARTIE I, H* est un
isomorphisme sur son image pleine.
Maintenant, tout automate (ou plus, généralement, tout ensemble
pointé) engendre, d'après la proposition 3 (ou la proposition 4)
précédente, un automate minimalisé ayant même ensemble pointé
sous-jacent, i. e, un automate dont le monoïde et l'ensemble des
signaux de sortie sont minimaux, mais dont l'ensemble des états
est inchangé. Il est facile de constater, en interprétant d'une
manière analogue à la précédente la relation d'indiscernabilité,
que l'automate minimal obtenu a pour monoïde opérant un monoïde

INDISCERNABILITE,

ACCESSIBILITE

isomorphe à celui que l'on appelle,
syntaxique de l'automate de départ.

5,

Un

autre

usuellement,

le monoïde

exemple.

Le cas des automates, traité au §4 précédent, suggère des
exemples nouveaux d'application des considérations générales
précédentes,
mais
de
nature
analogue,
Indiquons-en
un,
relativement
"esthétique" ou suggestif (en ce qu'il a de
semblable à la construction du monoïde syntaxique, évoquée
précédemment), sans pour autant le détailler outre mesure,
Désignons par GrOp la catégorie des groupes opérant à gauche
(pour varier) sur les ensembles pointés (sans pour autant que
cette opération respecte le point) et par ens; GrOp 4 Ens* le
foncteur "ensemble pointé sous-jacent" (lorsqu'on note, comme au
§4 précédent, Ens* la catégorie des ensembles pointés),
Il est, alors, facile de construire une théorie T' à 2 sortes
(Grp
et
ens ) et
une
équivalence
de
catégories
r g : Alg(T') 4 GrOp , Plus précisément, T' contient au moins le
diagramme (*) ci-dessous;
(*>

Grp x Grp

mult

Grp x ens

projet

oper

Grp
neutr

/ proj.

ens
point

1
De même, on construit sans difficulté (i, e. comme au §4
précédent) une théorie T* à 1 sorte (que nous préférons noter
ens , cette fois) ainsi qu'une équivalence
r*; Alg(T*) 4 Ens*

CH 48

INDISCERNABILITE,

ACCESSIBILITE

entre catégories , Plus précisément,
diagramme (**) ci-dessous:
(**)

contient au moins le

ens
point

Il est tout aussi simple de construire un homomorphisme
H: T* 4 T'
(dont une restriction est l'injection canonique du
diagramme
(#*) dans
le diagramme
(*) ) de sorte
que
Alg(H); Alg(T' ) 4 Alg(T*)
et
ens: GrOp 4 Ens*
soient
"équivalents", i, e, tel que le diagramme ci-dessous commute:

Alg(T')

-> GrOp

Alg(H)

ens

v

•? Ens*

Alg(T*)

r*
On en déduit immédiatement (voir la PARTIE 0) que ens admet un
adjoint à gauche, Une vérification immédiate montre, en effet,
que tout ensemble pointé
(E,e) engendre librement le groupe
trivial ({i}, 1) opérant à gauche trivialement sur (E,e) ,
Par conséquent, H a la propriété de permanence et, d'après le
proposition G, §3, PARTIE I, H est un isomorphisme sur son image
pleine,
De même, toute structure
A' = (G, (E, e),t) de groupe ( G )
opérant (grâce à l'opération
T ) sur un ensemble pointé
( (E,e) ) engendre, d'après la proposition 3 précédente, une
structure minimale (G', (E,e), T') , "réalisant" le même ensemble
pointé sous-jacent mais avec un groupe opérant G' minimalisé,
Pour le construire, il nous suffit d'interpréter la relation
d'indiscernabilité, au sens
du §1 précédent, (on pourra se
reporter au diagramme ci-dessous;

CH 49

RART.

II

INDISCERNABILITE,

ACCESSIBILITE

Y'(projet)

Y'(oper)
A ' ^ ^ ^ Y ' (Grp)+Y' (ens)=Y' (Grpxens) <=
Y' (ens)=Y' (H(ens))
]g-.t[

).
Si g,g' e G » A'(Grp)) , ils s'identifient (d'après le lemme de
Yoneda - voir la PARTIE 0) à deux flèches (encore notées)
g,g1 ; Y'(Grp) 4 A' . Alors, il est facile d'établir qu'on a:
g =A'.arP g- #

(1)
si, et seulement si, on a;

(2) pour toute flèche t; Y'(ens) 4 A' , on a;
]g,t[.Y'(oper) = ]g', t[. Y'(oper) .
Mais, une flèche t;Y'(ens) 4 A1
s'identifie (d'après le lemme
de Yoneda - voir la PARTIE 0) à un élément (encore noté) t e E
et, de même;
~ ]9't[ s'identifie au couple (g,t) ,
- ]g'it[ s'identifie au couple (g',t) ,
- ]git[.Y'(oper) s'identifie à A'(oper)(g,t)) a T(g,t) = g.t ,
- jg'itt.Y'toper) s'identifie à A' (oper)(g', t))=T(g', t)ag«. t,
par conséquent, on a;
g sA.,Qnf> g1 ,

(1)
si, et seulement si;
(3) pour tout élément

t

de l'ensemble sous-jacent E , on a:
g.t • g'.t ,
(autrement dit, si on ne peut discerner la manière dont opèrent
g et g' ! ),
ou encore si, et seulement si;

RART.

II

: INDISCERNABILITE,

(4) pour tout élément
(si on note
t ).

Stab(t)

ACCESSIBILITE

...

t de l'ensemble sous-jacent E , on a;
g. g " 1 e Stab(t)
le sous-groupe de
G stabilisateur de

Mais, si on pose
û = rt ^ « E Stab(t) , il est facile de
vérifier que
A
est un sous-groupe distingué de
G , En
conséquence, on a G' a Q/Û , i, e. le groupe minimalisé G' est
quotient de G par son sous-groupe distingué, intersection de
tous les stabilisateurs.

BIBLIOGRAPHIE

(C.F.tf.M. )

S, MacLane:
Catégories for
Springer, 1971,

the

Working

Mathematician,

(CS.D.P, )

C. Lair:
Conditions Syntaxiques de Plongement, I et
II, Diagrammes, vols, 2 et 3, Paris, 1979 et
1980,

(I.I.A.C.)

J. A, Goguen et J. Meseguer:
Initiality, Induction, and Computability, in
Algebraic Methods in Semantics, édité par
M, Nivat et J. C. Reynolds, Cambridge Univ,
Press, 1985.

(S.Q.P.A. )

C, Henry:
Sur Quelques Problèmes de Plongements en
Algèbre, Diagrammes, vol. 10, Paris, 1983,