Dubbio sul Principio d'inclusione ed esclusione
Salve,
mentre stavo studiando il principio di inclusione ed esclusione, mi sono bloccato sulla dimostrazione:
Nella 6° riga (la prima sarebbe quella con cui comincia "Proposizione 2 (Pri. . . "), non capisco perché per dimostrare la prima e la seconda formula, abbiano fatto vedere che, con determinate formule applicate ad A e B otteniamo l'insieme vuoto.
Non ne vedo il collegamento, sembrano completamente diverse da quello che si vuole dimostrare o al passaggio logico.
Potete darmi una mano?
mentre stavo studiando il principio di inclusione ed esclusione, mi sono bloccato sulla dimostrazione:
Nella 6° riga (la prima sarebbe quella con cui comincia "Proposizione 2 (Pri. . . "), non capisco perché per dimostrare la prima e la seconda formula, abbiano fatto vedere che, con determinate formule applicate ad A e B otteniamo l'insieme vuoto.
Non ne vedo il collegamento, sembrano completamente diverse da quello che si vuole dimostrare o al passaggio logico.
Potete darmi una mano?
Risposte
Ciao AlexanderSC, l'idea è questa: per due insiemi disgiunti di cardinalità finita vale la formula \(|X\cup Y|=|X|+|Y|\) (il principio della somma a cui fa riferimento il testo).
Nella dimostrazione si applica questa formula due volte. Comincia con \(X=A-B\) e \(Y=B\): per usarla, devi prima far vedere che tali insiemi sono appunti disgiunti, cioè la loro interesezione è vuota; non è troppo difficile rendersene conto che questo è vero (stai sottraendo a uno tutti gli elementi dell'altro!).
Fatto questo applichi il principio, che di per sé sarebbe \[|X\cup Y|=|(A-B)\cup B|=|A-B|+|B|,\] ma tenendo presente la prima delle ovvie uguaglianze del testo ottieni semplicemente \[|A\cup B|=|A-B|+|B| \quad (*).\] Adesso basta ripetere questi passi per una seconda volta, con \(X=A-B\) e \(Y=A\cap B\). La loro interesezione è vuota, e applicando il principio passando dalla seconda delle ovvie uguaglianze hai \[|X\cup Y|=|(A-B)\cup (A\cap B)|=|A|=|A-B|+|A\cap B|.\] Bene, hai finito: sostituisci \(|A-B|\) esprimendolo in termini della \((*)\) e ottieni la tua formula.
Nella dimostrazione si applica questa formula due volte. Comincia con \(X=A-B\) e \(Y=B\): per usarla, devi prima far vedere che tali insiemi sono appunti disgiunti, cioè la loro interesezione è vuota; non è troppo difficile rendersene conto che questo è vero (stai sottraendo a uno tutti gli elementi dell'altro!).
Fatto questo applichi il principio, che di per sé sarebbe \[|X\cup Y|=|(A-B)\cup B|=|A-B|+|B|,\] ma tenendo presente la prima delle ovvie uguaglianze del testo ottieni semplicemente \[|A\cup B|=|A-B|+|B| \quad (*).\] Adesso basta ripetere questi passi per una seconda volta, con \(X=A-B\) e \(Y=A\cap B\). La loro interesezione è vuota, e applicando il principio passando dalla seconda delle ovvie uguaglianze hai \[|X\cup Y|=|(A-B)\cup (A\cap B)|=|A|=|A-B|+|A\cap B|.\] Bene, hai finito: sostituisci \(|A-B|\) esprimendolo in termini della \((*)\) e ottieni la tua formula.
Grazie, c'è voluto un po' di tempo, ma ho capito tutto! 
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo