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

Aus Wikiversity
Zur Navigation springen Zur Suche springen



Maximal widerspruchsfreie modallogische Ausdrucksmengen

Wir wollen die Vollständigkeit der modallogischen Modelle zeigen, d.h. die Beziehung, dass wenn aus einer modallogischen Ausdrucksmenge die Gültigkeit von folgt, dass dann bereits aus modallogisch ableitbar ist. Die Ausdrucksmenge umfasst dabei stets das System und unter modallogisch ableitbar meint man ableitbar mit Hilfe von Modus Ponens und der Nezessisierungsregel. Dies muss hier betont werden, da es auf der Modellseite in natürlicher Weise Ausdrucksmengen gibt, die unter der Nezessisierungsregel abgeschlossen sind, und solche, die es nicht sind.

In einer -Modallogik gelten das modallogische Distributionsaxiom, die aussagenlogischen Tautologien und weitere, für spezifische Ausdrücke. Ferner ist abgeschlossenen unter dem Modus Ponens und der Nezessisierungsregel. In einem modallogischen Modell , das erfüllt, gilt in jedem Weltpunkt , also

Die Gültigkeitsmenge in einem Weltpunkt ist unter aussagenlogischen Operationen und insbesondere unter dem Modus Ponens abgeschlossen. Dagegen ist die Gültigkeitsmenge in einem Weltpunkt nicht unter der Nezessisierungsregel abgeschlossen. Im allgemeinen muss es zu einem modallogischen System überhaupt keine vollständige widerspruchsfreie Erweiterung geben, die der Nezessisierungsregel genügt, siehe Aufgabe 27.6.

Von daher verstehen wir unter einer widerspruchsfreien Teilmenge innerhalb einer modallogischen Sprache eine Teilmenge , die die -Modallogik umfasst und die unter Modus Ponens abgeschlossen ist und keinen (aussagenlogischen) Widerspruch enthält. Maximal widerspruchsfrei bedeutet wieder, dass aus jeder echten Erweiterung ein Widerspruch aussagenlogisch ableitbar ist. Zu jeder Welt in einem beliebigen modallogischen Modell von ist die Gültigkeitsmenge eine solche Teilmenge.



Lemma  

Es sei eine modallogische Ausdrucksmenge, die aussagenlogisch widerspruchsfrei sei.

Dann gibt es eine maximal widerspruchsfreie Ausdrucksmenge .

Beweis  

Dies ist eine rein aussagenlogische Aussage, die im Prinzip aus Lemma 5.17 folgt. Allerdings ist hier durch die Anwesenheit von die Sprache etwas anders. Für diesen Zweck kann man modalisierte Aussagen einfach als neue Aussagenvariablen auffassen. Man kann auch direkt das Lemma von Zorn in der jetzigen Situation anwenden. Oder man kann im abzählbaren Fall wie folgt schließen: Mit ist auch die modallogische Sprache überhaupt abzählbar. Wir betrachten eine Abzählung , der modallogischen Ausdrücken und definieren

falls dies widerspruchsfrei ist, und ansonsten durch

Die Vereinigung ist dann maximal widerspruchsfrei.




Das universelle modallogische Modell

In einer jeden Welt in einem modallogischen Modell ist die Gültigkeitsmenge maximal widerspruchsfrei. Für zwei Welten gilt dabei

Die rechte Seite kann man also als eine notwendige Bedingung dafür ansehen, dass von aus erreichbar ist. Im universellen modallogischen Modell definiert man die Erreichbarkeitsrelation durch diese notwendige Bedingung.


Konstruktion  

Es sei , , eine Menge von Aussagenvariablen und die zugehörige modallogische Sprache. Es sei die Menge aller umfassenden, (aussagenlogisch) maximal widerspruchsfreien Teilmengen

Auf definieren wir eine Erreichbarkeitsrelation durch

Wir nennen versehen mit dieser Relation und der durch , wenn , festgelegten Belegung das universelle modallogische Modell.

Wir identifizieren also Welten mit der Menge der in ihnen gültigen modallogischen Aussagen. Wenn eine Erreichbarkeitsrelation sein soll, so muss diese Beziehung gelten. Die rechte Seite ist dabei eine Implikation, keine Äquivalenz; es wird nicht gefordert, dass aus auch folgt.


Konstruktion  

Es sei , , eine Menge von Aussagenvariablen und die zugehörige modallogische Sprache. Es sei eine -modallogische Ausdrucksmenge. Es sei die Menge aller umfassenden, (aussagenlogisch) maximal widerspruchsfreien Teilmengen

Auf definieren wir eine Erreichbarkeitsrelation durch

