Induzione insieme delle parti
Salve scusate per piacere
qualcuno potrebbe postarmi in maniera chiara come si dimostra per induzione(prima forma)
che l'insieme delle parti di un insieme |A|=n è uguale a 2^n
io su quelle trovate su internet non ci ho capito molto
grazie attendo
qualcuno potrebbe postarmi in maniera chiara come si dimostra per induzione(prima forma)
che l'insieme delle parti di un insieme |A|=n è uguale a 2^n
io su quelle trovate su internet non ci ho capito molto
grazie attendo
Risposte
Il caso base è banale. Se supponi che sia valido per insiemi di cardinalità $n-1$, preso un insieme $A={a_1,...,a_n}$ hai che $\mathcal{P}(A)=\mathcal{P}({a_1,...,a_{n-1}})\cup $ {tutti i sottoinsiemi in cui compare $n}$.
Per quanto riguarda la cardinalità dell'ultimo insieme, hai che è la somma
[tex]\displaystyle 1+ \sum_{k=1}^{n-1} C_{k,n-1}[/tex] dove con
$C_{k,n-1}$ intendo le combinazioni senza ripetizione di $k$ elementi presi da un insieme di $n-1$ elementi (perchè $a_n$ lo tengo fisso, mentre gli altri vanno presi in tutte le combinazioni possibili). Quell'1 rappresenta l'insieme ${n}$, che ha cardinalità 1.
Per sapere quanto fa quella somma, usi il binomio di Newton.
Paola
Per quanto riguarda la cardinalità dell'ultimo insieme, hai che è la somma
[tex]\displaystyle 1+ \sum_{k=1}^{n-1} C_{k,n-1}[/tex] dove con
$C_{k,n-1}$ intendo le combinazioni senza ripetizione di $k$ elementi presi da un insieme di $n-1$ elementi (perchè $a_n$ lo tengo fisso, mentre gli altri vanno presi in tutte le combinazioni possibili). Quell'1 rappresenta l'insieme ${n}$, che ha cardinalità 1.
Per sapere quanto fa quella somma, usi il binomio di Newton.
Paola
no troppo diversa da come l ha fatta la mia prof..
la mia prof l ha fatta diciamo molto simile a questa:
http://www.matapp.unimib.it/~dallavolta ... uzione.pdf
ma non riesco a capirla proprio.
la mia prof l ha fatta diciamo molto simile a questa:
http://www.matapp.unimib.it/~dallavolta ... uzione.pdf
ma non riesco a capirla proprio.
e poi con n+1 e non n-1 io faccio l induzione..
Non c'è assolutamente differenza tra usare l'ipotesi induttiva con $n-1$ o $n$.
Qual è la parte della dimostrazione che mi hai linkato che non capisci, esattamente? Posso spiegartela.
Paola
Qual è la parte della dimostrazione che mi hai linkato che non capisci, esattamente? Posso spiegartela.
Paola
da quando inizia dal punto n+1 in poi..
non potresti darmi un tuo contatto skype, msn o facebook
sai via chat è tutto piu semplice
grazie
non potresti darmi un tuo contatto skype, msn o facebook
sai via chat è tutto piu semplice
grazie
ti ho aggiunto in msn..
entri per piacere..
entri per piacere..
C'è un forum, usalo. Non ho intenzione di spargere in giro i miei contatti personali, anzi, manco mi ricordavo di avere messo MSN disponibile qui.
Se mi dici qual è il problema qui ti aiuto, altrimenti fai senza di me.
Paola
Se mi dici qual è il problema qui ti aiuto, altrimenti fai senza di me.
Paola
tel ho detto dal punto in cui lo dimostra con n+1 in poi
li nn capisco niente.
li nn capisco niente.
La dimostrazione del pdf mi sembra anche imprecisa a dire il vero.
Supponiamo che la tesi che vogliamo dimostrare valga per $card(A)=n$ e proviamola per $n+1$. Sia $A={a_1,...a_{n+1}}$.
Chiaramente, essendo $\mathcal{P}(A)$ l'insieme di tutti i possibili sottoinsiemi di $A$, si ha:
[tex]\mathcal{P}(A)=\{X\subset A : a_{n+1}\in X\}\amalg \{Y\subset A : a_{n+1}\notin Y\}[/tex]
dove [tex]\amalg[/tex] è il simbolo di unione disgiunta.
Ma gli insiemi del tipo ${X\subset A : a_{n+1}\in X}$ sono fatti nel seguente modo: $a_{n+1}$ ha presenza fissa in essi, mentre gli altri elementi sono presi in tutti i modi e numeri possibili da $A':={a_1,...,a_n}$. Quindi si può dire che esiste una corrispondenza biunivoca tra $\mathcal{P}(A')$ e ${X\subset A : a_{n+1}\in X}$, e questo implica anche che questi ultimi 2 insiemi hanno stessa cardinalità, che è pari a $2^n$ per ipotesi induttiva.
Per quanto riguarda gli insiemi del tipo ${Y\subset A : a_{n+1}\notin Y}$, è abbastanza chiaro che sono tutti e soli gli elementi di $\mathcal{P}(A')$ e quindi di nuovo cardinalità $2^n$.
Perciò, dato che l'unione era disgiunta, si avrà [tex]card(\mathcal{P}(A))=2^n +2^n[/tex] e questo conclude la prova.
Paola
Supponiamo che la tesi che vogliamo dimostrare valga per $card(A)=n$ e proviamola per $n+1$. Sia $A={a_1,...a_{n+1}}$.
Chiaramente, essendo $\mathcal{P}(A)$ l'insieme di tutti i possibili sottoinsiemi di $A$, si ha:
[tex]\mathcal{P}(A)=\{X\subset A : a_{n+1}\in X\}\amalg \{Y\subset A : a_{n+1}\notin Y\}[/tex]
dove [tex]\amalg[/tex] è il simbolo di unione disgiunta.
Ma gli insiemi del tipo ${X\subset A : a_{n+1}\in X}$ sono fatti nel seguente modo: $a_{n+1}$ ha presenza fissa in essi, mentre gli altri elementi sono presi in tutti i modi e numeri possibili da $A':={a_1,...,a_n}$. Quindi si può dire che esiste una corrispondenza biunivoca tra $\mathcal{P}(A')$ e ${X\subset A : a_{n+1}\in X}$, e questo implica anche che questi ultimi 2 insiemi hanno stessa cardinalità, che è pari a $2^n$ per ipotesi induttiva.
Per quanto riguarda gli insiemi del tipo ${Y\subset A : a_{n+1}\notin Y}$, è abbastanza chiaro che sono tutti e soli gli elementi di $\mathcal{P}(A')$ e quindi di nuovo cardinalità $2^n$.
Perciò, dato che l'unione era disgiunta, si avrà [tex]card(\mathcal{P}(A))=2^n +2^n[/tex] e questo conclude la prova.
Paola
ora mi dimostreresti per piacere
che il prodotto cartesiano |A|=n e |B|=m allora|AXB|=nxm
la dimostrazione che ho sui miei appunti è simile a questa ma non la trovo in giro.. e dagli appunti non riesco a capirla
grazie
corretto
ah cmq senti perchè 2^n + 2^n fa 2^n+1??
come ti esce questo risultato?
che il prodotto cartesiano |A|=n e |B|=m allora|AXB|=nxm
la dimostrazione che ho sui miei appunti è simile a questa ma non la trovo in giro.. e dagli appunti non riesco a capirla
grazie
corretto
ah cmq senti perchè 2^n + 2^n fa 2^n+1??
come ti esce questo risultato?
Dato che puoi scrivere [tex]\displaystyle A\times B=\amalg_{a\in A} \{a\}\times B[/tex], basta dimostrare che [tex]\{a\}\times B[/tex] ha cardinalità [tex]card(B)[/tex] e questo mi pare chiaro, dato che il primo elemento è fisso e gli altri prendono tutti i possibili valori in $B$.
Con l'induzione non mi viene in mente come dimostrarlo... ma se trovi la dimostrazione e mi dici qual è il problema ci si guarda.
Paola
Con l'induzione non mi viene in mente come dimostrarlo... ma se trovi la dimostrazione e mi dici qual è il problema ci si guarda.
Paola
leggi la seconda domanda di sopra 
$2^{n+1}=2*2^n$
Paola
Paola
e ma tu sopra hai scritto 2^n+2^n cosa centra?
Come sarebbe a dire "come ti esce" $2^n+2^n=2^(n+1)$ ...?EDIT. Appunto, appena vista la risposta di prime_number. Cosa non ti torna?
2^n+2^n non fa 2^n+1
che proprietà applichi per far uscire da 2^n+2^n
2^n+1??
che proprietà applichi per far uscire da 2^n+2^n
2^n+1??
[ Non ci credo... ]
$a+a=2*a$
quindi
$2^n + 2^n= 2*(2^n)=2*2^n$
Edit.
@prime_number
L'imprecisione che dicevi: intendi l'inclusione stretta?
$a+a=2*a$
quindi
$2^n + 2^n= 2*(2^n)=2*2^n$
Edit.
@prime_number
L'imprecisione che dicevi: intendi l'inclusione stretta?
ok poi un altra cosa
ho notato che la differenza simmetrica si rifanno allo XOR della tavola di verità
ma lo stesso equivale per l unione disgiunta..
com è possibile? mica sono la stessa cosa??
ho notato che la differenza simmetrica si rifanno allo XOR della tavola di verità
ma lo stesso equivale per l unione disgiunta..
com è possibile? mica sono la stessa cosa??
@Rggb: quei 2 insiemi che ho descritto il pdf li chiama $B$ e $C$ ed essi sono sottoinsiemi di $\mathcal{P}(A)$, non di $A$. Dunque non è vero, come scrive il pdf, che $\mathcal{P}(A)=\mathcal{P}(B)\cup\mathcal{P}(C)$.
L'unione disgiunta non è un'operazione tra insiemi, diversamente dalla differenza simmetrica. L'unione disgiunta è una normalissima unione, che però aggiunge un'informazione agli insiemi che stai trattando, ovvero che hanno intersezione nulla.
Paola
L'unione disgiunta non è un'operazione tra insiemi, diversamente dalla differenza simmetrica. L'unione disgiunta è una normalissima unione, che però aggiunge un'informazione agli insiemi che stai trattando, ovvero che hanno intersezione nulla.
Paola
si ok ma sbaglio o la loro tavolta di verita si riferisca anch essa allo xor in maniera diciamo cosi pratica?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo