Kurs:Einführung in die mathematische Logik (Osnabrück 2011-2012)/Vorlesung 5

Weitere Axiomensysteme

In der letzten Vorlesung haben wir gesehen, wie man die Gruppenaxiome in der Prädikatenlogik erster Stufe formulieren kann. Eine Gruppe im herkömmlichen mathematischen Sinn ist prädikatenlogisch formuliert eine Menge zusammen mit einer Interpretation für eine Konstante und ein zweistelliges Funktionssymbol (nämlich ein ausgezeichnetes Element und eine Verknüpfung), unter der gemäß der Modellbeziehung die Gruppenaxiome gültig sind.

Wir geben ein weiteres Beispiel, das die Beziehung zwischen mathematischer und prädikatenlogischer Formulierung deutlich machen soll.

Definition

Eine Relation ${}\preccurlyeq$ auf einer Menge ${}I$ heißt Ordnungsrelation oder Ordnung, wenn folgende drei Bedingungen erfüllt sind.

1. Es ist ${}i\preccurlyeq i$ für alle ${}i\in I$.
2. Aus ${}i\preccurlyeq j$ und ${}j\preccurlyeq k$ folgt stets ${}i\preccurlyeq k$.
3. Aus ${}i\preccurlyeq j$ und ${}j\preccurlyeq i$ folgt ${}i=j$.

Neben den Variablen besteht das zugehörige Symbolalphabet allein aus einem zweistelligen Relationssymbol, das wir ebenfalls mit ${}\preccurlyeq$ bezeichnen. Die für eine Ordnung verlangten Eigenschaften führen zu dem folgenden einstufigen Axiomensystem ${}\Gamma$.

1. $\forall x(x\preccurlyeq x).$

2. $\forall x\forall y\forall z(x\preccurlyeq y\wedge y\preccurlyeq z\rightarrow x\preccurlyeq z).$

3. $\forall x\forall y(x\preccurlyeq y\wedge y\preccurlyeq x\rightarrow x=y).$

In einer Menge mit einer zweistelligen Relation ${}R$ gilt das Axiomensystem ${}\Gamma$ genau dann, wenn die Relation eine Ordnungsrelation ist.

Die Folgerungsbeziehung

Mit Axiomensystemen verbindet man die Vorstellung, dass daraus „wichtige“ weitere Eigenschaften beweisbar sind. In einer jeden Gruppe gelten nicht nur die Gruppenaxiome, sondern auch alle Gesetzmäßigkeiten, die man aus den Gruppenaxiomen folgern kann. Dies wird in der mathematischen Logik durch den Folgerungsbegriff präzisiert.

Definition

Es sei ${}S$ ein Symbolalphabet erster Stufe, ${}\Gamma$ eine Menge von ${}S$- Ausdrücken und ${}\alpha$ ein ${}S$-Ausdruck. Man sagt, dass ${}\alpha$ aus ${}\Gamma$ folgt, geschrieben ${}\Gamma \vDash \alpha$, wenn für jede ${}S$- Interpretation ${}I$ mit ${}I\vDash \Gamma$ auch ${}I\vDash \alpha$ gilt.

Die Folgerungsbeziehung verwendet also das gleiche Symbol wie die Gültigkeitsbeziehung. Dass aus einer gewissen Ausdrucksmenge ${}\Gamma$ ein gewisser Ausdruck ${}p$ folgt, erfordert eine mathematische Argumentation, die aufzeigt, dass eine Menge mit zusätzlichen Strukturen, die ${}\Gamma$ erfüllt, stets auch ${}p$ erfüllen muss.

Beispiel

In einer Gruppe ist das neutrale Element, das es aufgrund der Definition einer Gruppe geben muss, eindeutig bestimmt. Mathematisch wird dies so bewiesen: Es sei ${}e$ das neutrale Element der Gruppe, und sei ${}e'$ ein weiteres Element, das ebenfalls die Eigenschaft des neutralen Elements erfüllt, d.h. es gilt ${}e'x=xe'=x$ für alle ${}x\in G$. Dann gilt einerseits ${}e'=e'e$, da ${}e$ neutrales Element ist, und andererseits ${}e'e=e$, da auch ${}e'$ neutrales Element ist. Also ist insgesamt ${}e'=e'e=e$ und ${}e$ und ${}e'$ stimmen überein.

Die Eindeutigkeit des neutralen Elementes kann man als den Ausdruck

$\alpha :=\forall z(\forall x(zx=x\wedge xz=x)\rightarrow z=e)$

ansetzen, und die obige mathematische Argumentation bedeutet, dass der Ausdruck ${}\alpha$ aus den Gruppenaxiomen ${}\Gamma$ folgt, also die Folgerungsbeziehung

