Cloture intervallaire et extension logique d'une relation

Zeitpchr. f: math. Logik und Gmndlagen d. Math. Bd. 36, S.217-227 (1990)

CLOTURE INTERVALLAIRE ET EXTENSION LOGIQUE D’UNE RELATION

par PIERRE ILLE en Marseille (France)

Introduction

Dans son cours [l], $1, R. FRAissE a introduit la notion de (k,p)-isomorphisme qui permet une nouvelle interpretation de l’extension logique (ou klkmentaire) d’une relation. Par ail- leurs, dans son article [2], il introduit les notions d’intervalle, de finivalle, de firtre intervallaire et de cl6ture intervallaire d’une relation. Cette notion d’intervalle est une gknkralisation de la notion usuelle dans le cas d’une chaine (ou ordre total). Elle permet, en outre, de dkfinir les filtres et ultrafiltres intervallaires, qui permettent a leur tour d’ktendre aux relations la notion de cl8ture calquke sur le passage de la chaine des rationnels a celle des rtels. Le fait que la chaine des reels soit aussi une extension logique de celle des rationnels, conduit R. FRAissE a posk deux problkmes dont Yetude permettrait une gtnkralisation kventuelle de ce cas particulier. L‘objet de cet article est de rksoudre ces problkmes en introduisant la notion de cl6ture intervallaire logique d’une relation qui renforce a la fois les notions d’extension logique et de cl6ture intervallaire.

1. Dkhitions et problkmes

1.1. Extension logique.

Une multirelation de base E est une suite finie R,, . . . , R, de relations de base E . Un isomorphisme local de la multirelation M = R , . . , R, vers la multirelation N = S,. . . S, est un isomorphisme d’une restriction de Ri sur une restriction de &, pour i = 1,. .. , n . Un automorphisme local de M est un isomorphisme local de M vers elle-mCme. Tout isomorphisme local de M vers N sera dit un (0,p)-isomorphisme de M vers N , pour tout entier p. Un isomorphisme local f de M vers N sera dit un (k,p)-isomorphisme (k 2 1) de M vers N lorsque, pour tout ensemble de q 5 p Blkments de la base de M , il existe une extension de f ces nouveaux Clkments qui est un (k - 1, p - q)-isomorphisme de M vers N , et inversement en kchangeant M et N , f et sa transformation rkciproque f-’. Un (k,p)-automorphisme de M est un (k, p)-isomorphisme de M vers elle-m6me.

