Algebra Logicii - Logica Algebrica

7/30/2019 Algebra Logicii - Logica Algebrica

1/21

ALGEBRA LOGICII - LOGICA ALGEBRICA (I)

GEORGE GEORGESCU

Abstract

Intre logica matematica si algebra exista o relatie complexa. Algebra logicii si logicaalgebrica sunt doua dintre ipostazele acestei relatii. De multe ori, nu se face o distinctie

ntre algebra logicii si logica algebrica. Scopul acestui articol este de a propune o delimitarea celor doua domenii si de a discuta, din aceasta perspectiva, unele conexiuni dintre logicasi algebra. Pentru fiecare sistem logic n parte, putem vorbi despre o logica algebricasi despre o algebra a logicii. Studierea raportului dintre ele poate explica evolutia unorsubiecte matematice si poate influenta miscarea ideilor n domeniu.

In afara unor comentarii generale, lucrarea de fata se concentreaza asupra relatiei dintrelogica algebrica si algebra logicii n cazul sistemelor clasice (calculul propozitional si calcululcu predicate). Partea a doua a lucrarii va studia unele aspecte ale algebrei logicii si logiciialgebrice asociate unor logici neclasice (intuitionista, modala, temporala, multivalenta).

1 INTRODUCERE

Logica matematica este o disciplina ce apartine deopotriva si Matematicii si Logicii.Atunci cand ncepe un curs de logica matematica se pune n mod natural ntrebarea urmatoare:

(A) Ce este logica matematica?In acel moment nu putem raspunde decat prin formulari tip dictionar (de exemplu, con-form dictionarului Larousse, logica matematica este teoria stiintifica a rationamentelor, ex-cluzand procesele psihologice si care se divide n calculul propozitional si calculul predicatelor )sau prin enumerarea unor subdomenii ale logicii matematice (de exemplu, folosind clasificareaAMS 2000). Chiar daca nu raspundem la ntrebare putem discuta despre unele teme ale logiciimatematice si despre modul cum aceasta se raporteaza la alte discipline. In acest context aparentrebarea:

(B) Care este raportul dintre logica matematica si matematica?

In ceea ce priveste ntrebarea (B), se pot formula urmatoarele ntrebari ajutatoare:(b1) La ce foloseste logica matematicii?(b2) La ce foloseste matematica logicii?

Incercarea de a raspunde la ntrebarea (b1) conduce la o discutie complicata ce se finalizeazacu raspunsuri extrem de variate. Pentru subiectul nostru este mai interesanta ntrebarea (b2).Incercarea de a contura un raspuns la (b2) trebuie pus a n relat ie cu o alta ntrebare:

(c) Ce este un sistem logic ?Intrebarea (c) poate fi privita si ca un substitut al lui (A); ea ngusteaza sfera lui (A) darne apropie de posibilitatea de a da acesteia un raspuns. Sistemele logice provin din logica sifilosofie (logica clasica [60], logica intuitionista [38], logica modala [14], [22], etc.), din matematica(sistemul Zermelo-Fraenkel al teoriei multimilor), din informatica (logica dinamica, anumite

sisteme de logica temporala [49]), din fizica (logica mecanicii cuantice ), etc.Vom raspunde la ntrebarea (c) prin teza ca un sistem logic este descris de urmatoarele optdimensiuni [29]:

- dimensiunea sintactica;

1


2/21

- dimensiunea semantica;

- dimensiunea algebrica;- dimensiunea topologica;

- dimensiunea categoriala;

- dimensiunea probabilista;

- dimensiunea algoritmica;

- dimensiunea filosofica.Fiecare din aceste dimensiuni descrie ntr-un mod specific sistemul logic. Cunoasterea sistemuluilogic se realizeaza cu atat mai bine cu cat sunt surprinse mai multe dintre relat iile ce se pot stabilintre aceste dimensiuni. Sintaxa si semantica sunt dimensiunile principale ale unui sistem logic.In mod necesar orice descriere a sistemului logic trebuie sa nceapa cu aceste doua dimensiuni.Adaugarea unor alte dimensiuni se va face n functie de contextul n care este studiat sistemul

logic. In tratarea primelor sapte dimensiuni ale unui sistem logic ne folosim de concepte si derezultate din matematica. Instrumentarul matematic necesar(teoreme, metode, algoritmi, etc)difera de la sistem la sistem si de la dimensiune la dimensiune. Modul cum aceste teoreme,metode, algoritmi, etc. sunt folosite n studiul sistemului logic ne da un raspuns la ntrebarea(b2).

2 REPREZENTAREA TRIDIMENSIONALA A UNUI SISTEMLOGIC

De obicei, cursurile si manualele de logica se opresc asupra primelor trei dimensiuni din lista

de mai sus. In acest caz, sistemele logice sunt studiate din perspectiva unei relatii tripartite:sintaxa, semantica, algebra.

SINTAXA SEMANTICA

ALGEBRA

3333

3333

33

Sintaxa unui sistem logic S are doua componente: limbajul formal al sistemului si structuralogica. Limbajul sistemului este construit pornind de la o lista de simboluri primare (alfabet).Aplicarea unor reguli de combinare a simbolurilor primare conduce la obtinerea multimii expre-siilor (formule, enunturi). Expresiile reprezinta traducerea n limbajul formal a unor propozitiidin limbajul natural. Structura logica a limbajului se defineste prin axiomele si prin regulilede deductie ale sistemului. Acestea permit introducerea demonstratiilor formale, a teoremelorformale (enunturi ce admit o demonstratie formala) si a deductiilor formale din ipoteze.Fie un enunt si o multime de enunturi ale lui S. Vom nota:

: este o teorema formala a lui S; : se deduce formal din ipotezele .Semantica unui sistem logic S este legata de notiunea de interpretare (care difera de la un

sistem la altul si chiar pentru un acelasi sistem). O interpretare atribuie enunturilor sistemuluivalori de adevar. Multimea valorilor de adevar are o structura algebrica si o structura de ordine; ointerpretare transforma operatiile logice (conectori, cuantificatori) n operatii algebrice. Folosindinterpretarile se definesc principalele notiuni semantice: modelele unei teorii, enunturile universal

2


3/21

adevarate si deductia semantica din ipoteze.

Daca enuntul este adevarat n orice interpretare atunci spunem ca este universal adevarat(|= ).Fie un enunt si o multime de enunturi ale lui S. Atunci se deduce semantic din ipotezele ( |= ) daca este adevarat n orice model al lui .Sintaxa si semantica sunt componentele principale ale sistemului logic. Relatia dintre ele esteexprimata prin proprietatea de corectitudine (orice teorema formala este un enunt universaladevarat) si prin proprietatea de completitudine (orice enunt universal adevarat este teoremaformala).Semantica este lumea reala a unor structuri matematice; sintaxa este o lume virtuala ceexprima simbolic proprietatile structurilor formulate n limbaj natural. Mecanismul inferentialal sintaxei traduce formal rationamentele ce se petrec la nivelul semanticii.

Algebra unui sistem logic S are la baza o constructie canonica, numita algebra Lindenbaum-Tarski a lui S. Sa presupunem ca printre conectorii sistemului se numara si implicatia .Pe multimea E a enunturilor lui S se va considera urmatoarea relatie binara:

daca si numai daca si .Daca n sistemul logic sunt valabile:

(principiul identitatii)

daca si atunci .

atunci este o relatie de echivalenta pe E. In ipoteza ca relatia de echivalenta este com-patibila cu operatiile logice ale lui S, multimea cat E/ devine o structura algebrica ale careioperatii sunt obtinute din operatiile logice. Aceasta structura algebrica se numeste algebraLindenbaum-Tarski a lui S.Notam cu clasa de echivalenta a unui enunt din S. Pe multimea cat E/ se poate definirelatia de ordine prin:

daca si numai daca .Exista sisteme logice pentru care metoda de construct ie a algebrei Lindenbaum-Tarski nu sepoate aplica (de exemplu, sistemele modale S1, S2 si S3). In [7] este prezentata o metoda foartegenerala de algebrizare a sistemelor logice.

3 CE ESTE ALGEBRA LOGICII SI CE ESTE LOGICA AL-GEBRICA?

