teorema lui stone

7/23/2019 Teorema Lui Stone

http://slidepdf.com/reader/full/teorema-lui-stone 1/16

DOUĂ DEMONSTRAŢII ALE TEOREMEI DE REPREZENTARE A LUISTONE

Andra Jugănaru

I. Introducere

Scopul acestei lucrări este de a prezenta două demonstraţii ale teoremei următoare:orice algebră Boole este izomorfă cu o algebră Boole ale cărei elemente sunt părţi ale uneimulţimi. Acest rezultat, obţinut de Marshall H. Stone, în anul 193, a !ost considerat decisi"

pentru dez"oltarea matematicii secolului trecut.

#eorema a putut !i enunţată abia după ce, la s!$r%itul secolului al &'&(lea, cercetările pri"ind teoria )rupurilor au e"oluat, în condiţiile unui interes crescut al matematicienilor pentru abstractizarea al)ebrei. *robabil că teorema de reprezentare a lui +ale, publicată în

1--, care arăta că orice )rup abstract este abstract izomor! cu un )rup /concret0 de substituţiipermutări2, a !ost premisa de la care a pornit %i Stone.

ar teoriei )rupurilor, cea mai "eche ramură a al)ebrei abstracte, i(a urmat !iresc,teoria al)ebrelor booleene.

#eorema de reprezentare a lui +ale a reu%it să stabilească a4iomele teoriei )rupurilor abstracte, demonstr$nd că ele erau su!iciente pentru a enunţa proprietăţile /al)ebreisubstituţiilor0. 5n al)ebrele booleene, era într(ade"ăr necesară o teoremă de reprezentare caresă arate că a4iomele în)lobează /al)ebra claselor0. ar a%a cum nici în teoria )rupurilor

proprietăţile re!eritoare la permutări nu se puteau aplica tuturor )rupurilor, nici în al)ebrele booleene nu putea apărea un rezultat care să demonstreze că orice al)ebră 6oole esteizomor!ă cu toate submulţimile unei mulţimi. +lasa al)ebrelor 6oole cu această proprietateeste 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ă.*rin demonstrarea ei, lo)icienii A. 7indenbaum %i A. #ars8i, i(au creat lui Stone o

premisă importantă în descoperirea teoremei sale de reprezentare. i nu s(au re!erit însă laal)ebrele 6oole neatomice, structuri pe care Stone le(a apro!undat. ohnstone, 19-;: "ii(4"i2

5n al)ebră, teorema de reprezentare a lui Stone conceptualizează reprezentareastructurilor prin obiecte mai simple. a este un caz particular al reprezentării al)ebrelor uni"ersale ca produs subdirect al unor obiecte dintr(o clasă !i4ată, rezultat cunoscut cateorema lui 6ir8ho!!: orice algebră dintr-o clasă ecuaţională este izomorfă cu un produs

subdirect de algebre subdirect ireductibile. !icienţa aplicării acestei teoreme depinde însă decunoa%terea structurii al)ebrelor subdirect ireductibile. +um în cazul al)ebrelor 6oole, uniculobiect subdirect ireductibil este { }1,<; = L , se poate enunţa cu u%urinţă teorema lui Stone.Ast!el se reduce "eri!icarea identităţilor dintr(o al)ebră 6oole oarecare la calculul în cea maisimplă al)ebră 6oole: ; L .

5n lo)ică, s(a demonstrat le)ătura puternică dintre teorema de completitudine tare acalculului propoziţional %i teorema de reprezentare a lui Stone, !iecare dintre aceste rezultateconduc$nd la o demonstraţie a celuilalt. e aici poate !i e4trasă ideea studierii relaţiei dintrecompletitudine %i reprezentare pentru orice sistem lo)ic. =eor)escu +, ;<<-: 2

in momentul publicării ei, s(au propus numeroase demonstraţii ale teoremei luiStone. +ele două prezentate în continuare sunt, în opinia noastră, reprezentati"e pentru douădomenii importante ale matematicii, care ast!el se întrepătrund: al)ebra %i lo)ica. A%adar,

1



pentru demonstraţia al)ebrică, "om !olosi teoria ultra!iltrelor în al)ebrele 6oole, iar pentrudemonstraţia metamatematică, "om aplica un alt rezultat important din lo)ică: teorema decompletitudine a calculului propoziţional.

II. Prel!nar

*entru început, "om continua enunţarea c$tor"a de!iniţii %i rezultate preliminarii.

>ie B o al)ebră 6oole.

Se nume%te filtru o mulţime ne"idă B F ⊆ pentru care:i) pentru orice F y x ∈, , F y x ∈∧ ;ii) dacă y x ≤ şi F x∈ atunci F y∈ acă B F ≠ , F se nume%te filtru propriu. ?n !iltru F este propriu dacă %i numai

dacă F ∉< . F se nume%te filtru prim dacă F y x ∈∨ implică F x∈ sau F y∈ .

