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
Io non capisco cosa scrivi. La punteggiatura e le declinazioni verbali non sono un optional in italiano.
Paola
Paola
la tavola di verità dell unione disgiunta in maniera pratica, si puo riferire allo XOR?
@Gauss1991
Nemmeno io riesco a comprendere la domanda... cosa intendi esattamente con "la tavola di verità dell'unione disgiunta"? Puoi fare (forse) un esempio?
@prime_number
Ho riletto la dimostrazione: mi sa che è proprio errata... Effettivamente l'autore si è un po' complicato la vita; si può dimostrare in un modo molto più semplice.
Nemmeno io riesco a comprendere la domanda... cosa intendi esattamente con "la tavola di verità dell'unione disgiunta"? Puoi fare (forse) un esempio?
@prime_number
Ho riletto la dimostrazione: mi sa che è proprio errata... Effettivamente l'autore si è un po' complicato la vita; si può dimostrare in un modo molto più semplice.
rggb come l unione corrisponde alla tavola di verità dell or logico
l unione disgiunta puo corrispondere alla tavolta di verita dello xor??
l unione disgiunta puo corrispondere alla tavolta di verita dello xor??
No, lo XOR corrisponde alla differenza simmetrica. L'unione disgiunta non è un operatore logico, è solo un modo particolare di scrivere l'unione, che corrisponde invece all'OR.
Paola
Paola
ok grazie..
cmq io ho fatto un esempio della tua dimostrazione guarda qui:
sia A={a,b,c} con n+1 elementi(c)
P(A)={0,{a},{b},{a,b}} U {{a,c},{c,},{b,c},A}
ora sappiamo che la prima parte contiene tutti i sottinsiemi di A in cui non ci sia l'elemento 'c'
mentre la seconda parte contiene tutti i sottinsiemi di A in cui ci sia l'elemento 'c'
e fin qui tutto ok
ora come ragiono sulle cardinalità?
cmq io ho fatto un esempio della tua dimostrazione guarda qui:
sia A={a,b,c} con n+1 elementi(c)
P(A)={0,{a},{b},{a,b}} U {{a,c},{c,},{b,c},A}
ora sappiamo che la prima parte contiene tutti i sottinsiemi di A in cui non ci sia l'elemento 'c'
mentre la seconda parte contiene tutti i sottinsiemi di A in cui ci sia l'elemento 'c'
e fin qui tutto ok
ora come ragiono sulle cardinalità?
Io vedo $c$ in entrambe le tue suddivisioni 
.
Sulle cardinalità, se ti riferisci alla dimostrazione, non devi ragionare nulla, perché usi l'ipotesi induttiva. Il trucco sta, avendo un insieme con $n+1$ elementi, nel cercare di ricreare una situazione in cui ne hai $n$, numero per il quale sai che ciò che vuoi provare si avvera.
L'induzione si usa sempre così, devi trovare il modo di ricondurti all'ipotesi induttiva.
Paola
.Sulle cardinalità, se ti riferisci alla dimostrazione, non devi ragionare nulla, perché usi l'ipotesi induttiva. Il trucco sta, avendo un insieme con $n+1$ elementi, nel cercare di ricreare una situazione in cui ne hai $n$, numero per il quale sai che ciò che vuoi provare si avvera.
L'induzione si usa sempre così, devi trovare il modo di ricondurti all'ipotesi induttiva.
Paola
ok ho modificato i due insiemi. pero non ho capito il discorso che hai fatto dopo
cioe tu in pratica hai che nella prima parte hai l insieme delle parti di A={a,b} che per ipotesi induttiva è uguale a 2^n intendo questa come prima parte:
P{A}={0,{a},{b],{a,b}} giusto?
e nella seconda parte??
cioe tu in pratica hai che nella prima parte hai l insieme delle parti di A={a,b} che per ipotesi induttiva è uguale a 2^n intendo questa come prima parte:
P{A}={0,{a},{b],{a,b}} giusto?
e nella seconda parte??
Vediamo numericamente cosa succede. Prendiamo $n=2$ e supponiamo di sapere che è vera la tesi. Ora vediamo cosa accade per $n+1=3$.
$A={a,b,c}$
[tex]\mathcal{P}(A)=\{\emptyset, \{a\},\{b\},\{a,b\}\}\amalg \{\{c\}, \{a,c\},\{b,c\},\{a,b,c\}\}[/tex]
Come vedi entrambi questi due sottoinsiemi di $\mathcal{P}(A)$ hanno $2^n=2^2=4$ elementi, come previsto dalla nostra ipotesi induttiva.
Paola
$A={a,b,c}$
[tex]\mathcal{P}(A)=\{\emptyset, \{a\},\{b\},\{a,b\}\}\amalg \{\{c\}, \{a,c\},\{b,c\},\{a,b,c\}\}[/tex]
Come vedi entrambi questi due sottoinsiemi di $\mathcal{P}(A)$ hanno $2^n=2^2=4$ elementi, come previsto dalla nostra ipotesi induttiva.
Paola
"prime_number":
La dimostrazione del pdf mi sembra anche imprecisa a dire il vero.
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.
Paola
l ho capito il ragionamento, ma non riesco a capire cosa vuoi dire con questa cosa..
di quali due insiemi parli, non stai parlando dell sottoinsieme dell insieme delle parti che contiene tutti gli elementi compreso {c} in questo caso?
Intendi che non capisci di chi parlo quando dico "questi ultimi 2 insiemi"?
Se è così, intendevo $\mathcal{P}(A')$ e ${X\subset A: a_{n+1}\in X}$
Paola
Se è così, intendevo $\mathcal{P}(A')$ e ${X\subset A: a_{n+1}\in X}$
Paola
da quanto ho capito io in questo intero periodo tu dici semplicemente che il sottinsieme di P(A) che contiene tutti gli elementi an+1 ha cardinalita 2^n?
ma poi tu dici
mentre gli altri elementi sono presi in tutti i modi e numeri possibili da A':={a1,...,an}
quali altri elementi.. in quest osottinsieme ci sono solo gli elementi in cui c è {c}..
questi altri elementi quali sono?
mentre gli altri elementi sono presi in tutti i modi e numeri possibili da A':={a1,...,an}
quali altri elementi.. in quest osottinsieme ci sono solo gli elementi in cui c è {c}..
questi altri elementi quali sono?
Il fatto è che quel sottoinsieme delle parti è fatto da insiemi del tipo ${a_{n+1}, c_1,...c_k}$ con $c_1,...,c_k \in {a_1,...a_n}$ e $k$ qualsiasi, $0\leq k\leq n$.
Anche dall'esempio numerico che ti ho fatto prima vedi chiaramente come i due sottoinsiemi in cui dividi l'insieme delle parti siano estremamente simili. Uno è fatto da certi sottoinsiemi di $A$, l'altro dagli stessi identici sottoinsiemi a cui però hai aggiunto l'elemento $a_{n+1}$, che nell'es.num. avevamo chiamato $c$.
Paola
Anche dall'esempio numerico che ti ho fatto prima vedi chiaramente come i due sottoinsiemi in cui dividi l'insieme delle parti siano estremamente simili. Uno è fatto da certi sottoinsiemi di $A$, l'altro dagli stessi identici sottoinsiemi a cui però hai aggiunto l'elemento $a_{n+1}$, che nell'es.num. avevamo chiamato $c$.
Paola
mm ok e quindi perchè questo sottinsieme di P(A) che contiene c ha cardinalita 2^n??
Come ti ho detto è identico all'altro sottoinsieme di $P(A)$, hai solo aggiunto $a_{n+1}$ ad ogni sottoinsieme, è chiaro che non ne hai mutato la cardinalità.
Se tu ha 17 gruppi di mele e aggiungi una mela ad ogni gruppo, rimani con 17 gruppi di mele, solo più grossi.
Paola
Se tu ha 17 gruppi di mele e aggiungi una mela ad ogni gruppo, rimani con 17 gruppi di mele, solo più grossi.
Paola
ok..questo si ma in maniera formale come facciamo a dire questa cosa..
e questo che non riesco a capire cioe dopo aver scritto P(A) in questo modo
P(A)={0,{a}.{b},{ab}} U {{a,c},{c}.{bc},A}
dove la prima parte contiene l insieme delle parti di |A|=n e la seconda parte l insieme delle parti di |A|=n+1.
cosa dobbiamo dire? che il primo è 2^n ed il secondo è 2^n perche?
come lo diciamo in maniera formale?
e questo che non riesco a capire cioe dopo aver scritto P(A) in questo modo
P(A)={0,{a}.{b},{ab}} U {{a,c},{c}.{bc},A}
dove la prima parte contiene l insieme delle parti di |A|=n e la seconda parte l insieme delle parti di |A|=n+1.
cosa dobbiamo dire? che il primo è 2^n ed il secondo è 2^n perche?
come lo diciamo in maniera formale?
ok..questo si ma in maniera formale come facciamo a dire questa cosa..
e questo che non riesco a capire cioe dopo aver scritto P(A) in questo modo
P(A)={0,{a}.{b},{ab}} U {{a,c},{c}.{bc},A}
dove la prima parte contiene l insieme delle parti di |A|=n e la seconda parte l insieme delle parti di |A|=n+1.
cosa dobbiamo dire? che il primo è 2^n ed il secondo è 2^n perche?
come lo diciamo in maniera formale?
e questo che non riesco a capire cioe dopo aver scritto P(A) in questo modo
P(A)={0,{a}.{b},{ab}} U {{a,c},{c}.{bc},A}
dove la prima parte contiene l insieme delle parti di |A|=n e la seconda parte l insieme delle parti di |A|=n+1.
cosa dobbiamo dire? che il primo è 2^n ed il secondo è 2^n perche?
come lo diciamo in maniera formale?
Io te l'ho scritto in maniera formale quando ti ho riscritto la dimostrazione interamente, per cui vai a vedere indietro.
Paola
Paola
e questo sto cercando di farti capire..sto rileggendo piu volte la dimostrazione
ma questa cosa non riesco a capirla..
ovvero da li come arriviamo a dire in maniera formale che entrambi hanno cardinalità 2^n?
(scusami eh.. sono un po ritardato nel capire le cose.. ma se non le riesco a capire è piu forte di me non mi arrendo..)
ma questa cosa non riesco a capirla..
ovvero da li come arriviamo a dire in maniera formale che entrambi hanno cardinalità 2^n?
(scusami eh.. sono un po ritardato nel capire le cose.. ma se non le riesco a capire è piu forte di me non mi arrendo..
)
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo