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



Allgemeingültige Ausdrücke

Es sei eine Sprache erster Stufe über einem Symbolalphabet . Für einen Ausdruck und eine Interpretation haben wir in der letzten Vorlesung die Gültigkeit ü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 ein Symbolalphabet und ein - Ausdruck in der Prädikatenlogik erster Stufe. Man nennt allgemeingültig (oder eine semantische Tautologie), wenn er in jeder - Interpretation gilt, also 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

oder

(wobei ein Ausdruck ist), siehe Aufgabe 8.1. Wenn man in eine aussagenlogische Tautologie für die Aussagenvariablen beliebige prädikatenlogische Ausdrücke einsetzt,[1] so erhält man auch eine Tautologie im obigen Sinn, siehe Aufgabe 8.4 (die entprechende syntaktische Version wird in Lemma 10.2 behandelt). Beispielsweise erhält man aus der aussagenlogischen Tautologie

die prädikatenlogische Tautologie (mit naheliegenden Zugehörigkeiten der Symbole)

die aber keinen eigentlichen prädikatenlogischen Sachverhalt ausdrückt.



Gültigkeit von Ausdrucksmengen

Für eine Menge von Ausdrücken und einer -Interpretation schreibt man , wenn in jeder Ausdruck aus gilt. Man sagt, dass ein Modell für ist. Eine -Struktur heißt ein Modell für , wenn jede Variablenbelegung zu dieser Struktur eine Interpretation liefert, die ein Modell für ist.

Diese Sprechweise wird insbesondere für Axiomensysteme 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 hierbei 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 in diesem zweiten Sinn 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 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 mit einem ausgezeichneten Element und mit einer Verknüpfung

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

  1. Die Verknüpfung ist assoziativ, d.h. für alle gilt
  2. Das Element ist ein neutrales Element, d.h. für alle gilt
  3. Zu jedem gibt es ein inverses Element, d.h. es gibt ein mit

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

Nennen wir diese drei Ausdrücke zusammen . Dann ist eine Gruppe eine Menge mit einer Interpretation für und für , d.h. es muss ein ausgezeichnetes Element (häufig schreibt man oder ) geben und eine zweistellige Funktion auf (eine Verknüpfung), derart, dass gilt. Eine Gruppe ist also ein Modell für .

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


Eine Relation auf einer Menge heißt Ordnungsrelation oder Ordnung, wenn folgende drei Bedingungen erfüllt sind.

  1. Es ist für alle .
  2. Aus und folgt stets .
  3. Aus und folgt .


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

In einer Menge mit einer zweistelligen Relation gilt das Axiomensystem genau dann, wenn die Relation eine Ordnungsrelation ist. Eine geordnete Menge ist also ein Modell für .



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 ein Symbolalphabet erster Stufe, eine Menge von - Ausdrücken und ein -Ausdruck. Man sagt, dass aus folgt, geschrieben , wenn für jede - Interpretation mit auch gilt.

Die Folgerungsbeziehung verwendet also (wie schon im aussagenlogischen Kontext) das gleiche Symbol wie die Gültigkeitsbeziehung. Dass aus einer gewissen Ausdrucksmenge ein gewisser Ausdruck folgt, erfordert eine mathematische Argumentation, die aufzeigt, dass eine Menge mit gewissen zusätzlichen Strukturen, die erfüllt, stets auch 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 das neutrale Element der Gruppe, sei vorgegeben und seien inverse Elemente zu , d.h. es gelte und . Dann ist insgesamt

Die Eindeutigkeit des inversen Elementes kann man mit den Symbolen , wobei eine Konstante und ein zweistelliges Funktionssymbol ist, als den Ausdruck

ansetzen, und die obige mathematische Argumentation bedeutet, dass der Ausdruck aus den Gruppenaxiomen folgt, also die Folgerungsbeziehung

vorliegt.


Da ein allgemeingültiger Ausdruck in jeder Interpretation gilt, kann man auch sagen, dass aus der leeren Ausdrucksmenge folgt, also gilt. Wenn die Gruppenaxiome sind, und die im obigen Beispiel erwähnte Eindeutigkeitsausssage für das inverse Element ist, so ist

allgemeingültig.


Definition  Referenznummer erstellen

Es sei ein Symbolalphabet und es sei ein - Ausdruck in der Prädikatenlogik erster Stufe. Man nennt erfüllbar, wenn es eine - Interpretation mit gibt.

Für eine Ausdrucksmenge 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 genau dann allgemeingültig ist, wenn die Negation nicht erfüllbar ist.

Zwischen Folgerung und Erfüllbarkeit besteht der folgende Zusammenhang.


Lemma Referenznummer erstellen

Es gilt genau dann, wenn nicht erfüllbar ist.

Beweis

Siehe Aufgabe 8.16.



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 bedeutet inhaltlich gesprochen, dass der Term zur Sorte gehört, die durch 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 besteht, wobei ein einstelliges Funktionssymbol und (für „Definitionsbereich“) und (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 ist die Funktion zwar auf jedes Element aus anwendbar, man kann aber relevante Eigenschaften einer Abbildung spezifisch für die durch bzw. bestimmten Teilmengen (den Definitionsbereich bzw. Zielbereich) formulieren. Beispielsweise besagt der Ausdruck

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

beschrieben.



Beispiel  Referenznummer erstellen

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

beschrieben, wobei Konstanten, zweistellige Funktionssymbole und (für Körper) und (für Vektorraum) zwei einstellige Relationssymbole sind, mit denen man den Körper und den Vektorraum erfassen möchte. Die grundlegende Skalarmultiplikation wird durch

beschrieben, die beiden Distributivgesetze durch

und




Fußnoten
  1. Insofern ist auch die Bezeichnung Aussagenvariable gerechtfertigt, da für sie prädikatenlogische Ausdrücke eingesetzt werden können.