?n !iltru ma4imal propriu al lui B se nume%te ultrafiltru.acă ! este o submulţime a lui B , atunci filtrul generat de ! este intersecţia tuturor

!iltrelor ce includ pe ! . +u alte cu"inte, !iltrul )enerat de ! este cel mai mic !iltru însensul incluziunii2 ce include pe ! . @om nota cu [ ) ! !iltrul )enerat de ! =eor)escu A:112.

Mulţimea !iltrelor proprii ale lui B este ordonată în raport cu incluziunea. ?nultra!iltru este un element ma4imal al acestei mulţimi. +u alte cu"inte, un !iltru propriu "

este ultra!iltru dacă %i numai dacă pentru orice !iltru propriu F , din F " ⊆ rezultă F " = .5n cazul al)ebrelor 6oole in!inite, demonstrarea e4istenţei ultra!iltrelor impune

in"ocarea a4iomei lui orn: #rice mulţime inducti$ ordonată admite cel puţin un element maximal .

?rmătorul rezultat poartă numele de teorema de e4istenţă a ultra!iltrelor:

#eorema de e4istenţă a ultra!iltrelor %entru orice filtru propriu F există un ultrafiltru " astfel &nc't " F ⊆

(emonstraţie>ie Σ mulţimea !iltrelor proprii ale lui B ce includ pe F . "ident, Σ∈ F . @om

arăta că ( )⊆Σ, este inducti" ordonată. >ie ( ) ) ii F ∈ o !amilie total ordonată de !iltre din Σ .

*entru orice ) *i ∈, , *i F F ⊆ sau i * F F ⊆ . Botăm ) i

i F +∈

= . @om demonstra că + este un!iltru propriu. acă + y x ∈, atunci e4istă ) *i ∈, ast!el înc$t i F x∈ %i * F y∈ . *utem

presupune, de e4emplu, că *i F F ⊆ . Atunci, * F y x ∈, , deci + F y x * ⊆∈∧ . A doua proprietate din de!iniţia !iltrului se "eri!ică imediat. Atunci + este un maCorant al !amiliei

( ) ) ii

F ∈ %i ( )⊆Σ, este inducti"ă. Aplic$nd a4ioma lui orn, rezultă e4istenţa unui ultra!iltru

" ce include pe F .

;



?rmătorul rezultat poartă numele de teorema de caracterizare a ultra!iltrelor:

#eorema de caracterizare a ultra!iltrelor (acă F este un filtru propriu al lui B , atunci sunt eci$alente următoarele

afirmaţiii) F este ultrafiltru;ii) F este filtru prim;iii) pentru orice B x∈ , F x∈ sau F x∈

(emonstraţieiii ⇒ : *resupunem prin absurd că F nu este prim, deci e4istă B y x ∈, ast!el înc$t

F y x ∈∨ , dar F y x ∉, . Atunci incluziunile stricte { }[ ) x F F ∪⊂≠ %i { }[ ) y F F ∪⊂

≠ arată că!iltrele { }[ ) x F ∪ %i { }[ ) y F ∪ nu sunt proprii, deci conţin pe < . in { }[ ) x F ∪∈< rezultăe4istenţa unui element F a∈ ast!el înc$t <=∧ xa . Analo), e4istă F b∈ ast!el înc$t

<=∧ yb . Atunci ( ) ( ) ( ) ( ) ( ) ( ) y xb x yaba yb xa ∨∧∨∧∨∧∨=∧∨∧=< . +um F b x yaba ∈∨∨∨ ,, din F ba ∈, 2 %i F y x ∈∨ din ipoteză2, rezultă că F ∈< .

+ontradicţie, deci F este prim.iiiii ⇒ : F x x ∈=∨ 1 .iiii ⇒ : *resupunem prin absurd că e4istă un !iltru propriu + ast!el înc$t + F ⊂

≠ .Atunci e4istă + x∈ %i F x∉ . >olosind ipoteza, + F x ⊂∈ , deci + x x ∈∧=< . +ontradicţie,deci F este ultra!iltru.

*entru teorema de reprezentare a lui Stone e4istă două !orme:.eorema %entru orice algebră Boole B există o mulţime ne$idă ! şi un morfismboolean in*ecti$ ( ) ! Bd Ρ →: .

.eorema %entru orice algebră Boole B există o mulţime ne$idă ! şi un morfismboolean in*ecti$ ! L Bd ;: → .

Dbser"aţii:1. *rima !ormă a teoremei reduce calculul boolean într(o al)ebră 6oole oarecare la

calcul cu mulţimi.

;. A doua !ormă a teoremei reduce calculul boolean într(o al)ebră 6oole oarecare înt$ila calcul în ! L; , iar apoi calculul în !

L; se reduce la calcul în ; L operaţiile se !ac pecomponente2.