$\Gamma \vDash \alpha$

vorliegt.

Allgemeingültige Ausdrücke

Definition

Es sei ${}S$ ein Symbolalphabet und ${}\alpha$ ein ${}S$- Ausdruck in der Prädikatenlogik erster Stufe. Man nennt ${}\alpha$ allgemeingültig (oder eine semantische Tautologie), wenn er in jeder ${}S$- Interpretation ${}I$ gilt, also ${}I\vDash \alpha$ wahr ist.

Allgemeingültige Ausdrücke sind Tautologien im semantischen Sinn. Wir werden später noch Tautologien im syntaktischen Sinn kennenlernen und die Übereinstimmung der beiden Konzepte zeigen. Da ein allgemeingültiger Ausdruck ${}p$ in jeder Interpretation gilt, kann man auch sagen, dass ${}p$ aus der leeren Ausdrucksmenge folgt, also ${}\emptyset \vDash p$ gilt. Beispiele sind die Ausdrücke

$\forall x\forall y\forall z((x=y\wedge y=z)\rightarrow x=z)$

oder

$(\forall xp)\rightarrow p$

(wobei ${}p$ ein Ausdruck ist). Wenn ${}p_{1},p_{2},p_{3}$ die Gruppenaxiome sind, und ${}p$ die im obigen Beispiel erwähnte Eindeutigkeitsausssage für das neutrale Element ist, so ist auch

$p_{1}\wedge p_{2}\wedge p_{3}\rightarrow p$

allgemeingültig.

Definition

Es sei ${}S$ ein Symbolalphabet und es sei ${}\alpha$ ein ${}S$- Ausdruck in der Prädikatenlogik erster Stufe. Man nennt ${}\alpha$ erfüllbar, wenn es eine ${}S$- Interpretation ${}I$ mit ${}I\vDash \alpha$ gibt.

Für eine Ausdrucksmenge ${}\Gamma$ bedeutet die Erfüllbarkeit, dass die darin enthaltenen Ausdrücke simultan in einer Interpretation erfüllbar sind. Zwischen Allgemeingültigkeit und Erfüllbarkeit besteht die Beziehung, dass ${}p$ genau dann allgemeingültig ist, wenn die Negation ${}\neg p$ nicht erfüllbar ist.

Zwischen Folgerung und Erfüllbarkeit besteht der folgende Zusammenhang.

Lemma

Es gilt ${}\Gamma \vDash \alpha$ genau dann, wenn ${}\Gamma \cup \{\neg \alpha \}$ nicht erfüllbar ist.

Beweis

Siehe Aufgabe 5.4.

$\Box$

Das Koinzidenzlemma

Die folgende Aussage, das Koinzidenzlemma, zeigt, dass der Wert eines Terms und die Gültigkeit eines Ausdrucks unter einer Interpretation nur von den in dem Term bzw. Ausdruck vorkommenden freien Variablen abhängt. Ihr Beweis ist ein typisches Beispiel für einen Beweis durch Induktion über den Aufbau der Terme bzw. Ausdrücke.

Lemma

Es sei ${}S$ ein Symbolalphabet erster Stufe und ${}U\subseteq S$ eine Teilmenge. Es sei ${}t$ ein ${}U$- Term und ${}\alpha$ ein ${}U$- Ausdruck. Es seien zwei ${}S$- Interpretationen ${}I_{1}$ und ${}I_{2}$ in einer gemeinsamen Grundmenge ${}M$ gegeben, die auf ${}U$ identisch seien. Dann gelten folgende Aussagen.

1. Es ist ${}I_{1}(t)=I_{2}(t)$.
2. Es ist ${}I_{1}\vDash \alpha$ genau dann, wenn ${}I_{2}\vDash \alpha$ (dazu genügt bereits, dass die Interpretationen auf den Symbolen aus ${}U$ und auf den in ${}\alpha$ frei vorkommenden Variablen identisch sind).

Beweis

(1). Wir führen Induktion über den Aufbau der ${}U$-Terme. Für den Induktionsanfang müssen wir Variablen und Konstanten aus ${}U$ betrachten. Für eine Variable ${}x$ (oder eine Konstante) aus ${}U$ ist nach Voraussetzung ${}I_{1}(x)=I_{2}(x)$. Im Induktionsschritt können wir annehmen, dass ein ${}n$-stelliges Funktionssymbol ${}f$ aus ${}U$ gegeben ist sowie ${}U$-Terme ${}t_{1},\ldots ,t_{n}$, für die die Interpretationsgleichheit schon gezeigt wurde. Nach Voraussetzung wird ${}f$ in beiden Interpretationen durch die gleiche Funktion ${}f^{M}$ interpretiert. Daher ist

