Kurs:Einführung in die mathematische Logik (Osnabrück 2014)/Vorlesung 8/kontrolle

Allgemeingültige Ausdrücke

Es sei ${}L^{S}$ eine Sprache erster Stufe über einem Symbolalphabet ${}S$. Für einen Ausdruck ${}\alpha \in L^{S}$ und eine Interpretation ${}I$ haben wir in der letzten Vorlesung die Gültigkeit ${}I\vDash \alpha$ über den Aufbau der Sprache rekursiv definiert. Wie im aussagenlogischen Kontext führen wir semantische Tautologien über die Gültigkeit bei jeder Interpretation ein.

Definition Referenznummer erstellen

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 (Vollständigkeitssatz der Prädikatenlogik). Beispiele sind die Ausdrücke

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

oder

$(\forall x\alpha )\rightarrow \alpha$

(wobei ${}\alpha$ ein Ausdruck ist), siehe Aufgabe 8.2. Wenn man in eine aussagenlogische Tautologie für die Aussagenvariablen beliebige prädikatenlogische Ausdrücke einsetzt, so erhält man auch eine Tautologie im obigen Sinn, siehe Aufgabe 8.4 (die entprechende syntaktische Version wird in Lemma 10.2 behandelt).

Gültigkeit von Ausdrucksmengen

Für eine Menge ${}\Gamma \subseteq L^{S}$ von Ausdrücken schreibt man ${}I\vDash \Gamma$, wenn in ${}I$ jeder Ausdruck aus ${}\Gamma$ gilt. Man sagt, dass ${}I$ ein Modell für ${}\Gamma$ ist. Eine ${}S$-Struktur heißt ein Modell für ${}\Gamma$, wenn jede Variablenbelegung zu dieser Struktur eine Interpretation liefert, die ein Modell für ${}\Gamma$ ist.

Diese Sprechweise wird insbesondere für Axiomensysteme ${}\Gamma$ verwendet, die eine mathematisch wichtige Struktur festlegen. Die erfüllenden Modelle heißen dann so, wie der Definitionsname in der Definition lautet, die dieses Axiomensystem verwendet. Die Modelle nennt man im üblichen mathematischen Sprachgebrauch Beispiele für diejenige mathematische Struktur, die durch die Definition festgelegt wird.

Axiomensysteme

Grundsätzlich gibt es zwei Bedeutungen von Axiomensystemen. Einerseits wird ein Axiomensystem aufgestellt, um eine in einem gewissen Sinn vertraute Struktur präzise zu erfassen und ihre Eigenschaften aus den fixierten Grundeigenschaften zu folgern. Man spricht von einem intendierten Modell, das durch das Aufstellen eines Axiomensystems mathematisch beschrieben werden soll. Die Axiome selbst werden dann durch die Gültigkeit im intendierten Modell gerechtfertigt und können nicht weiter hinterfragt werden. In diesem Sinne gibt es in der Geometrie die euklidische Axiome für die Ebene bzw. den Raum, oder die Dedekind-Peano-Axiome für die natürlichen Zahlen, die wir später behandeln werden, oder die Axiome für die reellen Zahlen, die man in der Analysis I einführt, oder die Axiome für die Mengenlehre (typischerweise Zermelo-Fraenkel mit Auswahlaxiom), die eine Festlegung für den mengentheoretischen Rahmen der gesamten Mathematik bilden. Eine wichtige Fragestellung ist, ob die Axiome die Struktur eindeutig festlegen.

Andererseits kann man jede willkürliche Vorgabe einer Menge von Ausdrücken als ein Axiomensystem ansehen. Es gibt dann jeweils mehrere verschiedene Strukturen, die diese Axiome erfüllen. Ein Axiomensystem in diesem Sinn will nicht ein bestimmtes Modell charakterisieren, sondern abstrakte Eigenschaft, die in unterschiedlichen Kontexten auftreten, bereitstellen. Eigenschaften, die man aus den Axiomen erschließen kann, gelten dann für sämtliche Modelle, die die Axiome erfüllen. Die Ökonomie dieses mathematischen Ansatzes liegt eben darin, dass man Schlüsse nicht am Objekt durchführt, sondern abstrakt und allgemein. Wichtige Axiomensysteme sind die Axiome für Gruppen, Ringe, Körper, angeordnete Körper, Vektorräume, metrische Räume, topologische Räume, Maßräume, Mannigfaltigkeiten.

Wichtige Bewertungskriterien für beide Arten von Axiomensystemen sind.

1. Die Axiome sollen möglichst einfach formuliert sein.
2. Die Axiome sollen möglichst einfach (in einem Modell) überprüfbar sein.
3. Die Axiome sollen reichhaltige Folgerungen erlauben.
4. Die Axiome eines Systems sollen untereinander unabhängig sein; es darf kein Axiom redundant sein.