III. De!on"tra#a alge$rcă a teore!e lu Stone

5n această secţiune "om prezenta o demonstraţie a teoremei de reprezentare a lui Stone pe baza proprietăţilor ultra!iltrelor într(o al)ebră 6oole.

@om nota cu ! mulţimea ultra!iltrelor lui B %i cu ( ) ! Bd Ρ →: !uncţia de!inită prin( ) { }" x ! " xd ∈∈= , pentru orice B x∈ . *entru orice B y x ∈, %i pentru orice ultra!iltru

" a"em echi"alenţele:( ) y xd " ∨∈ ⇔ " y x ∈∨

3



⇔ " x∈ sau " y∈ " este prim2 ⇔ ( ) xd " ∈ sau ( ) yd " ∈ ⇔ ( ) ( ) yd xd " ∪∈ .

( ) y xd " ∧∈ ⇔ " y x ∈∧

⇔ " x∈ %i " y∈ " este !iltru2 ⇔ ( ) xd " ∈ %i ( ) yd " ∈ ⇔ ( ) ( ) yd xd " ∩∈ .

( ) xd " ∈ ⇔ " x ∈⇔ " x∉ din teorema de caracterizare a

ultra!iltrelor, iii)2 ⇔ ( ) xd " ∉

⇔ ( ) xd / " ∈

Am demonstrat că ( ) ( ) ( ) yd xd y xd =∨ , ( ) ( ) ( ) yd xd y xd ∩=∧ , ( ) ( ) xd / xd = , ceea

ce arată că d este mor!ism boolean. acă <≠ x atunci e4istă un ultra!iltru " ast!el înc$t" x∈ , deci ( ) xd " ∈ %i ( ) ≠ xd E. Am arătat că ( ) = xd E implică <= x , deci

1−d E

{ }<2 = . eci d este inCecti"ă.

I%. S"te!ul &or!al al calcululu 'ro'o(#onal

Sistemul !ormal al calculului propoziţional este descris prin trei componente: sinta4a,semantica %i al)ebra 7indenbaum(#ars8i.

Sinta4a calculului propoziţionalAl!abetul sistemului !ormal al calculului propoziţional este !ormat din următoarele

simboluri:1. "ariabile propoziţionale, notate ...,, 0$u , e"entual cu indiciF

;. simboluri lo)ice conectori2: ¬ simbolul de ne)aţie2 %i → simbolul de

implicaţie2.3. parantezele: ( ) [ ],, .Se "a presupune că mulţimea 1 a "ariabilelor propoziţionale este in!inită.*ornind de la aceste simboluri primiti"e, "om construi cu"intele asamblaCele2. *rin

de!iniţie, un cu"$nt este un %ir !init de simboluri primiti"e, scrise unul după altul.Se nume%te enunţ orice cu"$nt ϕ ce "eri!ică una dintre condiţiile următoare:i2 ϕ este o "ariabilă propoziţionalăFii2 e4istă un enunţ ψ ast!el înc$t ψ ϕ ¬= Fiii2 e4istă enunţurile ψ , θ ast!el înc$t θ ψ ϕ →= .@ariabilele propoziţionale se "or numi enunţuri atomice elementare2. @om nota cu 2

mulţimea enunţurilor. *entru 2 ∈ψ ϕ , introducem abre"ierile:ψ ϕ ψ ϕ →¬=∨ disCuncţia2

2 ψ ϕ ψ ϕ ¬→¬=∧ conCuncţia2( ) ( )ϕ ψ ψ ϕ ψ ϕ →∧→=↔ echi"alenţa2.

5n dez"oltarea sinta4ei calculului propoziţional "om urmări stabilirea unei noţiuni caresă reprezinte ade"ărurile !ormale ale sistemului %i a unei noţiuni care să spună ce este

in!erenţa sintactică.D a4iomă a sistemului !ormal al calculului propoziţional este un enunţ care are una din!ormele următoare:

G



A12 ( )ϕ ψ ϕ →→

A;2 ( )( ) ( ) ( )( ) χ ϕ ψ ϕ χ ψ ϕ →→→→→→A32 ( ) ( )ϕ ψ ψ ϕ →→¬→¬unde χ ψ ϕ ,, sunt enunţuri arbitrare.D teoremă !ormală este un enunţ ϕ ce "eri!ică una dintre condiţiile următoare:#12 ϕ este o a4iomă

#;2 e4istă un enunţ ψ ast!el înc$t ψ %i ϕ ψ → sunt teoreme ϕ

ϕ ψ ψ →, se nume%te

deducţie modus ponens2.@om nota cu . mulţimea teoremelor, iar !aptul că ϕ este o teoremă prin 3 ϕ .D demonstraţie !ormală a unui enunţ ϕ este un %ir !init de enunţuri nψ ψ ψ ,,,

;1