${}{\begin{aligned}I_{1}(ft_{1}\ldots t_{n})&=f^{M}(I_{1}(t_{1}),\ldots ,I_{1}(t_{n}))\\&=f^{M}(I_{2}(t_{1}),\ldots ,I_{2}(t_{n}))\\&=I_{2}(ft_{1}\ldots t_{n}).\end{aligned}}$

(2). Wir führen Induktion über den Aufbau der ${}U$-Ausdrücke, wobei die zu beweisende Aussage über je zwei Interpretationen zu verstehen ist. Für die Gleichheit und ein Relationssymbol ${}R$ aus ${}U$ folgt die Aussage unmittelbar aus (1), da ja ${}R$ in beiden Interpretationen als die gleiche Relation zu interpretieren ist. Der Induktionsschritt ist für Ausdrücke der Form ${}\neg \alpha ,\,\alpha \wedge \beta ,\,\alpha \rightarrow \beta$ aufgrund der Modellbeziehung unmittelbar klar. Es sei nun ein ${}U$-Ausdruck der Form ${}\exists x\alpha$ gegeben, und es gelte ${}I_{1}\vDash \exists x\alpha$. Dies bedeutet aufgrund der Modellbeziehung, dass es ein ${}m\in M$ derart gibt, dass ${}I_{1}{\frac {m}{x}}\vDash \alpha$ gilt. Die beiden umbelegten Interpretationen ${}I_{1}{\frac {m}{x}}$ und ${}I_{2}{\frac {m}{x}}$ stimmen auf den Symbolen aus ${}U$ und den in ${}\alpha$ frei vorkommenden Variablen überein: Die Variable ${}x$ wird so oder so als ${}m$ interpretiert und die anderen freien Variablen aus ${}\alpha$ sind auch in ${}\exists x\alpha$ frei. Nach Induktionsvoraussetzung gilt ${}I_{2}{\frac {m}{x}}\vDash \alpha$ und daher wiederum ${}I_{2}\vDash \exists x\alpha$.

$\Box$

Substitution

Wir besprechen nun die Variablensubstitution, wobei wir weitgehend der Darstellung von Ebbinghaus, Flum, Thomas folgen.

Variablen repräsentieren verschiedene Werte, die man für sie einsetzen kann. Auf formaler Ebene bedeutet dies, dass eine oder mehrere Variablen durch gewisse Terme ersetzt werden. In der Ersetzung macht es einen großen Unterschied, ob gebundene oder freie Variablen vorliegen. Der Ausdruck

$x\geq 0\rightarrow \exists y(x=y\cdot y)$

bedeutet in einem angeordneten Körper interpretiert, dass die nichtnegative Zahl ${}x$ als Quadrat darstellbar ist (also eine Quadratwurzel besitzt), was für ${}\mathbb {R}$ wahr ist, für ${}\mathbb {Q}$ im Allgemeinen (das hängt von der Interpretation für ${}x$ ab) nicht. Gleichbedeutend (bei einer inhaltlichen Interpretation) mit diesem Ausdruck ist

$x\geq 0\rightarrow \exists z(x=z\cdot z),$

aber nicht

$x\geq 0\rightarrow \exists x(x=x\cdot x),$

das nur bei ${}x=0$ oder ${}x=1$ wahr ist. Von daher wird die weiter unten zu gebende Definition für die Substitution von Ausdrücken berücksichtigen, ob Variablen frei oder gebunden sind. Ferner wird es wichtig sein, in einem Ausdruck neue Variablen einzuführen. Damit diese Konstruktion eindeutig definiert ist, legen wir eine durchnummerierte (und abzählbare) Variablenmenge ${}v_{1},v_{2},v_{3}\ldots$ zugrunde.

Definition

Es sei ein Symbolalphabet ${}S$ einer Sprache erster Stufe gegeben. Es seien ${}x_{1},\ldots ,x_{k}$ paarweise verschiedene Variablen und ${}t_{1},\ldots ,t_{k}$ fixierte ${}S$- Terme. Dann definiert man rekursiv über den Aufbau der Terme die Substitution ${}s{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}$ für jeden ${}S$-Term ${}s$.

1. Für eine Variable ${}x$ ist

   ${}x{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}:={\begin{cases}x,{\text{ falls }}x\neq x_{i}{\text{ für alle }}i\,,\\t_{i},{\text{ falls }}x=x_{i}\,.\end{cases}}\,$

2. Für eine Konstante ${}c$ ist

   ${}c{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}:=c\,.$