Metodele algebrice au fost introduse n logica de catre George Boole n patru scrieri (douacarti si doua articole ) publicate n jurul anului 1850 (vezi [9], [10], [11] , [12] ). Chiar titlurileacestora vorbesc despre o analiza matematica a logicii, despre un calcul al rationamentelordeductive si despre o cercetare a legilor gandirii. Ideile lui Boole au determinat n mod deci-siv dezvoltarea ulterioara a logicii si a unei parti a algebrei. Se pune ntrebarea: cercetarile luiBoole se situeaza n algebra sau n logica? Iata ce spun doi mari ganditori despre contributiilelui Boole:Augustus de Morgan : It finds the laws of thought symbolized in the forms of algebra [21].Bertrand Russell : Pure mathematics was discovered by Boole, in a work which he called theLaws of Thought. His book was in fact concerned with formal logic and this is the same as

mathematics.Contributiile lui Boole si ale urmasilor sai directi (De Morgan, Schroder, Pierce, etc.) sunt unamestec de logica si de calcul algebric. Este important de observat ca ideea separarii calcululuialgebric de logica se ntalneste chiar n cartea lui Boole din 1854; autorul vorbeste chiar de o

3


4/21

algebra a logicii.

Termenul Algebra logicii a fost impus de continuatorii lui Boole . O eleva a lui Peirce, Chris-tine Ladd, scrie n 1883 o lucrare intitulata On the Algebra of Logic, iar Schroder publicantre anii 1890 si 1905 monografia n trei volume Vorlesungen uber die Algebra der Logik.La Whitehead (1898) si Huntington ( 1904), prin algebra logicii se ntelege un calcul simbolicextras din logica propozitionala si din teoria naiva a multimilor (vezi [34]).Nu ntamplator prima lucrare de logica a lui Moisil se intituleaza Recherches sur lalgebre de lalogique (vezi [55]) . Aceasta lucrare a inaugurat spiritul algebric n care, prin Moisil si elevii sai,s-a dezvoltat o mare parte din logica matematica romaneasca. Contributiile din [55] combinaalgebra cu logica fara a face o demarcatie ntre ele. Separarea celor doua planuri este proclamatade Moisil n mod explicit n lucrarea [56]:Au calcul des theses correspond ce quil convient dappeler lAlgebre de la Logique, en donnant

a ce terme la signification generale detude algebrique des systemes suggeres par le calcul destheses.Notiunea de algebra Boole n sensul folosit astazi apare prima data n monografia [88] (cf.[66], p.73). Constituirea teoriei algebrelor Boole ca un corp matematic consistent a fost realizatan principal de catre Stone, Birkhoff si Tarski n deceniul patru al secolului trecut. De atunci,algebrele Boole s-au dezvoltat continuu, n relat ie cu alte tipuri de algebre, cu analiza, topologia,probabilitatile, informatica, etc. Dupa aparitia primelor sisteme logice formalizate (datorate nspecial lui Hilbert) s-a pus ntr-un mod explicit problema relatiei ntre sistemul logic si algebrelesale. Raspunsul a fost dat de Lindenbaum si Tarski prin constructia ce le poarta numele. Alge-brele asociate unui sistem logic Sau ca prototip algebra Lindenbaum-Tarski a lui S. Studiul lorpoate fi desprins de logica si poate constitui obiectul unui domeniu al algebrei de sine statator.

Sursele dezvoltarii domeniului rezultat sunt probleme pur algebrice, proprietati ale sintaxei sisemanticii lui S reflectate n plan algebric, precum si relatiile cu alte discipline din matematica,informatica, filosofie, etc. Urmatoarea tabela nfatiseaza structurile algebrice corespunzatoareunor sisteme logice foarte cunoscute.

Sistem logic Structuri algebrice

calculul propozitional clasic algebre Boole

calculul propozitional intuitionist algebre Heyting

calcule propozitionale modale algebre modale

calcule propozitionale temporale algebre temporale

logici Lukasiewicz MV-algebre

logici Post algebre Postlogici Moisil algebre Lukasiewicz-Moisil

logici BL BL-algebre

calculul cu predicate clasic algebre cilindricealgebre poliadice

calculul cu predicate intuitionist algebre Heyting poliadice

Si astazi ntalnim numeroase carti si lucrari asupra algebrei logicii. Termenul desemneazadeopotriva calcule logice n forma algebrica sau studiul algebrelor unui sistem. In ultimeledecenii se vorbeste din ce n ce mai mult despre logica algebrica a unui sistem logic , mai alespentru algebrele calculelor cu predicate (vezi [35] si [41]). In [7] se considera ca actul de nastere

al logicii algebrice moderne este lucrarea lui Tarski [86]:Algebraic logic in the modern sense can be said to have begun with Tarskis 1935 paper on thefoundation of the calculus of systems.Intrebuintarea celor doua notiuni (algebra logicii si logica algebrica) poate produce o anumita

4


5/21

confuzie. Se pune atunci problema precizarii celor doua notiuni printr-o delimitare mai exacta

a domeniilor pe care le desemneaza.In algebra logicii vor intra toate proprietatile algebrelor asociate unui sistem logic S; logicaalgebrica va retine acele proprietati algebrice ce provin (direct sau indirect) din sintaxa sausemantica lui S. Pentru fiecare sistem logic, logica algebrica este o parte a algebrei logicii .Granitele logicii algebrice n interiorul algebrei logicii nu sunt definitiv trasate; rezultate puralgebrice pot avea un impact ulterior asupra sistemului logic.

4 ALGEBRA LOGICII VS LOGICA ALGEBRICA

Motivatia delimitarii ntre algebra logicii si logica algebrica ncepe cu un argument firesc:o suma de fapte matematice ce se constituie ntr-un ntreg trebuie sa poarte un nume. Exista

si un argument ce tine de relatia dintre sistemul logic si algebrele sale. Cercetari din logica seprelungesc n probleme si rezultate pur algebrice; reciproc, prin proiectarea unor proprietati al-gebrice asupra sistemului logic se ajunge la o mai buna cunoastere a sa. Pentru a ilustra aceastateza vom face apel la un episod semnificativ din istoria logicilor multivalente.Este cunoscut ca primele sisteme de logica multivalenta au fost introduse n mod independentde catre J. Lukasiewicz si E. Post. Analiza judecatilor modale din textele aristoteliene l-a con-dus pe Lukasiewicz n 1920 la considerarea unui sistem de logica cu trei valori [53]. Ulterior,Lukasiewicz si elevii sai au studiat logici n-valente si chiar infinit valente [54]. In mod indepen-dent, Post a introdus n 1921 un sistem de logica n-valenta din ratiuni pur matematice [68].Gr. C. Moisil a introdus n 1940 algebrele Lukasiewicz 3-valente si n 1941 algebrele Lukasiewicz4-valente ca modele algebrice ale logicilor lukasiewicziene cu trei, respectiv cu patru valori

(vezi [56], [57]). Apoi, prin generalizarea acestor structuri algebrice, Moisil a definit algebreleLukasiewicz n-valente. Scopul declarat al lui Moisil a fost construirea algebrei logicii core-spunzatoare logicilor lui Lukasiewicz. A. Rose a gasit n 1956 un exemplu prin care demonstraca structurile propuse de Moisil algebrizeaza n mod adecvat logicile lui Lukasiewicz numai pen-tru valentele 3 si 4. Pentru valente de la 5 n sus implicatia lukasiewicziana nu mai poate definitan structurile definite de Moisil (vezi [8], p.471). Vom ncerca o explicatie a acestui fapt facandapel la raportul dintre algebra logicii si logica algebrica.In logica lui Lukasiewicz implicatia are rolul central; toti ceilalti conectori se pot exprima nfunctie de implicatie. La Moisil, n primul plan sta structura de latice, o negatie slaba sioperatiile de nuantare (endomorfismele chrysippiene). Endomorfismele chrysippiene asociazaunei propozitii din logica n-valenta n-1 propozitii din logica bivalenta (= nuante). Pentru alge-

brele Lukasiewicz 3-valente si 4-valente Moisil a demonstrat un principiu de determinare. In in-terpretare, principiul de determinare al lui Moisil afirma ca o propozitie din logica n-valenta estedeterminata de nuantele sale. Este important de observat ca n definitia algebrelor Lukasiewiczn-valente principiul de determinare apare ca axioma 1. Distingem doua momente esentiale nactiunea lui Moisil de algebrizare a logicilor lui Lukasiewicz:

- Pornind de la logicile lui Lukasiewicz (3-valente si 4-valente), Moisil defineste algebreleLukasiewicz 3-valente si 4-valente, pentru care demonstreaza principiul de determinare.Acesta este un act de trecere de la logic a la algebra, iar ceea ce rezulta (definitii sipropozitii) se situeaza n logica algebrica.

