Alguns aspectes actuals de lògica algebraica

ALGUNS ASPECTESACTUALS DE LOGICA ALGEBRAICA Josep Pla Facul a de Ma emA iques . Uni e si a de Ba celona . Pub . Ma . UAB Nó 12  Juny 1979 L'any 1955 Paul . 1UAL2 , 10S eu a °Com-)osi io Ma hema icae, o1 .12° lla icle "Algeb aic Logic" en el que dóna una o - mali zació al--eb aica del concep e de deducció . A llen o n dels anys seixan a 1'escola d'An onio MONTE11ZO dóna unama- eixa ? esen ació algeb aica de la lógica pe ó, en lloc de cen a la se aa enció en la lógica booleana,debili a la gUes ió al subs a posi iude la lógica . La idea que hi la al desso adlaques ap esen ació és la se- --Uen . si pensem en el cálcul de p oposicionscons ui sob e un conjun no bui X de lle es com en llálgeb a lliu e P(X) sob e X dIope acions --1 i  (moni ia, la , ) ime a ; biná ia, la egona) enim que, si x E X, alesho es x i -1-1 x són dues exp essions di e en s en P(X) . Alesho es cal in o- dui -i s'in odueix - una elació d'e lui aléncia en P(X) que iden i iqui, d'aco d amb el que nosal es es-)e em del cálcul de p oposicions,ce es ó mules . El camí sin ic ic consis eixen dona el conce ; .) e de demos - ació : slaga en ce es exly essions dis in-ides en P(X) V~ 1 = i ?--i(q->o), on p, qE P(X)~ i  ' ~~ 2 = (P--~(q~ ))-~ .((' .~~7)--m(n-+ ))~ on p,q, C P(X)~1 Ci~ 3 =  - 1 "1 P --s P,  on  p E  P (X) Y  ; i una egla de deducció,anomenada %odus ponens " : M .P . 1 = ~ (P,P---> q,,]) : p,qE P(X)~V  (P-q,9,q) : P, q E . ~'(X)~ . S anomena eo ema o a exp essió 9 E P(X) al 7ue exis eix una successi6 ini a d exg essions -) 1 , . 2 2 a mb 1 .  p i F LA 1 `A2 %J Lh 3) o bé alque 2 .  exis eixen pi, pk (j,k < i) i (P j ,p k ,p i ) EL ` . n' Diem que una exg essió és un eo ema usan el símbol :k- ? . Aques a idea es po -ene ali za a qualse olconjun A Q P(X) i in odui els A- eo emes (Al --- p) .  Iiom conside a 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  -- q-,> p Es una elació dlequi aléncia i esul a que P(X)/` és una álgeb a_ de Boole : l 1 51-eb a de Ta ski-Lidenbaum . Semblan men ,  p -A q  si,  i nomás si, A %. n -q i A1-q--> > 7 ; esul a que P(X)/ -~ A és ambé una álgeb ade Boole . Es aques o d ed'ideesel que ecull 1'escola d'A . MONTEI- RO (A . MONTEIRO [1960] ; 119711 ; An onio DIEGO [19651 ;[1966] quande ineix les Algeb esde Hilbe i les P eálgeb es de Hilbe . Hom diu que una e na (A, .,D) és una p eAlgeb a de Hilbe si, i només si, PH 1 .  és una ope ació bina ia en A ; PH 2 .  D G A ; PH 3 .  x .(y .x) E D, pe cada pa ell x,y E A ; PH 4 .  (x .(y .z)) .((x .y) .(x .z» E . D, pe  x,y,z E A ; PH 5 .  M . P . :  si x E D  i  x .yC- D, alesho es yED . Es impo an dIobse a que la elació en A, x  .51i~ D y  si,  i només  si,  x .y e D és una elació de p eo d e - alcom passa a en P(X) - i, pe an , enim una elaciódlequi aléncia ° D LI .álgeb a quocien , ja que - D és com,?a ible amb dóna (A/=-= D y .PD) on . és una ope ació en A/== D ,  D E A/ -D  i  D és máxim en (A/-D>'3 --Z- D ) . Aques ipus dles uc u ess'anomenen álgeb es de Hilbe - i són la éplica de les álgeb es de Boole quocien - i es ca ac e i zen Una e na (A, .,u), on . és una ope ació biná ia en A i u E A, és una álgeb a de Hilbe si, i només si, AH l* .  La elació x G y si,  i només si,  x .y = u és una elaciód'o d e ; AH 2*  x .u=u ;  u .x=x ; AH 3 .  -(y -) = (- y) .(x .z) . Aques a de inició es oba en F ancescdIAssísSALES 01971), D'aques a mane a hem in odui de o mana u al el concen- e d"álgeb a de Hilbe , que podem pensa com llen algeb aic més ¡don¡ pe a desc iu e la lógica p oposicional posi i a . En una álgeb a de Hilbe (A, .,u) els sis emes deduc ius D sónels subconjun s D Q A als que SD 1 .  u E D ; SD 2 .  x .y e- D  i  x E- D,alesho es y E D . Hom po eu e que .9 = { D . : D és un s .d . de (A, .,u)~ és un sis emaclausu a - unacol .lecció de pa sde A ancada pe in e seccionsa bi á ies - que e i ica : és ini a i ; el eo ema de la deducció de Ta ski . Fini a i :  x ~ D si, i només si, exis eix unacol .lecció ini a x 1 , . . .,x n dlelemen s de D i x E D(x1, . . .,xn) - s .d .  engend a  pe x 1 , . . . ,x n . Teo ema de la deducció :  x E D(D,y) si, i només si, y .x 5 D, on D és un s . d .,  x,  y E A a bi a is i D(D,y) és el s .d . engend a pe D i pe y . En aques o d e dlidees slinse eixen els eballs de Helena RASI0LVA i Roman SIKORSKI . Veu e H . Rasiowa D9701,119743 . Els sis emes deduc ius i educ ibles se eixen pe a dona una ep esen ació de S one de les Algeb es de Hilbe . Con éindica - an sols de passada - que les opologies que hom oba amb aques ipus de ep esen acions son opologies poc desi jables des dIun pun de is a opológic i de llana- lis¡ . Un al e o d e dlidees (c . Rasiowa, op .ci .) que hom po plan eja -se un cop summe gi en aques Ambi és el queens plan eja la seg en gUes ió a pa i dIunaope ació . de Hilbe , és possible d'alguna mane a in odui ope acions e icula sen el conjun o de- na (A, .,u)? (Pensem que en les Algeb es de Boole, g ácies a la complemen ació, podem, a pa i de la implicació,de i- ni les ope acions e icula s ; a a pe ó no disposem pas de negació .) Les Algeb esde Abbo -Sales (Abbo [1970] ; F .A . Sales [1974) ; J .Pla 1977]) pe me ende ini , a pa i de ., un sup em pe a cada dos elemen s . Cal indica que aques es Algeb es enen una pa icula i a cu iosa i és : si enen elemen mínim són Algeb esde Boole ; i els seus sis emes deduc ius i e- duc ibles, maximals i p ime scoincideixen . Diem quI és una álgeb a de Abbo -Sales : és una álgeb a de Hilbe (A, .,u) alque (x .y) .y =(y .x) .x  (ca ac e i zació de Sales £19741) . Alesho es x V y = (x .y) .y  és un sup em en  (A, 9 ) . 24 Si aga em dlen ada un e icle (A, ^ , -/ u) i una ope ació bina ia . en A alque (A, .,u) sigui una álgeb a de Hilbe , ob enim els anomena s e icles de Hilbe (c . Sales 119741 ; J .Pla [1977] ;[1978]) si l'o d e del e icle i llo d eindul pe . coincideixen . . (Si en lloc dIun e icle p enem un su- p a e icle ob enim els sup a e icles de Hilb e .) En aques con ex hem pogu dona un ac amen uni a i de les Al-eb es de Abbo -Sales, de Hey ing, de Boole . To es elles són gene ali zacions e icula s del subs a eminen - men 16gicde les álgeb esde Hilbe . Hom demos a queels il es de e icle de (A, ^ , u) són sis emes deduc ius, que els sis emes deduc ius p ime s cain- cideixen amb els sis emesdeduc ius i educ ibles i slob é, amb ce es limi acions, una ep esen ació de S onedlaques- es no eses uc u es16gic-algeb aiques . Una g ies ió quehom po plan eja enca a en una álgeb a de Hilbe ( esp . en un e icle o en un sup a e icle de Hilbe ) és la qües ió de les negacions . Aix6 po a a in odui el concep e algeb aic de negació en un conjun o dena ( esp . en un e icle, en un sup a e icle) . Si (A,-_< ) és un conjun o dena (c . G .BODIOU L1964]), o a aplicació c : A ----- e  A alque N 1 .  x - y  implica  - L y < -c x  ;  N 2 .  x < L 2 x s anomenanegació . Una negació o a és o a negació que e i ica Z 2x =x, pe o x E A .  Si A és un e icle, L és una negació e i - cula o de Mo an si és negació i,  a més :N 3 .  L (x n y) _ Tx y ;  z (x y) = z x n Z y . (No cal pas que sigui o a, si bé o a negació o a és e- icula , si es á de inida en un e icle) . (Sob e qües ions gene als de les negacions en e icles comple s, c . F . ESTE- VA £19741) . Si po emaques es idees a les Algeb es de pe a o aaA, llaplicació Z : A  .-y A ax  , . .-~  - C a (x) =x .a és una negació .  Si - C a és Po a, A é mínim i a= mín que, De o ma semblan hom po anali za en els e icles de Hil- e icula s . Sibé Haskell CURRY en aques sen i no coneixem ins en aques alinia i, pe an , cons- obe a . que slinspi a en la lógicaclás- sica, podem llíga les negacions ambels sis emes deduc ius ia el concep e de con sis éncia . be cóm són les negacions C19521 eali zaun análisi a ui cap eballexhaus iu i ueix una qües ió Amplia Con inuan en la semán ica Hilbe eiem Fó ain e essan e ec ua , ambé en aques sen i , di exhaus iu que, a ui pe a ui, no s 1 ha pas e . un es u- Una al a idea desen olupada pe P .R . Halmos (op .ci .) i in- dependen men pe L .HENKIN-J .D .MONK-A .TARSK I [19711 i L .Men- kin-A .Ta ski [19601, [1961,), consis eixen . in odui en les álgeb es de Boole ope ado s que, d'alguna mane a, ecullin la idea dels quan i icado s . AixíHalmoscons ueix les A1- eeb es monádiques i H-M-Tcons ueixen les álgeb es cilind i- ques . A .Mon ei o ecull aques esidees en A .Mon ei o ([1957] ; 11960] ; 11967] ; [1974]) i les aplica a es uc u es més ebles comsón les Algeb es de Hey ing . No coneixem, pe ¿, cap e- ballde e icles de Hilbe monAdics,ni ampoc dlálgeb es de Hilbe monádiques . La di icul a au en el e que pe in odui els ci a s ope ado s hom u ili za les p opie a s e icula s i no coneixem cap eball en que s in odueixin ia 1'ope ació de Hilbe .(que és llope acid de la lógica) . 26 C eiem que, en les álgeb es de Abbo - .Sales,pod íem pe ec a- men in odui ope ado s exis encials o uni e sals i ob in- d e álgeb es de Abbo -Sales monádiques .  Hi es em eballan . Donem la idea de Halmosd'álgeb amonádica . Sigui (A,^ , .i , - 1 ;0,u) una álgeb a de Boole i sigui al que E l .  -30=0 ;  E2 . .  x  x ;  E3 .  (x -3 y) _  x -3 y . En aques es álgeb es els sis emes deduc ius monádics sónels sis emes deduc ius als que, si  9 x E D, alesho es x E D . Obse em, de passada, que els axiomes de 1'ope ado -9 es do- nen a a és de les ope acions e icula s i d'o d e . Con é di , a i d'ésse igu osos, que, sibé les álgeb es ci- línd iques in en en algeb i za el cálcul de p edica s i an in e eni a iables, les álgeb es monádiques algeb i zen les lógique s modals . Una segona ia pe a dona el concep e de lógica algeb aica ou in oduida1'any1930 pe A .Ta ski (c .A .Ta ski [1930]) i la idea exp essada en aques eball la podem desc iu e se- mán icamen de la o masegüen "Dona una lógica equi al a dona el conjun de consegUancies de cada conjun " . Fo malmen una lógica abs ac a és una pa ella (A,C), on A ~ o i C :  (A)  ---% 9(A ) e i ica C 1 .  Pe o 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'ope ado Cs'anomena ope ado de conseg éncia . Realmen A .Ta skiimposa a dues es iccions :  Co . Ca d(A) :5x o 2 7 i C2 .  C(X) = U C(F), on F s!¡ X i F és ini (en lloc de (2)) . Aques a de inició de A .Ta ski, si bé inspi ada en el cAlcul de p oposicions i co ec a a llho a de o mali za el cálcul de p oposicions ; esde émassa es ic i a ja que exclou, dlan- u i, les lógiquesin ini á ies cada copmés impo an s . Hem pogu eu e (V .VERDO [19781) que la lógica p obabilis ica (en el sen i o - ) és una lógica in ini á ia . . Hem indica ja, en el cas de les Algeb es de Hilbe ( e icles de Hilbe ), que la col .lecció dels sis emes deduc ius és un sis ema clausu a i un eo ema gene al de M . .WARD [1942] ensdiu que un sis emaclausu a_C i un ope ado de conseqüéncia C és el ma eix ; si em I? =IX : C(X) =X  és C(X) = n ~Y : Y E ) ' i Y 2 X ~ . Teo emes com el de Schmid - diu :un ope ado C és ini a i si, i només si, el seu sis emaclausu a és o amen induc- iu - i el de Pie ce - diu : si C és ini a i, els ele nen s del sis emaclausu a,~ i educ ibles cons i ueixen unaba- se mínima de ~>- sugge eixen la possibili a de dona p opie- a s de C a a e s del seu sis emaclausu a associa . Una gUes ióimpo an quecal esold e i en la que hem e- balla (c .J .Pla(197b1 ; V .Ve dú 119781) consis eix en impo- sa co  20 )ns a C (a ;? ) pe alque es e i iqui el eo e- ma de la deducció de Ta ski . A a bé el eo ema de la deduc- ció de Ta ski és un eo ema in imamen lliga amb llope ació i po ocó e que, en A, no es disposide cap ope aci6 . . Quines condicions ha de sa is e , doncs, C (o,C) pe al de pode in odui en A una ope aci6 . que ens pe me i denun- cia el eo ema de la deducció : y E C(X,x)  si, i només si,  x .y E :C(X)  ? Les espos es donades pe J .Pla i V .Ve dú di e eixen en el següen sen i , : 2 8 men es que el p ime dóna una condició que pe me de ini , en A di ec amen , una ope ació . que e i ica el eo ema de la deducció, el segon a la següen cons ucció To oge ado C pe me de de ini una elació d'equi aléncia induida pe la elació cíe p eo d e x :!!5 Cy  .si,  i només si,  y E C(4x}) . Podemdonespassa al c ;uocien A/ == C i conside a 1'álgeb a quocien (A/== C ,C), on Ces i es de ineixde o ma na u al . Alesho esV .Ve dúimposa condiciona a (A,C) de o ma que, en (A,C), es e i iqui el eo ema de la deducció . L'an e io conside ació ens p opo ciona una una lógica (A,C) i una aplicaciócompa ible p ojecciócanónica -M Sabem que - R és men * pe (X,!) si, i només si 6 : 9 (A/ - C ) , 9 (A/ :- C ) epijec i a, que i pe - J1 i que C(x) =C(y) . lógica (A,C) , amb Ci C ; la (A,C) es á gene a p ojec i a - pe o x,  y E A,  71 (x) =Z1 (y) Aques a ideaés la KO 119731 de o ma mo isme bilógic . abs ac es i h :A 1  -  A 2 és Di B 1 .  h és mo isme  (i .e .  h -1 (Y) E 11` í ,  pe cada YE MB 2 .  h gene a p ojec i amen (A 1 ,C 1 ) a pa i de que ecullel eball de D .J .BROWN-R .SUSZ- gene al quan in odueixel concep e de Si (A 1 ,C 1 ) i (A 2,C2 ) són dues álgeb es una aplicació que e i ica (A 2 ,C 2 ) i h (i .e . Je, =h -1 (Y) : Y E % 2 ) ; MB 3 .  h és epijec i a, di em que h és un mo isme bilógic en e (A 1 ,C 1 ) i (A 2 ,C 2 ) La impo áncia eal d'aques a de inició seunom - és la següen h és un mo isme bilógic si, i només si, - que jus i ica el en e (A 1 ,C 1 ) i(A 2 ,C 2 ) 29 WA:W , 1 . (1942) °The closu eope a o so a la ices'l . Annals o a h, 43,n°2,p .191-196 .