Für uns stehen zunächst Axiomensysteme im zweiten Sinne im Mittelpunkt; grundsätzlich kann man jede Ausdrucksmenge ${}\Gamma \subseteq L^{S}$ als ein Axiomensystem auffassen. Als Beispiele betrachten wir aber nur mathematisch relevante Axiomensysteme. Um ein Axiomensystem prädikatenlogisch zu repräsentieren, muss man zuerst das Symbolalphabet und anschließend die Axiome festlegen. Betrachten wir beispielsweise die mathematische Definition einer Gruppe.

Definition Referenznummer erstellen

Eine Menge ${}G$ mit einem ausgezeichneten Element ${}e\in G$ und mit einer Verknüpfung

$G\times G\longrightarrow G,\,(g,h)\longmapsto g*h,$

heißt Gruppe, wenn folgende Eigenschaften erfüllt sind.

1. Die Verknüpfung ist assoziativ, d.h. für alle ${}f,g,h\in G$ gilt

   ${}(f*g)*h=f*(g*h)\,.$

2. Das Element ${}e$ ist ein neutrales Element, d.h. für alle ${}g\in G$ gilt

   ${}g*e=g=e*g\,.$

3. Zu jedem ${}g\in G$ gibt es ein inverses Element, d.h. es gibt ein ${}h\in G$ mit

   ${}h*g=g*h=e\,.$

In formal-prädikatenlogischer Formulierung besteht das Symbolalphabet (neben den Variablen) aus einer Konstanten ${}e$ und aus einem zweistelligen Funktionssymbol ${}\mu$. Die in der Gruppendefinition auftretenden Axiome (die Gruppenaxiome, also die drei auftretenden Bedingungen) kann man mit diesen Symbolen einfach schreiben als

1. $\forall x(\forall y(\forall z\,\mu x\mu yz=\mu \mu xyz)).$

2. $\forall x(\mu xe=x\wedge \mu ex=x).$

3. $\forall x\exists y(\mu xy=e\wedge \mu yx=e).$

Nennen wir diese drei Ausdrücke zusammen ${}\Gamma$. Dann ist eine Gruppe eine Menge mit einer Interpretation ${}I$ für ${}e$ und für ${}\mu$, d.h. es muss ein ausgezeichnetes Element ${}e^{G}$ (häufig schreibt man ${}e_{G}$ oder ${}e$) geben und eine zweistellige Funktion (eine Verknüpfung), derart, dass ${}I\vDash \Gamma$ gilt. Eine Gruppe ist also ein Modell für ${}\Gamma$.

Als weiteres Beispiel wiederholen wir die Definition der Ordnungsrelation, die wir in der fünften Vorlesung behandelt haben.

Definition Referenznummer erstellen

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 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. Eine geordnete Menge ist also ein Modell für ${}\Gamma$.

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 Referenznummer erstellen

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 ${}\alpha$ folgt, erfordert eine mathematische Argumentation, die aufzeigt, dass eine Menge mit zusätzlichen Strukturen, die ${}\Gamma$ erfüllt, stets auch ${}\alpha$ erfüllen muss.

Beispiel Referenznummer erstellen

In einer Gruppe ist das inverse Element zu einem jeden 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, sei ${}x\in G$ vorgegeben und seien ${}y,z\in G$ inverse Elemente zu ${}x$, d.h. es gelte ${}yx=xy=e$ und ${}zx=xz=e$. Dann ist insgesamt

${}y=ye=y(xz)=(yx)z=ez=z\,.$

Die Eindeutigkeit des inversen Elementes kann man mit den Symbolen ${}\{e,\mu \}$, wobei ${}e$ eine Konstante und ${}\mu$ ein zweistelliges Funktionssymbol ist, als den Ausdruck

${}\alpha :=\forall x(\forall y(\forall z(\mu yx=e\wedge \mu xy=e\wedge \mu zx=e\wedge \mu xz=e\rightarrow y=z)))\,$

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

$\Gamma \vDash \alpha$

vorliegt.

Da ein allgemeingültiger Ausdruck ${}\alpha$ in jeder Interpretation gilt, kann man auch sagen, dass ${}\alpha$ aus der leeren Ausdrucksmenge folgt, also ${}\emptyset \vDash \alpha$ gilt. Wenn ${}\alpha _{1},\alpha _{2},\alpha _{3}$ die Gruppenaxiome sind, und ${}\alpha$ die im obigen Beispiel erwähnte Eindeutigkeitsausssage für das inverse Element ist, so ist auch

$\alpha _{1}\wedge \alpha _{2}\wedge \alpha _{3}\rightarrow \alpha$

