Principiul incluziunii-excluderii

În matematică și în special în teoria mulțimilor , principiul incluziunii-excluderii este o identitate care leagă cardinalitatea unei mulțimi , exprimată ca o uniune de mulțimi finite, cu cardinalitatea intersecțiilor dintre aceste mulțimi.

Notăm cu $\left|A\right|$ ${\ displaystyle \ left | A \ right |}$ $\ left | A \ right |$ cardinalitatea unui set $LA$ ${\ displaystyle A}$ $LA$ și ia în considerare o familie finită de mulțimi finite: $A_{1},A_{2},\cdots ,A_{n}$ ${\ displaystyle A_ {1}, A_ {2}, \ cdots, A_ {n}}$ $A_ {1}, A_ {2}, \ cdots, A_ {n}$ . Pentru cardinalitatea unirii acestei familii avem

\left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{i=1}^{n}\left|A_{i}\right|-\sum _{1\leq i<j\leq n}\left|A_{i}\cap A_{j}\right|+\sum _{1\leq i<j<k\leq n}\left|A_{i}\cap A_{j}\cap A_{k}\right|-\ \cdots \ (-1)^{n-1}\left|A_{1}\cap \cdots \cap A_{n}\right|=

{\ displaystyle \ left | \ bigcup _ {i = 1} ^ {n} A_ {i} \ right | = \ sum _ {i = 1} ^ {n} \ left | A_ {i} \ right | - \ sum _ {1 \ leq i <j \ leq n} \ left | A_ {i} \ cap A_ {j} \ right | + \ sum _ {1 \ leq i <j <k \ leq n} \ left | A_ {i} \ cap A_ {j} \ cap A_ {k} \ right | - \ \ cdots \ (-1) ^ {n-1} \ left | A_ {1} \ cap \ cdots \ cap A_ {n} \ dreapta | =}

\ left | \ bigcup _ {{i = 1}} ^ {n} A_ {i} \ right | = \ sum _ {{i = 1}} ^ {n} \ left | A_ {i} \ right | - \ sum _ {{1 \ leq i <j \ leq n}} \ left | A_ {i} \ cap A_ {j} \ right | + \ sum _ {{1 \ leq i <j <k \ leq n} } \ left | A_ {i} \ cap A_ {j} \ cap A_ {k} \ right | - \ \ cdots \ (-1) ^ {{n-1}} \ left | A_ {1} \ cap \ cdots \ cap A_ {n} \ right | =

$=\sum _{i=1}^{n}\left(-1\right)^{i+1}\sum _{1\leq j_{1}<...<j_{i}\leq n}\left|\bigcap _{k=1}^{i}A_{j_{k}}\right|$ ${\ displaystyle = \ sum _ {i = 1} ^ {n} \ left (-1 \ right) ^ {i + 1} \ sum _ {1 \ leq j_ {1} <... <j_ {i} \ leq n} \ left | \ bigcap _ {k = 1} ^ {i} A_ {j_ {k}} \ right |}$ $= \ sum _ {{i = 1}} ^ {n} \ left (-1 \ right) ^ {{i + 1}} \ sum _ {{1 \ leq j_ {1} <... <j_ { i} \ leq n}} \ left | \ bigcap _ {{k = 1}} ^ {{i}} A _ {{j_ {k}}} \ right |$

Reprezentare cu o diagramă Euler-Venn a carcasei pentru trei seturi

In caz $n=2$ ${\ displaystyle n = 2}$ $n = 2$ formula este redusă la aceasta, foarte intuitivă și poate fi obținută din definiții, care pot fi exprimate ca

|A\cup B|=|A|+|B|-|A\cap B|

{\ displaystyle | A \ cup B | = | A | + | B | - | A \ cap B |}

| A \ cup B | = | A | + | B | - | A \ cap B |

In caz $n=3$ ${\ displaystyle n = 3}$ $n = 3$ principiul este exprimat cu egalitate

|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|

{\ displaystyle | A \ cup B \ cup C | = | A | + | B | + | C | - | A \ cap B | - | A \ cap C | - | B \ cap C | + | A \ cap B \ cap C |}

| A \ cup B \ cup C | = | A | + | B | + | C | - | A \ cap B | - | A \ cap C | - | B \ cap C | + | A \ cap B \ cap C |

Acest lucru este demonstrat prin utilizarea de mai multe ori a celei anterioare și a distributivității intersecției față de uniune:

