par BRUNO POIZAT i n Ptwis (France)

11 y a dans la faune math6matique dcux cspkces fort distinctes qui portent lc noin d’uAlg8bres de Post ces deux denominations rendent hornmago aux travaux d%MlL I,. POST sur les logiques Q plusieurs valeurs dc vBrit6; celle dc premi6r.c esphce sont drs structures algebriques, B chacune desquelles est assoei6 un nombre fini, leur ordre. le prototype de ces algkbres de Post d’ordre m Btant certaincs fonctions engendrant. I’ensemble de tous les tableaux de verit6 sur m valeurs; celles d’ordre 2 sont tout, simplement les alghbres de Boole; le lecteur d6sirant de documenter sur cette espbce, dont il n’est pas question ici, peut consulter le livrc de HELENA RASIOWA, An Algebraic Approach to Non-Classical Logics, North Holland, 1974.

Dans cet article, une alghbre de Post de base B est une famille A de fonctions ii plusieurs arguments de B dans B ({(tables de veritk B-valukes ))), contenant les fonctions- identit6 (sblecteurs) et close pour la composition des fonctions. EMIL L. POST a class6 dans sa thbse [7] et [S] toutes ces alghbres qui ne contiennent que des fonctions B nomhre fini d’arguments lorsque l’ensemble de base B a deux Bl6ments.

A sa suite, de nombreux chercheurs ont essay6 de classer au moins partiollement ces algebres lorsque B reste fini, mais a plus de 2 dements; ce problbme est plus corn- plexe, ne serait-ce que parce que lorsque IBI 5 3, il y a une infinite continupotcnte. do talles alg8bres. En avanqant dans cette direction, toujours dans le ca.s oh B est fini, 1,. A. KALUZHNIN et ses Blbves [l] remarquerent qu’une algebre de Post forniee do fonctions B nombre fini d’arguments est caract6risee par les relations d’arit’i: finie qiw cliacun de ses Bl6ments prkservk, et Btablirent une dua.lit6 entre les algbbres de Post, d’une part, et d’autre part les ensembles de relat.ions clos pour les operations: ccnd- jonction de la. relation vide, des diagonales, changements de variables, conjonctions, projections H (toutes ces notions seront definies ci-aprbs). Ce thkorkme s’inscrit dans Ic prolongemeat de la tTh6orie de Galois abstraiteu do MARC KRASNER ([2], [3]).

Le but principal de cet article est de g6n6raliser cette ccthkorie de Galoifi)) RU cas oi l non seulement I’ensemble B est infini, mais aussi oh les alghbres sont compos6rs de fonctions pouvant avoir une infinit4 d’arguments. Dans la premiere partie, je pr6- cise la dbfinition des algebres de Post; un point essentiel est que je tiens absolument a identifier me fonction avec celle qu’on obt.ient en lui ajoutant des variables muettes (si on ne le faisait pas, il faudrait supposer que nos alghbres sont closes pour l’adjonction de variables muettes; dans [7] et [S], E. L. POST ne fait pas cette hypothhse); j’obtiens un resultat curieux sur les aritBs des 6lbments d’une alghbre de Post (Corollaire 2 ) . La deuxibme partie, du meme style, concerne les relations. Dans la troisihme partie la thkorie de Galois est developpee, et divers cas particuliers sont examinks. Dans la quatrihme partie, je caracthrise les clbtures d’un ensemble de relations d’arit,6 finie par cles formules finies d’un certain type au moyen d’6nonces dans le style du th6or8mo de h R s fhENoNTrrs [ 121. Dans la cinquibme partic: je construis une relation particulihiv-

32 BRUNO POIZAT

ment rigidc, c’est-8-dire yui n’est stabilisee que par le moins de fonctions possible; la oonstruction repose sur une gCn6ralisation au cas infirii tl’un lerr-ime S . B YAULON- YKTI 114).

Dans w t articlr, I’nxiome du choix wt utilis6; IXldesigne le cardinal de l’cnseniblc x’; H i I est un cardinal, 2‘ d6signt. son tmdin:il surcesseur; toutefois le successeur de CD

cst not6 w1 et non d .

I . AlgPhrw (10 Post

On considere dor6navant un ensemble B de cardinal ,!3 2 2, qu’on appclle In l)asc, ct drs envmblcs X , Y , Z, . . ., appel6s cnscmbles de variables; un X-point, ou X - axsignation, est p n r definition iinc application dc X dans B, et une X-fonction d e base B une application de B‘ dans B.