3. Für ein ${}n$-stelliges Funktionssymbol ${}f$ und ${}n$ Terme ${}s_{1},\ldots ,s_{n}$ ist

   ${}fs_{1}\ldots s_{n}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}:=fs_{1}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\ldots s_{n}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\,.$

Definition

Es sei ein Symbolalphabet ${}S$ einer Sprache erster Stufe gegeben. Es seien ${}x_{1},\ldots ,x_{k}$ paarweise verschiedene Variablen und ${}t_{1},\ldots ,t_{k}$ fixierte ${}S$- Terme. Dann definiert man rekursiv über den Aufbau der ${}S$- Ausdrücke die Substitution ${}\alpha {\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}$ für jeden ${}S$-Ausdruck ${}\alpha$.

1. Für Terme ${}s_{1},s_{2}$ setzt man

   ${}(s_{1}=s_{2}){\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}:=s_{1}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}=s_{2}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\,.$

2. Für ein ${}n$-stelliges Relationssymbol ${}R$ und ${}n$ Terme ${}s_{1},\ldots ,s_{n}$ setzt man

   ${}(Rs_{1}\ldots s_{n}){\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}:=Rs_{1}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\ldots s_{n}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\,.$

3. Für einen Ausdruck ${}\alpha$ setzt man

   ${}(\neg \alpha ){\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}:=\neg \alpha {\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\,.$

4. Für Ausdrücke ${}\alpha$ und ${}\beta$ setzt man

   ${}(\alpha \wedge \beta ){\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}:=\alpha {\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\wedge \beta {\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\,$

   und ebenso für die anderen zweistelligen Junktoren.

5. Für einen Ausdruck ${}\alpha$ seien ${}x_{i_{1}},\ldots ,x_{i_{r}}$ diejenigen Variablen (unter den $x_{1},\ldots ,x_{k}$), die in ${}\forall x\alpha$ frei vorkommen. Es sei ${}v=x$, falls ${}x$ nicht in ${}t_{i_{1}},\ldots ,t_{i_{r}}$ vorkommt. Andernfalls sei ${}v$ die erste Variable (in einer fixierten Variablenaufzählung, falls es abzählbar viele Variablen gibt, bzw. in einer fixierten Wohlordnung der Variablenmenge), die weder in ${}\alpha$ noch in ${}t_{i_{1}},\ldots ,t_{i_{r}}$ vorkommt. Dann setzt man

   ${}(\forall x\alpha ){\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}:=\forall v\alpha {\frac {t_{i_{1}},\ldots ,t_{i_{r}},v}{x_{i_{1}},\ldots ,x_{i_{r}},x}}\,$

   und ebenso für den Existenzquantor.

Die folgende Aussage, das Substitutionslemma, geben wir ohne Beweis. Es stiftet eine Beziehung zwischen Substitutionen und Uminterpretationen. In Verallgemeinerung der Schreibweise ${}I({\frac {m}{x}})$ für eine Uminterpretation schreiben wir ${}I({\frac {m_{1},\ldots ,m_{k}}{x_{1},\ldots ,x_{k}}})$ für die sukzessive Uminterpretation der untereinander verschiedenen Variablen ${}x_{1},\ldots ,x_{k}$ (dabei seien ${}m_{1},\ldots ,m_{k}$ Elemente der Grundmenge ${}M$ der Interpretation). Es werden also die ${}x_{i}$ als ${}m_{i}$ interpretiert und alle anderen Variablen werden gemäß ${}I$ interpretiert.

Lemma

Es sei ein Symbolalphabet ${}S$ einer Sprache erster Stufe gegeben und es seien ${}x_{1},\ldots ,x_{k}$ paarweise verschiedene Variablen und ${}t_{1},\ldots ,t_{k}$ fixierte ${}S$- Terme. Es sei eine ${}S$- Interpretation ${}I$ gegeben. Dann gelten folgende Aussagen.

1. Für jeden ${}S$- Term ${}s$ gilt

   ${}I{\left(s{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\right)}={\left(I{\frac {I(t_{1}),\ldots ,I(t_{k})}{x_{1},\ldots ,x_{k}}}\right)}(s)\,.$

2. Für jeden ${}S$- Ausdruck ${}\alpha$ gilt

   $I\vDash \alpha {\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}{\text{ genau dann, wenn }}{\left(I{\frac {I(t_{1}),\ldots ,I(t_{k})}{x_{1},\ldots ,x_{k}}}\right)}\vDash \alpha .$

<< | Kurs:Einführung in die mathematische Logik (Osnabrück 2011-2012) | >> PDF-Version dieser Vorlesung Arbeitsblatt zur Vorlesung (PDF)