$|A\cup B\cup C|=|(A\cup B)\cup C|=|A\cup B|+|C|-|(A\cup B)\cap C|$ ${\ displaystyle | A \ cup B \ cup C | = | (A \ cup B) \ cup C | = | A \ cup B | + | C | - | (A \ cup B) \ cap C |}$ $| A \ cup B \ cup C | = | (A \ cup B) \ cup C | = | A \ cup B | + | C | - | (A \ cup B) \ cap C |$

\,=\,|A|+|B|-|A\cap B|+|C|-|(A\cap C)\cup (B\cap C)|

{\ displaystyle \, = \, | A | + | B | - | A \ cap B | + | C | - | (A \ cap C) \ cup (B \ cap C) |}

\, = \, | A | + | B | - | A \ cap B | + | C | - | (A \ cap C) \ cup (B \ cap C) |

=|A|+|B|+|C|-|A\cap B|-\left(|A\cap C|+|B\cap C|-|(A\cap C)\cap (B\cap C)|\right)

{\ displaystyle = | A | + | B | + | C | - | A \ cap B | - \ left (| A \ cap C | + | B \ cap C | - | (A \ cap C) \ cap ( B \ cap C) | \ right)}

= | A | + | B | + | C | - | A \ cap B | - \ left (| A \ cap C | + | B \ cap C | - | (A \ cap C) \ cap (B \ cap C) | \ dreapta)

=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|

{\ displaystyle = | A | + | B | + | C | - | A \ cap B | - | A \ cap C | - | B \ cap C | + | A \ cap B \ cap C |}

= | A | + | B | + | C | - | A \ cap B | - | A \ cap C | - | B \ cap C | + | A \ cap B \ cap C |

Demonstrații

Dovada I

Va trebui să se arate că fiecare element al întregului $\bigcup _{i=1}^{n}A_{i}$ ${\ displaystyle \ bigcup _ {i = 1} ^ {n} A_ {i}}$ $\ bigcup _ {{i = 1}} ^ {n} A_ {i}$ se numără o singură dată. Este $x\in A_{1}\cap A_{2}\cap \cdots \cap A_{k}$ ${\ displaystyle x \ in A_ {1} \ cap A_ {2} \ cap \ cdots \ cap A_ {k}}$ $x \ in A_ {1} \ cap A_ {2} \ cap \ cdots \ cap A_ {k}$ Și $x\notin A_{k+1}\cap \cdots \cap A_{n}$ ${\ displaystyle x \ notin A_ {k + 1} \ cap \ cdots \ cap A_ {n}}$ $x \ notin A _ {{k + 1}} \ cap \ cdots \ cap A_ {n}$ , adică rearanjarea mulțimilor și presupunerea că $X$ ${\ displaystyle x}$ $X$ aparțin primului $k$ ${\ displaystyle k}$ $k$ .

Termenul $\sum _{i=1}^{n}\left|A_{i}\right|$ ${\ displaystyle \ sum _ {i = 1} ^ {n} \ left | A_ {i} \ right |}$ $\ sum _ {{i = 1}} ^ {n} \ left | A_ {i} \ right |$ contează $X$ ${\ displaystyle x}$ $X$ exact ${\binom {k}{1}}$ ${\ displaystyle {\ binom {k} {1}}}$ ${\ binom {k} {1}}$ ori, în timp ce al doilea termen al dezvoltării însumării, adică $\sum _{1\leq i<j\leq n}\left|A_{i}\cap A_{j}\right|$ ${\ displaystyle \ sum _ {1 \ leq i <j \ leq n} \ left | A_ {i} \ cap A_ {j} \ right |}$ $\ sum _ {{1 \ leq i <j \ leq n}} \ left | A_ {i} \ cap A_ {j} \ right |$ contează $X$ ${\ displaystyle x}$ $X$ exact ${\binom {k}{2}}$ ${\ displaystyle {\ binom {k} {2}}}$ ${\ binom {k} {2}}$ ori etc.

De aici și elementul $X$ ${\ displaystyle x}$ $X$ în principiul incluziunii-excluderii se numără exact

$\sum _{i=1}^{k}(-1)^{i-1}{\binom {k}{i}}$ ${\ displaystyle \ sum _ {i = 1} ^ {k} (- 1) ^ {i-1} {\ binom {k} {i}}}$ $\ sum _ {{i = 1}} ^ {k} (- 1) ^ {{i-1}} {\ binom {k} {i}}$ ori

Observăm că indicele $the$ ${\ displaystyle i}$ $the$ variază până la $k$ ${\ displaystyle k}$ $k$ pentru că luând în considerare $i=k+1$ ${\ displaystyle i = k + 1}$ $i = k + 1$ , intersecția dintre $k+1$ ${\ displaystyle k + 1}$ $k + 1$ cu ceilalți $A_{i}$ ${\ displaystyle A_ {i}}$ $Către}$ nu va conține $X$ ${\ displaystyle x}$ $X$ .