ast!el înc$t ϕ ψ =n %i pentru orice ni ≤≤1 se "eri!ică una dintre condiţiile următoare:12 iψ este o a4iomăF;2 e4istă doi indici, i *4 <, ast!el înc$t i *4 ψ ψ ψ →= .

>ie Γ o mulţime de enunţuri, %i ϕ un enunţ. @om spune că enunţul ϕ este dedusdin ipotezele Γ dacă una dintre condiţiile următoare este "eri!icată:

12 ϕ este a4iomăF;2 Γ ∈ϕ F32 e4istă un enunţ ψ ast!el înc$t ψ %i ϕ ψ → sunt deduse din ipotezele Γ modus

ponens2.D Γ (demonstraţie !ormală a lui ϕ este un %ir de enunţuri nψ ψ ψ ,,,

;1 ast!el

înc$t ϕ ψ =n %i pentru orice ni ≤≤1 se "eri!ică una dintre condiţiile următoare:12 iψ este o a4iomăF

;2 Γ ∈iψ F

32 e4istă doi indici, i *4 <, ast!el înc$t i *4 ψ ψ ψ →= . =eor)escu 6: 1(G2

Semantica sistemului !ormal L

*$nă acum am dez"oltat sistemul L la ni"el !ormal, !ără a atribui enunţurilor "alori deade"ăr. Acest lucru "a !i realizat în para)ra!ul de !aţă prin noţiunea de interpretare.

D interpretare a lui L este o !uncţie oarecare ;: L1 , → .

*ropoziţia 1

%entru orice interpretare ;: L1 , → există o funcţie unică;

H

: L 2 , → care satisface

proprietăţile următoarea) ( ) ( )u,u, =

H

pentru orice 1 u∈ ;

b) ( ) ( )ϕ ϕ HH

,, ¬=¬ pentru orice 2 ∈ϕ ;

c) ( ) ( ) ( )ψ ϕ ψ ϕ HHH

,,, →=→ pentru orice 2 ∈ψ ϕ ,

(emonstraţie

I



e!iniţia lui H

, se !ace prin inducţie, urmărind cazurile a)-c). emonstrarea unicităţii

lui H

, se !ace tot prin inducţie. >ie ;: L 2 g → ast!el înc$t:

aJ2 ( ) ( )u,u g = pentru orice 1 u∈ F bJ2 ( ) ( )ϕ ϕ g g ¬=¬ pentru orice 2 ∈ϕ ;

cJ2 ( ) ( ) ( )ψ ϕ ψ ϕ g g g →=→ pentru orice 2 ∈ψ ϕ ,

@om arăta că pentru orice 2 ∈α , ( ) ( )α α g , =H

. istin)em trei cazuri pentru α :

