Beweisarchiv: Mengenlehre: Mengenoperation: Differenzgesetz

Aus Wikibooks

Injektivität Surjektivität Bijektivität: Faktoren - Komposition - Linksinverse - Linkskürzbarkeit - Rechtsinverse - Rechtskürzbarkeit

Mächtigkeiten (Kardinalzahlen): lineare Ordnung - Kardinalität und Bijektionen - Potenzmenge

Deskriptive Mengenlehre: Satz von Young

Rechenregeln für Mengenoperationen: Assoziativgesetze - Distributivgesetze - Differenzgesetze

Inhaltsverzeichnis

1 Durchschnitt mit Differenz

[Bearbeiten] Durchschnitt mit Differenz

Dieser Beweis kommt aus dem Bereich der Datenbanken und soll zeigen, dass jeder Durchschnitt (INTERSECT) auch mit dem Subtrahieren (MINUS) von Mengen abgebildet werden kann.

[Bearbeiten] Voraussetzung

$A,\ B$ seien beliebige Mengen.

[Bearbeiten] Behauptung

$A \cap B = A \setminus ( A \setminus B)$

[Bearbeiten] Beweis

Es ist $x\in A\setminus B$ genau dann, wenn $x\in A \and \neg(x\in B)$ , also gilt weiter $x\in A\setminus(A\setminus B)$ genau dann, wenn $x\in A\and\neg(x\in A \and \neg(x\in B))$ . Es ist zu zeigen, dass dies äquivalent zu $x\in A\and x\in B$ ist. In der Tat gilt bereits im Rahmen der Aussagenlogik die Äquivalenz von $p\and\neg(p\and\neg q)$ und $p\and q$ :

Es gelte $p\and q$ , insbesondere sowohl $p$ als auch $q$ . Somit ist $p\and \neg q$ falsch und $\neg(p\and\neg q)$ sowie schließlich $p\and\neg(p\and\neg q)$ wahr.
Es gelte $p\and\neg(p\and\neg q)$ , insbesondere $p$ und $\neg(p\and\neg q)$ . Letzteres ist nach De Morgan äquivalent zu $\neg p\or\neg\neg q$ . Wegen $p$ folgt $\neg\neg q$ bzw $q$ (doppelte Negation). Insgesamt ergibt sich also $p\and q$ .