Soit M une multirelation de base E ; une extension M’ de M a un ensemble E‘ contenant E est une extension logique (ou klkmentaire) de M lorsque pour toute partie finie X de E et tous entiers k,p, l’identitk sur X est un (k,p)-isomorphisme de M vers M‘. I1 est kquivalent de dire que pour toute formule logique P d’arite n a laquelle M et M‘ sont attribuables et pour toute suite a l , . .. , a, extraite de E , on a P ( M ) (al, ..., a,) = P ( M ’ ) ( a l , ..., an>.

Considkrons une multirelation M = R l . . . R , de base E et un ultrafiltre U sur un ensem-

15 Ztschr. f. math. Logik

218 P. ILLE

ble Z . Notons F(Z, E ) l’ensemble des fonctions dCfinies sur Z a valeurs dans E , considCrees modulo l’kquivalence suivante, encore notCe U: deux fonctions f et g de F(Z, E ) seront Cqui- valentes modulo U lorsque l‘ensemble des BlCments x de Z tels que f ( x ) = g ( x ) , appartient h U . Pour toute partie F de F(Z, E) , contenant les fonctions constantes, est definie la multirelation M = El.. .R,, de base F , appelee ultrapuissance de M , comme suit: pour i = 1,. .., n et pour les elements fl, ... ,f,, de F, ou n, est l’aritt: de R , , R ( f l , ..., f , , ) = + (resp. -) lorsque l’ensemble des elements x de Z tels que R , ( f , ( x ) , ...,fn,( x ) ) = + (resp. -) est un Clement de U . L‘ultrapuissance M est normale (voir [l], $ 5 ) lorsque pour tous elements f i t . . . ,fm de F, tous tlements g , , . . . , g,. de F(I , E ) et tous entiers k, p , il existe un Clement X de U et des 616- ments h l , ... , h,, de F tels que pour tout element x de X l’application, qui change g,(x) en h, (x ) pour i = 1,. . ., m‘ et qui est fixe sur f l ( x ) , .. . , f m ( x ) , est un (k,p)-automorphisme de M . En identifiant les fonctions constantes a leur unique valeur et si M est normale, alors M est une extension logique de M.

1 . 2 . Interval le , f inival le e t c l6 ture interval la i re . Une partie D de la base E d’une relation R est un intervalle de R lorsque tout automor-

phisme local de RID, une fois etendu par l’identitt sur E - D , est un automorphisme local de R . Par exemple, l’ensemble vide, E et les singletons de E sont des intervalles de R . D’autre part, l’intersection de deux intervalles de R est un intervalle de R .

Soit R une relation de base E et soit D une partie de E . Pour chaque entier positif p , di- sons que deux p-uples (xl, . . . , x,) et (y,, . . . , y p ) extraits de D sont equivalents modulo ( R , D ) , lorsque l’application qui change x, en y , pour i = 1,. . . , p , est un automorphisme local de R I D qui est extensible par l’identitk sur E - D en un automorphisme local de R . L‘ensemble D est un finivalle de R lorsque pour chaque entier p , il n’existe qu’un nombre fini de classes d’kquivalence modulo ( R , D ) entre p-uples. La reunion et l’intersection de deux finivalles de R est un finivalle de R et le complkmentaire par rapport a E d’un finivalle de R est un finivalle de R .

Un jiltre intervallaire F de R est un ensemble non vide d’intervalles non vides de R , vbri- fiant les deux conditions suivantes: tout intervalle de R qui inclut un element de F est un tlement de F ; l’intersection de deux elements de F est un BlCrnent de F. Un filtre intervallaire de R est trivial lorsqu’il contient un singleton. Un ultrafiltre intervallaire de R est un filtre intervallaire de R maximal par inclusion. Un filtre intervallaire F de R est un ultrafiltre intervallaire de R si et seulement si chaque intervalle de R qui coupe tous les elements de F, appartient a F.

Considerom une relation R de base E et associons a chaque ultrafiltre intervallaire U de R , non trivial, une relation R ( U ) de base E(U) disjointe de E de telle sorte que pour toute partie finie F de E( v) et pour tout element D de U , il existe un isomorphisme local de R ( U) vers R I D dkfini sur F et, de plus, les relations associees a deux ultrafiltres intervallaires de R distincts ont des bases disjointes. Nous pouvons alors definir, sans ambiguite, la cl6ture intervallaire R + de R de base E+, reunion de E et des E(U), de la faqon suivante: si F est une partie finie de E et si G est une partie finie de E+-E alors il existe des ultrafiltres intervallaires de R , U,, ... , U, tels que G est la reunion de G1, ... , G, 06 pour i = 1, ..., n , GI = G n E ( 17,). Pour i = 1, . . ., n il existe un element D, de U, , disjoint de F, de telle sorte que les D, soient mutuellement disjoints et il existe f; un isomorphisme local de R(UJ vers RID, defini sur GI, Notons f l’application de domaine F u G qui est une extension des f; et qui est fixe sur F : la restriction de R + A F u G est telle que f soit un isomorphisme local de R + vers R .

C L ~ T U R E INTERVALLAIRE ET EXTENSION LOGIQUE D'UNE RELATION 219

1 . 3 . Problemes concernant les not ions de cl8ture interval la i re e t d 'extension logique (voir [Z], p. 335-336).

Probleme 1 . Si U est un ultrafiltre intervallaire non trivial d'une relation R , alors existe- t-il une relation R ( U ) de base non vide telle que la cl8ture intervallaire de R , obtenue en associant aux ultrafiltres intervallaires de R distincts de U la relation de base vide et en associant a U la relation R(U) , soit une extension logique de R?

ProblBme 2 . Soit R une relation de base E , soient U et Vdes ultrafiltres intervallaires non triviaux de R et soit R + une cl8ture intervallaire de R obtenue en associant a U une relation R ( U) de base E( U), a Vune relation R (V) de base E( V) et aux ultrafiltres intervallaires de R distincts de U et de Vla relation de base vide. Si R+l(E u E(U)) et R+I(E u E(V) ) sont des extensions logiques de R , alors R + est-elle une extension logique de R?

1 . 4 . Cl8ture interval la i re logique. At% de rksoudre les problemes 1 et 2, nous introduisons la notion suivante: partons

comme en 1.2 d'une relation R de base E et definissons la clature intervallaire R + de R obtenue en associant a chaque ultrafiltre intervallaire non trivial U de R une relation R ( U ) de base E( U). La clature intervallaire R + de R sera dite logique lorsque pour tout ultrafiltre intervallaire non trivial U de R et pour tout element D de U , on a: R+l(D u E ( U ) ) est une extension logique de RID.

2. Proprietks des extensions logiques et des cl6tures intervallaires

2.1. Si R est une relation de base E et si D, , . . . , D, sont des intervalles de R mutuellement disjoints. Supposons qu'il existe des ensembles XI, . . . , X, mutuellement disjoints et disjoint de E et des relations R , , ... , R, de bases respectives D1 u X , , ... , D , u X, tels que Ri soit une extension logique de R / D i pour i = 1 , . . ., n . Notons X la reunion des Xi , E+ la reunion de E et de X et dkfinissons R + une relation de base E+ par: si F, est une partie finie de D, u Xi pour i = 1, ..., n et si F est une partie finie de E' = E - (Dl u ... u 0,) alors pour i = 1, ..., n il existe un isomorphisme local J de Ri vers RIDi de domaine Fi. La restriction R+I(F u F, u ... u F,) est telle que l'application dkfinie sur F u F, u ... u F, qui est l'extension des f; et qui est fixe sur F, soit un isomorphisme local de R + vers R .

Pour tous les entiers k , p , sipour i = 1, ..., n f i est un (k,p)-isomorphisme de Ri vers RIDi ( O M de RIDi vers R i ) de domaine F, et de codomaine Gi alors l'application dejinie sur E' u F, u ... u F,, notee fl u .. . u f , u Id,., qui est l'extension desfi et qui estfixe sur E', est un (k,p)-isomorphisme de R+ uers R ( O M de R uers R + ) . En particulier, R + est une extension logique de R .

Preuve par rkcurrence sur k 2 0. Le cas ou k = 0 rksulte de la definition de R + . Si k 2 1 , considkrons le cas ou pour i = 1, . . ., n J est un (k,p)-isomorphisme de Ri vers RIDi. Soit H une partie finie de E + , de cardinal q 5 p , disjointe de Fl u . ._ u F, u E' qui est le domaine de f , u ... uf, u IdE,. Donc H est une partie finie de (Dl u XI) u ... u (0, u X,) et pour i = 1 , . .., n notons Hi l'intersection H n (Di u Xi ) de cardinal qi s q . Pour i = 1 , . . ., n il existe gi une extension de f; de domaine Fi u Hi qui est un ( k - 1,p - 9,)-isomorphisme de Ri vers RID, et donc un ( k - 1,p - 9)-isomorphisme de Ri vers RIDi. Par hypothese de recurrence, gl u .. . u g, u Idr est un (k.- 1 , p - q)-isomorphisme de R + vers R qui est dkfini surH u (F, u ... u F,) u E' et qui, de plus, est une extension de f , u ... u f , u Idr. Inversement,

15'

220 P.ILLE

soit H une partie de E , de cardinal q 5 p , disjointe de (G, u . . . u G,) u E' qui est le domaine de l'application (fi u . . . u f, u IdE.)-l = f;' u . . . u f;' u IdE.. Ainsi, H est une partie de D1 u .. . u D,, et pour i = 1, ..., n notons Hi l'intersection H n Di de cardinal qi 5 q. Pour i = 1, ..., n il existe une extension gi de f;', de domaine Gi u Hi, qui est un (k - 1,p - q,)-isomorphisme de RIDi vers Ri et donc un (k - 1,p - 9)-isomorphisme de RIDi vers Ri. Par hypothkse de rtcurrence, gI u .. . u g , u IdEr est un ( k - 1,p - q)-isomorphisme de R vers R + , qui est une extension de (fl u . . . u f,, u Id,,)-'. Ainsi, f i u . . . u f, u IdEr est un (k,p)-isomorphisme de R + vers R .

Si F est une partie finie de E alors posons G = E' n F et F, = F n Di pour i = 1 , . . ., n. Pour i = 1,. .., n, comme R , est une extension logique de RIDi, pour tous les entiers k,p, I d , est un (k,p)-isomorphisme de Ri vers RIDi. Par ce qui prtc&de, Id, u .. . u Id, u Idr et donc Id, u . . . u Id, u Idc = IdF sont des ( k , p)-isomorphismes de R + vers R . Ainsi, R + est une extension logique de R .

2.2. Etant donnte R + la clature intervallaire d'une relation R obtenue en associant B chaque ultrafiltre intervallaire non trivial U de R une relation R ( U ) de base E(U).

Pour que R + soit une cl6ture intervallaire logique de R , il suffit que pour tout ultrafiltre intervallaire non trivial U de R , on ait : si D est un klkment de U alors il existe un Clkment D' de U , contenu dans D, tel que R+l(D' u E ( U)) soit une extension logique de RID'.

Soit D un tltment de U et soit D' un tltment de U, contenu dans D, tel que R+l(D' u E ( U)) soit une extension logique de RID'. Si F est une partie finie de D' u E ( U ) et si G est une partie finie de D - D', alors il existe un Cltment D" de U contenu dans D' et qui est disjoint de F n E . I1 existe un isomorphisme local g dkfini sur I; n E ( U ) de R+l(D' u E ( U ) ) vers RID" et comme R + est une clature intervallaire de R , l'applicationfdk- finie sur F qui est l'extension de g fixe sur F n E , est un isomorphisme local de R + l ( D ' u E ( U ) ) vers RID'. Par 2.1, comme D' est un intervalle de RID, pour que R + l ( D u E ( U ) ) soit une extension logique de RID, il suffit que l'extension de f par l'identitt sur G soit un isomorphisme local de R + l ( D u E(U) ) vers RID. Or, comme R + est une clature intervallaire de R , l'extension de g par l'identitt sur F n E et sur G , ou encore l'extension de f par l'identitt sur G, est un isomorphisme local de R + l ( D u E ( U ) ) vers RID.

