Beweisarchiv: Mengenlehre: Mengenoperation: Distributivgesetz

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

[Bearbeiten] Durchschnitt über Vereinigung

[Bearbeiten] Voraussetzung

$A,\ B,\ C$ seien beliebige Mengen.

[Bearbeiten] Behauptung

$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$

[Bearbeiten] Beweis

$\subseteq$ : x sei ein Element der linken Seite, also $x \in A \cap (B \cup C)$ . Dann gilt $x \in A$ und $x \in B \cup C$ . Da x in der Vereinigung von B und C liegt, ist (Fall 1) $x \in B$ oder (Fall 2) $x \in C$ . Im Fall 1 ist $x \in A \cap B$ , im Fall 2 ist $x \in A \cap C$ . Damit liegt x in der Vereinigung $(A \cap B) \cup (A \cap C)$ , ist also Element der rechten Seite.

$\supseteq$ : x sei ein Element der rechten Seite, also $x \in (A \cap B) \cup (A \cap C)$ . Damit gilt (Fall 1) $x \in A \cap B$ oder (Fall 2) $x \in A \cap C$ . In beiden Fällen haben wir $x \in A$ . Außerdem ist $x \in B$ oder $x \in C$ , zusammengefasst also $x \in B \cup C$ . Nach Definition des Durchschnitts liegt x in $A \cap (B \cup C)$ , ist also Element der linken Seite.

Alternativ: Es gilt

$x \in A \cap (B \cup C)\iff x\in A\and(x\in B\or x\in C)$

und

$x \in (A \cap B) \cup (A \cap C) \iff (x\in A\and x\in B)\or (x\in A \and x\in C).$

Die Behauptung folgt daher aus der Distributivität von $\and$ über $\or$ , d.h. der allgemeinen Äquivalenz von $p\and(q\or r)$ und $(p\and q)\or(p\and r)$ .

[Bearbeiten] Durchschnitt über beliebige Vereinigung

[Bearbeiten] Voraussetzung

Sei $A$ eine Menge, $I$ eine (Index-)Menge und zu jedem $i\in I$ sei $B i$ eine Menge.

[Bearbeiten] Behauptung

$A \cap \bigcup_{i\in I} B_i = \bigcup_{i\in I}(A \cap B_i)$

Element der linken Menge zu sein ist für jedes $x$ äquivalent zu $x\in A\and\exist i\in I\colon x\in B_i$ , für die rechte dagegen zu $\exist i\in I\colon (x\in A\and x\in B_i)$ . Aber auf prädikatenlogischer Ebene gilt bereits die allgemeine Äquivalenz von $p\and\exist i\colon q_i$ mit $\exist i\colon(p\and q_i)$ - hier mit $p$ für $x\in A$ und $q i$ für $i\in I \and x\in B_i$ :

Aus $p\and\exist i\colon q_i$ folgt sowohl $p$ als auch $\exist i\colon q_i$ , aus letzterem $q i$ für ein geeignetes $i$ . Zusammen mit $p$ folgt für dieses $i$ dann $p\and q_i$ , insbesondere $\exist i\colon(p\and q_i)$ .
Aus $\exist i\colon(p\and q_i)$ folgt - für geeignetes $i$ - die Gültigkeit von $p\and q_i$ , also sowohl $p$ als auch $q i$ . Folglich gilt $q i$ für dieses $i$ , d.h. $\exist i\colon q_i$ , zusammen mit $p$ also $p\and\exist i\colon q_i$ .

[Bearbeiten] Bemerkung

Der vorhergehende Satz kann auch als Spezialfall dieses Satzes für den Fall einer zweielementigen Indexmenge angesehen werden.

[Bearbeiten] Vereinigung über Durchschnitt

[Bearbeiten] Voraussetzung

$A,\ B,\ C$ seien beliebige Mengen.

[Bearbeiten] Behauptung

$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$

[Bearbeiten] Beweis

Hier folgt die Gleichheit aus der allgemeinen Äquivalenz von $p\or(q\and r)$ und $(p\or q)\and(p\or r)$

[Bearbeiten] Vereinigung über beliebigen Durchschnitt

[Bearbeiten] Voraussetzung

Sei $A$ eine Menge, $I$ eine (Index-)Menge und zu jedem $i\in I$ sei $B i$ eine Menge.

[Bearbeiten] Behauptung

$A \cup\bigcap_{i\in I}B_i = \bigcap_{i\in I}(A\cup B_i)$

[Bearbeiten] Beweis

Hier folgt die Aussage aus der allgemeinen Äquivalenz von $p\or\forall i\colon q_i$ und $\forall i\colon (p\or q_i)$ - hier mit $x\in A$ für $p$ sowie $i\in I\Rightarrow x\in B_i$ :

Angenommen, $p$ ist wahr. Dann ist sowohl $p\or\forall i\colon q_i$ wahr als auch $p\or q_i$ für jedes $i$ , also $\forall i\colon (p\or q_i)$ .
Angenommen, p ist falsch.
- Gilt $p\or\forall i\colon q_i$ , so folgt $\forall i\colon q_i$ . Sei $i$ beliebig. Dann folgt hieraus $q i$ und erst recht $p\or q_i$ . Da $i$ beliebig war, folgt $\forall i\colon (p\or q_i)$ .
- Gilt $\forall i\colon (p\or q_i)$ und ist $i$ beliebig, so folgt $p\or q_i$ , nach Voraussetzung sogar $q i$ . Da $i$ beliebig war, folgt $\forall i\colon q_i$ und erst recht $p\or\forall i\colon q_i$ .