Math Wiki
Don't have an account?
Register
Advertisement
Register
in: Logică matematică

Teorema lui Stone

Modificare
Marshall Harvey Stone

Marshall Harvey Stone

Enunţ[]

Teoremă. Orice algebră Boole este izomorfă cu o algebră Boole ale cărei elemente sunt părţi ale unei mulţimi.

Acest rezultat, enunţat de Marshall Harvey Stone în 1936, a fost considerat decisiv pentru dezvoltarea matematicii secolului XX.

Istoric[]

Teorema a putut fi enunţată abia după ce, la sfârşitul secolului al XIX-lea, cercetările privind teoria grupurilor au evoluat, în condiţiile unui interes crescut al matematicienilor pentru abstractizarea algebrei. Probabil că teorema de reprezentare a lui Cayley, publicată în 1878, care arăta că orice grup abstract este abstract izomorf cu un grup „concret” de substituţii (permutări), a fost premisa de la care a pornit şi Stone. Dar teoriei grupurilor, cea mai veche ramură a algebrei abstracte, i-a urmat firesc, teoria algebrelor booleene.

Teorema de reprezentare a lui Cayley a reuşit să stabilească axiomele teoriei grupurilor abstracte, demonstrând că ele erau suficiente pentru a enunţa proprietăţile "algebrei substituţiilor". În algebrele booleene, era într-adevăr necesară o teoremă de reprezentare care să arate că axiomele înglobează „algebra claselor”. Dar aşa cum nici în teoria grupurilor proprietăţile referitoare la permutări nu se puteau aplica tuturor grupurilor, nici în algebrele booleene nu putea apărea un rezultat care să demonstreze că orice algebră Boole este izomorfă cu toate submulţimile unei mulţimi. Clasa algebrelor Boole cu această proprietate este caracterizată de următoarea teoremă: o algebră Boole este izomorfă cu algebra tuturor submulţimilor unei mulţimi dacă şi numai dacă este completă şi atomică.

Prin demonstrarea ei, logicienii A. Lindenbaum şi A. Tarski, i-au creat lui Stone o premisă importantă în descoperirea teoremei sale de reprezentare. Ei nu s-au referit însă la algebrele Boole neatomice, structuri pe care Stone le-a aprofundat.


În algebră, teorema de reprezentare a lui Stone conceptualizează reprezentarea structurilor prin obiecte mai simple. Ea este un caz particular al reprezentării algebrelor universale ca produs subdirect al unor obiecte dintr-o clasă fixată, rezultat cunoscut ca teorema lui Birkhoff: orice algebră dintr-o clasă ecuaţională este izomorfă cu un produs subdirect de algebre subdirect ireductibile. Eficienţa aplicării acestei teoreme depinde însă de cunoaşterea structurii algebrelor subdirect ireductibile. Cum în cazul algebrelor Boole, unicul obiect subdirect ireductibil este se poate enunţa cu uşurinţă teorema lui Stone. Astfel se reduce verificarea identităţilor dintr-o algebră Boole oarecare la calculul în cea mai simplă algebră Boole:

În logică, s-a demonstrat legătura puternică dintre teorema de completitudine tare a calculului propoziţional şi teorema de reprezentare a lui Stone, fiecare dintre aceste rezultate conducând la o demonstraţie a celuilalt. De aici poate fi extrasă ideea studierii relaţiei dintre completitudine şi reprezentare pentru orice sistem logic. Din momentul publicării ei, s-au propus numeroase demonstraţii ale teoremei lui Stone. Dintre acestea, cele mai cunoscute sunt:

  • demonstraţia algebrică: utilizează teoria ultrafiltrelor în algebrele Boole
  • demonstraţia metamatematică: utilizează un rezultat important din logică, teoreme de completitudine a calculului propoziţional.

Preliminarii[]

Fie B o algebră Boole.

Se numeşte filtru o mulțime nevidă pentru care:

i) pentru orice

ii) dacă şi atunci

Dacă F se numeşte filtru propriu. Un filtru este propriu dacă şi numai dacă Un filtru maximal propriu al lui B se numeşte ultrafiltru.

Dacă X este o submulţime a lui B, atunci filtrul generat de X este intersecţia tuturor filtrelor ce includ pe X. Cu alte cuvinte, filtrul generat de X este cel mai mic filtru (în sensul incluziunii) ce include pe X. Vom nota cu filtrul generat de X.

