0 Daumen
357 Aufrufe

Aufgabe:. Seien A, B, C endliche Mengen. Zeigen Sie die folgenden Aussagen

|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|.

Avatar von

1 Antwort

0 Daumen

Es reicht zu zeigen, dass für beliebige endliche Mengen AA und BB gilt, dass AB=A+BAB|A\cup B| = |A| + |B| - |A\cap B|, denn dann folgt die zu beweisende Aussage unmittelbar über die Substitution B(BC)B\rightarrow (B\cup C) und entsprechende Mengenumformungen.


Wir dürfen aufgrund der Endlichkeit annehmen, dass A={a1,...,an}A=\{a_1,...,a_n\} und B={b1,...,bm}B=\{b_1,...,b_m\} mit entsprechenden Mächtigkeiten A=n|A|=n und B=m|B|=m.

Weiter nehmen wir o.B.d.A. an, dass a1=b1,...,ak=bka_1 = b_1, ..., a_k=b_k für ein kmin(n,m)k\leq min(n,m), also AB={a1,...,ak}={b1,...,bk}A\cap B = \{a_1,...,a_k\}=\{b_1,...,b_k\} und insbesondere AB=k|A\cap B| = k.

Es folgt AB=(A(AB))BA\cup B = (A \setminus (A\cap B)) \cup B und offenbar sind die Mengen A(AB)A\setminus (A\cap B) und BB disjunkt.

Damit gilt AB=(A(AB))B=A(AB)+B|A\cup B| = |(A \setminus (A\cap B)) \cup B| = |A \setminus (A\cap B)| + |B|.

Da A(AB)={ak+1,...,an}A\setminus (A\cap B) = \{a_{k+1},...,a_n\} folgt offenbar A(AB)=nk=AAB|A\setminus (A\cap B)| = n-k = |A| - |A\cap B|.

Entsprechend folgt schlussendlich AB=AAB+B=A+BAB|A\cup B| = |A| - |A\cap B| + |B| = |A| + |B| - |A\cap B|.

Avatar von 2,9 k

Ein anderes Problem?

Stell deine Frage