( 1 ∈α : ( ) ( ) ( )α α α H

,, g == F

( ϕ α ¬= : ( ) ( ) ( ) ( )α ϕ ϕ α HH

,, g g =¬=¬= pentru că ( ) ( )ϕ ϕ H

, g = ipoteza de inducţie2F

( ψ ϕ α →= : ( ) ( ) ( ) ( ) ( ) ( )α ψ ϕ ψ ϕ α HHH

,,, g g g =→=→= pentru că ( ) ( )ϕ ϕ H

, g = %i

( ) ( )ψ ψ H

, g = ipoteza de inducţie2.

+onsecinţe imediate. *entru orice 2 ∈ψ ϕ , a"em:

d2 ( ) ( ) ( )ψ ϕ ψ ϕ HHH

,,, ∨=∨ F

e2 ( ) ( ) ( )ψ ϕ ψ ϕ HHH

,,, ∧=∧ F

!2 ( ) ( ) ( )ψ ϕ ψ ϕ HHH

,,, ↔=↔ .

Dbser"aţie:

acă ;: L1 , → este o interpretare, atunci e4istă un unic mor!ism boolean

;

H

: L 2 , →care !ace comutati"ă următoarea dia)ramă:

@ 9 p

9 K H

hH

7 ;

h

h

L

−

, este de!init de ( )ϕ ϕ H

,, =

∧−

.

nunţul ϕ este ade"ărat în interpretarea ;: L1 , → dacă ( ) 1H

=ϕ , . ϕ este !als în

interpretarea ;: L1 , → dacă ( ) <H

=ϕ , . ?n enunţ ϕ este uni"ersal ade"ărat 5 ϕ 2 dacă este

ade"ărat în orice interpretare.

Dbser"aţie



'nterpretarea unui enunţ este "aloarea < sau 1 obţinută atunci c$nd tuturor "ariabilelor propoziţionale ce intră în componenţa sa le atribuim "alori din ; L . ?n enunţ uni"ersalade"ărat "a a"ea "aloarea 1 pentru orice "alori din ; L luate de "ariabilele propoziţionale ceapar în ϕ . 6ell, Macho"er, 199: 1I(1I92

*ropoziţia ; %entru orice enuţ ϕ , 3 ϕ implică 5 ϕ .

+orolar 3 %entru orice enunţ ϕ nu putem a$ea 3 ϕ şi 3 ϕ ¬ .

*ropoziţie G %entru orice enunţ ϕ a$em 3 ϕ ⇔ 5 ϕ .

Al)ebra 7indenbaum(#ars8iAl)ebra 7indenbaum(#ars8i este o al)ebră 6oole asociată canonic sistemului !ormal

L . *roprietăţile sintactice ale lui L se "or re!lecta în proprietăţi booleene, realiz$ndu(setrecerea de la sinta4ă la al)ebră.

7ema 1. %entru orice enunţuri ψ ϕ , a$em 3 ϕ şi 3 ψ ⇔ 3 ψ ϕ ∧

Se de!ine%te relaţia binară pe mulţimea 2 a enunţurilor lui L :ϕ ψ ⇔

def

3 ψ ϕ ↔

7ema ; este o relaţie de eci$alenţă pe 2 .

7ema 3

≤ este o relaţie de ordine pe H 2

7ema G

( ≤,H

2 este o latice distributi$ă &n care∧∧∧∧=

ψ ϕ ψ ϕ ,in! şi∨∧∧∨=

ψ ϕ ψ ϕ ,sup

7ema I

H 2 este o algebră Boole

Al)ebra 6oole ( 1,<,,,,H

¬∧∨ 2 poartă numele de al)ebra 7indenbaum(#ars8i,

asociată sistemului !ormal L .

Dbser"aţie:

acă notămH

: 2 2 p → surCecţia canonică ( )∧

=ϕ ϕ p pentru orice 2 ∈ϕ 2 atunci

pentru orice 2 ∈ψ ϕ , sunt "eri!icate condiţiile următoare:a2 ( ) ( ) ( )ψ ϕ ψ ϕ p p p ∨=∨ F



b2 ( ) ( ) ( )ψ ϕ ψ ϕ p p p ∧=∧ Fc2 ( ) ( )ϕ ϕ p p ¬=¬ Fd2 ( ) ( ) ( )ψ ϕ ψ ϕ p p p →=→ Fe2 ( ) ( ) ( )ψ ϕ ψ ϕ p p p ↔=↔ .

)alităţile a), b) sunt chiar de!iniţiile operaţiilor din H 2

, d) re"ine la a arăta că ( ) ( )ψ ϕ ψ ϕ ¬→¬↔→ , iar e) rezultă din b) %i d). +ele cinci e)alităţi de mai sus arată modul încare conectorii sunt con"ertiţi în operaţii booleene.

7ema %entru orice 2 ∈ϕ , 3 ϕ dacă şi numai dacă 1=

∧

ϕ (emonstraţie#rebuie să demonstrăm 3 ϕ ⇔ 3 ϕ ϕ ϕ ¬∨↔ . *resupunem 3 ϕ . +um 3

( )ϕ ϕ ϕ ϕ →¬∨→ con!orm 672, rezultă 3 ( ) ϕ ϕ ϕ →¬∨ . #otdeauna are loc 3 ( )ϕ ϕ ϕ ¬∨→ , deci3 ϕ ϕ ϕ ¬∨↔ . Neciproc, presupunem că 3 ϕ ϕ ϕ ¬∨↔ . ar 3 ϕ ϕ ¬∨ principiul terţului

e4clus2, deci prin modus ponens 3 ϕ .

Dbser"aţie Lema 8 o!eră o metodă al)ebrică pentru "eri!icarea dacă un enunţ este teoremă

!ormală.

>ie Σ o mulţime de enunţuri ale lui L Se de!ine%te următoarea relaţie binară pe 2 :Σ⇔Σψ ϕ H 3 ψ ϕ ↔ ⇔ Σ 3 ψ ϕ → %i Σ 3 ϕ ψ → .

*roced$nd analo) ca mai sus, se poate arăta că ΣH este o relaţie de echi"alenţă pe %i

căH

2 are o structură canonică de al)ebră 6oole, numită al)ebra 7indenbaum(#ars8i a lui

Σ . Botăm Σϕ clasa de echi"alenţă a lui 2 ∈ϕ . Atunci:

( )Σ

∨=Σ∨Σψ ϕ ψ ϕ F

( )Σ

∧=

Σ∧

Σψ ϕ ψ ϕ F

Σ¬=

Σ¬ ϕ ϕ F

⇔Σ≤Σψ ϕ

Σ 3 ψ ϕ → F

⇔=Σ 1ϕ Σ 3 ϕ .

*entru =Σ E obţinem al)ebra 7indenbaum(#ars8iH

2 . =eor)escu 6: -(92

Dbser"aţieemonstraţia al)ebrică a teoremelor de completitudine utilizează teorema de

reprezentare a lui Stone aplicată al)ebrei 7indenbaum(#ars8i.

%. Teore!a de co!'lettudne

#eorema de completitudine are ast!el două !orme:

-



1. 3 ϕ dacă şi numai dacă 5 ϕ ;. Γ 3 ϕ dacă şi numai dacă Γ 5 ϕ

#eorema de completitudine răspunde unor probleme naturale. *e de o parte, a"emenunţurile demonstrabile sintactic teoremele !ormale2, iar pe de altă parte a"em enunţurile

uni"ersal ade"ărate. >iresc, se pune problema comparării acestor !i)uri de enunţuri, ceea ce serealizează prin teorema de completitudine, care stabile%te echi"alenţa lor. e asemenea,teorema de completitudine ne o!eră un procedeu comod de "eri!icare a !aptului că un enunţeste o teoremă !ormală procedeu ce poate !i pro)ramat2.