allgemeingültig.

Definition Referenznummer erstellen

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 ${}\alpha$ genau dann allgemeingültig ist, wenn die Negation ${}\neg \alpha$ nicht erfüllbar ist.

Zwischen Folgerung und Erfüllbarkeit besteht der folgende Zusammenhang.

Lemma Referenznummer erstellen

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

Beweis

Siehe Aufgabe 8.13.

$\Box$

Sortenprädikate

Bei vielen mathematischen Strukturen bewegen sich die Objekte, über die quantifiziert werden soll, nicht in einer einzigen Menge, sondern in mehreren. Beispielsweise interessiert man sich nicht nur für Abbildungen von einer Menge in sich selbst, sondern auch für Abbildungen zwischen zwei Mengen. Bei einem Vektorraum wird ein Körper zugrunde gelegt, aus dem die „Skalare“ herrühren, während die Vektoren aus dem Vektorraum sind; die Axiome eines Vektorraums nehmen Bezug auf beide Arten. Bei einem metrischen Raum ist der Abstand zwischen zwei Punkten des Raumes eine reelle Zahl bzw. ein Element in einem angeordneten Körper. Man spricht von verschiedenen „Sorten“ (von Termen, von Objekten). Solche mathematische Strukturen lassen sich ebenfalls mit der Sprache erster Stufe beschreiben, wobei man einen einfachen Kniff anwendet, der von der mathematischen Praxis her etwas künstlich wirkt. Man wirft die Mengen zunächst zusammen und führt dann für jede Sorte ein Sortenprädikat ein, um sie wieder trennen zu können. Ein Sortenprädikat ist eine einstellige Relation, und ${}Pt$ bedeutet inhaltlich gesprochen, dass der Term ${}t$ zur Sorte gehört, die durch ${}P$ repräsentiert wird. Wir erläutern dieses Vorgehen an zwei Beispielen.

Beispiel Referenznummer erstellen

Eine angemessene prädikatenlogische Formulierung für Abbildungen zwischen zwei Mengen wird durch das Symbolalphabet beschrieben, das neben Variablen aus ${}\{F,D,Z\}$ besteht, wobei ${}F$ ein einstelliges Funktionssymbol und ${}D$ (für „Definitionsbereich“) und ${}Z$ (für „Zielbereich“) zwei einstellige Relationssymbole sind, mit denen man den Definitionsbereich und den Zielbereich einer Abbildung erfassen möchte. Bei Interpretation in einer Menge ${}M$ ist die Funktion ${}f=F^{M}$ zwar auf jedes Element aus ${}M$ anwendbar, man kann aber relevante Eigenschaften einer Abbildung spezifisch für die durch ${}D$ bzw. ${}Z$ bestimmten Teilmengen (den Definitionsbereich bzw. Zielbereich) formulieren. Beispielsweise besagt der Ausdruck

$\forall x(Dx\rightarrow Zfx),$

dass für jedes ${}x$, das zum Definitionsbereich gehört, der Funktionswert zu ${}Z$ gehören muss. Die Surjektivität (als Abbildung von der durch ${}D$ beschriebenen Menge, also $D^{M}$, in die durch ${}Z$ beschriebene Menge, also $Z^{M}$) wird durch

$\forall y{\left(Zy\rightarrow \exists x{\left(Dx\wedge fx=y\right)}\right)}$

beschrieben.

Beispiel Referenznummer erstellen

Eine angemessene prädikatenlogische Formulierung für Vektorräume wird neben Variablen durch

$\{0_{K},1,+_{K},\cdot _{K},0_{V},+_{V},\cdot ,K,V\}$

beschrieben, wobei ${}\{0_{K},1,0_{V}\}$ Konstanten, ${}\{+_{K},\cdot _{K},+_{V},\cdot \}$ zweistellige Funktionssymbole und ${}K$ (für Körper) und ${}V$ (für Vektorraum) zwei einstellige Relationssymbole sind, mit denen man den Körper und den Vektorraum erfassen möchte. Die grundlegende Skalarmultiplikation wird durch

$\forall x\forall y{\left(Kx\wedge Vy\rightarrow Vx\cdot y\right)}$

beschrieben, die beiden Distributivgesetze durch

$\forall x\forall y\forall z{\left(Kx\wedge Ky\wedge Vz\rightarrow {\left(x+_{K}y\right)}\cdot z={\left({\left(x\cdot z\right)}+_{V}{\left(y\cdot z\right)}\right)}\right)}$

und

$\forall x\forall y\forall z{\left(Kx\wedge Vy\wedge Vz\rightarrow x\cdot {\left(y+_{V}z\right)}={\left(x\cdot y\right)}+_{V}{\left(x\cdot z\right)}\right)}.$

Fußnoten