Une partie Y de X est dite support de la X-fonction f si la valeur de f en un point ne depend que de la restriction de ce point B Y : p 1 Y = q I Y implique f ( p ) = f ( q ) . On verifiers que l’ensemble des supports de f constitue un filtre de parties de X , ct que n’importe quel filtre est le filtre des supports d’une fonction convenablerncnt ohoisie; en g6n6ral il n’existe donc pas de support minimal, commc dans le ca4 oh l’ensemble de variable est fini, e t I’exprcqsion ((la fonction f depend effectivernoiit cle la variable X P ne peut gutre signifier que 5 appartient 8 I’intersection d r s supports de f .

Si Y est un hupport de In X-fonotion f , il est nature1 d’identifier f et l’uniquc I’-fonr- tion f* telle que f ( p ) = f * ( p 1 Y ) . Plus precis6ment la XI-fonction f, et la X,-fonc- tion f z seront dites kquivalentes s’il existe une (unique!) X , u X,-fonotion f telle que pour tout, X, u X,-point p , f ( p ) = f , ( p 1 XI) = f 2 ( p 1 X,); on mont,re facilemrnt q u ~ c’est bien une i.quivalence, dont les classes seront appelBes foiictions dc base B . Now diroLq encore que fl et f2 ddfinissent la m2me fonction f , que f1 reprdsmte la fonction I; par definition, X est dit support de la fonction f si c’est un support d’un de ses repr6s(w- tants: on remarquera qu’il y a alors une et une seule X-fonction qui repr6scnte f .

Toutes les notions qui seront introduites sont associ6es aux fonctions, mais font intervenir dans leur definition des choix de X-fonctions repr6sentant ces fonctions ; le soin de prouver que ces definitions sont bien indhpendantes de ce choix de repi.6- sentants sera laisse au lecteur incredule. En outre, par abus de notation, il m’arrivem de designer par la mhme lettre une fonction et la X-fonction qui la represente.

J’appelle aritk d’une fonction le minimum des cardinaux de ses supports; de chaque support d’une fonction on peut extraire un support de cardinal Bgal 8 son arite. Les relations 0-aires, unaires, binaires, , . , I-aires sont d’arit6 respectivw 0, 1,2, . . . , 1.

Les fonctions d’arit6 0 sont les constantes; parmi les fonctions d’arit6 1, on distingue les sdlecteurs, correspondant a l’application identique : le selecteur associC ti la variable P, ou x-dlecteur, donne au point p sa valeur en 2.

Soit e une application de X dans Y , qu’on appellera changemeiat de variubles; ti toutc fonction f do support X on associc la fonction f“ de support Y d6finie par ( p ) = f ( p 0 e) ; f“ est dite rdduite de f , principalement lorsque e n’est pas injectif (si Y n’a qu’un sen1 element,’ on parlera de la rdduite unaire de f ) .

THEORIE 1)E OALOIS POIJR TARS ATAJkl3RES J)R POST TKFlNlTAlRES 33

Soit f une fonction de support X, et soit i une application qui it tout 2 de X associe une fonction f,: de support Y?; la composde, ou superposde, des fonctions f,: et de f via I’application i est par definition la fonction g, de support Y = UY,, , ainsi definie: soit p un Y-point, et soit p le X-point tel que p z = f& I YJ; on pose g(q) = f ( p ) . On dira que la composition est it supports disjoints si les Y,. sont deux a deux disjoints.

Une algbbre de Post est par definition une classe de fonctions contenant tous les sklecteurs et close pour la superposition des fonctions; si le cardinal 1 majore stricte- ment les &rites des fonctions de A , nous dirons que A est, une I-algbhre de Post. Dans ce cas, si I est infini, pour d6crire les dements de A a changement de variables bi- jectifs pres, on peut se contenter d’un ensemble X fixe de variables de cardinal 1: en outre, toujours & changement de variable bijectif prds, toute composition se rambne B une composition oh tous les supports intervenants sont contenus dans X . C’est a.insi que dans le cas des o-alghbres de Post, qui ne contiennerrt donc que des fonctionu d’arit6 finie, on se contente d’un ensemble dknombrable fixe de variables. L’existencn d’un tel I n’est pas exig6e dans le cas g6n6ral.

TI est clair qu’une intersection d’algkbres de Post en est une, donc qu’6tant donnec une c h s e F de fonctions, il existe une plus petite algkbre de Post contenant F , appelee algbbre de Post engendrke par F . Une algebre de Post est close pa.r r6ductions, ca,r ces dernihres s’obtiennent en composant avec des selecteurs ; on v6rifiera que reciproyuc- mcnt si d une classe F de fonctions close par compositions et reductions on ajout.e (6vcntuollement) Ies decteurs, on obtient une algebre de Post,.

Lemme 1. Soit F une c h s e de fonctions; aoit A, la plus petite classe de fon,ctiona contenant F et close par changement,~ de variables bijectifs et auperpositioona d mu;oportcq disjoints, et soit A la c h s e formCe dea sklecteurs et dea rkduites des Alhenta dr A,: A rst l’ulgbbre de Post engendrke par F .

Demons t r a t ion . Soit A, la classe formhe des reduites des 616ments de A, ; comme A , est close par reductions (car la composOe de deux reductions en est une), il siiffit de voir que A , est close par compositions. Soit donc f de support X dans A , , et f“ unp reduite de f; pour tout y de ex, considerons un element g p de A, , gg &ant dans A , de support X!, . 11 nous suffit de montrer que la compos6e h s’obtient par une composi- tion & supports disjoints d’616ments de A , , suivie d’une reduction; nous pouvons tout’ d’abord supposer que les X, sont deux A deux disjoints, quitte it modifier g!/ et e , sans changer 0. ConsidErons alors l’application E de la reunion dos X , sur la reunion deu e , X , induite par les e,: la composee (& supports disjoints) de f et des g!/ est dans A , . et, h s’obtient en la reduisant d’abord par E , puis par e. 0

Propos i t i on 1. Soit F un ensemble de p fonctions d’aritd au plus A in,fini; l’algi!brt de Post engendrie par P est form,ke de fonctions d’aritd au plua A, et i1 y en. a( au plus sup($, P) de support X , s i 1x1 = A ,

D 6 m o n s t r a t i o n. La premiere assertion se d6duit du fait que les fonctions d’ariti? au plus I forment une algebre de Post (plus gknbralement, il en est de mdme des fonc- tion d’arit6 strictement inferieure it 1 si 1 est r6gulier). Passons au denombremcnt.: on remarquera que comme 1 I = A, A changement bijectif pres du liom des variables toute composition peut se faire en n’utilisant que des variables de X . ConsidBrons I’arborescence I < w (ensemble des suites finies B valeur dans 1) munie de son ordre partiel naturel; chaque 616merit de la cl6ture de F par l’op6ration A-aire ucomposition

3 Ztschr. f. math. Lo@

34 13HUNO POIZAT

b supports disjoints)) s’obticnt B partir de F par un procede qui se symbolise par un sous-arbre de Acm dont toutes les lwanches sont finies : i l y a donc 2” sch6mas de compo- sition; cet arbre &ant choisi, il faut remplacer cliacune de ses extrkmit6s par das 616mcnts de F, cc qui fait en tout 2 a * p‘; restend les ritdnctionx:. i l y en a

Corol la i re 1. On ne peut engendrer I’aEgPhrr, de toirtes 1 ~ s fonctiom ril’nrifd au plus JL

Dkmonst ra t ion . T1 y .zpfl* fonctions do support X , 1x1 = A ; or (pa),” = = f lA. 0 Soit @ un filtre de partie de x’; nous lui associoiis line fonction de base 2, do sup-