emonstraţia prezentată mai sus este de natură al)ebrică. 'deea !undamentală oreprezintă trecerea la al)ebra 7indenbaum(#ars8i %i in"ocarea teoremei lui Stone pentru)ăsirea interpretării necesare în demonstraţie. Această trecere prin al)ebră aruncă o luminămai completă asupra relaţiei dintre sinta4ă %i semantică, relaţie care are de !apt %i un substratal)ebric. *e scurt, sistemul !ormal L a !ost analizat din perspecti"a triun)hiului:

%I. De!on"tra#a !eta!ate!atcă a teore!e lu Stone

5n această secţiune este prezentată, în trei etape, o demonstraţie a teoremei dereprezentare a lui Stone pe baza teoremei de completitudine e4tinsă.

a2 >ie sistemul !ormal al calculului propoziţional L în care B1 = , 2 este mulţimea

enunţurilor, H 2 este al)ebra 7indenbaum(#ars8i, H: 2 2 p → este surCecţia canonică. @rem

să arătăm că e4istă un mor!ism boolean surCecti" B 2 f →H

: ast!el înc$t următoarea dia)ramă

să !ie comutati"ă:

9



6 p K 6

9 K H

6

1 6 !

*entru orice interpretare B B, →: e4istă %i este unică o !uncţie B 2 , →:H ast!el înc$t

a2 ( ) x x, =H

pentru orice B x∈ F

b2 ( ) ( )ϕ ϕ HH

,, ¬=¬ pentru orice 2 ∈ϕ F

c2 ( ) ( ) ( )ψ ϕ ψ ϕ HHH

,,, →=→ pentru orice 2 ∈ψ ϕ , .

(emonstraţiee!iniţia lui H

, se !ace prin inducţie, urmărind clauzele a)-c). emonstraţia

unicităţii luiH

, se !ace tot prin inducţie. >ie B 2 g →: ast!e înc$t:aJ2 ( ) ( ) x, x g = pentru orice B x∈ F

bJ2 ( ) ( )ϕ ϕ g g =¬ pentru orice 2 ∈ϕ FcJ2 ( ) ( ) ( )ψ ϕ ψ ϕ g g g →=→ pentru orice 2 ∈ψ ϕ , .

@om arăta că pentru orice 2 ∈α , ( ) ( )α α g , =H

. istin)em trei cazuri:

