4.1 Die Mengenlehre

In der gesamten Mathematik, aber auch darüber hinaus, spielen die Begriffe ,,Element`` und ,,Menge`` eine große Rolle. Man schreibt $m \in X$, und liest ,,$m$ ist Element der Menge $X$``. Es wird angenommen, daß man für jedes Element $m$ und jede Menge $X$ immer entscheiden kann, ob die Beziehung $m \in X$ gilt oder nicht. In der folgenden Einführung werden wir allerdings völlig auf die Elementbeziehung zur Definition der Mengenlehre verzichten.

4.1.1 Grundlegende Definitionen

Undefinierte Beziehung zwischen zwei Objekten, sie seien Mengen genannt, ist die Teilmengenbeziehung $\subseteq$. Diese Beziehung sei wie folgt definiert:

(M1)	$x \subseteq x$
(M2)	$x \subseteq y \;\wedge\; y \subseteq x \Longleftrightarrow x = y$
(M3)	$x \subseteq y \;\wedge\; y \subseteq z \Longrightarrow x \subseteq z$
(M4)	$\emptyset \subseteq x$
(M5)	$x \subseteq G$
(M6)	$x \subseteq y \;\wedge\; x \subseteq z \Longrightarrow x \subseteq y \cap z$
(M7)	$x \subseteq z \;\wedge\; y \subseteq z \Longrightarrow x \cup y \subseteq z$
(M8)	$x \cap ( y \cup z ) = ( x \cap y ) \cup ( x \cap z )$
(M9)	$x \cup ( y \cap z ) = ( x \cup y ) \cap ( x \cup z )$
(M10)	$x' \cap x = \emptyset$
(M11)	$x' \cup x = G$

$x$, $y$ und $z$ sind allgemeine Mengen, $\emptyset$ und $G$ sind spezielle Mengen. $x'$ wird das Komplement der Menge $x$ genannt und ist selbst eine Menge.

4.1.2 Mengenlehre - Boolescher Verband

Satz 4.1  

Die Grundgesetze der Mengenlehre bilden einen Booleschen Verband, wenn man $\subseteq$ mit $\sqsubseteq$ übersetzt, sowie $\cap$ mit $\sqcap$, $\cup$ mit $\sqcup$, $\emptyset$ mit 0, $G$ mit 1 und ' mit $\overline{~}$.

Beweis: Es ist nachzuweisen, daß sich alle Axiome des Booleschen Verbandes aus den Grundgesetzen der Mengenlehre nach Übersetzung ableiten lassen.

(H1) entspricht nach Übersetzung (M1), (H2) entspricht nach Übersetzung (M2), (H3) entspricht nach Übersetzung (M3). Aus (H1 - H3) lassen sich (V1 - V3) ableiten, wie bereits in Abschnitt 2.1.3 gezeigt wurde.

(V4) entspricht nach Übersetzung (M8) und (M9).

Die Komplementdefinition 2.12 ist nach Übersetzung identisch mit (M10) und (M11).

Definition 2.8 entspricht nach Übersetzung der Definition des Nullobjektes (M4).

Definition 2.8 entspricht nach Übersetzung der Definition des Einsobjektes (M5).

Es muß auch noch die im Booleschen Gleichungskalkül verwendete Einsetzungs- oder auch Substitutionsregel bewiesen werden. Das ist um so schwieriger, da sie überhaupt nicht in dem Kalkül formuliert werden kann, sondern nur im logischen Hintergrundkalkül.

Dort lautet sie etwa $G, A = B \Longrightarrow G'$, mit $G$ als Gleichung in der die Variable $A$ auftaucht und $G'$ als Gleichung $G$, in der ein Vorkommen von $A$ durch $B$ ersetzt wurde.

