Fandom

Math Wiki

Teorema lui Stone

1.029pages on
this wiki
Add New Page
Comments0 Share

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.

Marshall Harvey Stone.jpg

Marshall Harvey Stone

Enunţ Edit

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 Edit

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 L_2=\{0, 1\}, \! 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: L_2 .\!

Î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 Edit

Fie B o algebră Boole.

Se numeşte filtru o mulțime nevidă F \subseteq B \! pentru care:

i) pentru orice x, y \in F, \; x \land y \in F; \!

ii) dacă x \le y \! şi x \in F \! atunci y \in F. \!

Dacă F \neq B,\! F se numeşte filtru propriu. Un filtru este propriu dacă şi numai dacă 0 \not \in F. \! 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 [X] \! 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 U \subseteq F \! rezultă U =F. \!

Î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 F \subseteq U. \!

Demonstraţie.

Fie \Sigma \! mulţimea filtrelor proprii ale lui B ce includ pe F. Evident, F \in \Sigma. \! Vom arăta că (\Sigma, \subseteq) \! este inductiv ordonată. Fie  (F_i)_{i \in I} \! o familie total ordonată de filtre din \Sigma. \! Pentru orice i, j \in I, \; F_i \subseteq F_j \! sau F_j \subseteq F_i. \! Notăm G = \bigcup_{i \in I} F_i. \! Vom demonstra că G este filtru propriu. Dacă x, y \in G \! atunci există i, j \in I \! astfel încât x \in F_i \! şi y \in F_j.\! Putem presupune de exemplu, că F_i \subseteq F_j. \! Atunci, x, y \in F_i, \! deci x \land y \in F_j \subseteq G. \! A doua proprietate din definiţia filtrului se verifică imediat. Atunci G este un majorant al familiei (F_i)_{i \in I} \! şi (\Sigma, \subseteq) \! 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 x \in B, \; \; x \in F \! sau \bar x \in F. \!


Demonstraţie.

i \Rightarrow ii: \!

Presupunem prin absurd că F nu este prim, deci există x, y \in B \! astfel încât x \lor y \in F, \! dar x, y \not \in F. \! Atunci incluziunile stricte F \subset [F \cup \{x\}) \! şi F \subset [F \cup \{y\}) \! arată că filtrele [F \cup \{x\}) \! şi [F \cup \{y\}) \! nu sunt proprii, deci conţin pe 0. Din 0 \in [F \cup \{x\}) \! rezultă existenţa unui element a \in F \! astfel încât a \land x =0. \! Analog, există b \in F \! astfel încât b \land y =0. \! Atunci, există b \in F \! astfel încât b \land y=0. \! Atunci 0 = (a \land x) \lor (b \land y) = (a \lor b) \land (a \lor y) \land (x \lor b) \land (x \lor y). \! Cum a \lor b, \; a \lor y, \; x \lor b \in F \! (din a, b \in F \!) şi x \lor y \in F \! (din ipoteză), rezultă că 0 \in F. \! Contradicţie, deci F este prim.


ii \Rightarrow iii: \!

x \lor \bar x = 1 \in F. \!


iii \Rightarrow i: \!

Presupunem prin absurd că există un filtru propriu G astfel încât F \subset G. \! Atunci există x \in G \! şi x \not \in F. \! Folosind ipoteza, \bar x \in F \subset G, \! deci 0 = x \land \bar x \in G. \! 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 d: B \rightarrow P(X). \!

Teorema II.

Pentru orice algebră Boole B există o mulţime nevidă X şi un morfism boolean injectiv d: B \rightarrow L_2^(X). \!


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 L_2^x, \! iar apoi calculul în L_2^x, \! se reduce la calcul în L_2 \! (operaţiile se fac pe componente).

Demonstraţia algebrică a teoremei lui Stone Edit

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 d: B \rightarrow P(X) \! funcţia definită prin d(x) = \{ U \in X \; \vdots \; x \in U \}, \! pentru orice x \in B. \! Pentru orice x, y \in B \! şi pentru orice ultrafiltru U avem echivalenţele:

\begin{matrix} U \in d(x \lor y) & \Leftrightarrow & x \lor y \in U \\ & \Leftrightarrow & x \in U \; sau \; y \in U \\ & \Leftrightarrow & U \in d(x) \; sau \; U \in d(y) \\ & \Leftrightarrow & U \in d(x) \cup d(y). \end{matrix} \!   (U este prim)


\begin{matrix} U \in d(x \land y) & \Leftrightarrow & x \land y \in U \\ & \Leftrightarrow & x \in U \; si \; y \in U \\ & \Leftrightarrow & U \in d(x) \; si \; U \in d(y) \\ & \Leftrightarrow & U \in d(x) \cap d(y). \end{matrix} \!   (U este filtru)


\begin{matrix} U \in d(\bar x) &  \Leftrightarrow \; \bar x \in U \\ & \Leftrightarrow \; x \not \in U \\ & \Leftrightarrow \; U \not \in d(x) \\ & \Leftrightarrow \; U \in C_{d(x)}  \end{matrix} \!   (din teorema de caracterizare a ultrafiltrelor, iii))


Am demonstrat că d(x \lor y) = d(x) \cup d(y), \; d(x \land y) = d(x) \cap d(y), \; d(\bar x) = C_{d(x)}, \! ceea ce arată că d este morfism boolean. Dacă x \neq 0 \! atunci există un ultrafiltru U astfel încât x \in U, \! deci U \in d(x) \! şi d(x) \neq \varnothing. \! Am arătat că d(x) \neq \varnothing \! implică x=0, \! deci d^{-1} (\varnothing) = \{ 0 \}. \! Deci d este injectivă.

Sistemul formal al calculului propoziţional Edit

Resurse online Edit

Bibliografie Edit

  • 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.

Also on Fandom

Random Wiki