Acum se poate demonstra cu ușurință, având în vedere dezvoltarea binomului lui Newton , că suma în cauză este egală cu $1$ ${\ displaystyle 1}$ $1$ :

$1-\sum _{i=1}^{k}(-1)^{i-1}{\binom {k}{i}}=\sum _{i=0}^{k}(-1)^{i}{\binom {k}{i}}=(1-1)^{k}=0\qquad \Box$ ${\ displaystyle 1- \ sum _ {i = 1} ^ {k} (- 1) ^ {i-1} {\ binom {k} {i}} = \ sum _ {i = 0} ^ {k} (-1) ^ {i} {\ binom {k} {i}} = (1-1) ^ {k} = 0 \ qquad \ Box}$ $1- \ sum _ {{i = 1}} ^ {k} (- 1) ^ {{i-1}} {\ binom {k} {i}} = \ sum _ {{i = 0}} ^ {k} (- 1) ^ {{i}} {\ binom {k} {i}} = (1-1) ^ {k} = 0 \ qquad \ Box$

Dovada II (inducție pe n )

Avem asta

$\left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{k=1}^{n}(-1)^{k+1}\sum _{1\leq i_{1}<\cdots <i_{k}\leq n}\left|A_{i_{1}}\cap A_{i_{2}}\cap \cdots \cap A_{i_{k}}\right|$ ${\ displaystyle \ left | \ bigcup _ {i = 1} ^ {n} A_ {i} \ right | = \ sum _ {k = 1} ^ {n} (- 1) ^ {k + 1} \ sum _ {1 \ leq i_ {1} <\ cdots <i_ {k} \ leq n} \ left | A_ {i_ {1}} \ cap A_ {i_ {2}} \ cap \ cdots \ cap A_ {i_ { k}} \ dreapta |}$ $\ left | \ bigcup _ {{i = 1}} ^ {n} A_ {i} \ right | = \ sum _ {{k = 1}} ^ {n} (- 1) ^ {{k + 1} } \ sum _ {{1 \ leq i_ {1} <\ cdots <i_ {k} \ leq n}} \ left | A _ {{i_ {1}}} \ cap A _ {{i_ {2}} } \ cap \ cdots \ cap A _ {{i_ {k}}} \ right |$

Să verificăm $n=2$ ${\ displaystyle n = 2}$ $n = 2$ , întrucât pentru $n=1$ ${\ displaystyle n = 1}$ $n = 1$ este banal $\left|A_{1}\right|=\left|A_{1}\right|$ ${\ displaystyle \ left | A_ {1} \ right | = \ left | A_ {1} \ right |}$ $\ left | A_ {1} \ right | = \ left | A_ {1} \ right |$ , iar cazul va fi apoi util în continuarea probei:

$\left|A_{1}\cup A_{2}\right|=\left|A_{1}\right|+\left|A_{2}\right|-\left|A_{1}\cap A_{2}\right|$ ${\ displaystyle \ left | A_ {1} \ cup A_ {2} \ right | = \ left | A_ {1} \ right | + \ left | A_ {2} \ right | - \ left | A_ {1} \ limita A_ {2} \ right |}$ $\ left | A_ {1} \ cup A_ {2} \ right | = \ left | A_ {1} \ right | + \ left | A_ {2} \ right | - \ left | A_ {1} \ cap A_ { 2} \ dreapta |$

Să ne asumăm acum principiul adevărat $n$ ${\ displaystyle n}$ $n$ și dovedim că atunci este valabil și pentru $n+1$ ${\ displaystyle n + 1}$ $n + 1$ seturi. Merită asta

$\bigcup _{i=1}^{n+1}A_{i}=\left(\bigcup _{i=1}^{n}A_{i}\right)\cup A_{n+1}$ ${\ displaystyle \ bigcup _ {i = 1} ^ {n + 1} A_ {i} = \ left (\ bigcup _ {i = 1} ^ {n} A_ {i} \ right) \ cup A_ {n + 1}}$ $\ bigcup _ {{i = 1}} ^ {{n + 1}} A_ {i} = \ left (\ bigcup _ {{i = 1}} ^ {n} A_ {i} \ right) \ cup A_ {{n + 1}}$

De vreme ce ipoteza este adevărată pentru $n=2$ ${\ displaystyle n = 2}$ $n = 2$ merita

