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

Aus Wikiversity
Zur Navigation springen Zur Suche springen



Weitere Axiomenschemata

Definition  

Das modallogische Axiomenschema

nennt man Reflexivitätsaxiom.

Durch das Reflexivitätsaxiom wird die eigene Welt bei Möglichkeitsüberlegungen mitberücksichtigt.


Definition  

Das modallogische Axiomenschema

nennt man Autismusaxiom.

Durch das Autismusaxiom werden andere Welten bei Möglichkeitsüberlegungen nicht berücksichtigt, eventuell noch nicht einmal die eigene Welt. Wenn das Leerheitsaxiom gilt, so auch das Autismusaxiom.


Definition  

Das modallogische Axiomenschema

nennt man Fatalismusaxiom.

In diesem Fall gilt auch

und damit auch

Es gilt als auch das Ideologieaxiom. Im Fatalismus wird die Realität zur Ideologie gemacht.

Die folgenden Axiomenschemata sind sinnvoller, die Bezeichnungen werden sich später erklären, wenn wir die semantische Interpretation zur Verfügung haben.


Definition  

Das modallogische Axiomenschema

nennt man Symmetrieaxiom.


Definition  

Das modallogische Axiomenschema

nennt man Transitivitätsaxiom.


Definition  

Das modallogische Axiomenschema

nennt man euklidisches Axiom (oder Axiom ).



Lemma  

In einem modallogischen -System, in dem das Symmetrieaxiom und das euklidische Axiom gelten,

gilt auch das Transitivitätsaxiom.

Beweis  

Es sei das in Frage stehende System. Eine spezielle Instanz des Symmetrieaxioms liefert

Eine Umformulierung des euklidischen Axioms ist

Mit Lemma 24.5  (1) folgt daraus

und insgesamt mit dem Kettenschluss




Paradoxe Axiome

Einen modallogischen Ausdruck nennen wir paradox, wenn er, wenn man alle darin auftretenden (und somit auch alle ) weglässt, ein aussagenlogischer Widerspruch ergibt. Ein modallogisches Axiomenschema heißt paradox, wenn es davon eine paradoxe Instanz gibt.


Definition  

Das modallogische Axiomenschema

nennt man Antiaxiom.

Wenn das Antiaxiom gilt, so ist auch

das Antiaxiom ist also ideologisch. In einer -Modallogik führt das Antiaxiom zu einem Widerspruch, da ja dann zu einer aussagenlogischen Tautologie wegen der Nezessisierungsregel auch und somit der Widerspruch gilt. Wenn man dagegen das Antiaxiom auf Aussagenvariablen beschränkt, also

betrachtet, so ergibt sich ein sinnvolles -System.


Definition  

Das modallogische Axiomenschema

nennt man Löb-Axiom.

Bemerkung  

Für das Ableitungsprädikat

zu einer die Peano-Arithmetik umfassenden entscheidbaren Satzmenge gilt neben den in Bemerkung 23.7 angeführten Eigenschaften auch der Satz von Löb, nämlich

Wenn man

setzt, so kann man dies als

schreiben, es liegt also genau das Löb-Axiom vor (daher der Name des Axioms). Unter der modallogischen Beweisbarkeitslogik versteht man die -Modallogik, die durch das Löb-Axiom gegeben ist (das Transitivitätsaxiom lässt sich daraus ableiten). Es handelt sich um eine paradoxe Modallogik, in der man die Unvollständigkeit nachbbilden kann.


Es sei (gesprochen Falsum) eine Abkürzung für einen Widerspruch. Im Kontext der Beweisbarkeitslogik bedeutet dann die Nichtableitbarkeit eines Widerspruchs, also die Widerspruchsfreiheit des Systems. Aus dem Löb-Axiom (also der -Modallogik , die durch das Löbaxiom gegeben ist) lässt sich ableiten, dass diese Widerspruchsfreiheit ein Fixpunkt der Nichtableitbarkeit ist, d.h. es gilt

siehe Aufgabe 25.6. Dies bedeutet insbesondere, dass weder noch aus ableitbar ist (die Widerspruchsfreiheit des Systems ergibt sich aus Satz 26.10  (6)). Insbesondere ist dieses Ableitungssystem unvollständig, was dem ersten Gödelschen Fixpunktsatz entspricht. Darüber hinaus ist die letzte Unableitbarkeit gerade die Aussage des zweiten Gödelschen Fixpunktsatzes, den man also so modallogisch nachbilden kann (die Hauptarbeit liegt aber darin, zu zeigen, dass das arithmetische Ableitungsprädikat das Löb-Axiom erfüllt).



Einige klassische modallogische Systeme

Definition  

Das modallogische -System, in dem das Möglichkeitsaxiom gilt, heißt -System.


Definition  

Das modallogische -System, in dem das Reflexionsaxiom gilt, heißt -System.



Lemma  

Im modallogischen -System gelten die folgenden Aussagen.

Es ist

Insbesondere ist

und damit ist ein -System auch ein -System.

Beweis  

Die Kontraposition des Reflexivitätsaxioms ergibt direkt

also

Da dies für alle gilt, gilt nach Lemma 24.5  (5) auch

Der Zusatz folgt aus



Definition  

Das modallogische -System, in dem das Reflexionsaxiom und das Symmetrieaxiom gilt, heißt -System.



Definition  

Das modallogische -System, in dem das Reflexionsaxiom und das Transitivitätsaxiom gilt, heißt -System.


Definition  

Das modallogische -System, in dem das Reflexionsaxiom, das Symmetrieaxiom und das Transitivitätsaxiom gilt, heißt -System.



Lemma  

Für ein modallogisches -System sind folgende Aussagen äquivalent.

  1. Es gilt das Reflexivitätsaxiom und das euklidische Axiom
  2. Es gilt das Möglichkeitsaxiom, das Symmetrieaxiom und das Transitivitätsaxiom
  3. Es handelt sich um das -System.

Beweis  

Aus (1) folgt (2). Es sei das modallogische System, das durch die Gültigkeit von Reflexivitätsaxiom und euklidischem Axiom festgelegt ist. Nach Lemma 25.13 gilt mit dem Reflexivitätsaxiom auch das Möglichkeitsaxiom. Durch das Reflexivitätsaxiom gilt

und mit dem euklidischen Axiom gilt

was mit dem Kettenschluss

also die Symmetrie ergibt. Aus dem euklidischen Axiom und der Symmetrie ergibt sich nach Lemma 25.7 auch die Transitivität.

Aus (2) folgt (3). Sei die Vereinigung aus dem Möglichkeitsaxiom, dem Symmetrieaxiom und dem Transitivitätsaxiom. Das Symmetrieaxiom ergibt

das Möglichkeitsaxiom liefert

und das Transitivitätsaxiom liefert

Der Kettenschluss darauf angewendet liefert

also das Reflexivitätsaxiom.

Aus (3) folgt (1). Aus dem Transitivitätsaxiom

ergibt sich mit Lemma 24.5  (2)

Aufgrund des Symmetrieaxioms gilt

Angewendet auf ergibt dies

Dies ist gleichwertig zum euklidischen Axiom.




Lemma  

In einem modallogischen -System, in dem das Löb-Axiom gilt,

gilt auch das Transitivitätsaxiom.

Beweis  

Wir wenden das Löb-Axiom auf den Ausdruck an und erhalten ( steht für dieses modallogische System)

Wegen Lemma 24.5  (3) ist

und

Wegen der zuletzt angeführten Ableitung erhält man

und daraus mit Lemma 24.5  (1) auch

Ein zweifacher Kettenschluss liefert




Gerichtete Graphen

Für die Modelltheorie der Modallogik benötigen wir gerichtete Graphen. Dies ist mathematisch betrachtet einfach eine zweistellige Relation auf einer Menge.


Definition  

Ein gerichteter Graph ist eine Menge versehen mit einer fixierten Relation .

Die Menge der Punkte nennt man auch die Knoten des Graphen und man sagt, dass ein Pfeil von nach geht, wenn ist. In dieser Weise werden gerichtete Graphen veranschaulicht. Einen Pfeil von einem Knoten zu sich selbst heißt Schleife.

Im Kontext von Ordnungsrelationen und Äquivalenzrelationen haben wir schon die Eigenschaften reflexiv, symmetrisch, transitiv kennengelernt. Einen symmetrischen gerichteten Graphen nennt man auch einen ungerichteten Graphen. In diesem Fall nennt man einen verbindenden Pfeil eine Kante. Wir besprechen einige weitere Begrifflichkeiten und Eigenschaften.


Definition  

Es sei ein gerichteter Graph. Zu einer Teilmenge nennt man

die Vorgängermenge zu .


Definition  

Es sei ein gerichteter Graph. Zu einer Teilmenge nennt man

die Nachfolgermenge zu .

Ein Knoten ohne Nachfolger, also ohne abgehenden Pfeil (also auch keine Schleife), heißt Sackgasse.


Definition  

Eine Relation auf einer Menge heißt euklidisch, wenn zu mit und stets gilt.


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

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)