Insieme delle parti

[matty96]

Posto un problema semplice,ma molto "famoso",che dovrebbe essere risolto in primo superiore,poichè viene usata la formula che chiederò di dimostrare.

Dimostare che l'insieme della parti $P(n)$ è dato dal valore $2^n$

P.S. Per i più esperti:cnon bruciatelo,fatelo fare a chi non è,come me, tanto bravo in combinatoria

[ngshya]

Forse volevi dire la cardinalità di [tex]\displaystyle \mathcal{P}(S)[/tex]?

[matty96]

Esattamente(scusate se l'ho dato per scontato)

[staffo]

Visto che non lo ha ancora dimostrato nessuno, posto la mia soluzione:

Testo nascosto:

L'insieme delle parti è l'insieme contenente tutti i possibili sottoinsiemi dell'insieme dato.
La sua cardinalità sarà dunque data da:
$ 1 $, che corrisponde all'insieme vuoto; $ {n\choose 1} $ cioè tutte le possibili combinazioni ad uno a uno; $ {n\choose 2} $, cioè tutte le possibili combinazioni a due a due; .....

da cui:
$ 1 + {n\choose 1} + {n\choose 2} + ... + {n\choose n} = 2^n $

[Mist]

A questo punto, visto che il problema è stato sdoganato, inauguriamo una raccolta di dimostrazioni di questo fattuccio figoso...

Allora, chiamiamo $f(n)$ quella funzione che associa ad ogni numero la cardinalità dell'insieme delle parti di un insieme $A$ con $n$ elementi.

Bon, prendiamo ora un elemento $x \in A$ e dividiamo l'insieme delle parti di A in due sottoinsiemi $C=\{ X:X\in A \land x \in X \}$ e $B=\{ X:X\in A \land x \not \in X\}$. Si vede subito che essendoci una corrsipondenza biunivoca tra gli insiemi $C$ e $B$ e che $|B| = f(n-1)$ ( in quanto si è come se si lavorasse su $A/ \{ x\} $ ) si ah che la cardinalità dell'insieme delle aprti di A detto per ora $A_p$ è pari a $|A_p| = f(n) = 2f(n-1) = \cdots = 2^hf(n-h) = \cdots = 2^nf(0) = 2^n$

[ma_go]

immagino che tu intenda $X\subset A$ e non $X\in A$, quando definisci $B$ e $C$.

[mode="persona fastidiosa"]piccola nota stilistica: è buona norma -per aumentare la leggibilità- usare uno stile diverso per chiamare questi "insiemi di insiemi"; per cui, invece di scrivere $B$ e $C$, potresti scrivere $\mathcal{B}$ e $\mathcal{C}$ (o, ancora meglio, $\mathcal{F}$ e $\mathcal{G}$, o quantomeno lettere che non facciano sembrare che $A, B$ e $C$ stanno "sullo stesso piano").[/mode]

ora la mia dimostrazione preferita del fatterello, più qualcosa di folklore:

Testo nascosto:

ad ogni sottoinsieme $X\subset A$ associamo quella che si chiama la sua "funzione caratteristica", $\chi_X: A\to\{0,1\}$, definita da $\chi_X(a) = 1$ se $a\in X$, e $0$ altrimenti. ad ogni funzione $f:A\to \{0,1\}$ associamo il sottoinsieme $X_f = \{x\in A \mid f(x)=1\}$. è facile vedere che $X_{\chi_X} = X$, quindi i sottoinsiemi di $A$ sono in corrispondenza biunivoca con le funzioni $A\to \{0,1\}$, che sono $2^n$.

nota bene: non è neppure necessario usare entrambe le corrispondenze funzioni <-> sottoinsiemi, visto che entrambi sono finiti: basta dimostrare che una delle due è iniettiva o suriettiva, e si vince. ho usato entrambe le corrispondenze solo perché sono vere in generale (e per insiemi infiniti non basta dimostrare l'iniettività o la suriettività di una delle due).

piccola digressione: se consideriamo $\{0,1\}$ come l'anello (campo) $\mathbb{F}_2 = \mathbb{Z}/2\mathbb{Z}$ delle classi di resto mod 2, con le sue operazioni, possiamo osservare le seguenti cose:
- $\chi_{X\triangle Y} = \chi_X+\chi_Y$ ($\triangle$ indica la differenza simmetrica, $X\triangle Y = (X\cup Y) \setminus (X\cap Y) = (X\setminus Y)\cup (Y\setminus X)$);
- $\chi_{X\cap Y} = \chi_X\cdot\chi_Y$ ;
- $\chi_{A\setminus X} = \chi_{X^c} = 1-\chi_X$;
- $\chi_{X\cup Y} = (1-\chi_X)(1-\chi_Y)$.
ogni tanto penso che possano tornare comode.

[lama luka]

Non dimentichiamoci della cara vecchia dimostrazione per induzione (che non mi pare sia stata utilizzata, leggendo velocemente le altre), visto che ma_go mi ha "bruciato" l'utilizzo della funzione caratteristica

Procediamo per induzione su n, il 'lemma' è vero per n=0, quindi possiamo supporlo vero per n.
Sia X un insieme di n+1 elementi, fissato $ x_0\in X $ si ha

$ \mathcal{P}(x)=\{A\subset X:x_0 \notin A \} \cup \{A \subset X : x_0\in A\} $

Poichè i due insiemi a secondo membro sono disgiunti, la cardinalità dell'unione è data dalla somma delle due cardinalità; abbiamo dunque:

$ \{ A\subset X: x_0\notin A\}=\mathcal{P}(X- \{x_0\}) $
$ \{A\subset X : x_0\in A\}=\{A\cup \{x_0\}: A\in\mathcal{P}(X-\{x_0\})\} $

per l'ipotesi induttiva #$ \mathcal{P}(X-\{x_0\})=2^n $ e quindi entrambi gli insiemi hanno cardinalità $ 2^n $, da cui P(X) ha cardinalità $ 2^n + 2^n =2^{n+1} $. Concludo

[matty96]

Io l'ho risolta come staffo,anche perchè quella soluzione è più semplice e veloce,però ho letto le altre e sono terribilmente originali.Veramente belle

[staffo]

Altra soluzione vista sui video degli stage (davvero interessante):
considero un insieme di n elementi. poi considero due valori: valore $ 0 $ se l'elemento non farà parte del sottoinsieme, valore $ 1 $ se l'elemento farà parte del sottoinsieme. Ora tutti i possibili sottoinsiemi sono tutte le possibili assegnazioni di questi valori agli n elementi, cioè $ 2^n $

[lama luka]

Altra soluzione vista sui video degli stage (davvero interessante):
considero un insieme di n elementi. poi considero due valori: valore $ 0 $ se l'elemento non farà parte del sottoinsieme, valore $ 1 $ se l'elemento farà parte del sottoinsieme. Ora tutti i possibili sottoinsiemi sono tutte le possibili assegnazioni di questi valori agli n elementi, cioè $ 2^n $

E quindi l'utilizzo della funzione caratteristica citata da ma_go

[staffo]

non avevo letto il nascondi perdonatemi