- Obtinerea definitiei algebrelor Lukasiewicz n-valente prin generalizarea cazurilor n=3 sin=4 se ncadreaza n algebra logicii. Sursele logice sunt partial uitate (implicatia

1 In definitia algebrelor Lukasiewicz-Moisil -valente, introduse de Moisil n 1969, un principiu de determinareapare din nou ca axioma (vezi [57], [8]).

5


6/21

lukasiewicziana) si, ntr-o masura oarecare, definitia noilor structuri este realizata prin

mimetism algebric. Generalizarea s-a realizat ntr-un spatiu din afara logicii algebrice,ceea ce a produs despartirea de logica lui Lukasiewicz.

Ulterior, prin ntoarcere de la algebra la logica, structurile create de Moisil au generat un noutip de logici cu mai multe valori (logicile Moisil), distincte de sistemele propozitionale ale luiLukasiewicz (vezi [57], [8]). Intamplarile povestite mai sus ilustreaza modul subtil n care algebralogicii si logica algebrica se separa si se ntrepatrund.

5 LOGICA ALGEBRICA A CALCULULUI PROPOZITIONALCLASIC

Pentru a delimita granitele logicii algebrice asociate unui sistem logic S trebuie sa raspundemla ntrebarea:Ce notiuni si proprietati ale algebrelor unui sistem logic S se afla n sfera logicii algebrice a lui S?Vom ncerca schita unui raspuns n cazul calculului propozitional clasic (L). Algebra Lindenbaum-Tarski a calculului propozitional L este o algebra Boole. Prin urmare, teoria algebrelor Booleconstituie algebra logicii pentru sistemul L. Atunci ntrebarea de mai sus va capata o forma maiprecisa:Ce notiuni si proprietati din teoria algebrelor Boole provin din notiuni si proprietati ale calcu-lului propozitional L?(a) In primul rand, logica algebrica a lui L va contine acele entitati si fapte algebrice ce tra-duc ntr-un mod direct entitati si fapte din sintaxa si semantica lui L. O asemenea situatie se

ntalneste n paralela dintre teoria multimilor consistente de enunturi (parte a sintaxei lui L)si teoria filtrelor n algebre Boole. In general, prin trecerea de la multimea enunturilor lui Lla algebra Lindenbaum-Tarski se realizeaza o corespondenta ntre unele notiuni din sintaxa siunele notiuni algebrice. In tabelul de mai jos este prezentata corespondenta dintre unele notiunilegate de multimile consistente ale lui L si unele not iuni asupra filtrelor booleene (vezi [60]).

Sintaxa Algebra

Sistem deductiv Filtru Boolean

Multime consistenta Multime cu proprietatea intersectiei finite

Sistem deductiv consistent Filtru propriu

Multime consistenta maximala Ultrafiltru

Corespondenta dintre multimi consistente si filtre se manifesta nu numai la nivelul con-ceptelor, ci si la nivelul rezultatelor din cele doua teorii. Pentru exemplificare, amintim douapropozitii asupra multimilor consistente maximale.

Propozitia 5.1. Orice multime consistenta se poate scufunda ntr-o multime consistenta max-imala.

Propozitia 5.2. Daca este o multime consistenta atunci sunt echivalente afirmatiile urmatoare:

(i) este consistenta maximala;

(ii) Pentru orice enunturi , ale lui L, daca atunci sau ;

(iii) Pentru orice enunt al lui L, sau .

6


7/21

Sa punem alaturi de aceste rezultate urmatoarele doua propozitii din teoria filtrelor booleene.

Consideram o algebra Boole (B, , , , 0, 1) oarecare.Propozitia 5.3. Orice filtru propriu al algebrei Boole B se poate scufunda ntr-un ultrafiltru allui B.

Propozitia 5.4. Daca U este un filtru propriu al algebrei Boole B atunci sunt echivalenteafirmatiile urmatoare:

(i) U este ultrafiltru;

(ii) U este filtru prim (daca a b U atunci a U sau b U);

(iii) Pentru oricea B, avem a U sau a U.

Propozitia 5.3 este varianta algebrica a Propozitiei 5.1, iar Propozitia 5.4 este variantaalgebrica a Propozitiei 5.2. Mai mult, demonstratiile propozitiilor algebrice sunt traduceri fideleale demonstratiilor proprietatilor sintactice corespunzatoare.(b) Exista situatii n care relatia dintre doua proprietati (una din logica si alta din algebra) nueste imediat vizibila. Un exemplu convingator este relatia dintre teorema de completitudine acalculului propozitional L si teorema de reprezentare a lui Stone [85]. Teorema de reprezentarea lui Stone se poate enunta n doua forme, raportate la doua exemple importante de algebreBoole: primul exemplu este algebra Boole P(X) a partilor unei multimi X, iar al doilea estealgebra Boole standard L2 = {0, 1}.

Teorema 5.5. Pentru orice algebra Boole B exista o multime nevida X si un morfism boolean

injectiv d : B P(X).

Teorema 5.6. Pentru orice algebra Boole B exista o multime nevida X si un morfism booleaninjectiv d : B LX2 .

Conform Teoremei 5.5, calculul ntr-o algebra Boole oarecare B se reduce la calculul n P(X);conform Teoremei 5.6, calculul n B se reduce la calculul n LX2 , deci n L2.In forma sa slaba, teorema de completitudine stabileste echivalenta dintre teoremele formale alelui L si enunturile universal adevarate:

Teorema 5.7. Pentru orice enunt al lui L: daca si numai daca |= .

Teorema de completitudine tare stabileste echivalenta dintre deductia sintactica si deductiasemantica:

Teorema 5.8. Fie o multime de enunturi ale lui L si un enunt. Atunci: daca si numai daca |= .

Teorema de reprezentare a lui Stone este contrapartea algebrica a teoremei de completitudine.Intelesul afirmatiei de mai sus trebuie privit n lumina a trei observatii:

- Teorema de completitudine este un rezultat de logica a carei demonstratie se bazeaza pemultimile consistente maximale; teorema de reprezentare a lui Stone este un rezultat dealgebra demonstrat cu teoria ultrafiltrelor. Pasii demonstratiei teoremei lui Stone sunt otraducere fidela a etapelor ce alcatuiesc demonstratia teoremei de completitudine.

- Fiecare dintre cele doua rezultate (teorema de completitudine si teorema lui Stone) poatefi demonstrat pornind de la celalalt.

7


8/21

- Atat demonstratia teoremei de completitudine, cat si cea a teoremei lui Stone invoca

axioma alegerii.In axiomatizarea Zermelo-Fraenkel a teoriei multimilor (fara axiomaalegerii), teorema de completitudine si teorema lui Stone devin enunturi echivalente logic.

(c) Un al treilea caz l constituie acele proprietati algebrice ce nu au un corespondent n sistemullogic, dar care sunt folosite n studiul altor sisteme logice. Un asemenea exemplu este teoremaSikorski-Halmos de caracterizare a algebrelor Boole injective ([37], [82] ).O algebra Boole A se numeste injectiva daca pentru orice morfism boolean injectiv k : B Csi pentru orice morfism boolean f : B A exista un morfism boolean g : C A astfel ncaturmatoarea diagrama este comutativa:

B C

A

Ek

ddf

g

Teorema 5.9. (Sikorski- Halmos). Pentru orice algebra Boole B sunt echivalente afirmatiileurmatoare:

(i) B este o algebra Boole injectiva;

(ii) B este o algebra Boole completa.

Teorema 5.9 este un rezultat algebric pur si nu pare a proveni dintr-o proprietate a calcu-lului propozitional clasic. Ea este nsa utilizata n mod esential n demonstratia unui rezultatimportant din teoria modelelor booleene: teorema de completitudine a lui Shorb ([84], [51]).Un al doilea exemplu este completarea McNeille a unei algebre Boole (vezi [37],[82]). Constructianu se plaseaza n logica algebrica a calculului propozitional, dar apare n demonstratii din logicaalgebrica a calculului cu predicate clasic ([20]) si n teoria modelelor booleene ale sistemuluiZermelo - Fraenkel ([46]).

6 ALGEBRE ALE CALCULULUI CU PREDICATE (CP)

In perioada 1948-1952, A. Tarski mpreuna cu elevii sai L. Chin si F. Thomson au introdusalgebrele cilindrice ca algebre asociate calculului cu predicate clasic (vezi [41]). Teoria lor a fostdezvoltata n special de A. Tarski, L. Henkin si J. D. Monk [41], apoi de D. Pigozzi, R. Maddux,H. Andreka, I. Nemeti, I. Sain, I. Hodkinson, R. Hirsch, T. Sayed Ahmed,etc.

