Klassenlogik – „Mathe für Nicht-Freaks“

Dieser Abschnitt ist noch im Entstehen und noch nicht offizieller Bestandteil des Buchs. Gib den Autoren Zeit, den Inhalt anzupassen!

Was in unserer Logik-Sprache noch fehlt, sind Mengen (Klassen). Im Kapitel Prädikatenlogik haben wir im Beispiel Arithmetik zwei 1-stellige Prädikate ${\mathcal {N}}$ (... ist eine natürliche Zahl) und ${\mathcal {G}}$ (... ist gerade) verwendet. In der Mathematik wird aber statt ${\mathcal {N}}$ die Menge der natürlichen Zahlen $\mathbb {N}$ verwendet und statt ${\mathcal {N}}(x)$ wird $x\in \mathbb {N}$ ( x ist ein Element von $\mathbb {N}$ geschrieben. Das Prädikat ${\mathcal {G}}$ wird durch die Definition der Menge der geraden Zahlen $\{x|x\in \mathbb {N} \land \exists z:2\cdot z=x\}$ überflüssig.

Die Sprache der Klassenlogik

Wir erweitern das Alphabet der Prädikatenlogik um das Elementzeichen $\in$ und um den Klassenbildungsoperator $\{|\}$:

Definition (Alphabet der Klassenlogik)

Die Sprache der Klassenlogik hat elf Arten von Zeichen:

1. die Aussagenkonstanten $K_{0},K_{1},K_{2},\dots$, ${\mathsf {W}}$ und ${\mathsf {F}}$,
2. die Junktoren $\neg$, $\land$, $\lor$, ${\dot {\lor }}$, $\Rightarrow$ und $\Leftrightarrow$,
3. die Klammern $($ und $)$ und das Komma $,$,
4. die Konstanten $c_{0},c_{1},c_{2},\dots$,
5. die Operationssymbole $F_{0},F_{1},F_{2},\dots$,
6. die Prädikate $P_{0},P_{1},P_{2},\dots$,
7. das Gleichheitszeichen $=$,
8. die Variable $v_{0},v_{1},v_{2},\dots$,
9. die Quantoren $\forall$, $\exists$ und $\exists !$ mit dem Doppelpunkt $:$,
10. das Elementzeichen $\in$,
11. den Klassenbildungsoperator $\{|\}$.

Jedem Prädikat und jedem Operationssymbol ist eine natürliche Zahl $n$ als Stellenzahl zugeordnet.

Definition (Terme der Klassenlogik)

Die Terme der Klassenlogik werden nach folgenden Regeln gebildet:

1. Jede Konstante $c$ und jede Variable $x$ ist ein Term.
2. Sind $t_{1},t_{2},\dots ,t_{n}$ Terme und ist $F$ ein $n$-stelliges Operationssymbol, so ist $F(t_{1},t_{2},\dots ,t_{n})$ ein Term.
3. Ist $x$ eine Variable und ist $A$ eine Formel, so ist $\{x|A\}$ ein Term.

Es gibt keine weiteren Terme.

Definition (Formeln der Klassenlogik)

Die Formeln der Klassenlogik werden nach folgenden Regeln gebildet:

1. Jede Aussagenkonstante ist eine Formel, ${\mathsf {W}}$ und ${\mathsf {F}}$ sind Formeln.
2. Ist $A$ eine Formel, so ist auch $\neg A$ eine Formel.
3. Sind $A$ und $B$ Formeln, so sind auch $(A\land B)$, $(A\lor B)$, $(A{\dot {\lor }}B)$, $(A\Rightarrow B)$ und $(A\Leftrightarrow B)$ Formeln.
4. Sind $t_{1},t_{2},\dots ,t_{n}$ Terme und ist $P$ ein $n$-stelliges Prädikat, so ist $P(t_{1},t_{2},\dots ,t_{n})$ eine Formel.
5. Sind $t$ und $s$ Terme, so ist $t=s$ eine Formel.
6. Ist $x$ eine Variable und ist $A$ eine Formel, so sind   $\forall x:A$,   $\exists x:A$   und   $\exists !x:A$   Formeln.
7. Sind $t$ und $s$ Terme, so ist $t\in s$ eine Formel.

Es gibt keine weiteren Formeln.

Die Regeln 1. und 2. für Terme und die Regeln 1. bis 6. für Formeln entsprechen den Regeln für die Terme und Formeln der Prädikatenlogik. Deshalb gilt:

Satz

Alle Ausdrücke der Aussagenlogik und der Prädikatenlogik sind auch Ausdrücke der Klassenlogik.

Klassenlogik und Mengenlehre

In der Sprache der Klassenlogik kann - und wird! - üblicherweise die Elementare Mengenlehre formuliert, vgl. Mengenlehre. Damit das funktioniert müssen für $\in$ und $\{|\}$ die folgenden Prinzipien gelten. Zunächst 3 Definitionen.

Definition (Leere Menge)

$\varnothing :=\{x\,|\,x\neq x\}$

Definition (Allklasse)

${\mathcal {V}}:=\{x\,|\,x=x\}$

Definition (Klassen)

$Cls(s):\Leftrightarrow s=\{x\,|\,x\in s\}$

Elemente sind Individuen: $s\in t\Rightarrow s\in {\mathcal {V}}$

Der Zusammenhang zwischen der Klassenbildung $\{x\,|\,\dotsm \}$ und der Elementrelation $\in$ wird Abstraktionsprinzip genannt:

Abstraktionsprinzip: $\forall y:\left(y\in \{x\,\vert A\left(x\right)\}\Leftrightarrow A\left(y\right)\right)$

In Worten: $y$ ist ein Element der Klasse $\{x\,\vert A\left(x\right)\}$ genau dann, wenn die Aussage $A(y)$ gilt.

Und für die Gleichheit von Klassen gilt das Extensionalitätsprinzip: zwei Klassen $s$ und $t$ sind gleich wenn sie dieselben Elemente haben.

Extensionalitätsprinzip: $Cls(s)\land Cls(t)\land \forall x:(x\in s\Leftrightarrow x\in t)\Rightarrow s=t$

Satz (Der Klassenbildungsoperator liefert Klassen)

$Cls(\{x|A(x)\})$

Beweis (Der Klassenbildungsoperator liefert Klassen)

Das Abstraktionsprinzip liefert $y\in \{x|x\in \{x|A(x)\}\}\Leftrightarrow y\in \{x|A(x)\}$. Daraus folgt mit dem Extensionalitätsprinzip $\{x|x\in \{x|A(x)\}\}=\{x|A(x)\}$ und mit der Definition von $Cls$ also $Cls(\{x|A(x)\})$. ✔