port X , que nous notons de la mkme lettre et, appelons foixtioii,-filtre associka B @, ct qui est ainsi d6finie: @ ( p ) = 1 si (x I px = I.> E @, @(p) = 0 sinon. @ est Ic filtre dcs supports de la X-fonction definissant @( ). On v6rifiera que ces fonctions-filtre forment. une algitbre de Post: B la notion de fonctionLfiltre r6duite correspond celle de filtre image directe pnr une application, e t it celle de composition des fonctions-filtre la. notion do filtre limite d’un ensemble de filtres suivant un filtre; nous parlerons rc- spectivement de filtre reduit et de filtre composB. Les fo~~.ctions-~ltraf~ltre associees RUX

ultrafiltres, forment une sous-algkbre de Post de celle des fonctions-filtre ; elle est, autoduale en ce sens qu’elle est conservhe par la permutation des vnleurs 0 at 1.

ill = 21. 0

nu moyen de Redement pa d’entre elks.

On verifier& sans p i n e le lemmc suivant,:

Lemme 2 . Le filtre des nupports d’une composde e.rt plus f i n ~ I W le composC den filtres ~ P S supports; en particulier le filtre des supports d’une rdduile P S ~ plus f in que le vddwit du filtre des supports.

= 2, et s i duns un.e compositioiz ci supports disjoints toutes les jonetions composantes sont n m constaiites, le f ilfre des supports de la composte est exacte- ment le com.posk du filtre des supports.

D6monr;Ptration. Soit g = f ( . . ., f , . , . . .); soit Y la reunion des supports Y, de f J : si Z est une partie de Y qui n’est pas dans le filtre compos6 du filtre des supports, alors par definition T = {x I Z,,. = Z n Y v est un support de f l . } n’est pas un support de f : on peut donc trouver deux X-points p et p‘, avec p I T = p‘ I T et f ( p ) + f (p ’ ) . Comme f , . n’est pas const>ante, elle prend leR deux valeurs 0 et 1, et il existe un Y,,- point y,,. tel que il.(y.,) = p(x), ainsi qu’un Y,.-point q,:. tel que f,.(q,;.) = p ’ ( x ) ; en outre, sur T, on choisit Q., et. q:. Bgaux. Comme les Y, sont disjoints, ii existe deux Y-points q et q‘ prolongeant respectivement les qr et les q,:. . Donc q I Z = (I‘ 1 Z, g ( q ) = f ( p ) + + f ( p ’ ) = ~ ( q ’ ) , et Z n’est pas un support de g.

des f v soit surjective.

P ropos i t i on 2. Si

Remarque . Le thBorkme ci-dessus reste vdable pour B > 2, B condition que cha.cune

Corol la i re 2. Soit A une nlgbbre de Post, d’aritk b o d e . et soit il le plus petit majorant strict des aritks des Clhents de A . Si /3 = 2, il = 2 ou est un cardinal z‘nfini rkgulier. S i > 2 , il peut &re n’irnporte p e l cardinal aupdrieur ou dgul d 2 .

Demons t r a t ion . Si = 2 , soit pi line famille de x cardinmx strictement infkrieurs & A, x < A, et soit p la somine des pi; soient f i des fonctions non-constantes (c’est-A- dire d’Arit6 nu moins 1 !) de A d’arit6 au moins p i , f de A d’ariti? au moins x ; d’a.pr6s

la proposition prkddente, lcur rompos6e h supports diujoints est d’aritC an moins p. done p < A . D’oh le r6sultat.

Si B > 2, considerom deux valeurs 0 ct 1 dans B, et pour tout X, aver 1x1 < A. la fonction f telle que f ( p ) = 1 si p 1 X nr prend que lrs vnleurs 0 nu 1 , f ( p ) = 0 sinon ; avec les projecteurs, ces fonctions formcnt une algithrr dc Post 0

Remarque . Les fonrtions surjectives d’uncb I-nlgh1)rc. d~ Post ont une arit6 born6e par 2 ou pu1 un cardinal infini r6guliw.

11. Rolationa

Une X-relation est un ensemble de X-points, ou encore, si on assimile un ensemble & sa fonction caraoteristique, une fonction de B“ dans l’ensemble { O , 1) A deus 616- ments. Si ,!I = 2, relations et fonctions sont en somme les m6mw objets vus SOUR un jour diff6rent. On dCfinit comme pour les fonctions le filtre des supports d’une X-rela- tion, et en identifiant, si Y c X , les Y-relations aux X-relations de support Y , on dAfinit les relations. L’uritt! d’une relation est le minimum des cardinaux de ses supports.

Si r est une relation de support X, sa X-largeur est par definition le nombre de X-points que contient la X-relation definissant T , et sa largeur est le minimum de ses X-largeurs. Si r est d’aritk K , sa large& est au plus /P.

Une relation d’arit6 a et de largeur 1, peut &re vue comme une matrice B coefficients dans B, A 1 lignes et a colonnes, les lignes representant les points qui sont dans r (deus telles matrices se correspondant par une permutation de lignes d6finissent la memc relation).

Parmi les relations, distinguons la relation vide, nothe 0, qui est d’arit6 0 (1’autr.r relation d’ariM 0, noMe 1, est celle qui contient tous Ics points) et les relations appel6es diagonales d’arite 2, qui traduisent le pr6dicat d’6galit6: p est dans d,.!, si r!t, seulement si px = py. 0 est la seule relation de largeur 0 (1 est do largeur l!).

Sur les relations sont definies les operations suivantes : Changenrent de variable. Soit e une application de X dans Y ; A une relation r de support X on associe la rela- tion rp de support Y d6finie par F(q) = r(q o e). On pourra appeler rdduitc: de r unc relation de la forme V . Conjonction. Soit ri un ensemble de relations, et soit X un dc leurs supports communs; o r i est d6finie par la X-relation intersection de celles qui definissent les Ti. Suivant les conventions habituelles, la conjonction portant sur I’ensemble vide vaut 1. Projection. gYr est la plus petite relation de support Y qui aontient I , . Ainsi, si X est un support de r contenant Y , un X-point p est dans 3% H i et seulement si y [ Y a un prolongement dans r. Dans la notation 3>’, Y d6signe 10s variables que l’on gsrde; les variables quantifi6es sont celles de x’ - Y.

I1 est clair qu’une intersection de classes de relations closes par ccadjonction de 0, des diagonales u, changements de variables, conjonctions, projections est close pour oes m$mes opkrations, done qu’une classe R de relation posshde une ct%ture 3 pour ccs op6rations. On peut definir par induction sur un ordinal appele complexit6 la notion de /orm.de, et tout Blement de fi s’obtient alors A partir de R par application d’unc telle formule; il s’agira dans ce cadre de formules du premier ordre (on ne quantifie que des inciividus) mais infinitaires (aucun cardinal ne limite le nombre de variables

3*

36 BRUNO POIZAT

libres dans les formules, ni la taille des conjonctions) ; une formule p u t 6tre vue comme un arbre bien fond6 aux vcrtcxes duquel on a associe une operation, celle B effectuer lorsqu’on atteint ce vertexe ; toutes cerj notiom sont trop classiques pour ittre d6crites en detail ici.

Une fonction f de support I o g r e naturellement sur les I-uples de X-points, en posant par dhfinition: f ( . . ., p i , . . .) (2) = f ( . . ., p i ( x ) , . . .). Nous dirons que f stab!‘- lise la relation r si chaque fois qu’on prend des points tous da,ns r , leur image par f est aussi dans r ; en d’autres termes, f est un homomorphisme dc r’ dans r.

Soit A une algbbre de Post, et soit AA+ la classe des Blkments de A d’aritk au plus 1. Appelons saturie A(r) de r par A l’ensemble des points images d’un ensemble de points de r par une fonction de A ; r est inclue dans A(r) puisque A contient les selecteurs. Si r est de largeur 1, le sature de r s’obtient par application uniquement d’B16ments de Al+ . On v6rifiera sans peine les deux lemmes suivant :

Lemme 3. Pour que la fonction f stabilise la relation r de largeur 1, il suffit (et il faut) que sea riduites d’aritk au plus 1 stabilisent T.

Lemme 4. Si A est une alg2bre de Post, r est stahilkke par chaque fonction de A s i et Reulement s i A ( r ) = r.

111. La th6orie de Galois

Le lecteur perspicace aura remarque que si R est une classe de relations, Ies fonc- tions qui stabilisent chaque element de R forment une algbbre de Post, et que si E’ cst une famille de fonctions, la classe des relations stabilisbes par chaque fonction de P est, close pour les opkrations d6finios dans la pr6cBdente section. C’est la reciproque clc ces assertions que nous d o n s maintenant Btablir: une algbbre de Post A est cxacte- ment 1% classe des fonctions stabilisant chnque relation stabilisee par tout Bli.ment, dc d (Proposit>ion 3), et une classe R de relations close pour les opkrations en question est, cxactenient la classe des relations stabilisBes par toutes les fonctions qui stabiliscnt chnque Blkment de R (Proposition 4).

Ainsi on voit que In correspondance, dite correspondance galoisienne, qui B une algkBre de Post A associe la classe R des relations stabilisees par chaque element de A est une. hijection cntre Ics a.lg8bres de Post et les classes closes de relations. C’est la le rBsultat. fondaniental de cette uth6orie de Galois,. Dam le corollaire 3, on se reatreint A n’utiliser qu’un ensemble fixe de vsria.bles, ainsi que dims le corollaire 4, oil cert,ains t,ypcs de disjonctions sont autorisks.

Propos i t ion 3. Soit A une alg2bre de Post; pour tout cardinal 1, il existe une rela- tion r stabilisie par tout iliment de A , d’ariti au plus PA, telle que toufe fonetion d’aritP au plus 1 qui stabilise r soit dam A .

DBmonstrat ion. Soit el la relation de largeur 1 et d’aritk PA, ainsi dbfinie (A un changement bijectif prbs du nom des variables): dans sa matrice, chaque colonne de longueur 1 occure une fois et une seule. A(el) est la relation r desirke. 0

Propos i t i on 4. Xoit R une famille de relations, et soit A l’algdbre de Post des /om- tions stabilisant chaque CEment de R ; soit c une relation d’ariti 01 et de largeur 1 + 0 (c’est-&-dire r + 0); la saturke A(r) de r par A s’ol!tient, d partir des re‘duite.9 d’ardti au

T H ~ O R I E I)E GALOIS POUR I,ES ALCBBRES DE POST INPINITAIRES 37

p l w /IA des dldments de II et des diagonales, par une f o m d e utilisant changemenfa &?

vcwiabh, conjonctions et projections, et qui ne fait intervenir que sup(&, ,!?’) variables.

Dbmons t r a t ion : lo) Calculons tout d’abord A ( @ A ) ; soit X , 1x1 = PA, le support minimal de cette relation; je dis que A(pA) = nrr l’interscction portant sur toutes lcs r6duites d’616ments de R de support X qui contiennent Q’. En effet, il est tout d’abord clair quc comme el c nt-7 et que A stabilise chaque r i , A(@*) c n r : ; prenonfi maintenant un X-point p du second membre, e t consid6rons une Bnum6ration des points (c’est- 8-dire des lignes) de e l , soit p , , . . . , p i , , . .: comme toutes les colonnes de ei sont distinctes, il existe une fonction f d’aritk au plus 1 telle que f (p , , . . ., p i , . . .) = p (et, cctte fonction f est m6me unique puisque toutes les colonnes possible se trouvent dam el) . Nous allons montrer que f est dans A , ce qui nous donne bien l’hgalitk; d6sirt5e; supposons donc que f n’est pas dans A , c’est-A-dire qu’elle ne stabilise pas une certaine relation r de R ; on a donc qo, . . . , q j , . . . E T , mais f (qO, . . . , q,i, . . .) # r ; dhfinissons MIL’ Ic support Y de r la relation d’equivalence suivant’e: y N y‘ si qj(y) = q j ( y ’ ) pour tout j, et rt5duisons r par l’application canonique e de Y sur son quotient Z par cette Bquivalence. On remarquera que toutes les colonnes de rp sont distinctes, et comme on les trouve toutes dans e l , on peut, quitte B faire un nouveau changcment de variable, supposer que Z c X et que rp est la projection de en sur 2, donc c rl’; et par con- sequent p , , . . . , p i , . . , E r e , mais p = /@,, . . . , p i , . . .) # r e (regarder leu coordonnkes Rur Z!) , ce qui est contraire it la dCfinition de p .

