Beweisarchiv: Mengenlehre: Mengenoperation: Differenzgesetz

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.

Voraussetzung

$A,B$ seien beliebige Mengen.

Behauptung

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

Beweis

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

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