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

Aus Wikiversity



Die Korrektheit des Ableitungskalküls

Im Laufe der Einführung des syntaktischen Prädikatenkalküls haben wir gesehen, dass die in ihm ableitbaren Ausdrücke allgemeingültig sind, dass also sämtliche durch den Prädikatenkalkül generierten formalen Tautologien auch semantische Tautologien sind. Wir halten den sogenannten Korrektheitssatz (für Tautologien) fest.



Satz  

Es sei ein Symbolalphabet und sei eine syntaktische Tautologie.

Dann ist auch eine semantische Tautologie.

Beweis  

Dies ergibt sich aus den einzelnen Korrektheitsüberlegungen im Anschluss an die Ableitungsregeln, siehe beispielsweise Lemma 11.4.


Der entworfene Kalkül produziert also nur inhaltlich korrekte Ableitungen. Eine gleichwertige Variante davon bezieht sich auf die Ableitbarkeit und die Folgerung.



Satz  

Es sei ein Symbolalphabet, eine Menge an - Ausdrücken und ein weiterer -Ausdruck.

Dann folgt aus der Ableitungsbeziehung die Folgerungsbeziehung .

Beweis  

Es sei vorausgesetzt. Dann gibt es endlich viele Ausdrücke derart, dass eine formale Tautologie ist. Nach Satz 14.1 ist auch allgemeingültig. Es sei eine Interpretation mit . Dann ist insbesondere und wegen der Allgemeingültigkeit von gilt . Also gilt auch .


Die Umkehrung dieser beiden Aussagen ist deutlich schwieriger: Es geht um die Frage, ob der Kalkül jeden allgemeingültigen Ausdruck formal ableiten kann, ob es also für jeden mathematischen Beweis eines Ausdrucks einer Sprache erster Stufe auch einen formalen Beweis gibt. Es ist die Frage, ob der Kalkül vollständig ist. Dass dies der Fall ist, ist der Inhalt des Vollständigkeitssatzes, der auf Gödel zurückgeht und den wir in dieser und der nächsten Vorlesung beweisen werden. Der Beweis ist recht aufwändig, so dass wir kurz die Strategie erläutern, die in einer einfacheren Form schon im Beweis des Vollständigkeitssatzes für die Aussagenlogik verwendet wurde. Wir verwenden Kontraposition und zeigen, dass aus der Nichtableitbarkeit die Nichtfolgerung folgt. Ersteres bedeutet, dass widerspruchsfrei ist, und Letzteres bedeutet, dass erfüllbar ist. Wir zeigen daher allgemein, dass eine widerspruchsfreie Ausdrucksmenge erfüllbar ist. Dazu füllen wir eine widerspruchsfreie Ausdrucksmenge, analog zum aussagenlogischen Fall (siehe Lemma 5.17), zu einer maximal widerspruchsfreien Ausdrucksmenge auf. Wenn diese zusätzlich „Beispiele enthält“ (um das zu erreichen, muss man die Symbolmenge erweitern) so kann man auf der Sprache eine Äquivalenzrelation definieren, deren Äquivalenzklassen die Grundlage eines erfüllenden Modells bilden. Wir beginnen mit dem Satz von Henkin, der die Erfüllbarkeit im maximal widerspruchsfreien Fall mit Beispielen erledigt.



Der Satz von Henkin

Definition  

Eine Menge an - Ausdrücken (über einem Symbolalphabet ) heißt maximal widerspruchsfrei, wenn sie widerspruchsfrei ist und wenn jede Hinzunahme eines jeden Ausdrucks die Menge widersprüchlich macht.


Definition  

Man sagt, dass eine Menge an - Ausdrücken (über einem Symbolalphabet ) Beispiele enthält, wenn es für jeden Ausdruck der Form einen - Term derart gibt, dass

zu gehört.

Diese beiden Begriffe sind durch folgende Aussage motiviert.


Lemma  

Es sei ein Symbolalphabet und eine - Interpretation auf einer Menge , wobei die Terminterpretation surjektiv sei.

Dann ist die Gültigkeitsmenge maximal widerspruchsfrei und enthält Beispiele.

Beweis  

Zunächst ist aufgrund des Korrektheitssatzes abgeschlossen unter Ableitungen. Für jeden - Ausdruck gilt die Alternative: Entweder oder . Insbesondere ist widerspruchsfrei. Wenn ist, so ist und daher ist widersprüchlich. Also ist maximal widerspruchsfrei.
Wir betrachten nun einen Ausdruck der Form . Wenn gilt, so gilt in für jeden Term , da ja der Vordersatz nicht gilt. Wenn hingegen gilt, so gibt es aufgrund des semantischen Aufbaus der Gültigkeitbeziehung ein derart, dass gilt. Wegen der vorausgesetzten Surjektivität der Belegung gibt es einen Term , der durch interpretiert wird. Daher gilt nach dem Substitutionslemma in . Also gilt in .



Lemma  

Es sei eine Menge an - Ausdrücken (über einem Symbolalphabet ), die maximal widerspruchsfrei ist. Dann gelten folgende Eigenschaften.

  1. Für jeden Ausdruck ist entweder oder .
  2. Aus folgt , d.h. ist abgeschlossen unter Ableitungen.
  3. Für Ausdrücke ist genau dann, wenn und ist.

Beweis  

(1). Wegen der Widerspruchsfreiheit kann nicht sowohl als auch zu gehören. Wenn weder noch zu gehören, so ist entweder oder widerspruchsfrei. Wären nämlich beide widersprüchlich, so würde für einen beliebigen Ausdruck sowohl

als auch

gelten. Dies bedeutet

und

woraus aufgrund der Fallunterscheidungsregel

folgt. Dies bedeutet aber, dass widersprüchlich ist.
(2). Es sei . Nach (1) ist oder . Das zweite kann nicht sein, da sich daraus sofort ein Widerspruch ergeben würde. Also ist .
(3). Die Richtung von links nach rechts folgt aus (2). Es seien also . Da nach Aufgabe 3.33 eine Tautologie ist, folgt nach Teil (2).


Wir werden nun umgekehrt zu Lemma 14.5 zeigen, dass man zu einer jeden maximal widerspruchsfreien Ausdrucksmenge , die Beispiele enthält, eine Interpretation konstruieren kann, deren Gültigkeitsmenge mit übereinstimmt. Diese Konstruktion, die wir die kanonische Termidentifizierung nennen, geht folgendermaßen.


Konstruktion  

Es sei eine Menge an - Ausdrücken (über einem Symbolalphabet ), die abgeschlossen unter Ableitungen ist. Dann definiert man auf der Menge aller - Terme eine Äquivalenzrelation durch

Es sei die Menge der Termklassen (also die Menge der Äquivalenzklassen zu dieser Äquivalenzrelation). Auf definiert man für jedes -stellige Relationssymbol eine -stellige Relation durch

und für jedes -stellige Funktionssymbol eine -stellige Funktion durch

Konstanten werden als

interpretiert.

Wir müssen natürlich zunächst zeigen, dass wirklich eine Äquivalenzrelation vorliegt und dass die Relationen und Funktionen wohldefiniert sind.


Lemma  

Es sei eine Menge an - Ausdrücken (über einem Symbolalphabet ), die abgeschlossen unter Ableitungen ist.

Dann liefert die in Konstruktion 14.7 beschriebene Konstruktion eine Äquivalenzrelation auf der Menge aller Terme und wohldefinierte Relationen bzw. Funktionen auf der Menge der Termklassen.

Beweis  

Eine Äquivalenzrelation liegt aufgrund von Axiom 10.5  (1) und Lemma 10.7 (1), (2) vor, da ja nach Voraussetzung abgeschlossen unter Ableitungen ist und insbesondere alle syntaktischen Tautologien enthält.