2,) Soit maintenant r d’aritt5 LX et de Iargeur I ; soit X un support de r de cardinal (Y,

ot soit Y c X tel que sur Y chaque colonne de la matrice de r se trouve une fois et une seule; r est de la forme r = ( 3 y p l ) n no&,, et A(r) = (jYA(e2)) n nd,. 0

< a . TI y a correspondance yaloisienne bijective entre lee a-alghbres de Post, et les ensembles de relations d’aritd stricte- ment infdrieure Ci LY, contenant 0, les diagonales, et clos pour les formules utilisant change- ment de variables, conjonctions et projections, et qui font intervenir strictement w i n s de or variables.

Corol la i re 3 . Soit bi un cardinal tel que s i y < a,

Clair a partir des deux propositions pr6ct5dentes.

lntroduisons maintenant la definition suivante : une classe ri de relations est ditu A-filtrante si tout ensemble de moins dc I de ces relations est contenu da.ns l’une d’entre ellcs ; pour une telle famille, toute fonction d’arite strictement inf6rieure & I qui stabilise cha.que ri stabilise aussi leur disjonction (op6ration correspondant la r6union); e t si I = 2 ou cst infini rbgulier, et si A est une I-alg8bre de Post, toute relation stablc par A est disjonction de la famille I-filtrante des A ( @ ) , e parcourant l’ensemble des sous-relations de r de largeur strictement inf6rieure it I. D’oh le corollaire:

Corol la i re 4. A’upposons que 1 = 2 ou soit infini rtgulier, et que pour tout p < 1, fi’‘ < o r ; il y a alors correspondance galoisienne bijective entre les il-alg&bres de Post, et les ensembles de relations d’aritd strictement infdrieure CE bi, contenant 0, lee diagonales, et cdos pour les forinules utilisant changements de variables, projections, conjonctions, di.sjoncti0n.s sur les ensembles 1-filtranta, qui font intervenir strictement moins de a variables.

Remarques . lo) Le corollaire 3, avec ,9 fini, LY = w, est le r6sultat de L. A. KALUZHNIN 11). Les formules considBr6es sont dans ce cas finies (dans La,@) car uno coiijonction non redo11dihntl! dc rclutions de base B finie, de support X fini, cst finie!

