Logische Theorien

Wir definieren zunächst, was eine Theorie ist. Gegeben sind zunächst die logischen Zeichen $\wedge$, welches für das logische "und" steht, $\vee$, welches für das logische "oder" steht, $\rightarrow$, welches für logische Implikation steht, $\bot$, welches für die immer falsche Aussage, das Falsum, steht, $\forall$, der Allquantor, $\exists$, der Existenzquantor.

Außerdem gegeben seien unendlich viele $n$-stellige Relationssymbole $R_0^n, R_1^n, R_2^n, \ldots$, wobei $n\in\mathbb{N}_1$; unendlich viele $n$-stellige Funktionssymbole $f_0^n, f_1^n, f_2^n, \ldots$, wobei $n\in\mathbb{N}_0$; und unendlich viele Variablensymbole $x_0, x_1, x_2, \ldots$.

Wir arbeiten nun mit dem Alphabet das all diese Symbole enthält, also einem unendlichen Alphabet, in diesem Fall. Nun wollen wir die Sprache der korrekt geformten Aussagen der Logik 1. Stufe definieren. Zunächst definieren wir die Sprache $\operatorname{Ter}$ der Terme:

• Alle Variablensymbole sind Terme: für alle $i$ ist $x_i \in \operatorname{Ter}$.
• Sind $t_1, \ldots, t_k\in\operatorname{Ter}$, so ist für alle $i$ auch $f_i^k(t_1,\ldots,t_k)\in\operatorname{Ter}$, das heißt, man darf einem Funktionssymbol so viele Terme übergeben, wie es Stellen hat.

Nun können wir die Sprache $\operatorname{For}$ der Formeln definieren:

• Es ist $\bot\in\operatorname{For}$: Die immer-falsche Aussage ist eine Formel.
• Sind $t_1,\ldots,t_k\in\operatorname{Ter}$, so ist für alle $i$ auch $R_i^k(t_1,\ldots,t_k)\in\operatorname{For}$, das heißt, man darf einem Relationssymbol so viele Terme übergeben, wie es Stellen hat.
• Sind $A, B\in\operatorname{For}$, so sind auch $A\wedge B, A\vee B, A\rightarrow B\in\operatorname{For}$.
• Ist $A\in\operatorname{For}$, so sind für alle $i$ auch $\forall_{x_i} A, \exists_{x_i} A\in\operatorname{For}$.

Dies war eine sehr technische Definition, die zwar immer funktioniert, aber nicht sehr praktisch zu benutzen ist. In den meisten Fällen schreiben wir nicht $f_i^n$ und $R_i^n$, sondern haben andere, konkretere Funktions- und Relationssymbole. Beispielsweise ist $+$ ein zweistelliges Funktionssymbol, das man zusätzlich üblicherweise als Infix notiert, und $\le$ ist ein zweistelliges Relationssymbol, das man ebenfalls als Infix notiert. Solange klar ist, wie man alles in die formale Schreibweise überführt, sind solche Kurzschreibweisen aber kein Problem, und werden in der Regel ohne größeren Kommentar übernommen.

Ein Spezialfall sind nullstellige Funktionssymbole, die wir ja definiert haben. Diese bezeichnet man auch als Konstanten. Beispielsweise ist die $0$ in vielen Theorien eine solche Konstante.

Freie Variablen und geschlossene Aussagen

Wir sagen, dass Quantoren deren Variablen "binden". Eine Variable heißt "frei", solange sie nicht gebunden wird. Man kann dies rekursiv definieren durch die Funktion $\operatorname{FV} : (\operatorname{Ter}\cup\operatorname{For})\rightarrow \{x_0,\ldots\}$

• $\operatorname{FV}(x_i) := \{x_i\}$
• $\operatorname{FV}(f_i^k(t_1,\ldots,t_k)) := \bigcup\limits_{j=1}^k\operatorname{FV}(t_j) = \operatorname{FV}(t_1) \cup \ldots \cup \operatorname{FV}(t_k)$
• $\operatorname{FV}(\bot) := \emptyset$
• $\operatorname{FV}(R_i^k(t_1,\ldots, t_k)) := \bigcup\limits_{j=1}^k\operatorname{FV}(t_j)$
• $\operatorname{FV}(A\wedge B) = \operatorname{FV}(A\vee B) = \operatorname{FV}(A\rightarrow B) := \operatorname{FV}(A)\cup\operatorname{FV}(B)$
• $\operatorname{FV}(\exists_x A) = \operatorname{FV}(\forall_x A) := \operatorname{FV}(A)\backslash\{x\}$

Diese Funktion deckt alle Möglichkeiten, wie eine Formel gebildet werden kann, ab. Sie gibt genau die Variablen zurück, die nicht irgendwann von einem Quantor gebunden werden. Eine Formel $Q$ heißt geschlossen, wenn $\operatorname{FV}(Q)=\emptyset$.

Theorien, Interpretationen, Modelle

Jetzt wird es erstmal etwas technisch …

Eine Menge von geschlossenen Formeln heißt Theorie. Manchmal wird in der Literatur auch eine Menge von Formeln generell als Theorie bezeichnet. Eine Theorie wird meistens als Axiomensystem benutzt. Beispiele für Theorien ist zum Beispiel die Theorie der Gleichheit $\operatorname{Eq}=\{\forall_x x=x, \forall_x\forall_y x=y \rightarrow y=x, \forall_x\forall_y\forall_z x=y \rightarrow y=z\rightarrow x=z\}$, oder die Gruppentheorie mit dem Relationssymbol $=$, dem zweistelligen Funktionssymbol $\circ$, das man als Infix notiert, der Konstante $e$, und dem einstelligen Funktionssymbol $^{-1}$, das man in Postfix-Notation notiert. Die Theorie enthält die Formeln $\operatorname{Eq}\cup\{ \forall_x a\circ e = a, \forall_x x\circ x^{-1} = e, \forall_x\forall_y\forall_z x\circ(y\circ z) = (x\circ y)\circ z\}$.

