Sottoinsiemi e insieme delle parti

Home » Sottoinsiemi e insieme delle parti

Autori e revisori

Leggi...

Notazioni

Leggi...

$A \subseteq B$	$A$ è un sottoinsieme di $B$ ;
$\emptyset$	Insieme vuoto;
$\mathcal{P}(A)$	Insieme delle parti di $A$ , ossia l’insieme dei suoi sottoinsiemi.

Introduzione

Leggi...

Un sottoinsieme di un insieme $A$ è un insieme formato da alcuni degli elementi di $A$ . Se immaginiamo gli insiemi come scatole con all’interno i propri elementi, un sottoinsieme è una nuova scatola che contiene solo alcuni degli elementi di partenza. Dato un insieme $A$ , è possibile considerare la collezione i suoi sottoinsiemi, che viene appunto detta insieme delle parti di $A$ .

In questo articolo definiamo formalmente le nozioni di sottoinsieme e di insieme delle parti e presentiamo la formula per il calcolo del numero di sottoinsiemi di un dato insieme.

Sottoinsiemi

Definizione 1. Dati due insiemi $A$ e $B$ diremo che $A$ è un sottoinsieme di $B$ (o è contenuto o incluso in $B$ ), se ogni elemento di $A$ appartiene anche a $B$ . Se $A$ è contenuto in $B$ scriveremo

$A \subseteq B.$

Se, invece $A$ non è un sottoinsieme di $B$ , ossia se qualche elemento di $A$ non appartiene a $B$ , si scrive $A \not \subseteq B$ .

$\quad$

Se $A$ è un sottoinsieme di $B$ , utilizzando un diagramma di Eulero-Venn mostriamo graficamente questa relazione nel modo seguente:

$\quad$

Rendered by QuickLaTeX.com

$\quad$

In formule la relazione di inclusione si può descrivere come segue:

$A \subseteq B \quad \iff \quad x \in B \; \forall x \in A,$

o, equivalentemente,

$A \subseteq B \iff \Bigl( x \in A \implies x \in B \Bigr).$

L’insieme vuoto $\emptyset$ è sottoinsieme di ogni insieme $A$ , $\emptyset \subseteq A$ : dalla definizione occorrerebbe verificare che ogni qual volta un elemento appartiene a $\emptyset$ , allora esso appartiene anche ad $A$ ; siccome non vi sono elementi nell’insieme vuoto, non vi è alcuna verifica da fare, dunque l’inclusione è vera.

Osservazione 2. Dati due insiemi $A$ e $B$ , essi sono uguali se e solo se uno è incluso nell’altro, ossia

$\begin{equation*} A=B \iff A\subseteq B\,\wedge\, B\subseteq A. \end{equation*}$

Infatti, chiaramente da $A = B$ segue immediatamente $A \subseteq B$ e $B \subseteq A$ . Viceversa, se $A \subseteq B$ e $B \subseteq A$ , ciò implica che tutti gli elementi di $A$ appartengono anche a $B$ e che tutti gli elementi di $B$ appartengono anche ad $A$ , pertanto $A$ e $B$ possiedono gli stessi elementi.

Se $A$ non è un sottoinsieme di $B$ , ciò vuol dire che vi è qualche elemento di $A$ che non appartiene a $B$ , ossia in formule

$\begin{equation*} \exists a\in A \,:\, a\notin B. \end{equation*}$

Definizione 3. Se $A$ è un sottoinsieme di $B$ , ma $A \neq B$ , si dice che $A$ è un sottoinsieme proprio di $B$ e si scrive

$A \subset B \qquad \text{oppure} \qquad A \subsetneq B.$

$\quad$

Per esempio, se

$B = \{ x: x \in \text{astuccio} \},$

$A = \{ x \in B : x \; \text{è una penna} \},$

allora chiaramente $A$ è un sottoinsieme di $B$ ovvero $A \subseteq B$ . Se inoltre, nel nostro astuccio non ci sono solo penne ma anche gomme e matite, allora $A$ è un sottoinsieme proprio di $B$ ovvero $A \subset B$ . Per finire notiamo che in alcuni libri si usa il simbolo $\subset$ per indicare $\subseteq$ , ma in genere il significato di questi simboli è chiarificato in una sezione preliminare del testo stesso.

Insieme delle parti e sua cardinalità