Algebrele poliadice (cu egalitate si fara egalitate), definite si studiate de P. R. Halmos (vezi [35]),constituie un alt tip de algebre asociate calculului cu predicate. Directia initiata de Halmos afost continuata de B. A. Galler, A. Daigneault, H. Leblanc, J. D. Monk, S. Comer, etc.Prima problema n definirea algebrelor calculului cu predicate a fost obtinerea unei notiuni decuantificator ntr-un context pur algebric. Cum era firesc, punctul de plecare al acestui demersa fost studierea modului cum actiunea cuantificatorior (existential si universal) se poate traducen algebra Lindenbaum-Tarski a lui CP. Pentru fiecare variabila din alfabetul lui CP, actiuneacuanticatorului existential asupra formulelor lui CP conduce la o operatie unara definita pe al-gebra Lindenbaum-Tarski. Pasul urmator a fost definirea notiunii de cuantificator existentialpe o algebra Boole oarecare. Atat Tarski, cat si Halmos au ajuns la o aceeasi definit ie a cuan-tificatorului existential prin trei axiome foarte simple. Dupa cum povesteste Halmos in [36],

selectarea acestor axiome nu a fost imediata:The algebraic axioms for existential quantification are simple, but it took me months to absorbthem into my bloodstream, to understand them intuitively and emotionally as well as merelytechnically.

8


9/21

Dupa cum am observat deja, fiecarei variabile a lui CP i este asociat un cuantificator existential

algebric n algebra Lindenbaum-Tarski a lui CP. Actiunea cuantificatorului existential asupraformulelor lui CP este reflectata n algebra Lindenbaum-Tarski printr-o multime de operatiiunare (cuantificatorii existentiali booleeni), legate ntre ele prin proprietati generate de struc-tura logica a lui CP.O a doua problema ce s-a pus n definirea algebrelor lui CP a fost stabilirea axiomelor care satraduca algebric aceste proprietati. Aici Tarski si Halmos au dat raspunsuri diferite. Desi auaceeasi sursa de inspiratie (algebra Lindenbaum-Tarski a calculului cu predicate clasic), alge-brele cilindrice si algebrele poliadice sunt structuri matematice distincte.Algebrele cilindrice mbogatesc structura de algebra Boole printr-o familie de cuantificatoriexistentiali algebrici si printr-o multime de constante dublu indexata (reflectand predicatul deegalitate al lui CP).

Halmos a procedat pas cu pas: a gasit ntai forma algebrica a cuantificatorilor, a studiat algebreleBoole cu un singur cuantificator (= algebre monadice), a introdus apoi algebrele poliadice si nfinal a ajuns la algebrele poliadice cu egalitate. Algebrele poliadice provin din calculul predi-catelor fara egalitate. In definitia lor este prezenta o familie de cuantificatori existentiali indexatade multimea tuturor partilor unei multimi nevide (ale carei elemente reprezinta variabilele) si deo familie de endomorfisme booleene (reprezentand substitutiile). Algebrele poliadice cu egalitatesunt obtinute prin adaugarea unei operatii ce algebrizeaza predicatul de egalitate din CP.Cele doua tipuri de algebre au o importanta parte comuna. Un rezultat al lui Galler [26]stabileste echivalenta ntre algebrele cilindrice de dimensiune infinita, local finite si algebrelepoliadice cu egalitate, local finite si de grad infinit. Teorema lui Galler nu este intamplatoare.Dupa cum vom vedea, algebrele cilindrice de dimensiune infinita, local finite si algebrele po-

liadice local finite, de grad infinit sunt structurile ce reflecta n mod direct calculul predicatelor(cu egalitate).Notiunile de algebra cilindrica si de algebra poliadica, mai largi decat aceste structuri asociaten mod nemijlocit lui CP s-au impus din ratiuni algebrice. A fost un prim pas de trecere de lalogica algebrica la algebra logicii a lui CP.Chiar daca au atacat probleme similare, o vreme cele doua teorii s-au dezvoltat pe baza unortehnici diferite. Cercetarile actuale au unificat cele doua directii; totusi teoria algebrelor cilin-drice este preponderenta (vezi [41] , [42], [64], [79]). Mai departe, vom discuta modul n care seobtine definitia algebrelor cilindrice avand ca prototip algebra Lindenbaum-Tarski asociata uneiteorii a calculului cu predicate.Sistemul formal al calculului cu predicate (CP) este construit avand ca punct de plecare struc-

turile de ordinul I. O structura de ordinul I A este formata dintr-o multime nevida A (universulstructurii) nzestrata cu operatii, relatii si constante.Alfabetul lui CP este compus dintr-o multime infinita V de variabile, din constantele logice ,, , , = si din simboluri de operatii, de relatii si de constante. Prin inductie se definesctermenii, formulele si enunturile lui CP. Vom numi proprietati de ordinul I acele proprietati alestructurilor ce pot fi formalizate n limbajul lui CL.Pentru simplitate vom presupune ca multimea V a variabilelor este numarabila:V = {v0, v1,...,vn,...}.O multime de axiome si de reguli de deductie completeaza sintaxa lui CP. Pornind de la axiomesi aplicand pas cu pas cate o regula de deductie se obtin teoremele formale. Daca este oteorema formala a lui CP atunci notam: .

Analog se defineste notiunea de deductie formala n CP. O teorie este o multime de enunturi alelui CP. Daca T este o teorie si o formula atunci notam:

T : din ipotezele T se deduce formal .Pentru a obtine algebrele calculului cu predicate va trebui sa examinam algebrele Lindenbaum-

9


10/21

Tarski asociate teoriilor lui CP. Fie F (resp. E) multimea formulelor (resp. enunturilor) lui CP.

Fixam o teorie T a lui CP. Pe multimea F consideram relatia binara T : T daca si numai daca T si T .T este o relatie de echivalenta pe F. Notam cu /T clasa de echivalenta a unei formule . Pemultimea cat AT = F/T introducem operatiile : /T/T = ( )/T; /T/T = ( )/T;(/T) = ()/T si constantele 1 = ( )/T, 0 = ( )/T (definitia lui 1 si 0 nu depindede enuntul ).Atunci (AT, , , , 0, 1) este o algebra Boole. Operatiile acestei algebre Boole corespunddisjunctiei, conjunctiei si negatiei lui CP. Pasul urmator este algebrizarea cuantificatorilor luiCP. Pentru fiecare variabila v a lui CP definim operatiile unare :v : AT AT si v : AT AT prin v(/T) = v/T si v(/T) = v/T.Operatiile unare (v)vV vor traduce algebric actiunea cuantificatorului existential , iar operatiile

unare (v)vV actiunea cuantificatorului universal . Se poate arata usor cav(/T) = v (/T) si v(/T) = v (/T).Avand ca model operatia v (resp. v) vom introduce notiunea de cuantificator existential(resp. cuantificator universal ) pe o algebra Boole oarecare.Fie (B, , , , 0, 1) o algebra Boole. O operatie unara : B B (resp. : B B) se numestecuantificator existential (resp. cuantificator universal) pe B daca verifica axiomele Q1 Q3(resp. Q

1 Q

3):

Q1 : 0 = 0;Q2 : a a;Q3 : (a b) = a b;Q

1 : 1 = 1;

Q

2 : a a;Q

3 : (a b) = a b;

Se verifica usor ca operatia v (resp. v) este un cuantificator existential (resp. universal)pe AT. Pentru orice i < vom nota ci = vi.

1

Predicatul de egalitate = introduce formule atomice de forma vi = vj (cu vi , vj variabile ale luiCP). Aceste formule atomice definesc urmatoarele constante ale lui AT : dij = (vi = vj)/T.Atunci putem considera urmatoarea algebra : AT =< AT, , , , 0, 1, ci, dij >i,ji,j


11/21

algebrele cilindrice sa poata fi reflectate suficient de multe proprietati importante ale lui CP.Intr-o alta formulare, problema este cat de aproape este o CA oarecare fata de o algebra ATce provine direct din sistemul logic. Un prim raspuns este dat de urmatoarea teorema:

Teorema 6.1. ([41], 2.6.49). Pentru orice algebra A avand aceeasi signatura cu algebrele cilin-drice, afirmatiile urmatoare sunt echivalente:(i) Exista o teorie T a lui PC astfel ncat A este izomorfa cu algebra Lindenbaum-Tarski ATasociata lui T;(ii) A este o algebra cilindrica de dimensiune si, pentru orice a A, multimeaa = {i < ; ci(a) = a} este finita.

Multimea a se numeste suportul elementului a al lui A. O algebra cilindrica n care fiecareelement are suportul finit se numeste local finit-dimensionala (pe scurt, local finita). Algebra

Lindenbaum-Tarski AT este local finita deoarece fiecare formula a lui CP contine un numar finitde variabile libere.Primul exemplu de algebra cilindrica este algebra Lindenbaum-Tarski AT asociata unei teoriiT. Ea provine din sintaxa lui CP si studiul sau sugereaza modul cum proprietatile sintactice alelui CP pot fi convertite n proprietati ale algebrelor cilindrice.Al doilea exemplu de algebra cilindrica si are sursa n semantica lui CP.Fie M o structura de ordinul I si M universul sau. Notam cu M multimea sirurilor cu elementedin multimea M (un sir s M este o functie s : M). Reamintim ipoteza ca multimea Va variabilelor lui CP este numarabila: V = {v0, v1,...,vn,...}.Atunci un sir s M poate fi identificat cu o interpretare a lui CP n M. Daca este o formulaa lui CP si s M atunci vom nota:

M |= [s]: s satisface formula n structura M.Pentru orice formula consideram multimea interpretarilor ce satisfac pe in M:M = {s M; M |= [s]}.Amintim ca F este multimea formulelor lui CP. Notam AM = {

M; F} . Multimea nevidaAM P(M) va fi universul unei algebre cilindrice.Mai ntai observam ca pentru orice formule si avem :M M = ( )M; M M = ( )M; M M = ()M.Aceste egalitati arata ca AM este nchisa la operatiile de reuniune (), de intersectie () side complementara (), deci (AM, , , , , M

) este o algebra Boole. Pentru orice i < consideram functia Ci : AM AM definita prin:Ci(

M) = {t M; exista s M, cu tj = sj pentru orice j = i}.

Pentru orice i, j < notam Dij = {s M; si = sj}.

Teorema 6.2. AM =< AM, , , , , M, Ci, Dij >i,ji,j


12/21

A =< A, , , , , M, Ci, Dij >i,j 0, definitiile de mai sus pot figeneralizate ntr-un mod evident. In acest caz obtinem notiunea de algebra cilindrica de multimi -dimensionala.

Fie o teorie consistenta T n limbajul LCP si M un model al lui T. Sa consideram algebrelecilindrice AT si AM construite n aceasta sectiune. Vom defini o functie f : AT AM n felulurmator: f(/T) =

M, pentru orice formula a lui CP.

Propozitia 6.6. f este un morfism de algebre cilindrice. Daca T este o teorie consistentamaximala atunci f este un izomorfism de algebre cilindrice.

7 LOGICA ALGEBRICA A CALCULULUI CU PREDICATE

Explorarea logicii algebrice a calculului cu predicate ncepe cu studiul algebrelor Lindenbaum-Tarski asociate teoriilor lui CP. Proprietati sintactice si semantice ale lui CP sunt traduse nproprietati ale algebrelor Lindenbaum-Tarski AT, apoi se ncearca demonstrarea lor pentru di-verse clase de algebre cilindrice. Datorita Teoremei 6.1, algebrele cilindrice local finite constituieo clasa privilegiata.

Ca reflectare a teoremei de completitudine a calculului propozitional L, teorema de reprezentarea lui Stone este punctul culminant al logicii algebrice a lui L. Legatura stransa ntre completi-tudinea lui L si reprezentarea algebrelor Boole ne conduce spre problema existentei unei relatiisimilare si n cazul altor sisteme logice. A reprezenta un obiect matematic prin entitati mai sim-ple este o problema frecvent ntalnita n matematica si conceptualizata n mai multe moduri. Incazul de fata luam n considerare reprezentarea algebrelor universale ca produs subdirect al unoralgebre apartinand unei clase fixate. Un rezultat general este cunoscuta teorema de reprezentarea lui Birkhoff [6]: orice algebra dintr-o clasa ecuationala (varietate) este izomorfa cu un produssubdirect de algebre subdirect ireductibile. Aceasta teorema se poate aplica eficient atunci candeste cunoscuta structura obiectelor subdirect ireductibile ale varietatii. Cum singura algebraBoole subdirect ireductibila este L = {0, 1}, rezulta ca teorema de reprezentare a lui Stone esteun caz particular al teoremei lui Birkhoff.Reprezentarea algebrelor cilindrice si a algebrelor poliadice este subiectul central al logicii al-gebrice a calculului cu predicate. Urmatorul rezultat este cunoscut sub numele de teorema dereprezentare a lui Tarski.

Teorema 7.1. Orice algebra cilindrica de dimensiune local finita este izomorfa cu un produssubdirect de algebre cilindrice de multimi, local finite si regulate.

Tarski a obtinut aceasta teorema nca de la nceputul cercetarilor sale asupra algebrelorcilindrice nsa prima demonstratie apare abia n monografia [41]. Exista mai multe demonstratiipur algebrice ale acestui rezultat ([1], [41], [61]) si una metamatematica, folosind teorema de

completitudine extinsa (vezi de exemplu [60]).O teorema de reprezentare asemanatoare a fost obtinuta de P. R. Halmos pentru algebrele po-liadice (cu egalitate si fara egalitate) local finite si de grad infinit. In algebrizarea teoremei de

1X este suportul lui X A.

12


13/21

completitudine, Halmos a pornit de la doua surse:

- demonstratia teoremei de completitudine prin modele booleene (Rasiowa-Sikorski [71]);- demonstratia teoremei de completitudine prin metoda constantelor (Henkin [39]).Prima sursa l-a condus pe Halmos la o teorema de reprezentare mai slaba prin care este sta-bilita existenta reprezentarilor functionale. Rezultatul acesta corespunde unei forme a teore-mei de completitudine ce afirma existenta unui model boolean pentru o teorie consistenta. Inlucrarea [39], Henkin demonstreaza ca orice teorie consistenta a lui CP admite un model siteorema de completitudine este obtinuta ca un corolar. Teorema de reprezentare a algebrelorpoliadice (cu egalitate si fara egalitate) este algebrizarea rezultatului lui Henkin. Mai mult,demonstratia data de Halmos teoremei sale de reprezentare este o transpunere algebrica fidelaa pasilor demonstratiei teoremei de completitudine prin metoda lui Henkin. De pilda, algebrelepoliadice bogate au ca prototip algebrele Lindenbaum-Tarski ale teoriilor Henkin, iar scufun-

darea unei algebre poliadice ntr-o algebra poliadica bogata constituie reflectarea algebrica aextinderii unei teorii consistente la o teorie Henkin. O alta demonstratie algebrica prin ultra-produse poate fi gasita n lucrarea [69].Sa revenim la reprezentarea algebrelor cilindrice. Se poate arata ca orice algebra cilindrica demultimi de dimensiune , local finita si regulata este simpla (are exact doua congruente). AtunciTeorema 7.1 se poate formula echivalent astfel:

Teorema 7.2. Orice algebra cilindrica de dimensiune , local finita este semisimpla.

Sa comparam teorema de reprezentare a algebrelor cilindrice (Teorema 7.1) cu teorema decompletitudine extinsa. Aplicand Teorema 7.1 n cazul particular cand algebra cilindrica A estechiar algebra Lindenbaum Tarski a unei teorii consistente T putem construi un model al lui T.

In acest fel obtinem teorema de completitudine extinsa din Teorema 7.1. Daca presupunem cateorema de completitudine este cunoscuta si aplicam Teorema 6.1 si Propozitia 6.6 atunci putemdemonstra Teorema 7.1.Atat teorema de completitudine cat si Teorema 7.1 sunt adevarate n prezenta axiomei alegerii.In axiomatizarea Zermelo-Fraenkel a teoriei multimilor (fara axioma alegerii), cele doua enunturi(teorema de completitudine si Teorema 7.1) sunt logic echivalente. Teorema 7.1 este un rezultatpur algebric. Principala sa calitate este de a fi reflectarea n algebra a teoremei de completitudine.Totusi aceasta teorema are unele limitari ce tin de:- dimensiunea ;- ipoteza de local-finitudine asupra algebrei cilindrice A;- natura obiectelor prin care A este reprezentata (algebre cilindrice de multimi, local finite si

regulate).Prima restrictie este nlaturata de urmatoarea generalizare a Teoremei 7.1:

Teorema 7.3. Fie un ordinal . Orice algebra cilindrica de dimensiune , local finita esteizomorfa cu un produs subdirect de algebre cilindrice de multimi, de dimensiune , local finitesi regulate.

In algebra universala este comod a lucra cu varietati de algebre (clase ecuationale). Ovarietate este caracterizata prin proprietatea de a fi nchisa la subalgebre, produse directe sicaturi. Clasa algebrelor cilindrice de dimensiune , local finite nu este nchisa la ultraproduse,deci ea nu poate fi axiomatizata n logica de ordinul I. Cu atat mai mult aceasta clasa nu esteo varietate.

Daca n formularea Teoremei 7.3 eliminam conditia de regularitate se obtine un concept dereprezentare mai apropiat de cel existent n cazul teoremei lui Stone. Mai precis, spunem ca oalgebra cilindrica de dimensiune este reprezentabiladaca este izomorfa cu un produs subdirectde algebre cilindrice de multimi (de dimensiune ).

13


14/21

Clasa algebrelor cilindrice reprezentabile include n mod strict clasa algebrelor cilindrice local

finite.In acelasi timp, exista algebre cilindrice nereprezentabile. Pentru dimensiuni finite avemurmatorul rezultat:

Teorema 7.4. Orice algebra cilindrica de dimensiune finita este simpla (deci subdirect inde-compozabila).

Conform teoremei precedente, studiul algebrelor cilindrice reprezentabile este interesant nu-mai n cazul unor dimensiuni infinite. Amintim cateva rezultate clasice asupra algebrelor cilin-drice reprezentabile:

Teorema 7.5. (Tarski [41]). Fie un ordinal > 0. Clasa algebrelor cilindrice de dimensiune reprezentabile este o varietate.

Teorema 7.6. (Henkin [41]). Clasa algebrelor cilindrice de dimensiune 2 reprezentabile este

finit axiomatizabila.Teorema 7.7. (Monk [59]). Clasa algebrelor cilindrice de dimensiune > 2 reprezentabile nueste finit axiomatizabila.

Conform Teoremei 7.5, clasa algebrelor cilindrice (de orice dimensiune) este axiomatizabilaprin ecuatii. In cazul dimensiunii 2 putem gasi un numar finit de ecuatii ca axiome, ceea cepentru alte dimensiuni este imposibil. In lucrarea [2], Andreka a propus un grad de complexitateal unei axiomatizari a algebrelor cilindrice reprezentabile. Sa notam, pentru un ordinal infinit:CA = clasa algebrelor cilindrice de dimensiune ;LFCA = clasa algebrelor cilindrice de dimensiune , local finite;RCA = clasa algebrelor cilindrice de dimensiune , reprezentabile;

P A = clasa algebrelor poliadice de grad ;L FPA = clasa algebrelor poliadice de grad , local finite;RPPA = clasa algebrelor poliadice de grad , reprezentabile.Relatia ntre aceste clase de structuri este mai sugestiv ilustrata vizual:

CP

LFCAhhhhhRCA

CA

L FPAhhhhhRP A

P A

I

q

14


15/21

Prin teorema lui Galler [26], categoriile LFCA si L FPA sunt echivalente. Dupa cum am

vazut, clasa LFCA a fost definita de Tarski prin raportare directa la calculul cu predicate.Trecerea de la LFCA la CA a fost primul pas spre algebra logicii lui PC. Al doilea pas sprealgebra logicii lui PC a fost definirea clasei RCA. Eforturile cercetatorilor s-au ndreptat nprimul rand asupra obiectelor din RCA. S-au obtinut teoreme de caracterizare ale algebrelorcilindrice reprezentabile (de exemplu, teorema lui Henkin [41]) si s-au pus n evidenta subclaseremarcabile ale lui RCA ([41]). Schimbarea notiunii de reprezentare (prin fascicole [16], cuasi-grupuri [62], etc.) conduce la o redesenare a hartii din figura de mai sus.Pentru teorema de completitudine s-au dat numeroase demonstratii. Dintre ele, patru ni se para avea o semnificatie deosebita pentru subiectul nostru. Este vorba de metoda lui Henkin [39],metoda Rasiowa- Sikorski ([71], [72]), metoda prin forcing [48] si metoda prin proprietati deconsistenta [56]. Fiecare dintre aceste demonstratii pune n evidenta o metoda de a construi

modele. Am vazut ca algebrizarea metodei lui Henkin a condus la demonstratii algebrice aleteoremei de reprezentare a algebrelor poliadice (local finite, de grad infinit) [35] si a algebrelorcilindrice (local finite, de dimensiune infinita)[41].Metodei Rasiowa-Sikorski i corespunde o teorema de reprezentare a algebrelor poliadice prinalgebre poliadice functionale ([35], [20]).Metoda forcing a fost introdusa de P. J. Cohen pentru demonstrarea independentei axiomeialegerii si a axiomei continuului ([15]). Inspirat de conceptul lui Cohen, A. Robinson a definit nteoria modelelor forcingul sintactic ([74]) si forcingul semantic ([75]). Forcingul sintactic a fostpus ntr-o forma generala de H. J. Keisler n [48]. Teorema modelului generic , demonstrata deKeisler n [48], este o metoda puternica pentru a obtine modele ale unor teorii. In particular,prin aplicarea ei se poate obtine o demonstratie a teoremei de completitudine. In lucrarea [27]

s-a definit o notiune de forcing n algebrele poliadice si a fost demonstrata o forma poliadica ateoremei modelului generic din lucrarea [48].A patra metoda de demonstratie a teoremei de completitudine are la baza proprietatile deconsistenta. Acestea sunt abstractizari ale familiei multimilor consistente. Rezultatul funda-mental asupra multimilor de consistenta este teorema de existenta a modelului: orice teorie ceapartine unei proprietati de consistenta admite un model (vezi, de exemplu, [56]). Aplicandteorema de existenta a modelului n cazul familiei multimilor consistente se obtine teorema decompletitudine : orice teorie consistenta admite un model. Demonstrarea unei variante poliadicesau cilindrice a teoremei de existenta a modelului este o problema deschisa.Am vazut cum teorema de completitudine si diversele sale demonstratii au fost subiectele deinspiratie cele mai importante pentru logica algebrica a calculului cu predicate.In principiu, cu fiecare rezultat semnificativ al logicii se poate imagina un traseu de algebrizareanalog celui din cazul teoremei de completitudine: se gaseste o formulare algebrica a rezultatu-lui, se cauta o clasa de algebre poliadice (sau cilindrice) ce permite obtinerea unei demonstratiia variantei poliadice (resp. cilindrice) si apoi subiectul trece n algebra logicii.Un asemenea rezultat semnificativ este teorema lui Craig (vezi [56]).Daca este un enunt al lui CP atunci vom nota cu CP() limbajul obtinut din CP retinandnumai simbolurile de operatii, de relatii si de constante ce apar n .

Teorema 7.8. (Craig) Fie si doua enunturi ale lui CP. Daca atunci exista unenunt astfel nc at , si CP() CP() CP().

Proprietatea de amalgamare (AP) este o conditie frecvent ntalnita n algebra. Prin definitie,o categorie C are proprietatea de amalgamare daca orice diagrama din C :

15


16/21

B

A

B

Bf

rrjg

cu f, g monomorfisme se poate completa la o diagrama comutativa n C:

B

A B

B

qu

If

qg Iv

n care u, v sunt de asemenea monomorfisme.

In [19], A. Daigneault a aratat ca algebrele poliadice local finite, de grad infinit verifica propri-etatea de amalgamare si ca Teorema 7.8 poate fi dedusa din acest rezultat.In lucrarea [67], D. Pigozzi a stabilit un rezultat similar pentru algebrele cilindrice local- finite.Mai mult, el a aratat ca pentru aceste structuri AP poate fi demonstrata plecand de la teoremalui Craig. Prin urmare, AP este contrapartea algebrica a teoremei de interpolare. Studiul APpentru diverse clase de algebre cilindrice sau poliadice a devenit o problema n sine (vezi [67],[80], etc.). AP a fost pusa n relatie atat cu subiecte de algebra logicii, cat si cu subiecte delogica algebrica.Rezumand discutia de pana acum, reprezentarea este algebrizarea completitudinii iar amalga-marea este algebrizarea interpolarii de tip Craig. Si alte rezultate din teoria modelelor au fosttrecute n spat iul algebrei. Dintre ele, mentionam teorema de omitere a tipurilor, teorema

