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

Aus Wikiversity
Zur Navigation springen Zur Suche springen



Semantik

Gelegentlich haben wir schon angedeutet, was die zuletzt eingeführten prädikatenlogischen Symbole, die wir rein formal als Zeichenreihen behandelt haben, eigentlich bedeuten sollen, was also ihr logisch-mathematischer Gehalt sein soll. Bei einer solchen Interpretation werden die Junktoren, die Quantoren und das Gleichheitszeichen stets in der gleichen Weise interpretiert, die Variablen, Konstanten, Relations- und Funktionssymbole aber unterschiedlich. Dazu erinnern wir an einige mathematische Begriffe. Wir setzen eine naive Mengenlehre und die natürlichen Zahlen „zum Zählen“ (wie schon weiter oben) voraus. Wir erinnern an einige grundlegende mathematische Definitionen.


Definition  

Es seien zwei Mengen und gegeben. Dann nennt man die Menge

die Produktmenge der beiden Mengen.

Für uns ist insbesondere das -fache Produkt einer Menge mit sich selbst, also

(mit Faktoren) wichtig.


Definition  

Unter einer -stelligen Relation auf einer Menge versteht man eine Teilmenge der -fachen Produktmenge .


Definition  

Seien und Mengen. Eine Abbildung von nach ist dadurch gegeben, dass jedem Element der Menge genau ein Element der Menge zugeordnet wird. Das zu eindeutig bestimmte Element wird mit bezeichnet. Die Abbildung drückt man als Ganzes häufig durch

aus.


Definition  

Es sei eine Menge. Unter einer -stelligen Abbildung auf versteht man eine Abbildung

vom -fachen Produkt von mit sich selbst nach .

Eine -stellige Funktion kann auch als eine -stellige Relation aufgefasst werden, bei der es zu jedem -Tupel genau ein gibt derart, dass zur Relation gehört. Dieses ist dann der Funktionswert der zugehörigen Funktion an der Stelle .



Interpretationen

Definition  

Es sei das Symbolalphabet einer Sprache erster Stufe. Unter einer -Struktur versteht man eine nichtleere Menge mit den folgenden Festlegungen.

  1. Für jede Konstante ist ein Element festgelegt.
  2. Zu jedem -stelligen Funktionssymbol (aus ) ist eine -stellige Funktion

    festgelegt.

  3. Zu jedem -stelligen Relationssymbol (aus ) ist eine -stellige Relation

    festgelegt.

Unter einer -(Variablen)belegung in versteht man eine Festlegung für jede Variable .

Unter einer -Interpretation versteht man eine -Struktur zusammen mit einer -Belegung.

Die Menge heißt auch Grundmenge der -Struktur bzw. der -Interpretation. Die Festlegung für die Konstanten und die Variablen ist einfach eine Abbildung von bzw. von der Variablenmenge in die Menge . Statt schreibt man auch , wobei eine Interpretation bezeichnet. Die Strukturen sind übliche Gegenstände der Mathematik.


Beispiel  

Es sei ein Symbolalphabet, das außer einer Variablenmenge aus einem einzigen einstelligen Funktionssymbol bestehe (die Konstantenmenge und die Relationssymbolmengen seien also leer). Eine -Struktur besteht dann aus einer nichtleeren Menge zusammen mit einer Abbildung

Beispiele sind mit der Nachfolgerfunktion, mit dem Quadrieren oder der Sinusfunktion oder der Exponentialfunktion, oder eine beliebige Menge mit der Identität, eine endliche Menge mit einer Permutation, u.s.w.



Beispiel  

Es sei ein Symbolalphabet, das außer einer Variablenmenge aus einem einzigen zweistelligen Funktionssymbol bestehe (die Konstantenmenge und die Relationssymbolmengen seien also leer). Eine -Struktur besteht dann aus einer nichtleeren Menge zusammen mit einer Abbildung

Eine solche Abbildung nennt man auch eine Verknüpfung auf ; sie ordnet (einem geordneten Paar aus) zwei Elementen der Menge ein weiteres Element der Menge zu. Die Addition oder die Multiplikation auf den natürlichen Zahlen sind jeweils eine solche Verknüpfung. Weitere Beispiele sind die Verknüpfung in einer Gruppe, die Vektorraumaddition, das Maximum von zwei reellen Zahlen, u.s.w.



Beispiel  

Es sei ein Symbolalphabet, das außer einer Variablenmenge aus einem einzigen einstelligen Relationssymbol bestehe (die Konstantenmenge und die Funktionssymbolmengen seien also leer). Eine -Struktur besteht dann aus einer nichtleeren Menge zusammen mit einer fixierten Teilmenge . Beispiele sind mit der Teilmenge der Primzahlen, oder der Teilmenge der Quadratzahlen, oder mit der Teilmenge der positiven Zahlen, oder der Teilmenge der rationalen Zahlen, u.s.w.




Interpretation von Termen

Mit einer solchen Interpretation wird das Symbolalphabet, das neben den Junktoren, Quantoren, dem Gleichheitszeichen und den Klammern das Alphabet der Sprache bildet, interpretiert. Man möchte aber die gesamte Sprache in , ausgehend von der Interpretation dieser Symbole, interpretieren. Der erste Schritt dazu ist die Interpretation der Terme. Die Wohldefiniertheit der folgenden Festlegung ergibt sich durch einen Beweis über den Aufbau der Terme.


Definition  

Zu einem Symbolalphabet erster Stufe und einer -Interpretation in einer Menge wird induktiv über den Aufbau der Terme für jeden -Term eine Interpretation in definiert.

  1. Für jede Konstante und jede Variable ist die Terminterpretation durch die Interpretation bzw. die Belegung direkt gegeben, also und .
  2. Wenn Terme mit den Interpretationen sind und wenn ein -stelliges Funktionssymbol ist, so wird der Term als interpretiert.