Dato un insieme $A$ , ha senso considerare la collezione di tutti i suoi sottoinsiemi.

Definizione 4. Dato un insieme $A$ , l’insieme i cui elementi sono tutti e soli i sottoinsiemi di $A$ si chiama insieme delle parti di $A$ e si indica col simbolo $\mathcal{P}(A)$ .

$\quad$

Per esempio, dato l’insieme $A = \{ 3\text{,} 7 \}$ , listiamo di seguito tutti i suoi sottoinsiemi, partendo dall’insieme vuoto $\emptyset$ e l’insieme stesso che sono sottoinsiemi di qualunque insieme:

$A_1 = \emptyset, \quad A_2 = \{ 3, 7 \}=A, \quad A_3 = \{3\}, \quad A_4 = \{ 7\}.$

Di conseguenza, l’insieme delle parti di $A$ è

$\mathcal{P}(A) = \{ A_1,A_2,A_3, A_4\} = \big\{ \emptyset, A, \{3\}, \{7\} \big\}.$

Notiamo esplicitamente che gli elementi dell’insieme delle parti $A$ sono a loro volta altri insiemi: tutti i possibili sottoinsiemi di $A$ !

Come altro esempio, l’insieme vuoto $\emptyset$ possiede come solo suo sottoinsieme l’insieme vuoto stesso, quindi

$\mathcal{P}(\emptyset) = \big\{ \emptyset \big\}.$

Si provi a descrivere, per esercizio, l’insieme delle parti di $B=\{1\}$ e di $C=\{1,2,3\}$ .

In generale, se $A$ è un insieme finito è possibile elencare tutti i suoi possibili sottoinsiemi. Risulta naturale chiederci quanti siano tali sottoinsiemi. La risposta è fornita dal seguente teorema, la cui dimostrazione è basata sul principio di induzione.

Teorema 5. Dato un insieme $A$ con $n$ elementi (ovvero $|A| = n$ ), la cardinalità di $\mathcal{P}(A)$ è $2^n$ .

$\quad$

Dimostrazione. Se $n=0$ , allora $A=\emptyset$ è l’insieme vuoto, e abbiamo già mostrato che $A$ possiede $\emptyset$ come unico sottoinsieme, cioè che $\mathcal{P}(A)= \big\{ \emptyset \big\}$ e quindi $|\mathcal{P}(A)|=1=2^0$ .

Supponiamo ora che un insieme con $n$ elementi possieda $2^n$ sottoinsiemi, consideriamo un insieme $A$ di $n+1$ elementi e fissiamone uno, che chiamiamo $a$ . I sottoinsiemi di $A$ si possono suddividere in quelli che non contengono $a$ e quelli che contengono $a$ .
I sottoinsiemi di $A$ che non contengono $a$ sono i sottoinsiemi di un insieme avente $n$ elementi, ossia sono in numero $2^n$ per l’ipotesi induttiva. D’altra parte, ogni sottoinsieme contenente $a$ si può ottenere da un sottoinsieme che non lo contiene, aggiungendo $a$ stesso, dunque anche questi sottoinsiemi sono $2^n$ . Ne segue che

$|\mathcal{P}(A)| = 2^n + 2^n = 2 \cdot 2^n = 2^{n+1}.$

Un’altra dimostrazione del fatto che, se $|A|=n$ allora $|\mathcal{P}(A)|=2^n$ , si ottiene come segue: elenchiamo gli $n$ elementi di $A$

$a_1,\dots, a_n.$

Dovendo formare un sottoinsieme di $A$ , bisogna decidere, per ciascun elemento, se esso vi appartiene o meno. Per il primo elemento si hanno quindi $2$ possibilità; per ciascuna scelta effettuata riguardo al primo elemento, anche per il secondo vi sono $2$ possibilità, ossia $2\cdot 2$ . Continuando in tal modo, notiamo che vi sono $n$ scelte indipendenti, ciascuna con $2$ opzioni, ossia $2^n$ possibili sottoinsiemi.

Menu

Chiudi

Sottoinsiemi e insieme delle parti

Autori e revisori

Leggi...

Notazioni

Leggi...

Introduzione

Leggi...

Sottoinsiemi

Insieme delle parti e sua cardinalità

Suggerimenti, refusi ed errori

Cosa dicono di noi