Bisher reden wir wiederum nur über Sprachen. Zwar haben Formeln eindeutig die Intention, etwas zu bedeuten, aber was das genau ist, wissen wir noch nicht: Bisher haben wir nur Syntax. Was wir nun brauchen, ist Semantik: Wir definieren, was eine Formel "heißen" soll.

Zunächst definieren wir, was eine Interpretation ist. Intuitiv ordnen wir hier einfach Funktionssymbolen und Relationssymbolen "echte" Funktionen und Relationen zu. Zunächst haben wir einen Träger $D$, das ist die Menge der Objekte, über die wir reden können.

Hierbei gibt es aber erstmal eine technische Schwierigkeit: Wir müssen rekursiv Bedeutungen für Formeln definieren, und haben deshalb zwischendurch auch mit offenen Formeln zu tun. Um dieses technische Problem zu lösen, hat eine Interpretation eine Belegung. Eine Belegung ist eine Funktion $\eta : \mathbb{N}_0\rightarrow D$. Wenn nun die Variable $x_i$ frei in einer Formel vorkommt, "interpretieren" wir sie als das Objekt $\eta(i)$.

Wir definieren nun rekursiv die Funktion ${\frak I}_\eta$, die Zeichenketten (Variablen, Termen und Formeln) "echte" Objekte zuordnet:

• Für jede Variable $x_i$ soll gelten ${\frak I}_\eta(x_i) := \eta(i)$.
• Für jedes verwendete Funktionssymbol $f_i^n$ soll ${\frak I}_\eta(f_i^n)$ eine $n$-Stellige Funktion $D^n\rightarrow D$ sein.
• Für jedes verwendete Relationssymbol $R_i^n$ soll ${\frak I}_\eta(R_i^n)$ eine $n$-Stellige Relation, also eine Teilmenge von $D^n$, sein.

Das Paar ${\cal M}=(D,{\frak I})$ heißt dann Interpretation. Wir definieren nun, was es heißt, dass eine Formel unter einer Interpretation gilt. Wir schreiben ${\cal M}\models F[\eta]$, um auszudrücken, dass eine Formel $F$ in der Interpretation $\cal M$ unter der Belegung $\eta$ gilt. Das ist wie folgt definiert:

• ${\cal M}\not\models \bot[\eta]$ – $\cal M$ erfüllt die immer falsche Aussage nicht.
• ${\cal M}\models R_i^k(t_1,\ldots,t_k)[\eta]$ genau dann, wenn $({\frak I}_\eta(t_1),\ldots,{\frak I}_\eta(t_k)) \in {\frak I}_\eta(R_i^k)$.
• ${\cal M}\models A\wedge B[\eta]$ genau dann, wenn ${\cal M}\models A[\eta]$ und ${\cal M}\models B[\eta]$.
• ${\cal M}\models A\vee B[\eta]$ genau dann, wenn ${\cal M}\models A[\eta]$ oder ${\cal M}\models B[\eta]$.
• ${\cal M}\models A\rightarrow B[\eta]$ genau dann, wenn aus ${\cal M}\models A[\eta]$ folgt ${\cal M}\models B[\eta]$.
• ${\cal M}\models \exists_{x_i} A[\eta]$ genau dann, wenn es ein $o\in D$ gibt, sodass ${\cal M}\models A[\tau]$, wobei $\tau(j) := \left\{\begin{array}{cl} o & \mbox{ falls } j=i \\ \eta(j) & \mbox{ sonst}\end{array}\right.$ die Belegung ist, die mit $\eta$ übereinstimmt, bis auf an der Stelle $i$.
• ${\cal M}\models \forall_{x_i} A[\eta]$ genau dann, wenn für alle $o\in D$ gilt ${\cal M}\models A[\tau]$, wobei wieder $\tau(j) := \left\{\begin{array}{cl} o & \mbox{ falls } j=i \\ \eta(j) & \mbox{ sonst}\end{array}\right.$.

Sei nun $T$ eine Theorie. Wir schreiben ${\cal M}\models T$, um auszudrücken, dass ${\cal M}\models A$ für alle $A\in T$. Eine Belegung brauchen wir an dieser Stelle nicht mehr beachten, da in einer Theorie alle Formeln geschlossen sind. Ist ${\cal M}\models T$, so heißt $\cal M$ ein Modell von $T$.

Oft fordert man noch, dass ${\frak I}_\eta(=) = \{(x,x)\mid x\in D\}$ die "echte" Gleichheit ist. Wir tun das aber nicht.

Beispiel: Gruppen

Die Modelle der oben definierten Gruppentheorie sind, wenn man $=$ als echte Gleichheit definiert, genau die Gruppen. Ein Beispiel für eine Interpretation wäre $(\mathbb{Z}, {\frak Z})$ mit ${\frak Z}(\circ) = (a,b)\mapsto a+b$, ${\frak Z}(^{-1}) = a\mapsto -a$, ${\frak Z}(e) = 0$. Ein anderes Beispiel wäre $(\mathbb{R}\backslash\{0\}, {\frak R})$ mit ${\frak R}(\circ) = (a,b)\mapsto a\cdot b$, ${\frak R}(^{-1}) = a\mapsto\frac{1}{a}$, ${\frak R}(e) = 1$.