( B∈α : ( ) ( ) ( )α α α H

,, g == F

( ϕ α ¬= : ( ) ( ) ( ) ( )α ϕ ϕ α HH

,, g g =¬=¬= pentru că ( ) ( )ϕ ϕ H

, g = ipoteza de

inducţie2F

( ψ ϕ α →= : ( ) ( ) ( ) ( ) ( ) ( )α ψ ϕ ψ ϕ α HHH

,,, g g g =→=→= pentru că ( ) ( )ϕ ϕ H

, g = %i

( ) ( )ψ ψ H

, g = ipoteza de inducţie2.

+onsecinţe imediate. *entru orice 2 ∈ψ ϕ , :d2 ( ) ( ) ( )ψ ϕ ψ ϕ

HHH

,,, ∨=∨ F

e2 ( ) ( ) ( )ψ ϕ ψ ϕ HHH

,,, ∧=∧ F

!2 ( ) ( ) ( )ψ ϕ ψ ϕ HHH

,,, ↔=↔ .

Dbser"aţie

1<



acă B B, →: este o interpretare, atunci e4istă %i este unic un mor!ism boolean

B 2 f →H

: , de!init prin ( )ϕ ϕ H

, f =

∧ pentru orice 2 ∈ϕ , ast!el înc$t următoarea dia)ramă să

!ie comutati"ă:

6 p K 6

9 K H

6

1 6 !

Atunci ( )

=

==

∧∧−

1O11 ϕ ϕ f f F este un !iltru propriu înH

2 %i a"em un izomor!ism

boolean B

2

→>

H:λ ,

=

∧∧

ϕ ϕ λ f F , pentru orice 2 ∈ϕ .

b2 >ie F un !iltru propriu înH

2 e"entual cel de la punctul a)2 %i ( ) F p 1−=∆ . ∆

este un sistem deducti" consistent în B %i pentru orice 2 ∈ψ ϕ , au loc echi"alenţele:

⇔∆∈↔⇔∈↔⇔∈↔⇔=∧∧∧

∧∧

ψ ϕ ψ ϕ ψ ϕ ψ ϕ F F

F F ∆ 3 ∆=∆⇔↔ ψ ϕ ψ ϕ , unde ∆

ϕ este

clasa de echi"alenţă a lui ϕ în raport cu ∆H . acă∆

=∆ H 2 2 este al)ebra 7indenbaum(

#ras8i asociată lui ∆ , atunci echi"alenţele spun că !uncţia(

∆→Φ 2

2

>H: de!inită prin

∆=

Φ

∧

ϕ ϕ F

pentru orice 2 ∈ϕ este un izomor!ism boolean.

11



c2 *resupunem că ∆ este o mulţime consistentă e"entual cea de la b)2 %i ! este

mulţimea modelelor lui ∆ . , L1 , ! O:P ;→= 5 Q∆ .

in teorema de completitudine rezultă ≠ ! E. *entru orice 2 ∈ψ ϕ , a"emechi"alenţele: ∆⇔∆=∆

ψ ϕ 3 ∆⇔↔ψ ϕ 5 ( ) 1H

=↔⇔↔ ψ ϕ ψ ϕ , pentru orice ! ,∈

( ) ( ) 1HH

=↔⇔ ψ ϕ ,, pentru orice ! ,∈ ( ) ( )ψ ϕ HH

,, =⇔ pentru orice ! ,∈ .

e!inim !uncţia ! L 2

;: →∆λ prin ( ) ( )ϕ ϕ λ

H

,, =

∆ pentru orice 2 ∈ϕ %i pentru orice

! ,∈ . chi"alenţele arată că λ este bine de!inită %i inCecti"ă, deci λ este mor!ism booleaninCecti".

*rin urmare, combin$nd punctele a), b), c) din demonstraţie, putem considera

compunerea următoarelor !uncţii: ( ) ! L 2

2

B;

H

>H →

∆ → →

Φ λ .

Se poate obser"a că !uncţia ! L Bd ;: → este un mor!ism boolean inCecti".

1;



%II. )onclu(

#eorema de reprezentare a lui Stone este unul dintre cele mai importante rezultaterecente din teoria al)ebrelor booleene. *rin ea, calculul într(o al)ebră 6oole oarecare se

reduce la calculul în al)ebra 6oole standard { }1,<; = L .5n această lucrare au !ost prezentate două demonstraţii ale teoremei lui Stone:

• prima, de natură al)ebrică1, se bazează pe proprietăţile ultra!iltrelor într(oal)ebră 6ooleF

• a doua, de natură metamatematică;, !olose%te ca instrument teorema decompletitudine e4tinsă.

5n !apt, teorema de reprezentare a lui Stone este "arianta al)ebrică a teoremei decompletitudine. Mai mult, demonstraţiile celor enunţuri sunt do"ada echi"alenţei lor matematice. *arcur)$ndu(le, obser"ăm că !iecare dintre ele poate !i demonstrat pe bazaceluilalt. 'ar într(o teorie a mulţimilor din care a4ioma ale)erii este e4clusă Băstăsescu, 19G:

-(--2, teorema de reprezentare a lui Stone %i teorema de completitudine sunt enunţuri lo)icechi"alente.

1 @. supra, p. 3.; @. supra, p. 9.

13



*$logra&e

6ell, Macho"er, 199 ( ohn 6ell, MoshR Macho"er, 6 /ourse in 9atematical Logic,Amsterdam(Be Tor8(D4!ord, d. Borth Holland *ublishin)

+ompan, 199, I99 p.

=eor)escu A U =eor)e =eor)escu, /urs de logică matematică şi computaţională, anul , semestrul , capitolul 6lgebre Boole, netipărit, 13I p.

=eor)escu 6 U =eor)e =eor)escu, /urs de logică matematică şi computaţională, anul , semestrul , capitolul :istemul formal al calculului propoziţional ,netipărit, 13I p.

=eor)escu + U =eor)e =eor)escu, 9atematica teoremelor de completitudine, în/Ne"ista de !iloso!ie0, #omul 7@, Br. 1(;, ;<<-, p. 1(-I.

ohnstone 19-; U *eter #. ohnstone, :tone spaces, +ambrid)e(7ondon(Be Tor8( Be Nochelle(Melbourne(Sidne, d. +abrid)e ?ni"ersit *ress,19-;, 3< (3912 p.