2.3. Soit B un ensemble fmi d'ultrafiltres intervallaires non triviaux d'une relation R de base E et soit R + une clbture intervallaire de R , de base E + , obtenue en associant a chaque tlkment U de B une relation R ( U ) de base E ( U ) et en associant aux ultrafiltres intervallaires de R n'appartenant pas h B la relation de base vide. Considtrons une partie A de B et notons X la rbunion des E(U) lorsque U dtcrit A . Pour chaque tltment U de B, il existe un tlement D(U) de U de sorte que les D ( U ) soient mutuellement disjoints.

2.3.1. Si U est un kldrnent de B - A et si D est un Climent de U, contenu dans D(U), alors D est un intervalle de R+I(E v X).

Si f est un isomorphisme de RIF sur RIF' ou F et F sont des parties finies de D, et si G est une partie finie de ( E u X ) - D = ( E - D ) u X , alors montrons que l'extension f c de f par l'identitt sur G est un automorphisme local de R+I(E u X ) . I1 existe des Cltments U, , . . . , U,, de A et pour i = 1, . . ., n if existe une partie G, de E ( Vi) de sorte que G soit la reunion de G n E et des Gi. Pour i = 1, . . ., n il existe un element Di de Ui, contenu dans D( Ui) et disjoint de G n E , et il existe un isomorphisme local5 de R+IE(Ui) vers RIDi dkfini sur Gi. L'appli-

CL6TURE INTERVALLAIRE ET EXTENSION LOGIQUE D'UNE RELATION 22 1

cation g dkfinie sur G u F qui est l'extension des A, fixe sur F et sur G n E, est un isomorphisme local de R+I(E u X ) vers R . L'application h definie sur la reunion de F', de G n E et desA(G,), qui est l'extension des f;' fixe sur F' et sur G n E , est un isomorphisme local de R vers R+I(E u X ) . Comme D est un intervalle de R , l'application f definie sur la reunion de G n E, de F et des A(G,) qui est l'extension de f fixe sur G n E et sur les A(G,), est un automorphisme local de R . Ainsi, fc = h -7. g est un automorphisme local de R+I(E u X ) .

2.3.2. Pour tout ClCment U de B - A , l'ensemble o d e s intervalles de R+I(E u X ) qui contiennent au moins un ClCment de U, est un ultrajiltre intervallaire non trivial de R+I(E u X ) .

Si D est un intervalle de R+I(E u X ) qui coupe tous les BlCments de 0, alors D n E est un intervalle de R qui coupe tous les elements de U. En effet, pour tous les elements D' de U, D ' n D ( U ) est un element de U qui, par 2.3.1, appartient a 0, Comme D coupe D ' n D ( U ) , D n E coupe D' n D ( U ) et donc D'. Ainsi, D n E appartient a U et D est un element de 0.

2.3.3. La cl6ture intervallaire de R+I(E u X ) , obtenue en associant d chaque ultrajiltre intervallaire de R+I(E u X ) , 02 U est un ClCment de B - A , la relation R ( v) et en associant aux autres ultrajiltres intervallaires de R+I(E v X ) la relation de base vide, est la relation R +. De plus, si R +

est une cl6ture intervallaire logique de R , alors R + est une cloture intervallaire logique de R+I(E u X ) .