$\left|\bigcup _{i=1}^{n+1}A_{i}\right|=\left|\bigcup _{i=1}^{n}A_{i}\right|+\left|A_{n+1}\right|-\left|\left(\bigcup _{i=1}^{n}A_{i}\right)\cap A_{n+1}\right|$ ${\ displaystyle \ left | \ bigcup _ {i = 1} ^ {n + 1} A_ {i} \ right | = \ left | \ bigcup _ {i = 1} ^ {n} A_ {i} \ right | + \ left | A_ {n + 1} \ right | - \ left | \ left (\ bigcup _ {i = 1} ^ {n} A_ {i} \ right) \ cap A_ {n + 1} \ right | }$ $\ left | \ bigcup _ {{i = 1}} ^ {{n + 1}} A_ {i} \ right | = \ left | \ bigcup _ {{i = 1}} ^ {n} A_ {i} \ right | + \ left | A _ {{n + 1}} \ right | - \ left | \ left (\ bigcup _ {{i = 1}} ^ {n} A_ {i} \ right) \ cap A_ {{n + 1}} \ right |$

Adică

$\sum _{k=1}^{n}(-1)^{k+1}\sum _{1\leq i_{1}<\cdots <i_{k}\leq n}\left|A_{i_{1}}\cap \cdots \cap A_{i_{k}}\right|+\left|A_{n+1}\right|-\sum _{k=1}^{n}(-1)^{k+1}\sum _{1\leq i_{1}<\cdots <i_{k}\leq n}\left|A_{i_{1}}\cap \cdots \cap A_{i_{k}}\cap A_{n+1}\right|=$ ${\ displaystyle \ sum _ {k = 1} ^ {n} (- 1) ^ {k + 1} \ sum _ {1 \ leq i_ {1} <\ cdots <i_ {k} \ leq n} \ left | A_ {i_ {1}} \ cap \ cdots \ cap A_ {i_ {k}} \ right | + \ left | A_ {n + 1} \ right | - \ sum _ {k = 1} ^ {n} (-1) ^ {k + 1} \ sum _ {1 \ leq i_ {1} <\ cdots <i_ {k} \ leq n} \ left | A_ {i_ {1}} \ cap \ cdots \ cap A_ {i_ {k}} \ cap A_ {n + 1} \ right | =}$ $\ sum _ {{k = 1}} ^ {n} (- 1) ^ {{k + 1}} \ sum _ {{1 \ leq i_ {1} <\ cdots <i_ {k} \ leq n} } \ left | A _ {{i_ {1}}} \ cap \ cdots \ cap A _ {{i_ {k}}} \ right | + \ left | A _ {{n + 1}} \ right | - \ sum _ {{k = 1}} ^ {n} (- 1) ^ {{k + 1}} \ sum _ {{1 \ leq i_ {1} <\ cdots <i_ {k} \ leq n} } \ left | A _ {{i_ {1}}} \ cap \ cdots \ cap A _ {{i_ {k}}} \ cap A _ {{n + 1}} \ right | =$

$=\sum _{k=1}^{n+1}(-1)^{k+1}\sum _{1\leq i_{1}<\cdots <i_{k}\leq n+1}\left|A_{i_{1}}\cap \cdots \cap A_{i_{k}}\right|$ ${\ displaystyle = \ sum _ {k = 1} ^ {n + 1} (- 1) ^ {k + 1} \ sum _ {1 \ leq i_ {1} <\ cdots <i_ {k} \ leq n +1} \ left | A_ {i_ {1}} \ cap \ cdots \ cap A_ {i_ {k}} \ right |}$ $= \ sum _ {{k = 1}} ^ {{n + 1}} (- 1) ^ {{k + 1}} \ sum _ {{1 \ leq i_ {1} <\ cdots <i_ {k } \ leq n + 1}} \ left | A _ {{i_ {1}}} \ cap \ cdots \ cap A _ {{i_ {k}}} \ right |$

Această propoziție este adevărată deoarece cei doi termeni ai egalității au același addenda cu același semn. Așa cum a fost menit să demonstreze.

Istorie

Principiul a fost folosit de Nicolaus al II-lea Bernoulli (1695-1726); formula este atribuită lui Abraham de Moivre (1667-1754); Joseph Sylvester (1814-1897) și Henri Poincaré (1854-1912) sunt amintiți pentru utilizarea și înțelegerea domeniului său de aplicare.

Elemente conexe

linkuri externe

( EN ) Principiul includerii-excluderii , în Encyclopedia Britannica , Encyclopædia Britannica, Inc.

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică