Insieme delle parti

In matematica, dato un insieme S, l'insieme delle parti di S, scritto ${\mathcal {P}}(S)$ o 2^S, è l'insieme di tutti i sottoinsiemi di S. Questa collezione di insiemi viene anche detta insieme potenza di S o booleano di S.

Per esempio, se S è l'insieme $\{a,b,c\}$, allora la lista completa dei suoi sottoinsiemi risulta:

• $\varnothing$ (l'insieme vuoto)
• $\{a\}$
• $\{b\}$
• $\{c\}$
• $\{a,b\}$
• $\{a,c\}$
• $\{b,c\}$
• $\{a,b,c\}$ che coincide con l'insieme stesso ${S}$

e quindi l'insieme delle parti di S è

${\mathcal {P}}(S)=\{\varnothing ,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},S\}$

Cardinalità dell'insieme delle parti

L'argomento diagonale di Cantor mostra che l'insieme delle parti di un insieme (infinito o no) ha sempre cardinalità strettamente più alta di quella dell'inseme stesso (talora informalmente si dice che l'insieme di potenza deve essere 'maggiore' dell'insieme originale).

Insiemi finiti

Se S è un insieme finito con |S|=n elementi, allora l'insieme delle parti di S contiene $|{\mathcal {P}}(S)|=2^{n}$ elementi. (Si può - come si fa abitualmente con i computer - rappresentare gli elementi di ${\mathcal {P}}(S)$ come numeri a n bit; l'n-mo bit si riferisce alla presenza o all'assenza dell' n-mo elemento di S. Ci sono 2ⁿ di tali numeri.)

Dimostrazione

Dimostrazione che $|{\mathcal {P}}(S)|=2^{n}$, con S insieme finito e di ordine n: (dimostrazione per induzione su n (I forma))

Se n = 0 necessariamente $S\equiv \emptyset$. E quindi ${\mathcal {P}}(S)=\{\emptyset \}\Rightarrow |{\mathcal {P}}(S)|=2^{0}=1$. Vera.

Sia n > 0, e supponiamo l'asserto vero per n-1. Cioè se T è un insieme e $|T|=n-1$ allora $|{\mathcal {P}}(T)|=2^{n-1}$.

Poiché $|T|=n>0$ necessariamente $T\neq \emptyset$ e dovrà avere almeno un elemento. Sia $x_{0}$ un elemento dell'insieme. Un qualunque sottoinsieme di T può contenerlo o meno:

• I sottoinsiemi che non contengono $x_{0}$, sono sottoinsiemi di $T\backslash \{x_{0}\}$; poiché $|T\backslash \{x_{0}\}|=n-1$, tali sottoinsiemi sono, per l'ipotesi induttiva $2^{n-1}$.
• I sottoinsiemi che contengono $x_{0}$, sono sottoinsiemi del tipo $X\cup {x_{0}}$; con X sottoinsieme di $T\backslash \{x_{0}\}$; quindi anche tali sottoinsiemi sono, per l'ipotesi induttiva $2^{n-1}$.

Quindi i sottoinsiemi di T sono in tutto $2^{n-1}+2^{n-1}=2\cdot 2^{n-1}=2^{n}$.

Insiemi infiniti

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 un insieme di numeri reali (identificando una sequenza infinita 0-1 con l'insieme degli indici in cui compaiono gli uno).
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 numeralità del continuo, vedi l'Argomento diagonale di Cantor.

Algebre

L'insieme delle parti di un insieme S, 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 subalgebra di un algebra booleana insieme delle parti.

L'insieme delle parti di un insieme S 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.

La notazione 2^S

Nella teoria degli insiemi, X^Y è l'insieme di tutte le funzioni da Y a X. Come 2 può essere definito {0,1} (vedi numeri naturali), 2^S è l'insieme di tutte le funzioni da S a {0,1}. Identificando una funzione in 2^S con la preimmagine corrispondente di 1, si osserva che c'è una biiezione tra 2^S e ${\mathcal {P}}(S)$, dove ogni funzione è la funzione caratteristica del sottoinsieme in ${\mathcal {P}}(S)$ con cui è identificata. Quindi 2^S e ${\mathcal {P}}(S)$ possono essere considerati identici secondo la teoria degli insiemi.

Assioma dell'insieme potenza

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.

Voci correlate

• Paradosso di Russell
• Cardinalità

Collegamenti esterni

• "Power Set" su MathWorld