Es sei die Menge der Äquivalenzklassen, die wir in diesem Zusammenhang Termklassen nennen. Es sei ein -stelliges Relationssymbol. Es sei ein -Tupel aus Termklassen, die einerseits durch das Termtupel und andererseits durch das Termtupel repräsentiert werde. Es gilt also bzw. . Wenn nun zu gehört, so folgt aus Lemma 10.7  (4) auch . Unter den gleichen Voraussetzungen folgt mit Lemma 10.7  (3) die Zugehörigkeit und somit

also die Wohldefiniertheit der Funktion.



Lemma  

Es sei eine Menge an - Ausdrücken (über einem Symbolalphabet ), die abgeschlossen unter Ableitungen ist.

Dann gilt für die Interpretation , wobei die in Konstruktion 14.7 beschriebene Menge aus Termklassen (mit der natürlichen Interpretation von Konstanten, Funktionssymbolen und Relationssymbolen) und die natürliche Belegung für Variablen ist, die Beziehung

für alle Terme .

Beweis  

Wir führen Induktion über den Aufbau der Terme, wobei der Induktionsanfang unmittelbar durch die natürliche Belegung gesichert ist. Die Aussage gelte nun für Terme und sei ein -stelliges Funktionssymbol. Dann ist


Die folgende Aussage heißt Satz von Henkin. Er wird durch Induktion über den sogenannten Rang eines Ausdrucks bewiesen. Dazu definieren wir.


Definition  

Unter einem atomaren Ausdruck versteht man Ausdrücke der Form , wobei und Terme sind, und der Form , wobei ein -stelliges Relationssymbol ist und Terme sind.


Definition  

Es sei ein Alphabet einer Sprache erster Stufe gegeben. Dann definiert man für Ausdrücke den Rang von durch

  1. , falls atomar ist.
  2. , falls ist.
  3. , falls mit ist.
  4. , falls oder ist.

Diese beiden Begriffe sind vor allem dann wichtig, wenn man eine Aussage über alle Ausdrücke induktiv beweisen möchte.


Satz  

Es sei eine Menge an - Ausdrücken (über einem Symbolalphabet ), die maximal widerspruchsfrei ist und Beispiele enthält.

Dann ist die in Konstruktion 14.7 gegebene Interpretation ein Modell für .

Insbesondere ist erfüllbar.

Beweis  

Es sei das konstruierte Modell zu und die zugehörige Interpretation mit der natürlichen Belegung für die Variablen. Wir zeigen die Äquivalenz

für alle Ausdrücke , durch Induktion über den Rang der Ausdrücke. Zum Induktionsanfang sei der Rang von gleich , also atomar. D.h. ist entweder von der Form oder . Im ersten Fall ist äquivalent zu bzw. in . Dies ist nach Lemma 14.9 äquivalent zu und das bedeutet .

Im zweiten Fall ist - nach Konstruktion von und - äquivalent zu , und dies ist äquivalent zu .

Es sei nun die Aussage für alle Ausdrücke vom Rang bewiesen und sei ein Ausdruck vom Rang . Wir betrachten die mögliche Struktur von gemäß Definition 7.2. Bei

ergibt sich die Äquivalenz aus der Induktionsvoraussetzung ( hat kleineren Rang als ) und Lemma 14.6  (1). Bei

besitzen die beiden Bestandteile kleineren Rang als . Die Zugehörigkeit ist nach Lemma 14.6  (3) äquivalent zur gemeinsamen Zugehörigkeit . Nach Induktionsvoraussetzung bedeutet dies und . Dies bedeutet wiederum aufgrund der Modellbeziehung. Bei

besitzt wieder einen kleineren Rang. Die Zugehörigkeit ist aufgrund der Eigenschaft, Beispiele zu enthalten und aufgrund von Axiom 11.1 äquivalent zur Existenz eines Terms und der Zugehörigkeit . Die Substitution von nach verändert nach Aufgabe 14.17 nicht den Rang. Wir können also auf die Induktionsvoraussetzung anwenden und erhalten die Äquivalenz zu . Nach dem Substitutionslemma ist dies äquivalent zu bzw. wegen Lemma 14.9. Dies ist äquivalent zu aufgrund der Modellbeziehung und der Surjektivität der Termabbildung.


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

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)