Questa voce o sezione sull'argomento matematica non cita le fonti necessarie o quelle presenti sono insufficienti.
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:
Indice
1Dimostrazioni
1.1Dimostrazione I
1.2Dimostrazione II (induzione su n)
2Storia
3Voci correlate
4Collegamenti esterni
Dimostrazioni
Dimostrazione I
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)
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.
Storia
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).