Damit werden alle Terme in der Grundmenge interpretiert. In vielen Situationen bleibt die Grundmenge und die Interpretation der Konstanten und der Relations- und Funktionssymbole gleich, während man die Variablenbelegung ändern möchte. Insbesondere möchte man Interpretationen für eine einzelne Variable abändern.


Definition  

Es sei ein Symbolalphabet erster Stufe und eine -Interpretation in einer Menge gegeben. Es sei eine Variable und ein Element der Grundmenge. Dann versteht man unter der Uminterpretation diejenige Interpretation von in , die strukturgleich zu ist und für deren Variablenbelegung

gilt.



Interpretation von Ausdrücken

Nachdem wir alle Terme bei einer gegebenen -Interpretation interpretieren können, wenden wir uns nun den Ausdrücken zu. Es ist das Ziel, jedem -Ausdruck eine Aussage (unter Bezug auf die Grundmenge und die Interpretation des Symbolalphabets) zuzuordnen, die wahr oder falsch ist.


Definition  

Zu einem Symbolalphabet erster Stufe und einer -Interpretation in einer Menge werden die -Ausdrücke folgendermaßen (induktiv über den Aufbau der Ausdrücke) interpretiert und als gültig (oder ungültig) charakterisiert (die Gültigkeit einer Aussage unter der Interpretation wird dabei als geschrieben). Es seien Terme und Ausdrücke.

  1. , wenn .
  2. , wenn .
  3. , wenn nicht gilt.
  4. , wenn und gilt.
  5. , wenn die Gültigkeit die Gültigkeit impliziert.
  6. , wenn es ein mit gibt.
  7. , wenn für alle die Beziehung gilt.

Dabei ist, wie bei jeder Definition, „wenn“ als „genau dann, wenn“ zu lesen. Auf der linken Seite stehen die formalen Ausdrücke zusammen mit der Erklärung, ob sie in der Interpretation gelten, und auf der rechten Seite steht eine logisch-mathematische Bedingung. Diese ist im Sinne des üblichen Gebrauchs in der Mathematik zu verstehen.

Da bei dieser Zuordnung alle möglichen Konstruktionsweisen für Ausdrücke auftauchen, ergibt sich eine Erklärung für jeden Ausdruck durch deren induktiven Aufbau. Für jeden Ausdruck gilt in einer Interpretation entweder oder nicht, wobei die Nichtgültigkeit zur Gültigkeit von äquivalent ist. Eine Interpretation liefert also insbesondere eine vollständige Aufteilung der -Ausdrücke in wahre und falsche Ausdrücke.



Beispiele

Beispiel  

Es sei ein Symbolalphabet, das außer einer Variablenmenge aus einem einzigen einstelligen Funktionssymbol bestehe (die Konstantenmenge und die Relationssymbolmengen seien also leer), so dass eine -Struktur aus einer Menge zusammen mit einer Abbildung

besteht. In einer solchen Interpretation wird jeder -Ausdruck interpretiert. Der Ausdruck

besagt die Surjektivität von . D.h. in einer -Interpretation gilt

genau dann, wenn die durch die Interpretation festgelegte Abbildung surjektiv ist. Der Ausdruck

besagt die Injektivität von . D.h. in einer -Interpretation gilt

genau dann, wenn die durch die Interpretation festgelegte Abbildung injektiv ist.



Beispiel  

Es sei das Symbolalphabet für einen angeordneten Körper, d.h. es gebe eine zweielementige Konstantenmenge , eine zweielementige Menge für die zweistelligen Funktionssymbole und eine einelementige Menge für ein zweistelliges Relationssymbol Wir betrachten die Interpretation mit der Grundmenge und die Interpretation mit der Grundmenge , wobei Konstanten, Funktionssymbole und das Relationssymbol in natürlicher Weise interpretiert werden (und die Variablenbelegung irgendwie festgelegt sei).

Der -Ausdruck (also der Ausdruck in vorgestellter Notation) wird unter den Interpretationen als bzw. als interpretiert und daher gelten und . Dagegen ist der Ausdruck unter falsch und unter richtig, also


Das vorstehende Beispiel zeigt, dass die Gültigkeit von Ausdrücken unter einer bestimmten Interpretation von Eigenschaften der Grundmenge abhängt und durch eine mathematische Argumentation erwiesen oder zurückgewiesen werden muss. Diese kann beliebig kompliziert sein. Insbesondere bedeutet die Modellbeziehung nicht, dass man für jeden Ausdruck entscheiden kann, ob er in einer Interpretation wahr oder falsch ist.



Gültigkeit von Ausdrucksmengen

Für die Gültigkeitsbeziehung sagt man auch, dass die Interpretation ein Modell für den Ausdruck ist oder den Ausdruck erfüllt. Für eine Menge von Ausdrücken schreibt man , wenn in jeder Ausdruck aus gilt. Man sagt, dass ein Modell für ist. Eine Struktur heißt ein Modell, wenn jede Variablenbelegung zu dieser Struktur eine Interpretation liefert, die ein Modell 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 sind im mathematischen Sprachgebrauch Beispiele für die Struktur, die durch die Definition festgelegt wird.

Betrachten wir beispielsweise die Definition einer Gruppe.


Definition  

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 Alphabet (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 . 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 ) geben und eine zweistellige Funktion (eine Verknüpfung), derart, dass gilt.



<< | Kurs:Einführung in die mathematische Logik (Osnabrück 2011-2012) | >>

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)