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 algebrica”si 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 apareıntrebarea:

(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 pusa ın relatie 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, anumitesisteme 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

- 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 relatiile ce se pot stabiliıntre 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 sistemullogic. 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 listade mai sus. In acest caz, sistemele logice sunt studiate din perspectiva unei relatii tripartite:sintaxa, semantica, algebra.

SINTAXA SEMANTICA

ALGEBRA

aaaaaaaaaa!!!!

!!!!

!!

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

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 constructie 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 asmathematics”.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

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 publicaıntre 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 l’algebre 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 qu’il convient d’appeler l’Algebre de la Logique, en donnanta ce terme la signification generale d’etude 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 realizataın principal de catre Stone, Birkhoff si Tarski ın deceniul patru al secolului trecut. De atunci,algebrele Boole s-au dezvoltat continuu, ın relatie 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 S au 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 algebricecalculul propozitional clasic algebre Boolecalculul propozitional intuitionist algebre Heytingcalcule propozitionale modale algebre modalecalcule propozitionale temporale algebre temporalelogici Lukasiewicz MV-algebrelogici Post algebre Postlogici Moisil algebre Lukasiewicz-Moisillogici BL BL-algebrecalculul cu predicate clasic algebre cilindrice

algebre poliadicecalculul 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 nastereal logicii algebrice moderne este lucrarea lui Tarski [86]:”Algebraic logic in the modern sense can be said to have begun with Tarski’s 1935 paper on thefoundation of the calculus of systems”.Intrebuintarea celor doua notiuni (algebra logicii si logica algebrica) poate produce o anumita

4

confuzie. Se pune atunci problema precizarii celor doua notiuni printr-o delimitare mai exactaa 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. Existasi 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 algebrele Lukasiewicz 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 definitaın 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 algebrele Lukasiewicz 3-valente si 4-valente, pentru care demonstreaza principiul de determinare.Acesta este un act de trecere de la logica 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

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

5

lukasiewicziana) si, ıntr-o masura oarecare, definitia noilor structuri este realizata prinmimetism 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 lui Lukasiewicz (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 notiuni asupra filtrelor booleene (vezi [60]).

Sintaxa AlgebraSistem deductiv Filtru BooleanMultime consistenta Multime cu proprietatea intersectiei finiteSistem deductiv consistent Filtru propriuMultime 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

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 orice a ∈ 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 booleaninjectiv 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

- Atat demonstratia teoremei de completitudine, cat si cea a teoremei lui Stone invocaaxioma 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

-k

@@Rf

�� 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 traduceın 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 definitie 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

Dupa cum am observat deja, fiecarei variabile a lui CP ıi este asociat un cuantificator existentialalgebric ı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 asociateın 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

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)v∈V vor traduce algebric actiunea cuantificatorului existential ∃, iar operatiileunare (∀v)v∈V actiunea cuantificatorului universal ∀. Se poate arata usor ca∀v(ϕ/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.1Predicatul 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,j<ω.AT este algebra Lindenbaum - Tarski a calculului cu predicate CP2. Notiunea de algebra cilin-drica se obtine prin abstractizare din AT .Fie α un ordinal oarecare. O algebra cilindrica de dimensiune α (CAα, pe scurt) este o algebrade forma A =< A,∨,∧,−, 0, 1, ci, dij >i,j<α unde (A,∨,∧,−, 0, 1) este o algebra Boole, (ci)i<αeste o multime de cuantificatori existentiali pe A si (dij)i,j<α este o multime de constante alelui A astfel ıncat urmatoarele axiome sunt satisfacute:C1 : cicj = cjci, pentru orice i, j < α;C2 : dij ∧ djk ≤ dik, pentru orice i, j, k < α;C3 : Pentru orice i, j < α si a ∈ A, daca a ≤ dij atunci dij ∧ cia ≤ a.

Se poate arata ca algebra Lindenbaum-Tarski AT asociata unei teorii T este o algebra cilin-drica de dimensiune ω.In aparenta, definirea cuantificatorilor pe algebra Boole si a algebrelor cilindrice este un actpur algebric: axiomele lor au fost alese din proprietatile lui AT astfel ıncat sa produca catmai ”multa algebra”. Afirmatia este corecta, ınsa important pentru logica algebrica este ca ın

1ω este cardinalul multimilor numarabile.2Constructia lui AT se realizeaza ın acelasi fel si pentru cazul ın care variabilele lui CP sunt indexate de

ordinalii mai mici decat un ordinal α infinit.

10

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, multimea∆a = {i < ω; ci(a) 6= 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). AlgebraLindenbaum-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.FieM 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 ınM. 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 6= i}.Pentru orice i, j < ω notam Dij = {s ∈Mω; si = sj}.

Teorema 6.2. AM =< AM,∪,∩,−, ∅,Mω, Ci, Dij >i,j<ω este o algebra cilindrica de dimensi-une ω.

Exemplul de algebra cilindrica din Teorema 6.2 poate fi extins ın asa fel ıncat sa nu ne mairaportam la sistemul logic CP. Fie M o multime nevida si Mω multimea sirurilor cu elemente ınM. Atunci, pentru orice i < ω putem defini functia Ci : P(Mω)→ P(Mω) prin:Ci(X) = {t ∈Mω; exista s ∈ X, cu tj = sj pentru orice j 6= i}, pentru orice X ⊆Mω.La fel ca mai sus, pentru orice i, j < ω notam Dij = {s ∈ Mω; si = sj}. Urmatorul rezultatgeneralizeaza Teorema 6.2.

Teorema 6.3. < P(Mω),∪,∩,−, ∅, Ci, Dij >i,j<ω este o algebra cilindrica de dimensiune ω.

O subalgebra a algebrei cilindrice din Teorema 6.3 se va numi algebra cilindrica de multimiω-dimensionala. Mai precis, o algebra cilindrica de multimi ω - dimensionala este de forma

11

A =< A,∪,∩,−, ∅,Mω, Ci, Dij >i,j<ω unde A este o subalgebra Boole a lui P(Mω) ınchisa laoperatiile Ci si la constantele Dij . Algebra cilindrica de multimiA este regulata daca ındeplinesteconditia urmatoare: pentru orice X ∈ A si s, t ∈Mω, daca s/∆X = t/∆X si s ∈ X atunci t ∈ X1.

Observatia 6.4. Algebrele cilindrice de forma AM sunt algebre cilindrice de multimi local finitesi regulate. In general, algebrele cilindrice de multimi nu sunt nici local finite, nici regulate.

Observatia 6.5. Inlocuind pe ω cu un ordinal oarecare α > 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 siM 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 decompletitudine 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

1∆X este suportul lui X ∈ A.

12

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 siregulate).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 reprezentabila daca este izomorfa cu un produs subdirectde algebre cilindrice de multimi (de dimensiune α).

13

Clasa algebrelor cilindrice reprezentabile include ın mod strict clasa algebrelor cilindrice localfinite. 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 estefinit 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;PAα = clasa algebrelor poliadice de grad α;LFPAα = 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

LFCAαhhhhhRCAα

CAα

LFPAαhhhhhRPAα

PAα

����

����

������

����

���1

PPPPPPPPPPPPPPPPPPPPPq

14

Prin teorema lui Galler [26], categoriile LFCAα si LFPAα sunt echivalente. Dupa cum amvazut, 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 construimodele. 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 ıncat ` ϕ→ θ, ` θ → ψ 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

B′

A

B′′

��*f

HHjg

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

B′A B′′′

B′′

PPqu

���1f

PPPqg ��1v

ı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 spatiul algebrei. Dintre ele, mentionam teorema de omitere a tipurilor, teoremaKeisler- 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 INCOMPLETITUDINEA LUI GODEL.

Teorema de incompletitudine a lui Godel ([32]) este, fara ındoiala, cel mai celebru rezultatal 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 notiunile 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

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 esteınsa 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 propozitionaleale 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 folosın obtinerea 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 firstorder 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

[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 Societyof 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

[30] G. Georgescu, A. Iorgulescu, S. Rudeanu, Some Romanian Researches in the Algebra ofLogic, In: Grigore C. Moisil si continuatorii sai, Ed. Academiei Romane, 2007, 86-132

[31] K. Godel, Die Vollstandigkeit der Axiome des logish Functionenkalkuls, Monatshefte furMathematik 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

[52] L. Leblanc, Representabilite et Definisabilite dans les Algebres Transformationnelles et dansles Algebres Polyadiques, Les Presses de L’Universite 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 l’algebre 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 inMathematics, 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 Godel, Fund. Math., 37,1950, 193-200

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

20

[73] A. Robinson, Introduction to Model Theory and to the Metamathematics of Algebra, NorthHolland, 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 Godel’s 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 applicationsto 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

21