Si F est une partie finie de E+ - ( E u X ) et si G est une partie finie de ( E u X ) , alors il existe des ultrafiltres V,, . .. , V, de A et pour i = 1 , . .., n il existe une partie GI de E(V,) de sorte que G n X soit la reunion des G,. I1 existe des ultrafiltres U,, . . . , U,,, de B - A et pour j = 1, ..., m il existe une partie I;I de E(U,) de sorte que F soit la reunion des 4. Pour j = 1, . . ., m il existe un klBment C, de U,, contenu dans D( U,) et disjoint de G n E , et il existe un isomorphisme local6 de R(U,) vers RIC, defini sur 6. Pour i = 1, ..., n il existe un el&- ment Dl de V , qui est contenu dans D(V,) et qui est disjoint de G n E . Montrons que l'application f dkfinie sur F v G qui est I'extension des 4 fixe sur G , est un isomorphisme local de R + vers R+I(E u X ) . Pour i = 1, .. ., n il existe un isomorphisme local g, de R(V,) vers RID, defini sur GI. L'application g definie sur F u G qui est l'extension des 6 et des g, fixe sur G n E, est un isomorphisme local de R + vers R . L'application h dkfinie sur la reunion de G n E , desfi(F,) et des g,(G,), qui est I'extension des g;' fixe sur G n E et sur lesfi(F,), est un isomorphisme local de R vers R+I(E u X ) . Ainsi, f = h . g est un isomorphisme local de R + vers R + / ( E u X ) et R + est la cl6ture intervallaire de R+/(E u X ) , obtenue en associant a chaque ultrafiltre intervallaire 0 de R+I(E u X ) , 06 U est un ClCment de B - A , la relation R ( U ) et en associant aux autres ultrafiltres intervallaires de R+I(E u X ) la relation de base vide. Si, de plus, R + est une cl6ture intervallaire logique de R . Pour tout Clement U de B - A et pour tout element D de 0, il existe un element D" de U qui est contenu dans D. Posons D = D" n D ( U ) , D' est un Blement de U, contenu dans D et dans D(U), de sorte que par 2.3.1, D' appartient a 0. Comme R + est une cl6ture intervallaire logique de R , R+l(D' u E ( U ) ) est une extension logique de RID' ou encore de (R+I(E u X ) ) / D . Par 2.2, R + est une cl6ture intervallaire logique de R+I(E u X ) .

3. Existence de cl6ture intervallaire logique et solution du probl6me 1

3.1. Si f est un isomoqhisme d'une relation R sur une relation R' et si A est une partie de la base de R telle que R soit une extension logique de RIA, alors R' est une extension logique de R'lf ( A ) .

222 P. ILLE

3.2. Soit R une relation n-aire de base E et soit D un intervalle de R . Comme D est un intervalle de R , D et donc E - D sont des finivalles de R et il existe un nombre fini de classes d’kquivalence modulo (R , E - D) entre n-uples extraits de E - D. Notons X I , . .. , X , ces classes et pour i = 1, . . ., q notons Ri la relation n-aire de base E - D valant + sur les n-uples de Xi.

Pour tous k,p, si f est un (k,p)-automorphisme de la multirelation (RIE - 0 ) . Rl...Rq, alors l’extension f o de f par l’identitk sur D est un (k,p)-automorphisme de R .

Preuve par recurrence sur k z O . La cas od k = 0 decoule de ce que pour tout n-uple (xl , . . . , x,) extrait de E - D, les n-uples (xl , . . . , x,) et ( f (xl), . . ., f (x,)) sont Cquivalents modulo (R, E - 0 ) .

3.3. Soit R une relation de base E et soit U un ultrafiltre intervallaire non trivial de R . Re- prenons les m&mes notations qu’en 1.1 et considtrons F u n ultrafiltre sur un ensemble I . Pour tout BlCment X de V, notons V(X) l’ensemble des BlBments de Vcontenus dans X ; V(X) est un ultrafiltre sur X . Pour tout element X de Vet pour toute partie Yde E, notons F ( X , Y) l’ensemble des fonctions de X dans Y considerees modulo V ( X ) et notons R ( X , Y) l’ultrapuissance de RIY dkfinie sur F ( X , Y), od V(X) est l’ultrafiltre choisi sur X , et remarquons que pour toute multirelation M = (RIY) * R1.. . R, de base Y, le premier terme de l’ultrapuissance M de M dCfinie sur F ( X , Y) est encore R(X, Y) et, comme Mi est normale, M’ est une extension logique de M . Enfin, identifions les fonctions constantes de F(Z, E ) a leur unique valeur, de sorte que leur ensemble sera encore note E et notons E(U) l’ensemble des fonctions f de F(1, E) telles que pour tout BlBment D de U , f - ’ ( D ) appartient a K Les ensembles E et E( U) sont disjoints car si a est un element de E alors, comme U n’est pas trivial, il existe un 616- ment D de U qui ne contient pas a et l’image reciproque de D par la fonction constante el &gale A a, est l’ensemble vide. D’autre part, l’ultrapuissance de R d6finie sur E+=E u E ( U ) est notee R + et la restriction R + I E ( U ) est notee R(U).

3.3.1. L’ultrapuissance R + est une extension logique de R . I1 suffit de montrer que R+ est normale. Etant donnes a l , ..., a, des ClCments de E,