Keisler- Shelah de caracterizare a echivalentei elementare, partial forcingul lui Keisler, etc. Inacelasi timp, algebrizarea altor teme ale teoriei modelelor (teoreme ale celor doi cardinali, mo-dele saturate, modele existential-nchise, teoria stabilitatii, etc.) ramane o problema deschisa.Tratarea teoremei de categoricitate a lui Morley n contextul algebrelor poliadice sau al alge-brelor cilindrice ar constitui un rezultat senzational pentru cercetarile din logica algebrica.S-a pus si problema definirii unor sisteme logice (mai complicate decat CP) a caror logica al-gebrica sa fie realizata de clase de algebre cilindrice (sau poliadice). Structurile algebrice alelogicii lui Keisler ([47]) sunt exact algebrele poliadice fara egalitate si de grad infinit.

8 ALGEBRIZAREA TEOREMEI DE INCOMPLETITUDINE

A LUI GODEL.Teorema de incompletitudine a lui Godel ([32]) este, fara ndoiala, cel mai celebru rezultat

al logicii matematice1. Printre altele, ea afirma ca n algebra lui Peano (ca sistem axiomatic),exista un enunt astfel ncat nici , nici nu este teorema formala.Algebrizarea teoremei de incompletitudine este o problema deschisa. Solutionarea ei ar constituiun atestat maximal pentru logica algebrica. Rezolvarea acestei probleme presupune urmatoriipasi:

(i) Definirea structurilor algebrice ce corespund sistemului formal al aritmeticii lui Peano;

(ii) Formularea variantei algebrice a teoremei de incompletitudine ;

(iii) Demonstrarea algebrica a acestei variante.

Pasii (i) si (ii) ai unei asemenea demonstratii au fost realizati chiar de Halmos n [35].Inalgebrele poliadice cu egalitate el a introdus not iunile de operatie, termen, predicat, constanta,

1Comentarii interesante asupra acestui rezultat pot fi gasite n lucrarea [77], precum si n Revista de Filosofie,LV, 1-2, 2008

16


17/21

etc. Aceasta i-a permis sa defineasca algebrele Peano n contextul algebrelor poliadice cu ega-

litate. Algebra Lindenbaum - Tarski a sistemului formal al aritmeticii lui Peano este o algebraPeano. Halmos a gasit si o formulare algebrica a teoremei de incompletitudine n termeniialgebrelor Peano simple : Not every Peano algebra is simple (cf. [35], p. 33). Pasul III estensa incomparabil mai greu de abordat. Exista totusi unele reusite n ncercarea de a algebrizademonstratia teoremei de incompletitudine. O etapa importanta n demonstratia teoremei luiGodel este urmatoarea propozitie: orice functie recursiva este reprezentabila n aritmetica luiPeano. Versiunea algebrica a acestei propozitii a fost obtinuta de L. Leblanc n monografia[52]. In sens invers, aplicarea teoremei de incompletitudine a condus la obtinerea unor rezultateimportante n algebre cilindrice ([63], [65]). Ca exemplificare, mentionam urmatoarea teoremaa lui Nemeti : algebrele cilindrice libere de dimensiune mai mare ca 3 nu sunt atomice ([63]).

9 OBSERVATII FINALE

In acest articol este analizata relatia dintre algebra logicii si logica algebrica n contextulunei reprezentari tridimensionale a unui sistem logic: sintaxa, semantica, algebra.Partea I a lucrarii are n vedere logica clasica (calculul propozitional si calculul cu predicate).Pentru calculul propozitional, granita dintre algebra logicii si logica algebrica a capatat un statutprecis. Cu totul altfel stau lucrurile n cazul calculului cu predicate. Rezultatele importante dinteoria algebrelor cilindrice si poliadice se ncadreaza n logica algebrica. Zona pur algebrica aacestei teorii nu este nca constituita ca un domeniu n sine.Partea a doua a lucrarii va studia raportul dintre algebra logicii si logica algebrica pentru unelelogici neclasice (intuitionista, modala, temporala, multivalenta). Pentru calculele propozitionale

ale acestor logici vom ntalni o mare varietate de algebre si de teoreme de reprezentare aleacestora; pentru calculele cu predicate corespunzatoare, atat algebra logicii cat si logica algebricasunt putin dezvoltate. In toate aceste cazuri ntalnim numeroase probleme deschise, a carorrezolvare ar constitui pasi importanti n afirmarea domeniului.

Sugestiile primite de la domnii profesori Sergiu Rudeanu si Dragos Vaida ne-au fost de folosn obt inerea formei finale a acestui articol. Autorul le multumeste n mod calduros.

References

[1] H. Andreka, I. Nemeti, A simple, purely algebraic proof of the completeness of some first

order logic, Algebra Universalis, 5, 1975, 8-15

[2] H. Andreka, Complexity of equations valid in algebras of relations, Annals of Pure and Appl.Logic, 28, 1994, 31-43

[3] H. Andreka, S. Givant, S. Mikulis, I. Nemeti, A. Simon, Notions of density that implyrepresentability in algebraic logic, Annals of Pure and Appl. Logic, 91, 1988, 93-190

[4] H. Andreka, J. D. Monk, I. Nemeti, (eds), Algebraic Logic, North Holland, 1991

[5] C. J. Bergman, R. D. Maddux, D. L. Pigozzi, (Eds), Algebraic Logic and Universal Algebrain Computer Science, Springer, LNCS, 425, 1990

[6] G. Birkhoff, Lattice Theory (third edition), Amer. Math. Soc., Providence, 1967

[7] W. J. Blok, D. Pigozzi, Algebraizable Logics, Memoirs AMS, vol. 77, 1989, no. 398

17


18/21

[8] V. Boicescu, A. Filipoiu, G. Georgescu, S. Rudeanu, Lukasiewicz- Moisil Algebras, North-

Holland, 1991[9] G. Boole, On a general method in analysis, Philosophical Transactions of the Royal Society

of London, 134, 1844, 225-282

[10] G. Boole, The Mathematical Analysis of Logic, 1847

[11] G. Boole, The Calculus of Logic, Cambridge and Dublin Mathematical Journal, 3, 1848,183-198

[12] G. Boole, An Investigation of the Laws of Thought, 1854

[13] C. C. Chang, H. J. Keisler, Model Theory, North-Holland, 1994

[14] B. Chellas, Modal Logic. An Introduction, Cambridge Univ. Press, 1980

[15] P. J. Cohen, Set Theory and the Continuous Hypothesis, W. A. Benjamin, Inc., 1966

[16] S. D. Comer, A sheaf theoretic duality theory for cylindric algebras, Trans. AMS, 169, 1985,75-87

[17] W. Craig, Logic in Algebraic Form, North Holland, 1974

[18] A. Daigneault, J. D. Monk, Representation theory for polyadic algebras, Fund. Math., 52,1963, 151-176

[19] A. Daigneault, On automorphisms of polyadic algebras, Trans. Amer. Math. Soc., 112,1964, 84- 130

[20] A. Daigneault, Theorie des modeles en logique mathematique, Montreal, 1967

[21] A. De Morgan, On the syllogism and on the logic of relations, Transactions of the CambridgePhilosophical Society, 10, 1864, 331- 358

[22] M. Dumitru, Modalitate si Incompletitudine, Ed. Paideea, 2001

[23] M. Fitting, Intuitionistic Logic, Model Theory and Forcing, North Holland, 1969

[24] M. Fitting, E. Orlowska, (Eds), Beyond Two : Theory and Applications of Multiple - ValuedLogic, Physice-Verlag, Springer, 2003

[25] J. M. Font, R. Jansana, D. L. Pigozzi, A survey of abstract algebraic logic, Studia Logica,71, 2003, 13-97

[26] B. A. Galler, Cylindric and polyadic algebras, Proc. AMS, 8, 1957, 176-183

[27] G. Georgescu, Sur le forcing faible dans les algebres polyadiques, C. R. Acad. Sci. Paris,280, 1975, 1257- 1258

[28] G. Georgescu, Extensii ale teoriei modelelor, In: Matematica n Lumea de Azi si de Maine,

Ed. Academiei, 1985, 116-123

[29] G. Georgescu, Matematica teoremelor de completitudine (I), Revista de Filosofie, LV, 1-2,2008, 71- 84

18


19/21

[30] G. Georgescu, A. Iorgulescu, S. Rudeanu, Some Romanian Researches in the Algebra of

Logic, In: Grigore C. Moisil si continuatorii sai, Ed. Academiei Romane, 2007, 86-132[31] K. Godel, Die Vollstandigkeit der Axiome des logish Functionenkalkuls, Monatshefte fur