Băstăsescu 19G U +onstantin Băstăsescu, ntroducere &n teoria mulţimilor , 6ucure%ti,d. idactică %i *eda)o)ică, 19G, 1I3 (1II2 p.

1G



ANE+E

5n această secţiune am inclus demonstraţia teoremei de completitudine e4tinsă, baz$ndu(ne pe proprietăţile calculului propoziţional prezentate în partea a patra a lucrării.3

*ropoziţie 1 %entru orice enunţ ϕ , 3 ϕ implică 5 ϕ .

(emonstraţie

@om arăta că dacă 3 ϕ , atunci ( ) 1H

=ϕ , pentru orice interpretare ;: L1 , → . Se

procedează prin inducţie asupra modului cum s(a de!init ϕ . +onsiderăm înt$i cazula4iomelor:

A12 ϕ este de !orma ( )α β α →→ .( ) ( ) ( ) ( ) ( ) ( ) ( ) 1

HHHHHHH

=∨¬∨¬=

→→= α β α α β ϕ ,,,,,a,, .

A;2 ϕ este de !orma ( )( ) ( ) ( )( )γ α β α γ β α →→→→→→ .

acă notăm ( )α H

, x = , ( )β H

, y = , ( )γ H

, z = atunci

( ) ( )( ) ( ) ( )( ) 1

H

=→→→→→→= z x y x z y x, ϕ după cum arată o simplă "eri!icare în ; L .

A32 ϕ este de !orma ( ) ( )α β β α →→¬→¬

ste su!icient să probăm ( ) ( ) 1=→→→ x y y x în ; L .*resupunem acum că ϕ a !ost obţinut prin modus ponens din 3 ψ , 3 ϕ ψ → .

'poteza inducţiei se reduce la ( ) 1H

=ψ , %i la ( ) 1H

=→ ϕ ψ , . Atunci:

( ) ( ) ( ) ( )ϕ ϕ ϕ ψ

HHHH

11 ,,,, =→=→= %i demonstraţia s(a încheiat.

+orolar 1 %entru orice enunţ ϕ nu putem a$ea 3 ϕ şi 3 ϕ ¬ . (emonstraţieacă e4istă un enunţ ϕ ast!el înc$t ϕ %i ϕ ¬ atunci pentru orice interpretare

am a"ea ( ) 1H

=ϕ , %i ( ) 1H

=¬ϕ , . +ontradicţie.

*ropoziţie ; %entru orice enunţ ϕ a$em 3 ϕ ⇔ 5 ϕ .

(emonstraţie( )⇒ din %ropoziţia ( )⇐ *resupunem că ϕ nu este teoremă !ormală. #rec$nd la al)ebra 7indenbaum(

#ars8i H 2 %i aplic$nd lema 8 G, enunţată în partea a patra a lucrării, rezultă 1≠

∧

ϕ . Aplicăm

teorema de reprezentare a lui Stone pentru al)ebra 6ooleH

2 . Atunci e4istă o mulţime

ne"idă ! %i un mor!ism boolean inCecti" ! L 2 d

;H: → . in inCecti"itatea lui d , rezultă

1≠

∧ϕ d în !

L; . eci e4istă ! x∈ ast!el înc$t ( ) 1≠

∧

xd ϕ în ; L .

3 @. supra, p. G.G @. supra, p. -.

1I



+onsiderăm proiecţia ;;: L L ! x →Π de!inită prin ( ) ( ) x f f x =Π pentru orice ! L f ;∈ .

xΠ este mor!ism boolean. Să luăm interpretarea ;: L1 , → dată de compunerea

următoarelor mor!isme booleene: ;;H L L 2 2 1 x ! d p

→ → → ⊆ Π . @om stabili că: ( ) ( ) xd ,

= ∧α α

H

.

emonstrăm prin inducţie asupra enunţului α .a2 1 ∈α

( ) ( ) ( )( )( ) ( ) xd pd ,, x

=Π==

∧α α α α

H

.

b2 β α ¬= %i ipoteza de inducţie !uncţionează pentru β , deci ( ) ( ) xd ,

= ∧β β

H

. Atunci

( ) ( ) ( ) ( ) ( ) ( ) ( ) xd xd xd xd xd ,,

=

¬=

¬=

¬=

=¬=

∧∧∧∧∧α β β β β β α

HH

.

c2 γ β α →= %i ipoteza de inducţie !uncţionează pentru β %i γ ,

deci ( ) ( ) xd ,

= ∧β β

H

%i ( ) ( ) xd ,

= ∧γ γ

H

.

Atunci:

( ) ( ) ( ) ( ) ( ) ( )

( ) ( ) ( ) xd xd xd

xd d xd xd ,,,

=

→=

→

=

→

=

→

=→=

∧∧∧∧

∧∧∧∧

α γ β γ β

γ β γ β γ β α HHH

*roprietatea a !ost demonstrată. Aplic$nd(o pentru ϕ α = rezultă ( ) ( ) 1H

≠

= ∧

xd , ϕ ϕ ,

deci ϕ nu este tautolo)ie.

1

teorema lui stone

Documents