În teoria mulțimilor , ansamblul părților unui set , echipat cu operațiile de intersecție , unire și trecere la complement , are o structură de algebră booleană . Din aceasta se pot deduce alte operații, cum ar fi diferența setată și diferența simetrică ...
Algebra seturi studiate aritmetică a acestor operațiuni ( a se vedea „ ensemblist Operațiunea “ pentru operațiuni care nu părăsesc permanent toate părțile unui întreg).
De-a lungul articolului, seturile luate în considerare trebuie să fie incluse într- un set U dat . Incluziunea este o relație de ordine (parțială) notată „⊂” sau „⊆” și definită pe setul de părți din U , notată P ( U ), prin:
A ⊂ B dacă și numai dacă ∀ x ∈ U ( x ∈ A ⇒ x ∈ B ).Egalitatea este definită prin extensionalitate, două seturi sunt egale atunci când au aceleași elemente, adică:
A = B dacă și numai dacă ∀ x ∈ U ( x ∈ A ⇔ x ∈ B ).sau
A = B dacă și numai dacă A ⊂ B și B ⊂ A .Prin urmare, următoarele proprietăți corespund, pentru egalități, echivalențelor din calculul propozițional din care sunt deduse. Acestea pot fi vizualizate cu diagrame Venn , un mod schematic de a descrie toate cazurile posibile pentru apartenența unui element la un număr finit (și suficient de redus) de seturi și care, prin urmare, poate permite, de asemenea, să descrie demonstrații egalitatea sau incluziunea.
În mod similar, incluziunile se reduc la implicații.
Uniunea set de A și B , notat " A U B " ( a se citi " A unire B "), este un set de elemente aparținând A sau B :
care înseamnă :
x ∈ A ∪ B dacă și numai dacă x ∈ A sau x ∈ B . ProprietățiSetul U furnizat împreună cu uniunea are următoarele proprietăți (pentru toate subseturile A , B , C din U ):
Setul A ∪ B este superioară legat de includerea celor două seturi A și B , adică conține A și B , și este conținută în orice set care conține A și B :
Prin urmare, includerea este definită din întâlnire:
A ⊂ B dacă și numai dacă A ∪ B = B .Setul de intersecție al lui A și B , notat „ A ∩ B ” (citiți „ A inter B ”) este setul de elemente ale lui A care sunt și elemente ale lui B și anume:
care înseamnă :
x ∈ A ∩ B dacă și numai dacă x ∈ A si x ∈ B .Se spune că două seturi care nu au element în comun, adică intersecția lor este goală, sunt disjuncte .
ProprietățiProprietățile intersecției sunt similare cu cele ale uniunii. Spunem că sunt duale dintre acestea, pentru că le obținem înlocuind semnul uniunii cu cel al intersecției și, dacă este necesar, schimbând ∅ și U , incluziunea și reciprocitatea acesteia. Pentru toate subseturile A , B , C din U avem următoarele proprietăți:
Setul A ∩ B este legat mai mică pentru includerea celor două seturi A și B , adică este inclus în A și B , și că acesta conține orice set inclus în același timp , în A și B :
Acest lucru permite includerea să fie definită de la intersecție de data aceasta:
A ⊂ B dacă și numai dacă A ∩ B = A .Cele două operații de reunire și intersecție sunt distributive una față de alta, adică avem următoarele două proprietăți, pentru toate mulțimile A , B , C :
Pe fiecare parte a primei egalități există un set și vrem să arătăm că aceste seturi sunt egale, adică să arătăm că orice element aparține primului dacă și numai dacă aparține celui de-al doilea. Nota respectiv a , b , c propuneri , , . Potrivit distributivitatea de în ceea ce privește ( pe care le putem verifica pe un tabel de adevăr ) avem
ceea ce traduce exact echivalența dorită:
Demonstrarea celei de-a doua egalități este identică, prin schimb și .
Este posibil să generalizăm reuniunea la un număr finit de mulțimi: revenim la cazul a două mulțimi prin reuniune binară succesivă și asociativitatea reuniunii asigură faptul că ordinea nu contează. La fel și pentru intersecție.
Dar este, de asemenea, posibil să generalizați aceste operații într-o familie nu neapărat finită de mulțimi.
Unirea unei familii de seturi este definită de:
.Această definiție nu depinde de U . Reuniunea unei familii goale este întregul gol.
Intersecția unei familii de mulțimi este definită de:
.Definiția de mai sus nu depinde de setul U decât atunci când familia este goală. în acest din urmă caz, intersecția familiei goale este prin definiție setul de referință U , care rămâne compatibil cu proprietățile intersecției. Nu putem defini „în absolut” (fără un set de referință) intersecția unei familii goale.
Unele dintre proprietățile reuniunii și ale intersecției binare se generalizează la caz infinit. Acum sunt în joc proprietățile calculului predicatelor (și nu numai ale calculului propozițional).
Un set de referință U dat, complementară a submulțimea A la U (adică în ceea ce privește U ) este un set de elemente de U , care nu aparțin A . Se notează cu U - A , A , A c sau chiar :
care înseamnă
x ∈ A c daca si numai daca x ∈ U și x ∉ A .Complementul A depinde de setul de referință U . Se caracterizează și prin cele două egalități:
A ∩ A c = ∅ și A ∪ A c = U .Operația suplimentară de trecere este involutiv adică ( A c ) c = A .
Trecerea la complementar inversează relația de incluziune:
A ⊂ B dacă și numai dacă B c ⊂ A cși, prin urmare, schimbă reuniunea și intersecția, care sunt limita superioară și cea inferioară, acestea sunt legile lui De Morgan :
( A ∩ B ) c = A c ∪ B c ; ( A ∪ B ) c = A c ∩ B c .O structură ordonată care, ca și setul de părți ale lui U prevăzute cu operațiile binare de reunire și intersecție, ale operației de trecere la complement și ale celor două elemente distincte verificare și U , satisface proprietățile acestor operații enumerate până la „acum se numește algebră booleană .
Diferența setată a lui A și B notată „ A \ B ” (citiți „ A minus B ”) este setul de elemente ale lui A care nu aparțin lui B și anume:
.Diferența dintre A și B în U este definită din complementară A ∩ B c , și apoi ( A ∩ B c ) c = A c ∪ B .
Dacă B este inclus în A , atunci A \ B este, de asemenea, scris „ A - B ” (citiți din nou „ A minus B ”) și este numit complementar cu B în A (sau relativ la A ). Găsim noțiunea de complementar de mai sus, care este complementar relativ la U :
. Proprietățile diferențeiAvem :
x ∈ A \ B dacă și numai dacă x ∈ A și x ∉ B x ∉ A \ B dacă și numai dacă x ∈ A ⇒ x ∈ BAșadar :
A \ B = ∅ dacă și numai dacă A ⊂ B .Proprietățile diferenței se obțin din definiția acesteia și din cele ale uniunii intersecției și complementului. De exemplu, prima care urmează este o serie de intersecții, în timp ce a doua folosește o lege De Morgan și distributivitatea intersecției pe uniune.
.
Diferența simetrică a lui A și B , notată „ A Δ B ” (citiți „ A delta B ”) este setul de elemente care aparțin fie lui A, fie lui B , dar nu și ambelor în același timp. Aceasta este diferența dintre A ∪ B și A ∩ B . Poate fi scris sub diferite forme:
.Avem :
x ∈ A Δ B dacă și numai dacă x ∈ A sau x ∈ B (sau exclusiv) x ∉ A Δ B dacă și numai dacă x ∈ A ⇔ x ∈ Bastfel diferența simetrică a două seturi este goală dacă și numai dacă cele două seturi sunt egale:
A Δ B = ∅ dacă și numai dacă A = B . Proprietăți ale diferenței simetriceSetul de părți ale lui U furnizate cu operația de diferență simetrică este un grup comutativ , cu ∅ pentru elementul neutru și unde fiecare subset al lui U este propriul său opus, adică pentru toate subseturile A , B , C ale U , avem:
O consecință este regularitatea: dacă A Δ B = A Δ C , apoi B = C .
Setul de părți ale lui U furnizat, pe lângă diferența simetrică, cu intersecția, este un inel comutativ unitar , adică, pe lângă proprietățile de asociativitate și comutativitate ale intersecției, și că U este un element neutru
Diferența simetrică, spre deosebire de uniune, nu este distributivă în raport cu intersecția.
Este o proprietate generală a algebrelor booleene că o operație definită ca diferență simetrică (cu uniunea intersecția și trecerea la complement) permite definirea unei structuri inelare, uneori numită inel boolean. Alte proprietăți, comune tuturor algebrelor booleene, sunt verificate ca:
A c = U Δ A și deci A c Δ A = U .sau ( A Δ B ) c = A c Δ B = A Δ B c .
Din punct de vedere axiomatic, în teoria mulțimilor tot ceea ce precede se dezvoltă din axioma extensionalității (egalitatea a două mulțimi), care garantează în special unicitatea construcțiilor introduse și a schemei axiomelor de înțelegere , care garantează existența lor , toate seturile introduse fiind definite ca un subset al unui set dat U.