Allgemein ist eine Gleichung $G$ von der Form $T = C$, mit $T$ ein Term, der die Variable $A$ enthält. Ein Term ist induktiv definiert als ,,Jede Variable/Konstante ist ein Term, wenn $A$ ein Term ist, dann ist $\overline{A}$ ein Term, ist auch $B$ ein Term, so ist $A \sqcap B$ und $A \sqcup B$ ein Term.`` Ein Beweis der Substitutionsregel kann daher z.B. induktiv erfolgen:

Induktionsanfang: Sei die Variable $A$ ein Term. Dann ist nachzuweisen: $A = C, A = B \Longrightarrow B = C$. Der Beweis ist einfach durch mehrfache Anwendung von (M2).

Induktionsschritt:

a)

$A \cup V = C, A = B \Longrightarrow B \cup V = C$. Nach Voraussetzung ist $B$ Teilmenge von $A$, $A$ Teilmenge von $A \cup V$, $A \cup V$ von $C$. Daher ist $B$ Teilmenge von $C$. Ebenso ist $V$ Teilmenge von $A \cup V$ und $A \cup V$ ist Teilmenge von $C$. Daher ist $V$ Teilmenge von $C$. Aus $B \subseteq C$ und $V \subseteq C$ folgt nach (M7) $B \cup V \subseteq C$. Andererseits ist $A$ Teilmenge von $B$ und $B$ Teilmenge von $B \cup V$. Daher ist $A$ Teilmenge von $B \cup V$. Außerdem ist $V$ Teilmenge von $B \cup V$. Nach (M7) ist daher auch $A \cup V$ Teilmenge von $B \cup V$. Nach Voraussetzung ist $C$ Teilmenge von $A \cup V$, daher ist $C$ Teilmenge von $B \cup C$. Hieraus und aus $B \cup V \subseteq C$ folgt $B \cup V = C$.

b)

$A \cap V = C, A = B \Longrightarrow B \cap V = C$. Der Beweis ist dual zu a).

c)

$A' = C, A = B \Longrightarrow B' = C$. Wenn $A = B$ ist, dann ist auch $A' = B'$. Daher ist $A'$ auch Teilmenge von $B'$. Mit $A'$ Teilmenge von $C$ folgt daher $B'$ Teilmenge von $C$. Andererseits folgt aus $C$ Teilmenge von $A'$ und $A'$ Teilmenge von $B'$ das $C$ Teilmenge von $B'$ ist. Daher ist $B' = C$.

Satz 4.2  

Ein Boolescher Verband ist eine Mengenalgebra, wenn man $\sqsubseteq$ mit $\subseteq$ übersetzt, sowie $\sqcap$ mit $\cap$, $\sqcup$ mit $\cup$, 0 mit $\emptyset$, 1 mit $G$ und $\overline{~}$ mit '.

Beweis: Es ist nachzuweisen, daß sich alle Grundgesetze der Mengenlehre aus den Axiomen des Booleschen Verbandes nach Übersetzung ableiten lassen.

(M1) entspricht nach Übersetzung Axiom (H1).

(M2) entspricht nach Übersetzung Axiom (H2).

(M3) entspricht nach Übersetzung Axiom (H3).

(H1 - H3) sind aus (V1 - V3) ableitbar, wie in Abschnitt 2.1.3 gezeigt wurde.

(M4) entspricht nach Übersetzung Definition 2.8

(M5) entspricht nach Übersetzung Definition 2.8

(M6) entspricht nach Übersetzung Definition 2.10

(M7) entspricht nach Übersetzung Definition 2.10

(M8) entspricht nach Übersetzung Axiom (V4)

(M9) entspricht nach Übersetzung Axiom (V4).

(M10) entspricht nach Übersetzung Definition 2.12

(M11) entspricht nach Übersetzung Definition 2.12

Damit ist die Äquivalenz des Booleschen Verbandes mit der Mengenalgebra bewiesen. Diese Mengenalgebra basiert allerdings nur auf der Teilmengenbeziehung, bzw. der Gleichheit, nicht auf der Elementbeziehung.