Alguns aspectes actuals de lògica algebraica

ALGUNS ASPECTESACTUALS DE LOGICA ALGEBRAICA Josep Pla Facultat de MatemAtiques . Universitat de Barcelona . Pub . Mat . UAB Nó 12  Juny 1979 L'any 1955 Paul ft . 1UAL2 , 10S treu a °Com-)ositio Mathematicae, vo1 .12° llarticle "Algebraic Logic" en el que dóna una formalització al--ebraica del concepte de deducció . A llentorn dels anys seixanta 1'escola d'Antonio MONTE11ZO dóna unamateixa ?resentació algebraica de la lógica peró, en lloc de centrar la sevaatenció en la lógica booleana,debilita la gUestió al substrat positiude la lógica . La idea que hi la al dessotadlaquestapresentació és la se- --Uent . si pensem en el cálcul de proposicionsconstruit sobre un conjuntno buit X de lletres com en llálgebra lliure P(X) sobre X dIoperacions --1 i  (moniria, la , )rimera ; binária, la regona) tenim que, si x E X, aleshores x i -1-1 x són dues expressions diferents en P(X) . Aleshores cal introduir -i s'introdueix - una relació d'erluivaléncia en P(X) que identifiqui, d'acord amb el que nosaltres es-)erem del cálcul de proposicions,certes fórmules . El camí sintictic consisteixen donar el conce ; .)te de demos - tració : slagafen certes exlyressions distin-ides en P(X) V~ 1 = i ?--i(q->o), on p, qE P(X)~ i  ' ~~ 2 = (P--~(q~r))-~ .((' .~~7)--m(n-+r))~ on p,q,rC P(X)~1 Ci~ 3 =  - 1 "1 P --s P,  on  p E  P (X) Y  ; i una regla de deducció,anomenada %odus ponens " : M .P . 1 = ~ (P,P---> q,,]) : p,qE P(X)~V  (P-q,9,q) : P, q E . ~'(X)~ . Sfanomena teorema tota expressió 9 E P(X) tal 7ue existeix una successi6 finita dvexgressions -) 1 , . 2 2 a mb 1 .  p i F LA 1 v `A2 %J Lh 3) o bé talque 2 .  existeixen pi, pk (j,k < i) i (P j ,p k ,p i ) EL `t . n' Diem que una exgressió és un teorema usant el símbol :k- ? . Aquesta idea es pot -eneralitzar a qualsevolconjunt A Q P(X) i introduir els A-teoremes (Al --- p) .  Iiom considera els axiomes 4 (A) = A 1 V (A 2V 14 3 V A Diem que 0 =q  si,  i només si, b-  p -P . q  i  t-- q-,> p Es una relació dlequivaléncia i resulta que P(X)/` és una álgebra_ de Boole : l 1 51-ebra de Tarski-Lidenbaum . Semblantment,  p -A q  si,  i nomás si, A %. n -q i A1-q--> > 7 ; resulta que P(X)/ -~ A és també una álgebrade Boole . Es aquestordred'ideesel que recull 1'escola d'A . MONTEIRO (A . MONTEIRO [1960] ; 119711 ; Antonio DIEGO [19651 ;[1966] quandefineix les Algebresde Hilbert i les Preálgebres de Hilbert . Hom diu que una terna (A, .,D) és una preAlgebra de Hilbert si, i només si, PH 1 .  és una operació binaria en A ; PH 2 .  D G A ; PH 3 .  x .(y .x) E D, per cada parell x,y E A ; PH 4 .  (x .(y .z)) .((x .y) .(x .z» E . D, per  x,y,z E A ; PH 5 .  M . P . :  si x E D  i  x .yCD, aleshores yED . Es important dIobservar que la relació en A, x  .51i~ D y  si,  i només  si,  x .y e D és una relació de preordre - talcom passava en P(X) - i, per tant, tenim una relaciódlequivaléncia ° D LI .álgebra quocient, ja que - D és com,?atible amb dóna (A/=-= D y .PD) on . és una operació en A/== D ,  D E A/ -D  i  D és máxim en (A/-D>'3 --ZD ) . Aquest tipus dlestructuress'anomenen álgebres de Hilbert - i són la réplica de les álgebres de Boole quocient - i es caracteritzen Una terna (A, .,u), on . és una operació binária en A i u E A, és una álgebra de Hilbert si, i només si, AH l* .  La relació x G y si,  i només si,  x .y = u és una relaciód'ordre ; AH 2*  x .u=u ;  u .x=x ; AH 3 .  -(y -) = (- y) .(x .z) . Aquesta definició es troba en FrancescdIAssísSALES 01971), D'aquesta manera hem introduit de formanatural el concente d"álgebra de Hilbert, que podem pensar com llentalgebraic més ¡don¡ per a descriure la lógica proposicional positiva . En una álgebra de Hilbert (A, .,u) els sistemes deductius D sónels subconjunts D Q A tals que SD 1 .  u E D ; SD 2 .  x .y eD  i  x ED,aleshores y E D . Hom pot veure que .9 = { D . : D és un s .d . de (A, .,u)~ és un sistemaclausura - unacol .lecció de partsde A tancada per interseccionsarbitráries - que verifica : és finitari ; el teorema de la deducció de Tarski . Finitari :  x ~ D si, i només si, existeix unacol .lecció finita x 1 , . . .,x n dlelements de D i x E D(x1, . . .,xn) - s .d .  engendrat  per x 1 , . . . ,x n . Teorema de la deducció :  x E D(D,y) si, i només si, y .x 5r D, on D és un s . d .,  x,  y E A arbitra ris i D(D,y) és el s .d . engendrat per D i per y . En aquestordre dlidees slinsereixen els treballs de Helena RASI0LVA i Roman SIKORSKI . Veure H . Rasiowa D9701,119743 . Els sistemes deductius irreductibles serveixen per a donar una representació de Stone de les Algebres de Hilbert . Convéindicar - tan sols de passada - que les topologies que hom troba amb aquest tipus de representacions son topologies poc desitjables des dIun punt de vista topológic i de llanalis¡ . Un altre ordre dlidees (cf . Rasiowa, op .cit .) que hom pot plantejar-se un cop summergit en aquestAmbit és el queens planteja la segttent gUestió a partirdIunaoperació . de Hilbert, és possible d'alguna manera introduir operacionsreticularsen el conjunt ordenat (A, .,u)? (Pensem que en les Algebres de Boole, grácies a la complementació, podem, a partirde la implicació,definir les operacionsreticulars ; ara peró no disposem pas de negació .) Les Algebresde Abbott-Sales (Abbott [1970] ; F .A . Sales [1974) ; J .Pla t1977]) permetendefinir, a partir de ., un suprem per a cada dos elements . Cal indicar que aquestes Algebres tenen una particularitat curiosa i és : si tenen element mínim són Algebresde Boole ; i els seus sistemes deductius irreductibles, maximals i primerscoincideixen . Diem quI és una álgebra de Abbott-Sales : és una álgebra de Hilbert (A, .,u) talque (x .y) .y =(y .x) .x  (caracterització de Sales £19741) . Aleshores x V y = (x .y) .y  és un suprem en  (A, 9 ) . 24 Si agafem dlentrada un reticle (A, ^ , -/ u) i una operació binaria . en A talque (A, .,u) sigui una álgebra de Hilbert, obtenim els anomenats reticles de Hilbert (cf . Sales 119741 ; J .Pla [1977] ;[1978]) si l'ordre del reticle i llordreindult per . coincideixen . . (Si en lloc dIun reticle prenem un suprareticle obtenim els suprareticles de Hilb ert .) En aquest context hem pogut donar un tractament unitari de les Al-ebres de Abbott-Sales, de Heyting, de Boole . Totes elles són generalitzacionsreticulars del substrat eminentment 16gicde les álgebresde Hilbert . Hom demostra queels filtres de reticle de (A, ^ , v u) són sistemes deductius, que els sistemes deductius primers caincideixen amb els sistemesdeductius irreductibles i slobté, amb certes limitacions, una representació de Stonedlaquestes novesestructures16gic-algebraiques . Una gtiestió quehom pot plantejar encara en una álgebra de Hilbert (resp . en un reticle o en un suprareticle de Hilbert) és la qüestió de les negacions . Aix6 porta a introduir el concepte algebraic de negació en un conjuntordenat(resp . en un reticle, en un suprareticle) . Si (A,-_< ) és un conjuntordenat (cf . G .BODIOU L1964]), tota aplicació c : A ----- e  A talque N 1 .  x - y  implica  - L y < -c x  ;  N 2 .  x < L 2 x stanomenanegació . Una negació forta és tota negació que verifica Z 2x =x, per tot x E A .  Si A és un reticle, L és una negació reti - cular o de Mor an si és negació i,  a més :N 3 .  L (x n y) _ Tx v t y ;  z (x v y) = z x n Z y . (No cal pas que sigui forta, si bé tota negacióforta és reticular, si está definida en un reticle) . (Sobre qüestions generals de les negacions en reticles complets, cf . F . ESTEVA £19741) . Si portemaquestes idees a les Algebres de per a tot aaA, llaplicació Z : A  .-y A ax  , . .-~  - C a (x) =x .a és una negació .  Si - C a és Porta, A té mínim i a= mín que, De forma semblant hom pot analitzar en els reticles de Hilreticulars . Sibé Haskell CURRY en aquest sentitno coneixem fins en aquestalinia i, per tant, consoberta . que slinspira en la lógicaclássica, podem llígar les negacions ambels sistemes deductius via el concepte de con sisténcia . bert cóm són les negacions C19521realitzaun análisi avui cap treballexhaustiu titueix una qüestió Amplia Continuant en la semántica Hilbert veiem Fórainteressant efectuar, també en aquest sentit, di exhaustiu que, avui per avui, no s 1 ha pas fet . un estuUna altra idea desenvolupada per P .R . Halmos (op .cit .) i independentment per L .HENKIN-J .D .MONK-A .TARSK I [19711 i L .Menkin-A .Tarski [19601, [1961,), consisteixen . introduir en les álgebres de Boole operadors que, d'alguna manera,recullin la idea dels quantificadors . AixíHalmosconstrueix les A1eebres monádiques i H-M-Tconstrueixen les álgebres cilindriques . A .Monteiro recull aquestesidees en A .Monteiro ([1957] ; 11960] ; 11967] ; [1974]) i les aplica a estructures més febles comsón les Algebres de Heyting . No coneixem, per¿, cap treballde reticles de Hilbert monAdics,ni tampoc dlálgebres de Hilbert monádiques . La dificultat rau en el fet que per introduir els citats operadors hom utilitza les propietats reticulars i no coneixem cap treball en que stintrodueixin via 1'operació de Hilbert .(que és lloperacid de la lógica) . 26 Creiem que, en les álgebres de Abbott- .Sales,podríem perfectament introduiroperadors existencials o universals i obtindre álgebres de Abbott-Sales monádiques .  Hi estem treballant . Donem la idea de Halmosd'álgebramonádica . Sigui (A,^ , .i , - 1 ;0,u) una álgebra de Boole i sigui tal que E l .  -30=0 ;  E2 . .  x  x ;  E3 .  (x v -3 y) _  x v -3 y . En aquestes álgebres els sistemes deductius monádics sónels sistemes deductius tals que, si  9 x E D, aleshores x E D . Observem, de passada, que els axiomes de 1'operador -9 es donen a través de les operacionsreticulars i d'ordre . Convé dir, a fi d'ésser rigurosos, que, sibé les álgebres cilíndriques intenten algebritzar el cálcul de predicats i fan intervenir variables, les álgebres monádiques algebritzen les lógique s modals . Una segona via per a donarel concepte de lógica algebraica fou introduida1'any1930 per A .Tarski (cf .A .Tarski [1930]) i la idea expressada en aquest treball la podem descriure semánticament de la formasegüent "Donar una lógica equival a donar el conjunt de consegUancies de cada conjunt" . Formalment una lógica abstracta és una parella (A,C), on A ~ o i C :  (A)  ---% 9(A ) verifica C 1 .  Per tot X!52 A,  X 5i C(X) ; C 2 .  si x -Q Yc A,  C(X) c C(Y) ; C 3 .  si x Q A,  C(CM) = C(X) . L'operador Cs'anomena operador de consegtténcia . Realment A .Tarskiimposava dues restriccions :  Co . Card(A) :5x o 2 7 i C2 .  C(X) = U C(F), on F s!¡ X i F és finit (en lloc de (2)) . Aquesta definició de A .Tarski, si bé inspirada en el cAlcul de proposicions i correcta a llhora de formalitzar el cálcul de proposicions ; esdevémassarestrictiva ja que exclou, dlantuvi, les lógiquesinfinitáries cada copmés importants . Hem pogut veure (V .VERDO [19781) que la lógica probabilistica (en el sentit o - ) és una lógica infinitária . . Hem indicat ja, en el cas de les Algebres de Hilbert (reticles de Hilbert), que la col .lecció dels sistemes deductius és un sistema clausura i un teorema general de M . .WARD [1942] ensdiu que un sistemaclausura_C i un operador de conseqüéncia C és el mateix ; si fem I? =IX : C(X) =X  és C(X) = n ~Y : Y E )t' i Y 2 X ~ . Teoremes com el de Schmidt - diu :un operador C és finitari si, i només si, el seu sistemaclausura és fortament inductiu - i el de Pierce - diu : si C és finitari, els elefnents del sistemaclausura,~ irreductibles constitueixen unabase mínima de ~>- suggereixen la possibilitat de donarpropietats de C a travers del seu sistemaclausura associat . Una gUestióimportant quecal resoldre i en la que hem treballat (cf .J .Pla(197b1 ; V .Verdú 119781) consisteix en imposar co  20 )ns a C (a ;? ) per talque es verifiqui el teorema de la deducció de Tarski . Ara bé el teorema de la deducció de Tarski és un teorema intimament lligat amb lloperació i pot ocórrer que, en A, no es disposide cap operaci6 . . Quines condicions ha de satisfer, doncs, C (o,C) pertal de poder introduir en A una operaci6 . que ens permeti denunciar el teorema de la deducció : y E C(X,x)  si, i només si,  x .y E :C(X)  ? Les respostes donades per J .Pla i V .Verdú difereixen en el següent sentif, : 2 8 mentres que el primer dóna una condició que permet definir, en A directament, una operació . que verifica el teorema de la deducció, el segon fa la següentconstrucció Tot ogerador C permet de definir una relació d'equivaléncia induida per la relació cíe preordre x :!!5 Cy  .si,  i només si,  y E C(4x}) . Podemdonespassaral c ;uocient A/ == C i considerar 1'álgebra quocient (A/== C ,C), on Ces i es defineixde forma natural . AleshoresV .Verdúimposa condiciona a (A,C) deforma que, en (A,C), es verifiqui el teorema de la deducció . L'anteriorconsideració ens proporciona una una lógica (A,C) i una aplicaciócompatible projecciócanónica -M Sabem que - R és ment* per (X,!) si, i només si 6 : 9 (A/ - C ) , 9 (A/ :- C ) epijectiva, que i per - J1 i que C(x) =C(y) . lógica (A,C) , amb Ci C ; la (A,C) está generat projectiva - per tot x,  y E A,  71 (x) =Z1 (y) Aquesta ideaés la KO 119731 de forma morfisme bilógic . abstractes i h :A 1  -  A 2 és Di B 1 .  h és morfisme  (i .e .  h -1 (Y) E 11` í ,  per cada YE MB 2 .  h genera projectivament (A 1 ,C 1 ) a partir de que recullel treball de D .J .BROWN-R .SUSZgeneral quan introdueixel concepte de Si (A 1 ,C 1 ) i (A 2,C2 ) són dues álgebres una aplicació que verifica (A 2 ,C 2 ) i h (i .e . Je, =h -1 (Y) : Y E % 2 ) ; MB 3 .  h és epijectiva, direm que h és un morfisme bilógic entre (A 1 ,C 1 ) i (A 2 ,C 2 ) La importáncia real d'aquesta definició seunom - és la següent h és un morfisme bilógic si, i només si, - que justifica el entre (A 1 ,C 1 ) i(A 2 ,C 2 ) 29 WA:W , r1 . (1942) °The closureoperatorsof a lattices'l . Annals of rfath, 43,n°2,p .191-196 .