Mulţimea filtrelor proprii ale lui B este ordonată în raport cu incluziunea. Un ultrafiltru este un element maximal al acestei mulţimi. Cu alte cuvinte, un filtru propriu U este ultrafiltru dacă şi numai dacă pentru orice filtru propriu F, din rezultă

În cazul algebrelor Boole infinite, demonstrarea existenţei ultrafiltrelor impune invocarea axiomei lui Zorn:

Orice mulţime inductiv ordonată admite cel puţin un element maximal.


Teorema de existenţă a ultrafiltrelor.

Pentru orice filtru propriu F există n ultrafiltru U astfel încât

Demonstraţie.

Fie mulţimea filtrelor proprii ale lui B ce includ pe F. Evident, Vom arăta că este inductiv ordonată. Fie o familie total ordonată de filtre din Pentru orice sau Notăm Vom demonstra că G este filtru propriu. Dacă atunci există astfel încât şi Putem presupune de exemplu, că Atunci, deci A doua proprietate din definiţia filtrului se verifică imediat. Atunci G este un majorant al familiei şi este inductivă. Aplicând lema lui Zorn, rezultă existenţa unui ultrafiltru U ce include pe F.


Teorema de caracterizare a ultrafiltrelor.

Dacă F este un filtru propriu al lui B, atunci sunt echivalente următoarele afirmaţii:

i) F este ultrafiltru;

ii) F este filtru prim;

iii) pentru orice sau


Demonstraţie.

Presupunem prin absurd că F nu este prim, deci există astfel încât dar Atunci incluziunile stricte şi arată că filtrele şi nu sunt proprii, deci conţin pe 0. Din rezultă existenţa unui element astfel încât Analog, există astfel încât Atunci, există astfel încât Atunci Cum (din ) şi (din ipoteză), rezultă că Contradicţie, deci F este prim.



Presupunem prin absurd că există un filtru propriu G astfel încât Atunci există şi Folosind ipoteza, deci Contradicţie, deci F este ultrafiltru.


Pentru teorema de reprezentare a lui Stone există două forme:

Teorema I.

Pentru orice algebră Boole B există o mulţime nevidă X şi un morfism boolean injectiv

Teorema II.

Pentru orice algebră Boole B există o mulţime nevidă X şi un morfism boolean injectiv


Observaţii

1. Prima formă a teoremei reduce calculul boolean într-o algebră Boole oarecare la calcul cu mulţimi.

2. A doua formă a teoremei reduce calculul boolean într-o algebră Boole oarecare întâi la calcul în iar apoi calculul în se reduce la calcul în (operaţiile se fac pe componente).

Demonstraţia algebrică a teoremei lui Stone[]

Vom prezenta o demonstaţie a teoremei de reprezentare a lui Stone pe baza proprietăţilor ultrafiltrelor într-o algebră Boole.

Vom nota cu X mulţimea ultrafiltrelor lui B şi cu funcţia definită prin pentru orice Pentru orice şi pentru orice ultrafiltru U avem echivalenţele:

  (U este prim)


  (U este filtru)


  (din teorema de caracterizare a ultrafiltrelor, iii))


Am demonstrat că ceea ce arată că d este morfism boolean. Dacă atunci există un ultrafiltru U astfel încât deci şi Am arătat că implică deci Deci d este injectivă.

Sistemul formal al calculului propoziţional[]

Resurse online[]

Bibliografie[]

  • Bell, Machover, 1997 - John Bell, Moshé Machover, A Course in Mathematical Logic,

Amsterdam-New York-Oxford, Ed. North Holland Publishing Company, 1997, 599 p.

  • Georgescu A – George Georgescu, Curs de logică matematică şi computaţională, anul

I, semestrul I, capitolul Algebre Boole, netipărit, 135 p.

  • Georgescu B – George Georgescu, Curs de logică matematică şi computaţională, anul

I, semestrul I, capitolul Sistemul formal al calculului propoziţional, netipărit, 135 p.

  • Georgescu C – George Georgescu, Matematica teoremelor de completitudine, în

"Revista de filosofie", Tomul LV, Nr. 1-2, 2008, p. 71-85.

  • Johnstone 1982 – Peter T. Johnstone, Stone spaces, Cambridge-London-New York-

New Rochelle-Melbourne-Sidney, Ed. Cabridge University Press, 1982, 370 (-391) p.

  • Năstăsescu 1974 – Constantin Năstăsescu, Introducere în teoria mulţimilor, Bucureşti,

Ed. Didactică şi Pedagogică, 1974, 153 (-155) p.

Community content is available under CC-BY-SA unless otherwise noted.
Advertisement

Fan Feed

More Math Wiki