Modallogik/Semantik/Systeme/Textabschnitt

Der durch die ${}K$-Modallogik gegebene axiomatische Rahmen gilt in jedem gerichteten Graphen, aufgefasst als modallogisches Modell. Wir fragen uns, wie speziellere modallogische Axiome mit Eigenschaften von gerichteten Graphen zusammenhängen. Der folgende Satz liefert eine Übersetzung zwischen diesen beiden Konzepten.

Satz

1. In einem gerichteten Graphen ${}(M,R)$ gilt das Möglichkeitsaxiom genau dann, wenn jeder Punkt ${}w\in M$ einen Nachfolger besitzt.
2. In einem gerichteten Graphen ${}(M,R)$ gilt das Reflexivitätsaxiom genau dann, wenn ${}R$ reflexiv ist.
3. In einem gerichteten Graphen ${}(M,R)$ gilt das Symmetrieaxiom genau dann, wenn ${}R$ symmetrisch ist.
4. In einem gerichteten Graphen ${}(M,R)$ gilt das Transitivitätsaxiom genau dann, wenn ${}R$ transitiv ist.
5. In einem gerichteten Graphen ${}(M,R)$ gilt das euklidische Axiom genau dann, wenn ${}R$ euklidisch ist.
6. In einem gerichteten Graphen ${}(M,R)$ gilt das Löb-Axiom genau dann, wenn ${}R$ transitiv ist und es in ${}M$ keine unendlichen Ketten gibt.

Beweis

(1). Es sei ${}(M,R)$ gegeben. Es sei zunächst vorausgesetzt, dass in ${}R$ jedes Element einen Nachfolger besitzt und sei

$w\vDash \Box \alpha$

für eine Welt ${}w\in M$. Es sei ${}v\in M$ mit ${}wRv$. Dann ist

$v\vDash \alpha$

und somit

$w\vDash \Diamond \alpha ,$

also

$w\vDash \Box \alpha \rightarrow \Diamond \alpha .$

Es sei umgekehrt angenommen, dass ${}M$ eine Sackgassenwelt ${}w$ besitzt. Dann ist für eine beliebige Aussagenvariable ${}p$

$w\vDash \Box p,$

aber

$w\not \vDash \Diamond p,$

und das Möglichkeitsaxiom kann nicht gelten.

(2). Es sei ${}(M,R)$ gegeben. Es sei zunächst ${}R$ reflexiv und sei

$w\vDash \Box \alpha .$

Wegen ${}wRw$ ist insbesondere

$w\vDash \alpha$

und damit

$w\vDash \Box \alpha \rightarrow \alpha .$

Wenn ${}R$ nicht reflexiv ist, so sei ${}w\in M$ und ${}wRw$ gelte nicht. Es sei ${}\mu$ die Belegung, bei der

$w\vDash p$

gelte, aber in allen anderen Welten ${}v\vDash \neg p$. Dann ist

$w\vDash \neg \Diamond p,$

und somit ist

$w\not \vDash p\rightarrow \Diamond p.$

(3). Es sei ${}(M,R)$ gegeben. Es sei zunächst ${}R$ symmetrisch und sei

$w\vDash \alpha .$

Es sei eine von ${}w$ aus erreichbare Welt ${}v$ gegeben, also ${}wRv$. Wegen der Symmetrie ist auch ${}vRw$ und somit ist

$v\vDash \Diamond \alpha .$

Also ist

$w\vdash \Box \Diamond \alpha .$

Wenn ${}R$ hingegen nicht symmetrisch ist, so seien ${}w,v\in M$ Welten mit ${}wRv$, aber nicht ${}vRw$. Es sei ${}p$ eine Aussagenvariable und es sei ${}\mu$ die Belegung, bei der

$w\vDash p$

gelte und so, dass in allen von ${}v$ aus erreichbaren Welten ${}z\vDash \neg p$ gelte. Dann ist

$v\vDash \neg \Diamond p,$

und somit ist

$w\not \vDash \Box \Diamond p,$

also

$w\not \vDash p\rightarrow \Box \Diamond p.$

(4). Es sei ${}(M,R)$ gegeben. Es sei zunächst ${}R$ transitiv und sei

$w\vDash \Box \alpha .$

Es sei ${}wRv$ und ${}vRz$ und somit

$z\vDash \alpha .$

Also ist

$v\vDash \Box \alpha .$

und damit

$w\vDash \Box \Box \alpha .$

Es sei nun ${}R$ nicht transitiv und seien ${}w,v,z\in M$ Punkte mit ${}wRv$, ${}vRz$, aber nicht ${}wRz$. Es sei ${}p$ eine Aussagenvariable und sei ${}\mu$ die Belegung, bei der ${}p$ in allen von ${}w$ aus erreichbaren Welten gelte, in allen anderen Welten nicht. Dann ist

$w\vDash \Box p$

und

$v\not \vDash \Box p,$

da ja ${}z\not \vDash p$, und somit ist

$w\not \vDash \Box \Box p,$

also

$w\not \vDash \Box p\rightarrow \Box \Box p.$

(5). Es sei ${}(M,R)$ gegeben. Es sei zunächst ${}R$ euklidisch und sei