Wir nennen versehen mit dieser Relation und der durch , wenn , festgelegten Belegung das -universelle modallogische Modell.

Die Relation und die Belegung im -universellen modallogischen Modell stimmen mit dem universellen Modell überein, es hndelt sich also um einen Teilgraphen. Es ist unser Ziel zu zeigen, dass im -universellen modallogischen Modell genau die Ausdrücke aus gelten.



Lemma  

Es sei ein -modallogisches System und ein modallogischer Ausdruck.

Dann folgt aus

die Beziehung

wobei

Beweis  

Die Ableitbarkeit bedeutet, dass es Ausdrücke mit

gibt. Nach Lemma 24.5  (1) ist

Aus Lemma 24.5  (4) folgt durch Induktion sofort

und somit mit dem Kettenschluss

Dies bedeutet




Lemma  

Es sei , , eine Menge von Aussagenvariablen und die zugehörige modallogische Sprache. Es sei ein -modallogisches System, es sei eine maximal widerspruchsfreie -Teilmenge und es sei ein modallogischer Ausdruck mit .

Dann gibt es eine maximal widerspruchsfreie -Teilmenge mit und mit im Sinne des -universellen modallogischen Modells.

Beweis  

Wir betrachten die Menge

die umfasst, da unter der Nezessisierungsregel abgeschlossen ist. Wir behaupten, dass diese Menge widerspruchsfrei ist. Andernfalls würde es endliche viele mit geben mit

Dies schreiben wir als

Nach Lemma 27.4 ist dann auch

Wegen des -Axioms ist

und somit

Da der Vordersatz zu gehört, und abgeschlossen unter Implikationen ist, ist auch

Da eine Tautologie ist und wegen der Nezessisierungsregel (die ja für Tautologien gilt) ergibt sich

was ein Widerspruch zu angesichts der Widerspruchsfreiheit von ist.

Somit ist widerspruchsfrei. Sei eine maximal widerspruchsfreie Teilmenge von , die es nach Lemma 27.1 gibt. Sei . Dann ist . Andernfalls wäre nämlich wegen der Maximalität (von ) , doch dann wäre . Es gilt also .




Lemma  

Es sei ein -modallogisches System. Dann gilt im -universellen modallogischen Modell für jede Welt und jeden modallogischen Ausdruck

die Beziehung

Beweis  

Wir führen Induktion über den Aufbau der modallogischen Sprache, und zwar gleichzeitig für alle Welten. Für Aussagenvariablen gilt die Behauptung unmittelbar aufgrund der festgelegten Belegung. Die Äquivalenz ist auch unter aussagenlogischen Konstruktionen abgeschlossen, da die unter -Ableitungen abgeschlossen sind. Es bleibt noch zu zeigen, dass sich die Äquivalenz bei modallogischen Operationen erhält, wobei wir mit dem Möglichkeitsoperator arbeiten. Sei also gegeben, wobei die Äquivalenz für und für alle Welten gelte. Wenn gilt, so gibt es eine Welt mit und . Aufgrund der Induktionsvoraussetzung gilt . Wegen der Definition der Erreichbarkeitsrelation bedeutet dies insbesondere . Sei umgekehrt . Dann folgt aus Lemma 27.5 die Existenz einer von aus erreichbaren -Welt mit , also nach Induktionsvoraussetzung und somit .




Die Vollständigkeit der Modallogik



Satz  

Es sei ein -modallogisches System und sei ein modallogischer Ausdruck.

Dann ist

genau dann, wenn

Beweis  

Die Hinrichtung ergibt sich aus Lemma 26.9. Für die Rückrichtung nehmen wir

an. Dann ist

(aussagenlogisch) nicht widersprüchlich und wir müssen zeigen, dass durch ein -modallogisches Modell erfüllbar ist. Wir betrachten dazu das -universelle modallogische Modell , in dem (in jedem Weltpunkt) gilt. Nach Lemma 27.1 gibt es eine maximal widerspruchsfreien -Ausdrucksmenge , die wir als Welt in betrachten können. Nach Lemma 27.6 gilt , was insbesondere die Gültigkeit von in zeigt.


Bemerkung  

Es sei betont, dass der Vollständigkeitssatz sich auf die Folgerung bezieht, die unter Bezug auf Modelle formuliert wird, nicht auf Rahmen. Typischerweise ist eine modallogische Ausdrucksmenge in gewissen Rahmen bei jeder Belegung gültig, aber auch noch in weiteren Rahmen bei gewissen Belegungen. Ein semantischer Beweis für die Ableitbarkeit kann also im Allgemeinen nicht allein mit Eigenschaften von gerichteten Graphen arbeiten, sondern muss auch Variablenbelegungen mitberücksichtigen.



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

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)