38 BRUNO POIZAT

P) Lt) corollaire 4, avec 1 = 2, cx > /I, t:stz du a h1. KRASNER. [3]; il dtablit line c‘or- rcspondance galoisienne bijective entre les derni-groupes d’applications ctc B d i m s R (pi contimnent l’aplication identique et les ensemble de X-relations, oii 1x1 2 [,!I[, contena.nt 0, les diagonales, et 010s par changements de variables, projections, con- jonctions, disjonctions. L’introduction de ((changements de variables ghn6ralis6s D h i permet d’6viter l’emploi de l’axiome du choix.

3”) Ck mdme corollaire pour il = w a 6th Btabli par I. ROSENBEIW [lo].

P) 011 peut aussi en donner une version du type du theoreme de I>. SCOTT / I 1 I: Si @ = w , et si r i est un ensemble de relations d’ariti! finie, A &ant I’w-alghbre de Post des fonctions d’arit6 finie qui stabilisent chaque ri (mais bien siir t’outes les w-algkbrcs de Post ne sont pas de ce type), toute relation d’arit6 finie stabilisee par chaque fonc- tion de A s’ohtient it partir des T i par une formule de Lml,m avec changements de varia- bles, projections, conjonctions, disjonctions sur .les familles w-filtrantes (dans Lm1+, on autorise conjonctions et disjonctions denombrables it condition qu’elles ne produisent que des formules n’ayant qu’un nombre fini de variables libres).

5”) Soit N I’alghbre de Post formee des fonctions d’arit6 0 ou 1; d’aprks lo coroll~.irc 4 RVOC L = 2, les t~elntions stabilisBes par X sont les disjonctions de conjonctions do diagonales, qui sont aussi les conjonctions de disjonctions de diagonales. Donc d’aprks la proposition 4, si ri est un ensemble de relations de support X , avec 1x1 = IY , UI.; H’obtient k partir des 1’; et de certaines disjonctions de diagonales par une formule utilisant cha,ngements de variables, projections et conjonctions, qui ne fait intervenir que variables: Si on dispose de suffisament de variables, on peut SR contenter dc faire porter les disjonctions sur Ies diagonales! Ce rksultat est d’ailleurs Bvident; par exemple si r et r‘ sont deux relations una,ires non-vides, r ( x ) u r ’(z) n’est autre quc

Un resultat du meme type, mais moins trivial, qui utilise un Icmmc ctc? 8 . 13. YABLONSKII [14J (voir la cinquihme partie), est prouv6 dam [l]: Si j3 est fini et strict,c- ment sup6rieur B 2, et si r est d’arit6 finie, i r (negation de r ) s’exprime it partir de r par une formule finie it partir de r , $,,, id , iy yui n’utilise que changements de variables, projections et conjonctions.

(Y) ( r ( y ) A r ( z ) A (& u &)).

IV. ThBorCmcx t l e dBfinissabilit*d glotmn

Un thBor&me bien eonnu de L. SVENoNlUs [121 iIffirInr qu’btant d o n n t h unc rola- tion r d’arit6 finie et un cnsemble R de relations d’arit6 finie definies sur un ensemble h!, 4 r n’cst pas definissable par une formule finie (en i , A, 3) it partir de R , alors il existo unc extension 616mentaire (M’ , R’, T ’ ) de la structure ( N , R, r ) avec une bijcction (r

dc M sur hi-m6me qui prdserve chaque Bl6ment de R’ et pas r‘. On peut consid6rc.r CP resultat comme la ccversion globale, du thdorkme de M. KRASNER [21: Dans I t s

ecas local*, on ne considere qu’une seule structure et la preservation par les auto- rnorphismes de cette structure, mais on est beaucoup plus liberal quant A la notion de formule; dans le cas global au contraire, on cxige des formuleh finks, mais on c~xamint~ aussi les extensions Blementaires de la structure consider6e.

Voioi la version globale de I’ccEndoth6orie de Galois abqtruiteo (voir 141; il y u une crreur dais la ddmonstration du th6orhme 3, gui est cepcndant correct) :

THiOltIE UEOALOIS POUR LBS ALGkBlWS DE POST 1NFINITAIBES 39

Propos i t i on 5. A%kl/t r une relation d’ai it(: / ; i i ; v , tC u n ensmnble de relations d’aritd f i tLir , dhfinies sur un rmemhle M , telles que r ne soit pas ddfinissable a partir de R par une formule finie e n v, A, 3. Alors il existe une extension Clkmentaire (ill’, R‘, r’) de ( M , R, r ) avec un endomorphisme de ( M , R’) qui ne stabilise pas r‘.

DBmonst ra t ion . Par compacit6 on se ranihnc au cas oh ( M , R ) est denombrnble; soit (Ml, R,, rl ) une ultrapuissance de ( M , R, r ) par un ultrafiltre o,-incompletj; on sait qu’une telle structure est o- (et mame q-) saturde. Par hypothkse, dans M , , il cxiste un uple ti, et un uple h satisfaisant tous les 6nonc6s en V, A, 3 de la structure ( M I , 12,) vrais pour 6, avec 6 E r, , h # r, ; introduisons des prBdicats auxilliaires f p ( x l , . . , , X I , , yl, . . ., y/,) que nous intcrpretons dans M , par utout BnoncB en v, A, 3 de la strixcture ( M l , R,) vrai pour i i h x l h . . l’est aussi pour h”y,^. . . “ y p . Cette structure enrichie satisfait :

(V-5 9 * . , x,, > J++l, 91 9 . . ’ 9,)) ($/,,+l) (f,,(% 7 . . * 9 x/, > Y1’ . . . , Yp) +

-+ f)’+l(XI > . . . ’ X p t 1 3 73,’ . ’ . 9 Yp+d) ;

prcnons alors unc restriction d6mcntaire dhmbrab le , contenunt M , ii et 6, (M‘, H‘, r’, fi, . . ., fi,, . . .) de ccttc structure enrichie; il suffit d’6num6rer M’ suivant lc type d’ordre (1) pour coristruire 6. partir des /;, un endomorphisme de (M’ , R’) yni wvoic ti sur 6. La version globalc dc la th6orie do Galois des alghbres de Post souleve moins d’en-

thousiasme. Introduisons une definition: je dis qu’un ensemble P de parties de E’ recouvre h i m E si pour tout entier n il existe un sous-ensemble fini P,l de P tel quc toutc partie B n C-lBrncnts do E wit contenue dans au moins un Blhmont de P I , . J e dirsi yue le bon recouvrcment cst trivial s i E lui mbme est dtlns la famille P ; c’est le seul cas possible si E est fini. I1 est clair que si r est hien recouverte par les r ; , toute fonc- tion d’arit6 finie qui stahilise chacun des r , stabilihe aussi r ; on reniarquera que cettc notion sc conserve par extonsion BlBmentaire.

P ropos i t i on 6. Soient r une relation d’aritd finie, R un rns~n7,ble de relations d’aritk finie, ddjinies sur un Pnsernhle M , telles que r ne soit pas. bien recouverte par dev relatione dPfinissables d partir des dldments de R par des formulev finies en A, 3. Alors il existe m e extension kldmentaire ( M ’ , R‘, r‘) de ( M , R, r ) et une fonctioa d’aritk finie, de base N’ qui stnbilise chaque tlkment de R‘ et pas r’.

DBmonstrat ion. H i r est de base M , on dt5finit airisi r ’ l l de base M I ’ : un uple satis- fait rtl si et sculc~ment si chacun de ses uples de coordonnees satisfait r. Cctte cor- respondance commute avcc les formules en A, 3, et l’hypothkse du theorhme ne signifio k n d’autre yue pour un ccrtain n on n’obtient pas r” ii partir deR r:, oh ri E R, par IIIW formule en v, A, 3. On reprend alors la d6monstration prBc6dente L partir de M I , cn choisissant la restriction de l’ultrapuissance de la forme M‘II, oh ill‘ est extension dl6mentaire de M ; on a donc une fonction f do M‘II dans M’ll qui stabilisc chaque ~2 v t pTq r’ll; en compohcint oattc. fonction avec les projections de iWll HUT- a!‘, on obtient 1~

fonctions de M’I4 dans dl’ qui stabilisent toutes tous leu r: et dont une au inoins tit:

stahilise pas r’.

\’oici uii exernplc dr Lon recouvrcment non trivial : ConsidBrons UII cnsembic A forin6 d‘616mcntn mIl index6 par l’enscmble e deb cnticrs relatifb, un ensembk h’, disjoirih clv A. fornid d’d6iiicnt~s b,, iildcx6s par Z priv0 dc 0, et un msc:niblc G, disjoint de A

et H, folnii. d’6lhcnts (I,) indrx6s par %. Sur 111 r h n i o n dp ces trois ciisemble, on con- sidBrc. la relation binitire r composk dc tous les couples (a,,, a,,+1), cle tous les couples (c,, , c , , + ~ ) , et dc tous les couples (a,,, b,,) pour n + 0.

Les forinules (3x1) . . . ( 3 ~ ~ ) ( r ( z , x l ) A r ( x l , x2) . . . A r(xs-, , .cs) A B ( x s ) ) forment UII hon r~~couvrement d~ A ( x ) . Cependant A n’est pas d0finissable A pitrtir do r ct U par urir formule en 3 et A. En effet la fonctioii suivante, d’aritC o, stabilise B ct r mais piis A : Soit X un ensemble de variables xIl index6es par 2, et posons f ( . . ., x -,,, . . ., xo, x l . . . . , c,, , . . .) = x~,, sauf s’il existe une entier relatif m tel que pour tout n x,, = a,,+,,,, auquel cas on pose f(. . ., r-,,, . . ., xu, . . ., L , ~ , . . .) = c,,,.

V. Rigiditd

Nous consid6rons maintrnant le probl8me auivant : Trouver dea relations d’aritb. la plus pctite possible, qui soient stabilis6es par le rnoins de fonctions possibles. Une relation r est dite A-rigide si les seules fonctions d’arit6 strictement infkrieure a 1 qui stabilinent r sont les projecteurs; r est dite absolurnent rigide ni ello n’est stahilistk que par les projecteurs; nous allons voir que I’existence de tclles relations d6peiid do l’hypo- tli8se du cardinal mesurable.

L’existence de relations binaires 2-rigides, c’est-&-dire sans cndomorphisnios autres que l’identit6, a 6t6 prouv6e dam 1131; celle de relations co-rigides d’arit6 3 si B = 2, d’arit6 2 si -= 2, dans [9]; les resultats qui vont suivre ont Bt6 annonchs dans 151.

Supposons ,9 fini; A tout ultrafiltre di de parties de X , on associe la fonction @( ) qui donne ail point p I’unique valeur a telle que { x / p x = a> soit dans di; les s6lecteurs correspondent aux ultrafiltres principaux ; on verifiera que ces fonctions-ultrafiltre forment une algebre de Post, qui n’est pas sans rappeler celle que now avons con- sid6r6e dans la premiere partie (sur la base 2).

Rappelons qu’un ultrafiltre eHt dit n-complrt s’il est c l o ~ pour les interseations portant sur strictement moins de a parties de X ; que si a > CD, et s’il existe un ultra- filtre non principal or-complet de parties de X , le cardinal de X est dit a-mesurable; yue I’affirmation de I’existence d’un ultrafiltre non principal o,-complet est connue sous le nom d’hgpothbe d’ULAM ou du cardinal mesurable. Dam le cas g6n6ra1, on d6finit l’algbbre de Post des fonctions-ultrafiltre-/?+ -wmplet .

J e laisxe au lecteur le plaisir de d6montlrer les deux lemmes suivant :

Lerrime 5. U n ensemble 0, de parties de X est un ultrafiltre a+-complet, 00 K 2 3,

(i) your toute partition de X en iy errsernbles deux d deux disjoints, l’un uu rnoins eut

(ii) l’intersection de deux ildments de @ n’est jawt,ais vide.

t e m m e 6. Un ensemble @ de parties de X est un ultrafiltrr s i et seulenzent si:

(i) pour toute partie Y de X , Y o u son compldment est dans di, (u) l’intersection de trois dl8ments de @ n’est jamais vide.

s i et seulement s i :

dam di,

THEOSIE DE GALOlS POUR LES ALGEBRES DE POST INFINITAIRPS 41

J’appellerai pseudo-ultrafiltre tout ensemble !P de parties de X tel que pour tout Y c X , Y ou son complement est dans Y, et tel que l’intersection de deux Blements de V nc? soit) jamais vidc; par exemple, si X cst fini do cardinal impair, lcs parties cie cardinal supdrieur B celui de leur complement constituent un pseudo-ultrafiltre. Au pseudo-ultrafiltres est associBe une algebre de Post sur la base 2 (fonctions monotones autodualeb dans la classification de Post).

Propos i t ion 7. Si 01 2 3, ou si LX 2 2 et ,!I 2 3 , l’algbbre de Post des lordions sta- bilisant toutes les relations d’arith au plus 01 est celle des fonctions-ultrafiltre-sup(&, b)+- complet. L’algdbre de Post des fonctions stabilisant toutes les relations binaires de base 2 ost celle des fonctions-pseudo-ultrafiltre.

DCmonstrat ion. Soit f une fonction de support X ; pour tout X-point p , posons X J f ) = p - I ( f ( p ) ) ; pour toute partition de X en sous-ensembles disjoints, I’un d’entre eux au inoins est de la forme X, ( f ) ; et pour que f stabilise toutes les relations d’arit,B au plus CX, il faut et il suffit que l’intersection d’au plus LX onsembles de la forme X,(/) svit toujours non-vide. La conclusion vient alors des lemmes. 0

Corol la i re 5 . Xi ,!I est fini, toute relation d’aritd finie est stabilisde par des /onctz’orby d’aritk arbitrairement grande.

Demonst ra t ion . Soit X un ensemble infini de cardinal A, et @ un ultrafiltre de parties de X compose d’BMments de cardinal A, c’est-&-dire contenant le filtre des parties de X dont le compl6ment est de cardinal strictement inferieur ci A ; la fonction associ6e B @ est d’arit6 1 et stabilise toutes les relations d’arit6 finie. 0

On remarquera que si /? 2 3, les fonctions-ultrafiltre-Bf -complet sont caracthisees par le fait que pour tout couple de points p , p’, X , n XI,, + 0.

Propos i t ion 8. X i B 2 3 , toute fonction qui stabilise -i&, et dont la rkduite unaire est l’identitk, est une fonction-ultrafiltre-/?+ -complet.

DBmonstrat ion. Soit f une telle fonction, de support X ; je dis tout d’abord que pour tout point p l’ensemble X , est non vide: en effet, comme la rBduite unaire de f vaut l’identite, le point constant q, tel que qx = f ( p ) , a f ( p ) pour image par f , et comme f stabilise i d z y , il faut bien que p prenne la valeur f ( p ) .

Soient p’ et p” deux points; posons a’ = f (p‘) , a” = f (p“) , X’ = X, , , , X” = X,,,,, Y = X - (X‘ w X”); nous cherchons B montrer que X’ n x“ + fl; soit b une valeur distincte de a’ comme de a”. Le point valant b sur X‘ et a’ en dehors a pour image b ou a’, mais en fait b car f stabilise i d z u , et pour la meme raison le point q’ valant a’ sur X’ et b en dehors a pour image a’, et Xqe = X ’ ; de m6me le point q“ valant a” sur X” et b en dehors a pour image a” et Xqrt = X”. Nous avons remplacb les deux points originaux par des points constants sur X’ , X“, Y et qui ne prenncnt quc deux ou trois valeurs; or, comme X , n’est jamais vide, pour tout B c B, la restriction f’ de f B BrX prend ses valeurs dans B’, et est donc une fonction de base B‘: il suffit de fiiire la verification pour les fonctions d’aritB au plus 3 et de base 3.

unaire est surjective (donc bijective) est d’aritt! 1.

f 3 0-l est une fonction-ultrafiltre d’arit6 finie, donc d’arit0 1. 0

Corol la i rc 6. Si ,!I 2 3, toute fonction d’aritt! finie qui stabilise i d L 7 , et dont la rkduite

Ddmonst r a t ion . Soit u la reduite unaire dc f ; tl’apr&s la ~)r~position prBcEdentn

42 BRUNO 1’01ZAT

Pour ,!? fini (dans ce C R R il est) inutile de preciser quc la r6duite unuirc cst surjective, puisqu’elle est injective!) ce rksultat est celui de S. B. YABLONSKII [1.41. On voit qu’en gBnBral une fonction satisfaisant les hypotheses du corollaire et. d’aritb. supkrieurc h 1 doit avoir une arit6 B+-mesurable.

Propos i t ion 9. I1 existe une relation qui n’est stabilisie que par les fonctions-ultra.- filtre-,!I+-compEet, d’aritk 3 si ,!I = 2, d’aritd 2 si 2 3. Cette relation est donc w-rigide si ,!I est fini, pa-rigide, oic ,up est le premier cardinal ,!I+-mesurable, si /? est in,fini.

J e suppose que t!l est infini, le cas ou B est, fini &ant trait6 par I. ROSENBERG dans [9]. Comme une relation binaire r 2-rigide doit Qtre antireflexive, je la considere commo un gra,phe orient6, et je dis ccil y a une flQche de a vers be au lieu de (a, b ) E r .

Lemme 7 . I1 existe une relation binaire r , sur une base de cardinal /?, telle que i d l , ! ! s’exprime cornme (32) (r(x , z ) A r (z , y ) ) (z et 9 sont diffdrents si et seulement si il existe z avec une fldche de x vers z et une fldche de z vers y), et telle que par toute ar&te pmsent au plus deux cycles (orient&) d’ordre 3 .

DBmonstrat ion. Partageons la base B en Q parties deux i deux disjoint)es, t>outos do cardinal p, B,, , B,, . . . , B,, , . . . ’ et posons A,, = B, u . . . u B,&; dBfinivsons par rdcurrence la trace de r sur A,, par les conditions suivantes: Pas de fleches entre 616- ments de A, . Supposons avoir d6fini 1’ sur A,, , et considkrons une bijection i l l+, cntre les couples (2, y) tels que x E A,,-, et y E B,,, ou x E B,, y E B,,, x y , d’une part, et les Bldments de d’autre part. Alors au niveau n + 1, on ajoute une fleche de x vers i,,+l((xp y)) et une flQche dc if,+,((z, y)) vers y. Montrons quc r ainsi construit,e a bien IR propri6tB demandke; appelons indice d’un kl6ment de B celui du B,, dans 1equr.l il git ; deux BlBments a et b ne peuvent Btrc relies par une flQche que s’ils sont d’indices diffbrents; Hi b est d’indice n supbrieur L celui de a, et s’il y a une flQche de a vws b, c’est que b est de la forme i , ,((a, d ) ) , et s’il y a une flQche de b vers a, c’est que b cst do la forme ili((att, a ) ) : il n’y a donc jamais simultankment une fl6che dc a vers 0 o t une flkhe de b vers a. Par consequent i&!, a bien la forme voulue.

Soicnt maintenant a et 6 avec une flQche de a vers b, et supposons que I’indice ‘IL

de b soit supBrieur A celui de a ; nous cherchons Q completer cette ar6te en un triangle orient6: il n’y a qu’un seul c d’indice supbrieur Q n qui convienne, c’est i f ,+ , ( ( [ ) , a)); ct s’il existe un c d’indice inferieur i n, il n’y en a qu‘un car alors b = &((a, c ) ) . Bi maintenant I’indice m de a cut suptkieur Q celui de b, il n’y a qu’un c d’indico superieur Q m qui convienno, c’est i I f ,+ , ( (b , a)), et il y en a au plus un d’indice inferieur i 111, car alors a = if, ,((c, 11)). Donc par toute arQte pawent au plus deux %cycles. 0

Revenons maintenant h la dCmonstration dc la proposition 9. ConsidBrons mainte- iiant B cornme form6 de deux parties B, et B, disjointes de cardinal ,!I, plus deux 616- ments que nous notons 0 et 1. Sur B,, mettons une copie r1 de la relation definie dam [13] : c’est une relation 2-rigide (sans endomorphismes autres que l’identitb), extraitc du bon ordre p + 2, qui n’a donc pas de cycles, en part’iculier pas de cycles d’ordre 2 ou 3. Sur B,, on met un exemplaire r2 de la relation du lemme 7. Ensuite on consi- dere une bijection i entre les couples d’B16ments distincts de B, et 10s Blhents de B,, ct 011 ajoute uno fldche de x vers i((z, y)) et une fl6che de , i ( (x , y)) vers y; enfin mcttons une fl6che de tout Blement de B, vers 0, uno f lkhe de 0 vers tout 61bment. dc B,, unt: f lhhe de tout 616mont do B, vers 1, line flhho de 1 vers tout BIBmcnt dc B, unc fldchc rlc: 0 vcrs 1. Jc dis quo l i ~ rolatioii I t ;l,itisi obtviiuc i~ la prupri6t6 do rigidit6 t1Ositi.o.

THhORIE DE CALOIS POUR L ES AT,GkBEES DE POST 1NFINlTAIHES 43

Soit f une fonction stabilisant R; elle stabilise aussi i d , , , , qui n’est autre quo (32) (R( z , z ) A R(x, y ) ) . Sa reduitc unairc g est donc injective. Cherchons les ar&es dc I2 p m lesquelles passent au moins quatre triangles: elle ne sont pas du type BIB, car par celles-ci passent au plus un triangle, le troisikme sommet &ant dans B,; ni du type BzB,, car par une telle ardte ne peuvent passer qu’au plus deux triangles ii troisihme sommet dans B,, et Oventuellement un seul B troisikme sommet dans B, (qui doit Ctre ti la fois projection de gauche de l’image rOciproque par i du premier et projection de droite de I’image r6ciproque par i du second). Donc ces fldohes sont celles de la forinc 01, IB,, B,O, plus certaines de la forme BIBz, B,B,; appelons 172’ la relation d6finic par cot ensemble de flcchea; coinme 9 cst injective, elle stabilise R‘; 01 est la seulo ardte par oh passent au moins deux triangles de R‘, donc g fixe 0 et 1. g stabilise B,, ensemble des BlBments b droite de 1 pour 172, donc g stabilise r lr restriction de €2 L B,, et vaut par consequent l’identit6 sur cet ensemble; mais g fixe Bgalement tout 616mcnt de B,, qui est de la forme i ( (a , b ) ) , car c’est le seul BlOment ii droite de a et B gauche de b et de 1. Done g est l’identitk, et d’apr8s la proposition 8, f est une fonction-ultrafiltrc-p+-complet.

Propos i t ion 10. A% est fini, il exivte u n e rrlrrfion d’arith d6noncbmhlP p i n’est stabiliske p e par les ultrafiltres co,-com,plet,v.

D6monst ra t ion . Si ds est un ultrafiltre w,-incomplet, on peut trouver X , , . . ., X , , , . . . dans lo filtre dont l’intersection est vide; les points p,, valant 0 sur X,, et 1 cn dehors ont tous pour image par @( ) 0 (0 et 1 sont deux valeurs dans B), et par cons6qucnt cctte fonction ne stabilise pas la relation d’aritO dhornbrable comprenant tous les points sauf le point comtant 0000000. . . La concaMnde dc cctte dcrnikrc relation avec une relation d’arit6 finie o-rigide convicnt.

En r6sum6, s i o n fait l’hypoth8se qu’il n’y rc pas de cardinal rriesumhle, on trouvo uncx relation absolument rigide d’arit6 2 si B est infini, d’arit6 denombrable si B cst fini.

R6ffBrences

111 BODNARCHUK, V. G., KALUZHNIN, L. A., KOTOV, V. N., and 13. A. ROMOV, Galois theory for

[2 ] KKASNRR, MARC, Sur line gdndralization de la notion de corps. J. Math. Pures Appl. 17 (1938),

131 KKAYNER, Maltc, Endothdorie de Galois abstraite. Congrks Intern. des Mathdrnaticiens, Yoscou

L41 Porz .~~ , BRUNO, Thborbmes globaux (de dkfinissabilitk). C. Id. Acad. Sci. Paris BHO (lY75),

[ 51 YOIZAT, BnrrNo, Une relation particdii.remerit rigid& C. It. Acad. Sci. h r i s ,I 289 (lY7G),

]ti] POST, EMII, L., Determination of all closed systems of t ru th t.tbles. 13ii11. Aiiicr. Math. So?. 26

17 1 POST, EMIL L., Introduction to a general theory of olomcntary propositions. Amcr. J. Mbhti.

[ X I POST, EMIL L., The two-valued iterative systcnis of rniitheniatical logic. Ann. of Math. Stud. 5,

I Y 1 Hosmwm(~, Tvo, Strongly rigid relations. Rocky Mount‘lins .J. of MtLth. 3 (1973), 631 - 639. [lo] ROSENBERG, Ivo, Une correspondence de CMois cntrc les rdg&res rtniversciles ct les rota tion8

dans le mbme univers. C. R. Awd. Rci. P‘I ri8 ,I 271) ( 11174). 5H I - hX2. 14 ‘1 BNO ( I975), (i I 5 - fj I(;.

PostJ algebras. Kibernetika 5 (1969), no 3, 1-10; 6 (lD69), no 5, 1-9.

367 -385.

1966; rdsurnds 2 (algbbre), p. 61.

845 - 847.

671 -673.

( 1 91 9/1920), 437.

48 (1921), 163 - 185.

Princetan 1941 - New York 1965.

44 XRUNO I’OIZAT

[ I 1 1 SCOTT, DANA, Logic with deniinicrably long formulas atid finitc strings of qwiitifiers. In: Tlit? Theory of Models (Proc. 1963 Internat. Sympos. Rerkely), No1 th-Holland, Amstcrdi~m 1966, p. 329-341.

I 121 SVENONIUS, LABS, A theorem on permiitntions in models. Theoria 25 (1959), 173- 178. [ 131 VOP~NKA, P., PIJLTR, A., and Z. HERDLIN, A rigid rolution exists on m y set. Comment. W a t l i .

L14] YABLONSKII, 8. B., Functional const,ruotions in Ic-vulued logic. Trudy Mat. lnst. Stelilov 51 Univ. Carolin. 6 (1965), 149- 155.

(1958), 5-142.

(Eingegangea mi 16. -4pril 1979)