$w\vDash \Diamond \alpha .$

Somit gibt es eine Welt ${}v$ mit ${}wRv$ und mit

$v\vDash \alpha .$

Es sei ${}z$ eine Welt mit ${}wRz$. Nach der euklidischen Eigenschaft ist dann auch ${}zRv$, daher ist

$z\vDash \Diamond \alpha .$

Somit ist

$w\vDash \Box \Diamond \alpha .$

Es sei nun ${}R$ nicht euklidisch und seien ${}w,v,z\in M$ Punkte mit ${}wRv$, ${}wRz$, aber nicht ${}vRz$. Es sei ${}p$ eine Aussagenvariable und sei ${}\mu$ die Belegung, bei der ${}\neg p$ in allen von ${}v$ aus erreichbaren Welten gelte, in allen anderen Welten nicht. Dann ist

$z\vDash p$

und somit

$w\vDash \Diamond p.$

In ${}v$ gilt hingegen ${}\Box \neg p$, also

$v\vDash \neg \Diamond p.$

Somit gilt

$w\vDash \neg \Box \Diamond p$

und damit

$w\not \vDash \Diamond p\rightarrow \Box \Diamond p.$

(6). Wir arbeiten mit der Kontraposition des Löb-Axioms, also mit

$\Diamond \alpha \rightarrow \Diamond (\alpha \wedge \neg \Diamond \alpha ).$

Es sei zunächst vorausgesetzt, dass ${}(M,R)$ die graphentheoretischen Eigenschaften besitzt. Sei ${}w\in W$ und

$w\vDash \Diamond \alpha .$

Dann gibt es eine Welt ${}v\in M$ mit ${}wRv$ und mit

$v\vDash \alpha .$

Wir betrachten Ketten ${}vRv_{2},v_{2}Rv_{3},\ldots$ mit ${}v_{i}\vDash \alpha$. Da es keine unendliche Kette gibt, bricht eine solche Kette ab, sagen wir in ${}v_{n}$. In ${}v_{n}$ gilt dann

$v_{n}\vDash \alpha \wedge \neg \Diamond \alpha .$

Wegen der Transitivität ist ${}v_{n}$ von ${}w$ aus erreichbar und somit ist

$w\vDash \Diamond (\alpha \wedge \neg \Diamond \alpha ).$

Es sei nun vorausgesetzt, dass ${}(M,R)$ nicht die Eigenschaften erfüllt. Wenn ${}R$ nicht transitiv ist, so ist nach Fakt in Verbindung mit Fakt die Gültigkeit des Löb-Axioms ausgeschlossen. Es sei also eine unendlich lange Kette der Form ${}w_{n}Rw_{n+1}$ gegeben. Wir belegen ${}w_{n}\vDash p$ für alle ${}n\in \mathbb {N}$ und ${}v\vDash \neg p$ für alle anderen Welten. Dann gilt

$w_{0}\vDash \Diamond p\wedge \neg \Diamond (p\wedge \neg \Diamond p),$

da außerhalb der Kette stets ${}\neg p$ gilt und innerhalb der Kette stets ${}\Diamond p$ gilt.

$\Box$

Bemerkung  

Ein Modell des Löb-Axioms ist insbesondere frei von Schleifen, d.h. es ist reflexivitätsfrei, es gilt also nie ${}wRw$. Eine solche Schleife würde ja direkt eine unendliche Kette produzieren. Der gerichtete Graph

$w_{n},n\in \mathbb {N} ,$

mit der durch ${}w_{n}Rw_{m}$, falls ${}n<m$ gegebenen Relation und der Belegung ${}w_{n}\vDash p$ für alle ${}n\in \mathbb {N}$ zeigt, dass das Löb-Axiom (in der Form $\Diamond p\rightarrow \Diamond (p\wedge \neg \Diamond p$) bei einer unendlichen transitiven Kette ohne Schleifen nicht gelten muss.

Beispiel

Wir betrachten für ${}n\in \mathbb {N} _{+}$ die modallogische Ausdrucksmenge, die durch

${}\alpha _{n}=\Diamond (p_{1}\wedge \ldots \wedge p_{n-1}\wedge \neg p_{n})\,$

gegeben ist. Da sich die Ausdrücke, die innerhalb des ${}\Diamond$-Operators von ${}\alpha _{n}$ stehen, gegenseitig ausschließen, braucht man zur Realisierung von ${}\alpha _{1}\wedge \ldots \wedge \alpha _{n}$ mindestens ${}n$ Punkte. Daher ist

${}\Gamma ={\left\{\alpha _{n}\mid n\in \mathbb {N} _{+}\right\}}\,$

nicht durch einen endlichen gerichteten Graphen erfüllbar. Die Ausdrucksmenge ist aber problemlos durch einen unendlichen gerichteten Graphen erfüllbar: Es seien ${}W_{n}$, ${}n\in \mathbb {N} _{+}$, die unendlich vielen Welten, in ${}W_{n}$ gilt ${}p_{1}\wedge \ldots \wedge p_{n-1}\wedge \neg p_{n}$ (die Wahrheitsbelegung ist ansonsten unerheblich) und jede Welt sei von jeder Welt aus erreichbar.