Mathematik und Physik, 37, 1930, 349-360

[32] K. Godel, Uber formal unentscheidbare Satze der Principia Mathematica und verwandterSysteme, Monatshefte fur Mathematik und Physik, 38, 1931, 173- 198

[33] K. Godel, The consistency of the axiom of choice and of the generalized continuum hypoth-esis, Princeton Univ. Press, 1940

[34] J. Green, The algebra of logic: what Boole really started

[35] P. R. Halmos, Algebraic Logic, Chelsea Publ. Comp., 1962

[36] P. R. Halmos, An autobiography of polyadic algebras, Logic J. of IGPL, 8, no.4, 1988,363-392

[37] P. R. Halmos, Lectures on Boolean Algebras, Van Nostrand, Priceton, Toronto, London,1963

[38] A. Heyting, Intuitionism. An Introduction, North Holland, 1956

[39] L. Henkin, The completeness theorem of the first-order functional calculus, J.Symb. Logic,14, 149, 159- 166

[40] L. Henkin, The discovery of my completeness proofs, Bull. Symb. Logic, 2, 1996, 127-158

[41] L. Henkin, J. D. Monk, A. Tarski, Cylindric Algebras, I, II, North-Holland, 1971, 1985

[42] L. Henkin, J. D. Monk, A. Tarski, H. Andreka, I. Nemeti, Cylindric Set Algebras, LectureNotes in Math., 883, Springer, 1981

[43] D. Hilbert, W. Ackermann, Grundzugen der theoretischen Logik, Springer-Verlag, 1928

[44] R. Hirsch, I. Hodkinson, Relation Algebras by Games, Studies in Logic and Foundations ofMathematics, vol. 147, 2002

[45] E. Huntington, Sets of independent postulates for the algebra of logic, Transactions AMS,

5, 1904, 288-309

[46] Th. J. Jech, Lectures in Set Theory with Particular Emphasis on the Method of Forcing,Lecture Notes in Math., 217, Sprinder-Verlag, 1971

[47] H. J. Keisler, A complete first- order logic with infinitary predicates, Fund. Math., 52, 1963,177-203

[48] H. J. Keisler, Forcing and the omitting types theorem, in : Studies in Model Theory, MAAStudies in Math., Buffalo, N.Y., 8, 1873, 96-133

[49] F. Kroger, Temporal Logic of Programs, Springer, 1985

[50] C. Ladd, On the algebra of logic, in: C.S.Peirce (ed.), Studies in Logic, Boston, Little,Brown, and Co.,1883, 17-71

[51] G. Loullis, Sheaves and Boolean- valued model theory, J. Symb. Logic, 44, 1979, 153-183

19


20/21

[52] L. Leblanc, Representabilite et Definisabilite dans les Algebres Transformationnelles et dans

les Algebres Polyadiques, Les Presses de LUniversite de Montreal, 1966[53] J. Lukasiewicz, On three valued logic (n poloneza), Ruch Filozoficzny, 5, 1920 160-171

[54] J. Lukasiewicz, A. Tarski, Untersuchungen uber den Aussagenkalkul, C. R. Seances Soc.Sci. Lettres Varsovie, Cl. III, 23, 1930, 30-50

[55] Gr. C. Moisil, Recherches sur lalgebre de la logique, Ann. Sci. Univ. Jassy, 22, 1936, 1-118

[56] Gr. C. Moisil, Recherches sur les logiques non-chrysipiennes, Ann. Sci. Univ. Jassy, 27,1941, 431- 466

[57] Gr. C. Moisil, Essais sur les logiques non- chrysipiennes, Ed. Academiei, Bucuresti, 1972

[58] Gr. C. Moisil, Sur la structure algebrique du calcul des propositions, Bull. Math. Soc.Roumaine Sci., 40, 1938, 3-8

[59] J. D. Monk, Non-finitizability of classes of representable cylindric algebras, J.Symb. Logic,34, 1969, 331-343

[60] J. D. Monk, Mathematical Logic, Springer,1976

[61] J. D. Monk, Omitting types algebraically, Ann. Sci. Univ. Clermont, Ser. Math., 16, 1978,101-105

[62] J. D. Monk, Connections between combinatorial theory and algebraic logic, In:Studies in

Mathematics, vol. 9, Amer.Math.Soc., 1974, 58-91

[63] I. Nemeti, Free algebras and decidability in algebraic logic, Ph. D. Thesis, HungarianAcademy of Sciences, 1986

[64] I. Nemeti, Algebraization of quantifier logics, an introductory overview, Studia Logica, 50,1991, 465-569

[65] I. Nemeti, G. Sagi, On the equational theory of representable polyadic algebras, J.Symb.Logic, 65, 2000, 1143-1167

[66] R. Padmanabhan, S. Rudeanu, Axioms for Lattices and Boolean Algebras, World Scientific,2008

[67] D. Pigozzi, Amalgamation, congruence extension, and interpolation properties in algebras,Algebra Universalis, 1, 1971, 269-349

[68] E. Post, Introduction to a general theory of elementary propositions of logic, Amer. J.Math., 43, 121, 163-185

[69] K. Potthoff, Representation of locally finite polyadic algebras and ultraproducts, Zeit. Math.Logik und Grund. Math., 17, 1971, 91-96.

[70] H. Rasiowa, An Algebraic Approach to Non-classical Logics, North-Holland, 1974

[71] H. Rasiowa, R. Sikorski, A proof of the completeness theory of G odel, Fund. Math., 37,1950, 193-200

[72] H. Rasiowa, R. Sikorski, The Mathematics of Metamathematics, Polish Scientific Publ.,1963

20


21/21

[73] A. Robinson, Introduction to Model Theory and to the Metamathematics of Algebra, North

Holland, 1974[74] A. Robinson, Forcing in model theory, Symposia Math., vol. 5, 1970, 64-82

[75] A. Robinson, Infinite forcing in model theory, Proc. Second Scandinavian Logic Symp.,(Oslo, 1970), North Holland, 1971

[76] S. Rudeanu, Gr. C. Moisil, a contributor to the early development of lattice theory1, Mult.-Valued Logic, 2, 1997, 323- 328

[77] S. Rudeanu, Calculabilitate intuitiva si teorema lui Godel, Revista de Logica (PublicatieOnline), No. 1, 2008

[78] T. Sayed Ahmed, Reducts of L3 has Godels incompleteness, therefore the free quasi-polyadic algebras of dimension 3 are not atomic, manuscript, 2001

[79] T. Sayed Ahmed, Algebraic logic, where does it stand today, Bulletin of Symb. Logic, 11,no. 4, 2005, 465- 516

[80] T. Sayed Ahmed, On amalgamation of reducts of polyadic algebras, Algebra Universalis,51, 2004, 301-359

[81] E. Schroder, Vorlesungen uber die Algebra der Logik, Leipzig, Eugen Muller, 1890-1905 .Reprint: Bronx, N.Y., Chelsea Publ. Comp., 1966, 3 vols.

[82] R. Sikorski, Boolean Algebras, Springer- Verlag, 1964[83] H. M. Sheffer, A set of five independent postulates for Boolean algebras, with applications

to logical constants, Trans. Amer. Math. Soc., 14, 1913, 481- 488

[84] A. M. Shorb, Contributions of Boolean- valued model theory, Ph. D. Thesis, Univ. ofMinesota, 1969

[85] M. H. Stone, The theory of representation for Boolean algebras, Trans. Amer. Math. Soc.,40, 1936, 37- 111

[86] A. Tarski, Grundzuge der Systemenkalkuls. Erster Teil., Fund. Math., 25, 1935, 503- 526

[87] A. Tarski, Logic, Semantics, and Metamathematics, papers from 1923 to 1938, Trans. J. H.Woodger, 2nd edition, Ed. J. Corcoran, Hackett Pub. Comp., Indianapolis, 1883

[88] A. N. Whitehead, A Treatise on Universal Algebra, with Applications, Cambridge Univ.Press, 1898

1Semnalam si o versiune a acestui articol n limba romana: S. Rudeanu, Contributiile lui Gr. C. Moisil ladezvoltarea timpurie a teoriei laticilor n: Grigore C. Moisil si continuatorii sai(coord.: A. Iorgulescu, S. Marcus,S. Rudeanu, D. Vaida), Editura Academiei Romane, 2007

Algebra Logicii - Logica Algebrica

Documents

Transcript of Algebra Logicii - Logica Algebrica