fl, .. . , f,, des elements de E ( U ) et g, , . . . , g, des elements de F(I , E ) - E+. I1 existe un 618- ment X de V et un BlBment D de U tels que a,, . . . , a, appartiennent a E - D, gl(X>, . . ., g,(X) soient inclus dans E - D et f , ( X ) , ..., f,,(X) soient inclus dans D . Ainsi, a l , ..., a, et g l / X , . . ., g , / X appartiennent a F ( X , E - D ) . DBfinissons, comme en 3.2, les relations R1, . . . , R, de base E - D. I1 existe des relations R ; , .. . , Rb de base F(X , E - D ) telles que R ( X , E - D) . R ;. . . R b soit l’ultrapuissance de (RIE - D) . R1.. . R, definie sur F ( X , E - D) et, donc, soit une extension logique de (RIE - D). Rl...Rq. Pour tous les entiers k,p, il existe des elements b l , . . . , b, de E - D tels que l’application qui change bi en gi/X pour i = 1, . . ., n et qui est fixe sur a l , ..., a,, soit un (k,p)-isomorphisme de (RIE- D ) . R l...R, vers R (X , E - D) + R 1.. . R h. D’autre part, il existe un Y de V(X) et donc de V, tel que pour tout BlBment x de Y, l’application qui change gi/X en gi(x) pour i = 1, . . ., n et qui est fixe sur a , , . . . , a,, soit un (k,p)-isomorphisme de R (X , E - D) . R:. . .R b vers (RIE - 0). R1.. .Rq. Par composition, si x appartient a Y, l’application X qui change bi en gi(x) pour i = 1,. .., n et qui est fixe sur a l , . . . , a, est un (k,p)-automorphisme de (RIE - D) . R 1 . . .R, et, par 3.2, l’extension Xo de X par l’identitk sur D est un (k,p)-automorphisme de R . Si x appartient a X et a K comme f,(x), ..., f,,(x) appartiennent a D, l’application qui change bi en gi(x) pour i = 1, . . ., n et qui est fixe sur a l , . . . , a, et sur fi(x), . . ., fm,(x) est une restriction de XD et, par suite, est un (k,p)-automorphisme de R .

CL~TURE INTERVALLAIRE ET EXTENSION LOGIOUE D’UNE RELATION 223

3.3.2. Pour tout iliment D de U, R+I(D v E ( U ) ) est une extension logique de R I D . Notons U ( D ) l’ultrafiltre intervallaire de R I D constitue des tlements de U contenus dans

D et notons E ( U ( D ) ) l’ensemble des fonctions f de F(Z, D ) telles que pour tout element D’ de U ( D ) , f - l ( D ’ ) soit un element de K Par 3.3.1, I’ultrapuissance R‘ de R I D definie sur D u E ( U ( D ) ) est une extension logique de RID. L’application dkfinie sur D u E ( U ( D ) ) qui est fixe sur D et qui associe a chaque element f de E ( U ( D ) ) I’application i. f de F(Z, E ) , ou i est l’inclusion de D dans E , est un isomorphisme de R‘ sur R+I(D u E ( U ) ) . Par 3.1, R+I(D u E ( U ) ) est une extension logique de R I D .

3.3.3. R + est la cl6ture intervallaire de R obtenue en associant d U la relation R ( U ) et en associant aux autres ultrafiltres intervallaires de R la relation de base vide.

Pour toute partie finie X de E(U) et pour tout element D de U, par 3.3.2, il existe un isomorphisme local de R ( U ) vers R I D defini sur X . La cl6ture intervallaire i=f de R , obtenue en associant a U la relation R ( U) et aux autres ultrafiltres intervallaires de R la relation de base vide, est donc bien definie. Montrons que R+ et i=f sont identiques: si a l , . . . , a,,, appartiennent a E et si f i , . . . ,f, sont des elements de E( U) alors il existe un element X de V et un Cltment D de U tels que a l , . . . , a,,, appartiennent a E - D et pour tout eltment x de X , f i ( x ) , . . . , f , ( x ) sont des elements de D et l’application qui change fi en f ; ( x ) pour i = 1 , . .., n et qui est fixe sur a l , . . . , a, est un isomorphisme local de R + vers R .

3.3.4. Atin d’apporter une rkponse positive au probleme 1, il suffit de choisir convenable- ment l’ensemble Z et l’ultrafiltre Vde sorte que E( U) ne soit pas vide. Par exemple, si Z = E et si V contient U alors IdE appartient a E( U).

3.4. Si R est une relation de base E et si A est ensemble d’ultrafiltres intervallaires non triviaux de R , alors il exkte pour chaque iliment U de A une relation R (U) de base E( U) non vide de sorte que la cl6ture de R , obtenue en associant a chaque klkment U de A la relation R (U) et en associant aux ultrafiltres intervallaires de R n’appartenant pas a A la relation de base vide, soit logique.

Par 3.3, il existe pour chaque element U de A une relation R(U) de base E ( U ) non vide telle que la cl6ture RU de R , obtenue en associant a U la relation R ( U ) et en associant aux ultrafiltres intervallaires de R distincts de U la relation de base vide, soit logique. Remar- quons que si E’( U) est un ensemble disjoint de E tel qu’il existe une bijection f de E( U) sur E’(U), alors nous pouvons definir l’unique relation R‘,, de base E u E’(U) telle que l’extension de f par l’identitt sur E soit un isomorphisme de RU sur R’,,. La relation R’,, est une c16- ture intervallaire de R qui, par 3.1, est logique. Nous pouvons donc supposer que a deux 616- ments distincts de A soient associees des relations de bases disjointes de sorte que la cI8ture intervallaire R + de R , obtenue en associant a chaque element U de A la relation R ( U ) et en associant aux ultrafiltres intervallaires de R n’appartenant pas a A la relation de base vide, soit bien dkfinie. Comme pour tout tltment U de A , R+I(E u E ( U ) ) = RU est une cl6ture intervallaire logique de R , R + est une cl8ture intervallaire logique de R .

4. Etude du probleme 2

4.1 . Une chaine D de base E est dense lorsque pour tous elements x et y de E tels que

Si D et D’ sont des chaines denses, de base non vide, sans minimum et sans maximum alors tout

x < y mod D , il existe un element z de E verifiant: x < z < y mod D .

224 P.ILLE

isomorphisme local de D vers D’ de domaine fini, est un (k,p)-isomorphisme de D vers D’, pour tous les entiers k et p .

Preuve par rkcurrence sur k 2 0. I1 dkcoule de 4.1 que si, de plus, les chahes D et D’ ont des bases disjointes alors la chaine D + D’ est une extension logique de D et de D’.

4.2. Un exemple de rkponse negative au problkme 2 (communiquk par R. FmissE).

Considkrons la chaine Q des nombres rationnels et dkfinissons pour chaque entier positif n, l’ensemble I , des nombres rationnels x tels que f i - (l/n) s x 5 f i et l’ensemble J, des nombres rationnels x tels que f i 5 x 5 6 + (l /n). Les ensembles I, et J,, sont des intervalles de Q et il existe des ultrafiltres intervallaires U et V de Q tels que U contienne les Z, et V les J,. Comme l’intersection des Z, et l’intersection des J,, sont vides, U et V ne sont pas triviaux. Soient a et b des nombres irrationnels: notons Q(U) (resp. Q(V)) la chaine de base E ( U ) = {a} (resp. E ( V ) = { b } ) et notons Q1 (resp. QJ la restriction de Q B l’ensemble des nombres rationnels x tels que x 5 f i (resp. x 2 6). La clature intervallaire Q (resp. Q”) de Q , obtenue en associant A U (resp. V) la chaine Q( U) (resp. Q( U)) et en associant aux autres ultrafiltres intervallaires de Q la chaine de base vide, est la chaine Q, + Q ( U ) + Q2 (resp. Q, + Q(V) + QJ. Par 4.1, Q’ et Q” sont des extensions logiques de Q. La cl6ture intervallaire a de Q , obtenue en associant i U la chahe Q(U), i Vla chaine Q(V) et aux autres ultrafiltres intervallaires de Q la chaine de base vide, est la chaine Q1 + Q ( U ) f Q(v) + Q 2 . Or, si IdB Ctait un (2,3)-isomorphisme de Q vers Q, alors il existerait un (1, 1)-isomorphisme f de a vers Q defini sur { a , b } . Comme il existe un nombre rationnel x tel que f ( a ) < x < f ( b ) , il existerait un isomorphisme local g de Q vers 0, dkfini sur { f ( a ) , x , f ( b ) } et qui est une extension de f - ’ de sorte que nous aurions: a < g ( x ) < b moda. Ainsi, a n’est pas une extension logique de Q. Remarquons d’ores et dejB, en vue de 4.4, que Q n’est pas une cl6ture intervallaire logique de Q. En effet, la base El de Q , , qui contient Zl, est un Blkment de U. Or, si Q / ( E l u E(U)) = Q1 + Q ( U ) ktait une extension logique de QIE1 = Q , , alors IdB serait un (2,2)-isomorphisme de Q1 + Q ( U ) vers Q1 . I1 existerait donc un (1, 1)-isomorphisme f , dCfini sur { a } , de Q1 + Q(U) vers Q , . Comme il existe un klkment x de El tel que x > f ( a ) , il existerait un isomorphisme local g de Q1 vers Q1 + Q ( U ) , dkfini sur {x , f ( a ) } , qui est une extension de f -I, de sorte que nous aurions: a < g ( x ) mod(Ql + Q ( U ) ) .

4.3. Un exemple de rCponse nkgative B la << rkciproque Y du problkme 2.

Plusprt!cist!ment, soit R une relation de base E , soient U et Vdes ultrafiltres intervallaires non triviaux de R et soit R + une cl6ture intervallaire de R , obtenue en associant a U une relation R ( U) de base E( U), a V une relation R (V) de base E( V) et aux ultrafdtres intervallaires de R distincts de U et de V la relation de base vide. Le fait que R + soit une extension logique de R n’entraine pas, en gkniral, que R+I(E u E ( U ) ) et R + / ( E u E ( V ) ) soient des extensions logiques de R .

Considerons des ensembles disjoints A et B tels qu’il existe une bijectionf, de N sur A , ou N dksigne l’ensemble des entiers naturels ordonnks usuellement, et fs une bijection de Q sur B, 06 Q dksigne l’ensemble des nombres rationnels ordonnks usuellement et considkrons la chaine C de base E = A u B , C =fa(N) + f B ( Q ) . Si x est un klkment de A , notons A, l’intervalle de C constituk des klkments y de A tels que x s y mod Cet si x est un klkment de B , notons B, l’intervalle de C constituk des klkments y de B tels que y s xmod C. Soit U (resp. V) un ultrafiltre intervallaire de C contenant les A, (resp. les B,). Comme l’intersection des A,

CL~TURE INTERVALWRE ET EXTENSION LOGIQUE D'UNE RELATION 225

(resp. des B,) est vide, I'ultrafiltre U (resp. V) n'est pas trivial. I1 existe une bijection fa. de Q sur un ensemble A' disjoint de A et de B et il existe une bijection fB' de Q' sur un ensemble B' disjoint de A , de A' et de B, od Q+ dksigne l'ensemble des nombres rationnels positifs ou nuls ordonnks usuellement. La cl6ture C+ de C, obtenue en associant a U la chaine C ( W = f a . ( Q ) de base E ( U ) = A ' , en associant A V la chaine C(V)=f,,(Q+) de base E(V) = B' et en associant aux ultrafiltres intervallaires de C distincts de U et de Vla chaine de base vide, est la chaine fa(N) + faj(Q) + fF(Q') + f B ( Q ) . Par 4.1, fa@) + fB , (Q+) + ~ B ( Q )

est une extension logique defB(Q) et par 2.1, comme B est un intervalle de C , C+ est une extension logique de C. Or, si C'I(E u E(V) ) =fa(N) +fF(Q') + f B ( Q ) ktait une extension logique de C, alors IdB serait un (4,4)-isomorphisme de C+I(E u E( V)) vers C. Notons a le minimum de fs.(Qt): il existerait un (3,3)-isomorphisme f de C+I(E u E(V) ) vers C dkfini sur {a) . Si f ( a ) appartient a A alors f ( a ) = f a ( n ) , ou n appartient a N, et il existe un (2,2)-isomorphisme g de C vers C+I(E u E ( V ) ) , dkfini sur { f A ( n ) , f A ( n + 1)} et qui est une extension de f-'. Comme il existe un ClCment x de B' tel que g(fa(n)) = a < x et x < g(fA(n + l)), il existerait un (l,l)-isomorphisme h de C + / ( E u E(V)) vers C , dkfini sur {a, x, g(fA(n + l))} et qui est une extension de g-' de sorte que nous aurions: f A ( n ) < h ( x ) et h ( x ) < f a ( n + 1). Si f ( a ) appartient a B , alors comme il existe un klkment x de B tel que x < f ( a ) , il existerait un (2,2)-isomorphisme g de C vers C' l ( E u E(V) ) , dkfini sur { x , f ( a ) } et qui est une extension def-'. Ainsi, g ( x ) < g ( f ( a ) ) = a = min(fs.(Q')) et donc g ( x ) appartient a A et il existe un klkment n de N tel que g ( x ) = f a ( n ) . I1 existerait donc un (1,l)-isomorphisme h de C' l (E u E(V)) vers C, dkfini sur {fa(n) , fa(n + l),a} et qui est une extension de g-'. Comme il existe un klkment y de B tel que h ( f a ( n ) ) = x < y < h( fa (n + l)), il existerait un isomorphisme local h' de C vers C + l ( E u E(V) ) , dkfini sur {x,y, h( fa (n + l)), h(a ) } et qui est une extension de h-' de sorte que nous aurions: f a ( n ) < h' (y ) < f A ( n + 1).

4.4. Le problkme 2 admet une riponse positive si seules les cl6tures intervallaires logiques sont considirt!es. En effet, si R + est une cl6ture intervallaire logique d'une relation R de base E , obtenue en associant d chaque ultrafiltre intervallaire non trivial U de R une relation R (v) de base E( U), alors R ' est une extension logique de R .

4.4.1. Montrons d'abord 4.4 dans le cas ou les ultrafiltres intervallaires de R auxquels sont associkes des relations de base non vide, sont en nombre fini. Notons alors Ul , . . . , U, ces ultrafiltres intervallaires de R . I1 existe pour i = 1, . . ., n un elkment Di de Ui de sorte que D 1 , . . . , D, soient mutuellement disjoints. Comme R + est une cl6ture intervallaire logique de R , R t / (Di u E(Ui ) ) est une extension logique de RIDi pour i = 1, ..., n. Par 2.1, pour montrer que R' est une extension logique de R , il suffit de montrer que si F, est une partie finie de Di u E(U,) pour i = 1,. .., n et si F est une partie finie de E , disjointe des Di, alors il existe pour i = 1, .. ., n un isomorphisme local de R + / (Di u E(U;)) vers RIDi de domaine & de sorte que l'application dkfinie sur F u Fl u . . . u F, qui est l'extension des fi et qui est fixe sur F, soit un isomorphisme local de R + vers R . Pour i = 1 , . . ., n il existe un isomorphisme local gi de R' /E(UJ vers RICi, dkfini sur Fi n E ( U J , oli Ci est un Clement de Ui disjoint de F, n E et contenu dans Di. Comme R' est une cl6ture intervallaire de R , non seulement pour i = 1, ..., n , l'applicationx, dkfinie sur F,, qui est l'extension de gi et qui est fixe sur Fi n E est un isomorphisme local de R' / (Di u E(Ui ) ) vers RIDi, mais aussi l'application dkfinie sur F u Fl u .. . u F, qui est fixe sur F et qui est l'extension des A, est un isomorphisme local de R ' vers R .

4.4.2. Revenons au cas gknkral et notons I l'ensemble des ultrafiltres intervallaires non tri-

226 P.ILLE

viaux de R . L‘ensemble des parties finies de Z est note PF(Z) et pour chacune d’elles A , 2 dC- signe la reunion des E ( U ) lorsque U dkcrit A . Pour tout element A de PF(Z), R + / ( E u 2) est la cl6ture intervallaire de R , obtenue en associant a chaque element U de A la relation R (U) et en associant aux ultrafiltres intervallaires de R n’appartenant pas a A la relation de base vide; de plus, R + ( E u 2) est une cl8ture intervallaire logique de R . Par 2.3.3, si A et B sont des elements de PF(Z) tels que B contienne A , alors R + / ( E u E) est une cl8ture intervallaire logique de R + / ( E u 6) . Par 4.4.1, comme R + / ( E u E) est obtenue a partir de R + / ( E u A) en associant seulement a un nombre fini d’ultrafiltres intervallaires de R + / ( E u 2) une relation de base non vide, R + / ( E u B ) est une extension logique de R + / ( E u x). Comme l‘ensemble des reunions E u 2, od A est un Clement de PF(Z), est filtrant par inclusion et admet pour reunion la base de R + , pour tout element A de PF(I), R + est une extension logique de R + / ( E u 2). En particulier, si A est la partie vide de I , nous obtenons que R + est une extension logique de R .

5. Probleme 3 (post par R. FraissC)

Partons d’une relation R de base E et d’un ultrafiltre intervallaire non trivial U de R . Soit R’ une cl8ture intervallaire de R , obtenue en associant a U une relation R’(U) de base E’(U) et en associant aux autres ultrafiltres intervallaires de R la relation de base vide.

Existe-t-il une relation R”( U) de base El’( U), un surensemble de E‘( U), telle que R”(U) /E‘ ( U ) = R ’ ( U ) et telle que la cl6ture intervallaire de R , dtfinie en associant a U la relation R”(U) et en associant aux autres ultrafiltres intervallaires de R la relation de base vide, soit logique?

Nous apportons dans ce qui suit une reponse positive i ce problkme. Notons I l’ensemble des indices i = (F, D ) ou F est une partie finie de E’ = E u E’ (U) et D est un element de U . Pour tout element i = (F, D ) de Z, i+ designe l’ensemble des elements i f = (F’, D‘) de Z tels que F soit inclus dans F’ et D contienne D’. Remarquons que si i , = ( F , , D,), . .., in = (F,,, 0,) sont des elements de Z alors comme D, n . . . n D, appartient a U , nous pouvons dkfinir 1’616- ment ( F , u ... u F,, D, n ... n D,,) de I est contenu dans i: n ... n i,’ . I1 existe donc un ultrafiltre Y sur Z qui contient i+ pour chaque itlCment i de Z. Definissons alors, comme en 3.3, la relation R + de base E + = E u E ( U ) qui est une cl8ture intervallaire logique de R .

Comme R’ est une cl8ture intervallaire de R , nous pouvons associer a chaque element i = (F, D) de Z, un isomorphisme local ti de R’ vers R dtfini sur F et tel que ti est fixe sur F n E et ti(F - E ) est contenu dans D . Pour chaque tlement a de E‘ est definie une fonction f , de I dans E , comme suit: si a est un tlement de E , f a est la fonction constante et Cgale a a (que l’on identifie a a ) et si a n’appartient pas a E , f, est telle que f , ( i ) = t , ( a ) d6s que a est un element de F, oii i = (F, 0). Remarquons que si a est un Clement de E’ - E , alors pour tout element Do de U , si i = (F, D ) est un BlCment de ( { a } , Do) + , comme a est un element de F, f , ( i> = t i ( a ) , et, comme D est inclus dans Do, t t (a ) appartient i Do. Ainsi, f;’(Do) contient ( { a } , Do) + et donc f;l(Do) appartient i Vde sorte quef, est un elCment de E( u>. La fonction F, definie sur E’, qui est fixe sur E et qui transforme chaque Clement a de E’ - E en fa, est donc a valeurs dans E + . Si a et b sont des elements distincts de E’, notons X l’ensemble des elements i de Z tels que f a ( i ) +fb(i). Pour montrer que F ( a ) * F ( b ) , il suffit de montrer que X est un element de K Si a et b appartiennent E alors, pour tout Clement i de I , f , ( i ) = a et fb( i ) = b de sorte que X = Z. Si seul a appartient B E alors, pour tout element i = (F, D ) de ( { b } , D o ) + od Do est un element de U ne contenant pas a , comme b appartient a F,

CL~TURE INTERVALLAIRE ET EXTENSION LOGIQUE D'UNE RELATION 227

fb(i) = t , (b) , et, c o m e D est inclus dans Do, t i (b) appartient a Do et t , (b) * a. Ainsi, X contient ( { b } , Do) et X appartient a K Si a et b appartiennent E' - E alors, pour tout 616- ment i de ({a, b } , E ) + ,&(i) = ri(a) etfb(i) = t i ( b ) . Comme ti est injective,h(i) +fb( i ) . Ainsi, X contient ( {a , b } , E ) + et X appartient a V; donc, F est injective. Si a,, . . . , a, sont des 616- ments de E', o~ n est l'aritk de R , alors il existe un element X de Vtel que pour tout element i de X , R + cf,, , . . . ,h,) soit Bgal A R ( L l ( i ) , . . . ,Ln(i)) . D'autre part, si i est un Clement de i;, ou io = ({al, . . . , a,), E ) , alors &(i) = t j (a l ) , . . . &(i) = ti(a,) de sorte que etant donne un elkment i de il et de X , R + Val, ..., fun) = R ( t i ( a , ) , ... , t,(a,)) et, comme ti est un isomorphisme local de R' vers R dont le domaine contient a*, ... , an, R ( t i ( a l ) , . .. , tj(a,,)) = R'(ai , ._. , a,). Ainsi, F est un isomorphisme de R' sur R + / F ( E ' ) .

I1 existe un ensemble E"(U), disjoint de E et contenant E'(U) de sorte que F admette un prolongement G qui est une bijection de E" = E u E"(U) sur E + . Notons R" I'unique relation de base E" telle que G soit un isomorphisme de R" sur R + et notons R"( U) la restriction de R" a E"(U) . Comme F est un isomorphisme, R"IE' = R' et donc R"IE'(U) = R'/E'(U) = R'(U) . Si A est une partie finie de E"(U) alors pour tout element D de U , comme R + est une cl8ture intervallaire de R , il existe un isomorphisme localfde R + vers R defini sur G ( A ) et a valeurs dans D de sorte que f. (GIA) est un isomorphisme local de R" vers R defini sur A et a valeurs dans D. Si A est une partie finie de E" et si D est un element de U disjoint de A n E alors il existe un isomorphisme local f de R + vers R defini sur G(A) , qui est fixe sur A n E = G ( A ) n E et tel que f ( G ( A ) - E ) soit inclus dans D. L'application g = f - ( G I A ) est donc un isomorphisme local de R" vers R defini sur A . Comme G et f sont fixes sur A n E , g est fixe sur A n E . Comme f ( G ( A ) - E ) est contenu dans D , g ( A - E ) est inclus dans D . Ainsi R" est la cl6ture intervallaire de R obtenue en associant a U la relation R"( U) et en associant aux autres ultrafiltres intervallaires de R la relation de base vide. Par 3.3.2, pour tout Clement D de U , R + / ( D u E ( U ) ) est une extension lpgique de RID et par 3.1, comme G- ' l (D u E ( U ) ) est un isomorphisme de R + l ( D u E ( U ) ) sur R"l(D v E"(U)) , R"l(D u E"(U)) est une extension logique de R"lD = RID. Ainsi, la cl8ture intervallaire R" de R est logique.

Bibliographie

[l] FuissB, R., Cours de logique mathkmatique I1 (thCorie des mod6les). Gauthier-Villars, Paris 1972; traduction anglaise: Reidel, Publ. Comp. Dordrecht 1974.

[2] FuissB, R., L'intervalle en thkorie des relations; ses genkralisations; filtre intervallaire et cldture d'une relation. In: Orders, Description and Roles (R. POUZET and D. RICHARD, eds.), North-Holland Publ. Comp., Amsterdam 1984, pp. 313-342.

P. Ille 211 bis ancien chemin de Cassis 13009 Marseille France

(Eingegangen am 8. Februar 1989)

Documents

Cloture intervallaire et extension logique d'une relation