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
Re: Insieme delle parti
Inviato: 01 gen 2011, 17:16
da ngshya
Forse volevi dire la cardinalità di [tex]\displaystyle \mathcal{P}(S)[/tex]?
Re: Insieme delle parti
Inviato: 01 gen 2011, 19:17
da matty96
Esattamente(scusate se l'ho dato per scontato)
Re: Insieme delle parti
Inviato: 13 gen 2011, 13:57
da 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; .....
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$
Re: Insieme delle parti
Inviato: 13 gen 2011, 17:32
da 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.
Re: Insieme delle parti
Inviato: 24 gen 2011, 22:24
da 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:
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
Re: Insieme delle parti
Inviato: 25 gen 2011, 11:20
da 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
Re: Insieme delle parti
Inviato: 25 gen 2011, 14:58
da 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 $
Re: Insieme delle parti
Inviato: 25 gen 2011, 22:00
da lama luka
staffo ha scritto: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
non avevo letto il nascondi