Insieme delle parti
In matematica, dato un insieme , l'insieme delle parti di , scritto , è l'insieme di tutti i possibili sottoinsiemi di . Questa collezione di insiemi viene anche detta insieme potenza di o booleano di .
Per esempio, se è l'insieme , allora la lista completa dei suoi sottoinsiemi risulta:
- (l'insieme vuoto)
- che coincide con l'insieme stesso
e quindi l'insieme delle parti di è
L'insieme delle parti di è alternativamente indicato in vari modi, come , , o .
Cardinalità dell'insieme delle parti
[modifica | modifica wikitesto]L'argomento diagonale di Cantor mostra che l'insieme delle parti di un insieme (infinito o no[1]) ha sempre cardinalità strettamente più alta di quella dell'insieme stesso.
Insiemi finiti
[modifica | modifica wikitesto]Se è un insieme finito con elementi, allora l'insieme delle parti di contiene sottoinsiemi.
Dimostrazione
[modifica | modifica wikitesto]Dimostrazione che , con insieme finito e di ordine : (dimostrazione per induzione su (I forma))
Se , necessariamente . E quindi . Vera.
Sia e supponiamo l'asserto vero per Cioè se è un insieme tale che , allora .
Poiché adesso si ipotizza che , necessariamente e dovrà avere almeno un elemento. Sia un elemento dell'insieme. Un qualunque sottoinsieme di può contenerlo o meno:
- I sottoinsiemi che non contengono , sono sottoinsiemi di ; poiché , tali sottoinsiemi sono, per l'ipotesi induttiva .
- I sottoinsiemi che contengono , sono sottoinsiemi del tipo ; con X sottoinsieme di ; quindi anche tali sottoinsiemi sono, per l'ipotesi induttiva .
Quindi i sottoinsiemi di sono in tutto .
Una dimostrazione alternativa si può basare sulla biiezione fra e l'insieme delle funzioni citata più sotto.
Se è un insieme finito con elementi, è immediato che l'insieme di queste funzioni ha sottoinsiemi. Questo fornisce una dimostrazione alternativa del risultato appena visto.
Insiemi infiniti
[modifica | modifica wikitesto]Si può anche considerare l'insieme delle parti di un insieme infinito: ad esempio l'insieme delle parti dell'insieme dei numeri naturali può essere messo in una corrispondenza uno-a-uno con l'insieme dei numeri reali.
L'insieme delle parti ha un'importanza fondamentale nella teoria degli insiemi infiniti. Infatti, nell'aritmetica transfinita definita da Georg Cantor, l'operazione di "esponenziazione", nel senso di individuazione della cardinalità dell'insieme delle parti di un dato insieme infinito, è l'unico modo per avanzare nella successione dei numeri cardinali. Nell'esempio suddetto, si passa dalla cardinalità del discreto, cioè degli insiemi per i quali è possibile stabilire una corrispondenza biunivoca con i naturali, come gli interi, i razionali e ogni loro prodotto cartesiano, alla cardinalità del continuo propria dei reali. Per la dimostrazione della non numerabilità del continuo, si veda l'argomento diagonale di Cantor.
Algebra
[modifica | modifica wikitesto]L'insieme delle parti di un insieme , con le operazioni di unione, intersezione e complemento formano l'esempio prototipale di un'algebra booleana.
Infatti, si può dimostrare che ogni algebra booleana finita è isomorfica all'algebra booleana dell'insieme delle parti di un insieme finito. Per le algebre booleane infinite questo non è più vero, ma ogni algebra booleana infinita è una sottoalgebra di un'algebra booleana insieme delle parti.
L'insieme delle parti di un insieme forma un gruppo abeliano quando si consideri l'operazione di differenza simmetrica (con l'insieme vuoto come sua unità ed ogni insieme essendo il suo inverso) ed un semigruppo commutativo quando si consideri l'operazione di intersezione. Si può quindi dimostrare (provando le leggi distributive) che l'insieme delle parti, considerato assieme a entrambe queste operazioni, forma un anello commutativo.
Biiezione con l'insieme 2S
[modifica | modifica wikitesto]Nella teoria degli insiemi, è l'insieme di tutte le funzioni da a . Il numero naturale 2 può essere definito insiemisticamente: , quindi è l'insieme di tutte le funzioni da a
Identificando una funzione in con la preimmagine corrispondente di 1, si osserva che c'è una biiezione tra e :
dove ogni funzione viene detta la funzione caratteristica del sottoinsieme in ed è definita in questo modo:
Quindi .
Assioma dell'insieme potenza
[modifica | modifica wikitesto]Nella teoria assiomatica degli insiemi (come sviluppata a partire dagli assiomi di Zermelo-Fraenkel), l'esistenza dell'insieme delle parti di qualsiasi insieme, anche infinito, è oggetto di un postulato detto assioma dell'insieme potenza.
Informatica
[modifica | modifica wikitesto]In informatica è possibile interpretare l'insieme delle parti di un insieme (detto anche booleano di ) come l'insieme di tutte le sequenze binarie di lunghezza , corrispondenti ai possibili sottoinsiemi di un insieme di cardinalità .
Per illustrare questa corrispondenza può essere utile numerare da a gli elementi dell'insieme fornito e associare il bit in posizione della sequenza binaria al -esimo elemento dell'insieme (quindi con ): se tale bit è uguale a , allora l'elemento è nel sottoinsieme così rappresentato, altrimenti il bit è uguale a e l'elemento non appartiene a tale sottoinsieme.
Per esempio, se è l'insieme di cardinalità , allora la generazione delle sue sequenze binarie, corrispondenti alla lista completa dei suoi sottoinsiemi, risulta:
L'algoritmo tipicamente utilizzato per la generazione di sequenze binarie è ricorsivo.
Note
[modifica | modifica wikitesto]- ^ Per la dimostrazione sugli insiemi infiniti è necessario l'assioma della scelta.
Voci correlate
[modifica | modifica wikitesto]Altri progetti
[modifica | modifica wikitesto]Wikimedia Commons contiene immagini o altri file sull'insieme delle parti
Collegamenti esterni
[modifica | modifica wikitesto]- insieme delle parti, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
- (EN) power set, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
- (EN) Eric W. Weisstein, Powerset, su MathWorld, Wolfram Research.
- (EN) Power set, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.
- (EN) Denis Howe, powerset, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL