Principio di inclusione-esclusione

Da Wikipedia, l'enciclopedia libera.
Vai alla navigazione Vai alla ricerca

In matematica ed in particolare nella teoria degli insiemi, il principio di inclusione-esclusione è un'identità che mette in relazione la cardinalità di un insieme, espresso come unione di insiemi finiti, con le cardinalità di intersezioni tra questi insiemi.

Denotiamo con la cardinalità di un insieme e consideriamo una famiglia finita di insiemi finiti: . Per la cardinalità dell'unione di tale famiglia si ha

Rappresentazione con un diagramma di Eulero-Venn del caso per tre insiemi

Nel caso la formula si riduce a quella, molto intuitiva e ricavabile dalle definizioni, esprimibile come

Nel caso il principio si esprime con l'uguaglianza

Questa si dimostra servendosi più volte della precedente e della distributività della intersezione rispetto alla unione:

Dimostrazioni

[modifica | modifica wikitesto]

Dimostrazione I

[modifica | modifica wikitesto]

Si dovrà dimostrare che ogni elemento dell'insieme viene contato una e una sola volta. Sia e , riordinando cioè gli insiemi e supponendo che appartenga ai primi .

Il termine conta esattamente volte, mentre il secondo termine dello sviluppo della sommatoria, cioè conta esattamente volte, ecc.

Dunque l'elemento nel principio di inclusione-esclusione è contato esattamente

volte

Osserviamo che l'indice varia fino a perché considerando , l'intersezione di con gli altri non conterrà .

Si può ora dimostrare facilmente, considerando lo sviluppo del Binomio di Newton, che la sommatoria in questione è uguale a :

Dimostrazione II (induzione su n)

[modifica | modifica wikitesto]

Abbiamo che

Verifichiamola per , dato che per è banalmente , e il caso tornerà poi utile nel proseguimento della dimostrazione:

Ipotizziamo ora vero il principio per insiemi, e dimostriamo che allora è vero anche per insiemi. Vale che

Poiché l'ipotesi è vera per vale

Ovvero

Tale proposizione è vera in quanto i due termini dell'uguaglianza hanno gli stessi addendi con lo stesso segno. Come volevasi dimostrare.

Il principio è stato utilizzato da Nicolaus II Bernoulli (1695-1726); la formula viene attribuita ad Abraham de Moivre (1667-1754); per il suo utilizzo e per la comprensione della sua portata vengono ricordati Joseph Sylvester (1814-1897) ed Henri Poincaré (1854-1912).

Voci correlate

[modifica | modifica wikitesto]

Collegamenti esterni

[modifica | modifica wikitesto]
  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica