Nella teoria degli insiemi , l' insieme delle parti di un insieme , dotato delle operazioni di intersezione , unione e passaggio al complemento , ha una struttura algebrica booleana . Altre operazioni possono essere dedotte da questo, come la differenza di insieme e la differenza simmetrica ...
L' algebra degli insiemi ha studiato l'aritmetica di queste operazioni (vedere " Elenco di insieme delle operazioni " per le operazioni che non lasciano permanenti tutte le parti di un intero).
Durante tutto l'articolo, i gruppi considerati sono tutti dovrebbero essere inclusi in un dato insieme U . L'inclusione è una relazione d'ordine (parziale) annotata "⊂" o "⊆", e definita sull'insieme di parti di U , annotata P ( U ), da:
A ⊂ B se e solo se ∀ x ∈ U ( x ∈ A ⇒ x ∈ B ).L'uguaglianza è definita dall'estensionalità, due insiemi sono uguali quando hanno gli stessi elementi, vale a dire che:
A = B se e solo se ∀ x ∈ U ( x ∈ A ⇔ x ∈ B ).o
A = B se e solo se A ⊂ B e B ⊂ A .Le seguenti proprietà corrispondono quindi, per le uguaglianze, alle equivalenze nel calcolo proposizionale da cui sono dedotte. Possono essere visualizzati con i diagrammi di Venn , un modo schematico di descrivere tutti i possibili casi di appartenenza di un elemento a un numero finito (e sufficientemente ridotto) di insiemi, e che può quindi consentire anche di descrivere dimostrazioni di uguaglianza o inclusione.
Allo stesso modo, le inclusioni si riducono a implicazioni.
L'insieme di unione di A e B , indicato con " A U B " (leggi " A unione B "), è l'insieme di elementi appartenenti ad A o B :
che significa :
x ∈ A ∪ B se e solo se x ∈ A oppure x ∈ B . ProprietàL'insieme U fornito con l'unione ha le seguenti proprietà (per tutti i sottoinsiemi A , B , C di U ):
L'insieme A ∪ B è il limite superiore per l'inclusione dei due insiemi A e B , cioè contiene A e B , ed è contenuto in ogni insieme contenente A e B :
Pertanto l'inclusione è definita dall'incontro:
A ⊂ B se e solo se A ∪ B = B .L'insieme di intersezione di A e B , indicato con " A ∩ B " (leggi " A inter B ") è l'insieme di elementi di A che sono anche elementi di B , vale a dire:
che significa :
x ∈ A ∩ B se e solo se x ∈ A e x ∈ B .Due insiemi che non hanno elementi in comune, cioè la loro intersezione è vuota, si dice che siano disgiunti .
ProprietàLe proprietà dell'incrocio sono simili a quelle dell'incontro. Diciamo che sono duali di questi, perché li otteniamo sostituendo il segno di unione con quello di intersezione, e se necessario scambiando ∅ e U , l'inclusione e il suo reciproco. Per tutti i sottoinsiemi A , B , C di U abbiamo le seguenti proprietà:
L'insieme A ∩ B è il limite inferiore per l'inclusione dei due insiemi A e B , cioè è incluso in A e in B , e che contiene qualsiasi insieme incluso contemporaneamente in A e in B :
Ciò consente questa volta di definire l'inclusione dall'incrocio:
A ⊂ B se e solo se A ∩ B = A .Le due operazioni di unione e di intersezione sono distributive l' una rispetto all'altra, cioè abbiamo le seguenti due proprietà, per tutti gli insiemi A , B , C :
Su ogni lato della prima uguaglianza c'è un insieme e vogliamo mostrare che questi insiemi sono uguali, cioè mostrare che qualsiasi elemento appartiene al primo se e solo se appartiene al secondo. Nota rispettivamente un , b , c proposte , , . Secondo la distributività del rispetto a (che possiamo verificare su una tavola di verità ) che abbiamo
che riflette esattamente l'equivalenza desiderata:
La dimostrazione della seconda uguaglianza è identica, scambiando e .
È possibile generalizzare la riunione a un numero finito di serie: torniamo al caso di due serie mediante una successiva riunione binaria e l'associatività della riunione assicura che l'ordine non abbia importanza. Allo stesso modo per l'incrocio.
Ma è anche possibile generalizzare queste operazioni a una famiglia di insiemi non necessariamente finita.
L'unione di una famiglia di insiemi è definita da:
.Questa definizione non dipende U . La riunione di una famiglia vuota è il tutto vuoto.
L'intersezione di una famiglia di insiemi è definita da:
.La definizione di cui sopra non dipende dall'insieme U tranne quando la famiglia è vuota. in quest'ultimo caso l'intersezione della famiglia vuota è per definizione l'insieme di riferimenti U , che rimane compatibile con le proprietà dell'intersezione. Non si può definire “in assoluto” (senza un insieme di riferimenti) l'intersezione di una famiglia vuota.
Alcune delle proprietà di riunione e intersezione binaria si generalizzano al caso infinito. Sono ora in gioco le proprietà del calcolo dei predicati (e non più solo del calcolo proposizionale). In particolare:
Un insieme di riferimento U dato, il complementare del sottoinsieme A di U (cioè rispetto al U ) è l'insieme di elementi di U che non appartengono a A . È indicato con U - A , A , A c o anche :
che significa
x ∈ A c se e solo se x ∈ U e x ∉ A .Il complemento di A dipende dal set di riferimento U . È inoltre caratterizzato dalle due uguaglianze:
A ∩ A c = ∅ e A ∪ A c = U .L'operazione di passaggio aggiuntivo è involutiva cioè ( A c ) c = A .
Il passaggio al complementare inverte la relazione di inclusione:
A ⊂ B se e solo se B c ⊂ A ce quindi scambia la riunione e l'intersezione, che sono il limite superiore e il limite inferiore, queste sono le leggi di De Morgan :
( A ∩ B ) c = A c ∪ B c ; ( A ∪ B ) c = A c ∩ B c .Una struttura ordinata che, come l'insieme delle parti di U provviste delle operazioni binarie di unione e di intersezione, dell'operazione di passaggio al complemento, e dei due elementi distinti ∅ e U , soddisfa le proprietà di queste operazioni enumerate fino ad ora si chiama algebra booleana .
La differenza di insieme di A e B denotata " A \ B " (leggi " A meno B ") è l'insieme di elementi di A che non appartengono a B , vale a dire:
.La differenza di A e B in U è definita dal complementare A ∩ B c , e quindi ( A ∩ B c ) c = A c ∪ B .
Se B è incluso in A , allora A \ B è anche scritto " A - B " (leggi di nuovo " A meno B "), ed è chiamato complementare a B in A (o relativamente a A ). Troviamo la nozione di complementare sopra, che è complementare relativamente a U :
. Proprietà della differenzaAbbiamo :
x ∈ A \ B se e solo se x ∈ A e x ∉ B x ∉ A \ B se e solo se x ∈ A ⇒ x ∈ Be così :
A \ B = ∅ se e solo se A ⊂ B .Le proprietà della differenza si ottengono dalla sua definizione e da quelle dell'unione dell'intersezione e del complemento. Ad esempio la prima che segue è una serie di intersezioni, mentre la seconda utilizza una legge di De Morgan e la distributività dell'intersezione sull'unione.
.
La differenza simmetrica di A e B , denotata " A Δ B " (leggi " A delta B ") è l'insieme di elementi che appartengono ad A o a B , ma non ad entrambi allo stesso tempo. È la differenza di A ∪ B e A ∩ B . Può essere scritto in varie forme:
.Abbiamo :
x ∈ A Δ B se e solo se sia x ∈ A oppure x ∈ B (o esclusiva) x ∉ A Δ B se e solo se x ∈ A ⇔ x ∈ Bquindi la differenza simmetrica di due insiemi è vuota se e solo se i due insiemi sono uguali:
A Δ B = ∅ se e solo se A = B . Proprietà della differenza simmetricaL'insieme di parti di U fornito con l'operazione di differenza simmetrica è un gruppo commutativo , con ∅ per elemento neutro, e dove ogni sottoinsieme di U è il proprio opposto, vale a dire che per tutti i sottoinsiemi A , B , C di U , abbiamo:
Una conseguenza è la regolarità: se A Δ B = A Δ C , poi B = C .
L'insieme delle parti di U fornito, oltre alla differenza simmetrica, con l'intersezione, è un anello commutativo unitario , vale a dire che oltre alle proprietà di associatività e commutatività dell'intersezione, e che U è un elemento neutro
La differenza simmetrica, a differenza dell'unione, non è distributiva rispetto all'incrocio.
È una proprietà generale delle algebre booleane che un'operazione definita come differenza simmetrica (con l'unione dell'intersezione e del passaggio al complemento) consente di definire una struttura ad anello, a volte chiamata anello booleano. Altre proprietà, comuni a tutte le algebre booleane, sono verificate come:
A c = U Δ A e quindi A c Δ A = U .oppure ( A Δ B ) c = A c Δ B = A Δ B c .
Da un punto di vista assiomatico, nella teoria degli insiemi tutto ciò che precede si sviluppa dall'assioma di estensionalità (uguaglianza di due insiemi), che garantisce in particolare l'unicità delle costruzioni introdotte, e dello schema degli assiomi di comprensione , che ne garantisce l'esistenza , tutti gli insiemi introdotti essendo definiti come un sottoinsieme di un dato insieme U.