Kurs:Einführung in die mathematische Logik (Osnabrück 2016)/Vorlesung 26/latex
\setcounter{section}{26}
\zwischenueberschrift{Semantik der Modallogik}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Gottfried Wilhelm von Leibniz.jpg} }
\end{center}
\bildtext {Von Gottfried Wilhelm Leibniz stammt die Idee, Notwendigkeiten über mögliche Welten zu verstehen.} }
\bildlizenz { Gottfried Wilhelm von Leibniz.jpg } {Christoph Bernhard Francke} {Andrejj} {Commons} {} {}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Kripke.JPG} }
\end{center}
\bildtext {Saul Kripke schuf die formale Modelltheorie für die Modallogik.} }
\bildlizenz { Kripke.JPG } {} {Oursipan} {Commons} {gemeinfrei} {}
Wir besprechen nun die Semantik der Modallogik, die mit gerichteten Graphen arbeitet, die die Idee von erreichbaren Welten modellieren.
\inputdefinition
{}
{
Unter einem
\definitionswort {modallogischen Modell}{}
versteht man einen
\definitionsverweis {gerichteten Graphen}{}{}
\mathl{(M,R)}{} zusammen mit einer
\definitionsverweis {Wahrheitsbelegung}{}{}
$\mu$ für die
\definitionsverweis {Aussagenvariablen}{}{}
für jeden Knotenpunkt
\mavergleichskette
{\vergleichskette
{w
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}
Die Knotenpunkte des gerichteten Graphen nennt man in diesem Zusammenhang auch \stichwort {Welten} {} oder Weltpunkte. Die von einer Welt $x$ aus verbundenen Welten $y$, also die mit
\mathl{xRy}{,} nennt man die von $x$ aus erreichbaren Welten, die Relation $R$ heißt auch \stichwort {Erreichbarkeitsrelation} {.} Durch die übliche Interpretation der aussagenlogischen Junktoren erhält man in jedem Weltpunkt eine Belegung für alle aussagenlogischen Ausdrücke in den gegebenen Aussagenvariablen. Darauf aufbauend kann man auch jedem modallogischen Ausdruck an jedem Knotenpunkt einen Wahrheitswert zuordnen, und zwar in folgender Weise. Dabei wird die Gültigkeit einer Aussage $\alpha$ in einer Welt $w$ als
\mathl{w \vDash \alpha}{} notiert.
\inputdefinition
{}
{
In einem
\definitionsverweis {modallogischen Modell}{}{}
\mathl{(M,R,\mu)}{}
\zusatzklammer {mit einer punktweisen Wahrheitsbelegung $\mu$} {} {}
definiert man die Gültigkeit von
\definitionsverweis {modallogischen Ausdrücken}{}{}
induktiv wie folgt: Es sei der modallogische Ausdruck $\alpha$ schon für jeden Weltpunkt definiert. Dann setzt man für einen jeden Weltpunkt
\mavergleichskette
{\vergleichskette
{w
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
\mathdisp {w \vDash \Box \alpha} { }
genau dann, wenn in jeder von $w$ aus erreichbaren Welt $v$ die Beziehung
\mathdisp {v \vDash \alpha} { }
gilt.
}
\inputbeispiel{}
{
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Baby Category 2.svg} }
\end{center}
\bildtext {} }
\bildlizenz { Baby Category 2.svg } {} {Melikamp} {Commons} {CC-by-sa 3.0} {}
Wir arbeiten mit den Aussagenvariablen
\mathl{p,q,r}{.} Im Weltpunkt $a$ gelte
\mathdisp {a \vDash p, q , \neg r} { }
und im Weltpunkt $b$ gelte
\mathdisp {b \vDash p, \neg q , r} { . }
Daraus kann man die Gültigkeit von aussagenlogischen Ausdrücken jeweils erschließen, beispielsweise gilt
\mathdisp {a \vDash p \wedge \neg r} { }
oder
\mathdisp {b \vDash \neg q \rightarrow r} { . }
Für modallogische Ausdrücke muss man den gerichteten Graphen berücksichtigen, wobei man induktiv über die Anzahl der Boxen vorgeht. Es geht also zunächst um Ausdrücke der Form $\Box \alpha$, wobei $\alpha$ ein rein aussagenlogischer Ausdruck ist
\zusatzklammer {also ohne jede Box} {} {.}
Die Gültigkeit von $\Box \alpha$ in einem Weltpunkt bedeutet, dass in jedem von diesem Weltpunkt aus erreichbaren Weltpunkt $\alpha$ gilt. Somit gilt beispielsweise
\mathdisp {a \vDash \Box p} { }
und
\mathdisp {a \vDash \neg \Box q} { }
und
\mathdisp {a \vDash \Box (q \vee r)} { , }
ferner
\mathdisp {b \vDash \Box p} { }
und
\mathdisp {b \vDash \Box \neg q} { . }
Damit kann man dann in jedem Punkt aussagenlogisch den Wahrheitswert von jeder modallogischen Aussage bestimmen, in der die Box nur einfach
\zusatzklammer {also ohne Verschachtelungen} {} {}
auftritt, beispielsweise
\mathdisp {a \vDash \Box p \wedge \neg r \wedge \neg \Box \neg r} { . }
Unter Berücksichtigung des gerichteten Graphen kann man dann auch den Wahrheitswert für jeden modallogischen Ausdruck mit modallogischer Verschachtelungstiefe $\leq 2$ bestimmen, also etwa
\mathdisp {a \vDash \Box \Box p} { , }
u.s.w.
}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Kripke frame.png} }
\end{center}
\bildtext {} }
\bildlizenz { Kripke frame.png } {} {Eusebius} {Commons} {CC-by-sa 3.0} {}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Kripke model.png} }
\end{center}
\bildtext {} }
\bildlizenz { Kripke model.png } {} {Eusebius} {Commons} {CC-by-sa 3.0} {}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Frames.png} }
\end{center}
\bildtext {} }
\bildlizenz { Frames.png } {} {Eusebius} {Commons} {CC-by-sa 3.0} {}
\inputdefinition
{}
{
Man sagt, dass ein
\definitionsverweis {modallogischer Ausdruck}{}{}
$\alpha$ in einem
\definitionsverweis {modallogischen Modell}{}{}
\mathl{(M,R,\mu)}{}
\definitionswort {gilt}{,}
geschrieben
\mathdisp {(M,R,\mu) \vDash \alpha} { , }
wenn
\mathdisp {w \vDash \alpha} { }
für alle
\mavergleichskette
{\vergleichskette
{w
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt.
}
\inputfaktbeweis
{Modallogik/K/Gültigkeit/Fakt}
{Lemma}
{}
{
\faktsituation {}
\faktfolgerung {\aufzaehlungvier{Die
\definitionsverweis {aussagenlogischen Tautologien}{}{}
der modallogischen Sprache gelten in jedem
\definitionsverweis {modallogischen Modell}{}{.}
}{In jedem modallogischen Modell
\mathl{(M,R,\mu)}{} gilt das
$K$-\definitionsverweis {Axiom}{}{,}
also
\mathdisp {M \vDash \Box (\alpha \rightarrow \beta) \rightarrow (\Box \alpha \rightarrow \Box \beta)} { . }
}{Die in einem
\zusatzklammer {jeden} {} {}
modallogischen Modell gültigen Ausdrücke sind abgeschlossen unter dem
\definitionsverweis {Modus ponens}{}{.}
}{Wenn ein
\definitionsverweis {modallogischer Ausdruck}{}{}
$\alpha$ in einem
\zusatzklammer {jedem} {} {}
modallogischen Modell gilt, so gilt auch $\Box \alpha$ in diesem
\zusatzklammer {jedem} {} {}
modallogischen Modell.
}}
\faktzusatz {}
\faktzusatz {}
}
{
(1) und (3) sind klar, da die Gültigkeit in einem Knoten die aussagenlogischen Gesetze respektiert. (2). Sei
\mavergleichskette
{\vergleichskette
{w
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mathdisp {w \vDash \Box (\alpha \rightarrow \beta)} { }
und
\mathdisp {w \vDash \Box \alpha} { . }
Dann gilt in jeder von $w$ aus erreichbaren Welt $v$
\mathdisp {v \vDash \alpha \rightarrow \beta \text{ und } v \vDash \alpha} { }
und damit
\mathdisp {v \vDash \beta} { . }
Also ist
\mathdisp {w \vDash \Box \beta} { . }
(4). Wenn
\mathl{(M,R,\mu) \vDash \alpha}{} in einem modallogischen Modell
\mathl{(M,R,\mu)}{} gilt, so gilt für jede Welt
\mavergleichskette
{\vergleichskette
{w
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
auch
\mathl{w \vDash \alpha}{.} Wegen dieser allgemeinen Gültigkeit gilt auch
\mathl{v \vDash \alpha}{} für jede von $w$ aus erreichbare Welt und damit
\mathl{w \vDash \Box \alpha}{.} Dies gilt in jedem Punkt dieses Modells.
\inputdefinition
{}
{
Man sagt, dass eine Menge $\Gamma$ von
\definitionsverweis {modallogischen Ausdrücken}{}{}
in einem
\definitionsverweis {modallogischen Modell}{}{}
\mathl{(M,R,\mu)}{}
\definitionswort {gilt}{,}
geschrieben
\mathdisp {(M,R,\mu) \vDash \Gamma} { , }
wenn
\mathdisp {(M,R,\mu) \vDash \alpha} { }
für alle
\mavergleichskette
{\vergleichskette
{\alpha
}
{ \in }{\Gamma
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt.
}
\inputdefinition
{}
{
Man sagt, dass ein
\definitionswort {modallogischer Ausdruck}{}
$\alpha$ in einem
\definitionsverweis {gerichteten Graphen}{}{}
\mathl{(M,R)}{}
\definitionswort {gilt}{,}
geschrieben
\mathdisp {(M,R) \vDash \alpha} { , }
wenn für jede
\definitionsverweis {Wahrheitsbelegung}{}{}
$\mu$
\mathdisp {(M,R, \mu) \vDash \alpha} { }
\definitionsverweis {gilt}{}{.}
}
\inputdefinition
{}
{
Es sei $\Gamma$ eine Menge von
\definitionsverweis {modallogischen Ausdrücken}{}{}
und $\alpha$ ein modallogischer Ausdruck. Man sagt, dass $\alpha$ aus $\Gamma$
\definitionswort {folgt}{,}
geschrieben
\mathl{\Gamma \vDash \alpha}{,} wenn für jedes
\definitionsverweis {modallogische Modell}{}{}
\mathl{(M,R,\mu)}{} mit
\mathdisp {(M,R,\mu) \vDash \Gamma} { }
auch
\mathdisp {(M,R,\mu) \vDash \alpha} { }
gilt.
}
Für
\mavergleichskette
{\vergleichskette
{\Gamma
}
{ = }{ \emptyset
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ergeben sich die modallogisch allgemeingültigen Ausdrücke. Aufgrund von
Lemma 26.5
gehören alle in der
$K$-\definitionsverweis {Modallogik}{}{}
ableitbaren Ausdrücke dazu. Wie in der Aussagenlogik und der Prädikatenlogik ist also der Ableitungskalkül korrekt und es erhebt sich die Frage, ob er auch vollständig ist.
\inputfaktbeweis
{Modallogik/Korrektheitssatz/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei $\Gamma$ ein
$K$-\definitionsverweis {modallogisches System}{}{}
und $\alpha$ ein modallogischer Ausdruck.}
\faktvoraussetzung {Es gelte
\mathdisp {\Gamma \vdash \alpha} { . }
}
\faktfolgerung {Dann ist auch
\mathdisp {\Gamma \vDash \alpha} { . }
}
\faktzusatz {}
\faktzusatz {}
}
{
Dies folgt aus Lemma 26.5.
Diese Aussage erlaubt es insbesondere, zu zeigen, dass aus einem gegebenen modallogischen Axiomensystem $\Gamma$ ein gewisser modallogischer Ausdruck $\alpha$ nicht ableitbar, indem man ein modallogisches Modell
\mathl{(M,R, \mu)}{} angibt, in dem $\Gamma$ gilt, aber $\alpha$ nicht.
\zwischenueberschrift{Semantik der einzelnen modallogischen Systeme}
Der durch die $K$-\definitionsverweis {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.
\inputfaktbeweis
{Modallogik/K/Systeme und Rahmen/Fakt}
{Satz}
{}
{
\faktsituation {}
\faktfolgerung {\aufzaehlungsechs{In einem
\definitionsverweis {gerichteten Graphen}{}{}
\mathl{(M,R)}{} gilt das
\definitionsverweis {Möglichkeitsaxiom}{}{}
genau dann, wenn jeder Punkt
\mavergleichskette
{\vergleichskette
{w
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
einen Nachfolger besitzt.
}{In einem gerichteten Graphen
\mathl{(M,R)}{} gilt das
\definitionsverweis {Reflexivitätsaxiom}{}{}
genau dann, wenn $R$
\definitionsverweis {reflexiv}{}{}
ist.
}{In einem gerichteten Graphen
\mathl{(M,R)}{} gilt das
\definitionsverweis {Symmetrieaxiom}{}{}
genau dann, wenn $R$
\definitionsverweis {symmetrisch}{}{}
ist.
}{In einem gerichteten Graphen
\mathl{(M,R)}{} gilt das
\definitionsverweis {Transitivitätsaxiom}{}{}
genau dann, wenn $R$
\definitionsverweis {transitiv}{}{}
ist.
}{In einem gerichteten Graphen
\mathl{(M,R)}{} gilt das
\definitionsverweis {euklidische Axiom}{}{}
genau dann, wenn $R$
\definitionsverweis {euklidisch}{}{}
ist.
}{In einem gerichteten Graphen
\mathl{(M,R)}{} gilt das
\definitionsverweis {Löb-Axiom}{}{}
genau dann, wenn $R$
\definitionsverweis {transitiv}{}{}
ist und es in $M$ keine unendlichen Ketten gibt.
}}
\faktzusatz {}
\faktzusatz {}
}
{
(1). Es sei
\mathl{(M,R)}{} gegeben. Es sei zunächst vorausgesetzt, dass in $R$ jedes Element einen Nachfolger besitzt und sei
\mathdisp {w \vDash \Box \alpha} { }
für eine Welt
\mavergleichskette
{\vergleichskette
{w
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Es sei
\mavergleichskette
{\vergleichskette
{v
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mathl{wRv}{.} Dann ist
\mathdisp {v \vDash \alpha} { }
und somit
\mathdisp {w \vDash \Diamond \alpha} { , }
also
\mathdisp {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$
\mathdisp {w \vDash \Box p} { , }
aber
\mathdisp {w \not\vDash \Diamond p} { , }
und das Möglichkeitsaxiom kann nicht gelten.
(2). Es sei
\mathl{(M,R)}{} gegeben. Es sei zunächst $R$ reflexiv und sei
\mathdisp {w \vDash \Box \alpha} { . }
Wegen
\mathl{wRw}{} ist insbesondere
\mathdisp {w \vDash \alpha} { }
und damit
\mathdisp {w \vDash \Box \alpha \rightarrow \alpha} { . }
Wenn $R$ nicht reflexiv ist, so sei
\mavergleichskette
{\vergleichskette
{w
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mathl{wRw}{} gelte nicht. Es sei $\mu$ die Belegung, bei der
\mathdisp {w \vDash p} { }
gelte, aber in allen anderen Welten
\mathl{v \vDash \neg p}{.} Dann ist
\mathdisp {w \vDash \neg \Diamond p} { , }
und somit ist
\mathdisp {w \not \vDash p \rightarrow \Diamond p} { . }
(3). Es sei
\mathl{(M,R)}{} gegeben. Es sei zunächst $R$ symmetrisch und sei
\mathdisp {w \vDash \alpha} { . }
Es sei eine von $w$ aus erreichbare Welt $v$ gegeben, also
\mathl{wRv}{.} Wegen der Symmetrie ist auch
\mathl{vRw}{} und somit ist
\mathdisp {v\vDash \Diamond \alpha} { . }
Also ist
\mathdisp {w \vdash \Box \Diamond \alpha} { . }
Wenn $R$ hingegen nicht symmetrisch ist, so seien
\mavergleichskette
{\vergleichskette
{w,v
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
Welten mit
\mathl{wRv}{,} aber nicht
\mathl{vRw}{.} Es sei $p$ eine Aussagenvariable und es sei $\mu$ die Belegung, bei der
\mathdisp {w \vDash p} { }
gelte und so, dass in allen von $v$ aus erreichbaren Welten
\mathl{z \vDash \neg p}{} gelte. Dann ist
\mathdisp {v \vDash \neg \Diamond p} { , }
und somit ist
\mathdisp {w \not \vDash \Box \Diamond p} { , }
also
\mathdisp {w \not \vDash p \rightarrow \Box \Diamond p} { . }
(4). Es sei
\mathl{(M,R)}{} gegeben. Es sei zunächst $R$ transitiv und sei
\mathdisp {w \vDash \Box \alpha} { . }
Es sei
\mathl{wRv}{} und
\mathl{vRz}{} und somit
\mathdisp {z \vDash \alpha} { . }
Also ist
\mathdisp {v \vDash \Box \alpha} { . }
und damit
\mathdisp {w \vDash \Box \Box \alpha} { . }
Es sei nun $R$ nicht transitiv und seien
\mavergleichskette
{\vergleichskette
{ w,v,z
}
{ \in }{ M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
Punkte mit
\mathl{wRv}{,}
\mathl{vRz}{,} aber nicht
\mathl{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
\mathdisp {w \vDash \Box p} { }
und
\mathdisp {v \not \vDash \Box p} { , }
da ja
\mathl{z \not \vDash p}{,} und somit ist
\mathdisp {w \not \vDash \Box \Box p} { , }
also
\mathdisp {w \not \vDash \Box p \rightarrow \Box \Box p} { . }
(5). Es sei
\mathl{(M,R)}{} gegeben. Es sei zunächst $R$ euklidisch und sei
\mathdisp {w \vDash \Diamond \alpha} { . }
Somit gibt es eine Welt $v$ mit
\mathl{wRv}{} und mit
\mathdisp {v \vDash \alpha} { . }
Es sei $z$ eine Welt mit
\mathl{wRz}{.} Nach der euklidischen Eigenschaft ist dann auch
\mathl{zRv}{,} daher ist
\mathdisp {z \vDash \Diamond \alpha} { . }
Somit ist
\mathdisp {w \vDash \Box \Diamond \alpha} { . }
Es sei nun $R$ nicht euklidisch und seien
\mavergleichskette
{\vergleichskette
{ w,v,z
}
{ \in }{ M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
Punkte mit
\mathl{wRv}{,}
\mathl{wRz}{,} aber nicht
\mathl{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
\mathdisp {z \vDash p} { }
und somit
\mathdisp {w \vDash \Diamond p} { . }
In $v$ gilt hingegen $\Box \neg p$, also
\mathdisp {v \vDash \neg \Diamond p} { . }
Somit gilt
\mathdisp {w \vDash \neg \Box \Diamond p} { }
und damit
\mathdisp {w \not \vDash \Diamond p \rightarrow \Box \Diamond p} { . }
(6). Wir arbeiten mit der Kontraposition des Löb-Axioms, also mit
\mathdisp {\Diamond \alpha \rightarrow \Diamond (\alpha \wedge \neg \Diamond \alpha )} { . }
Es sei zunächst vorausgesetzt, dass
\mathl{(M,R)}{} die graphentheoretischen Eigenschaften besitzt. Sei
\mavergleichskette
{\vergleichskette
{w
}
{ \in }{W
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mathdisp {w \vDash \Diamond \alpha} { . }
Dann gibt es eine Welt
\mavergleichskette
{\vergleichskette
{v
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mathl{wRv}{} und mit
\mathdisp {v \vDash \alpha} { . }
Wir betrachten Ketten
\mathl{vRv_2, v_2Rv_3, \ldots}{} mit
\mathl{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
\mathdisp {v_n \vDash \alpha \wedge \neg \Diamond \alpha} { . }
Wegen der Transitivität ist $v_n$ von $w$ aus erreichbar und somit ist
\mathdisp {w \vDash \Diamond (\alpha \wedge \neg \Diamond \alpha)} { . }
Es sei nun vorausgesetzt, dass
\mathl{(M,R)}{} nicht die Eigenschaften erfüllt. Wenn $R$ nicht transitiv ist, so ist nach
Lemma 25.18
in Verbindung mit
Lemma 26.9
die Gültigkeit des Löb-Axioms ausgeschlossen. Es sei also eine unendlich lange Kette der Form
\mathl{w_n R w_{n+1}}{} gegeben. Wir belegen
\mathl{w_n \vDash p}{} für alle
\mavergleichskette
{\vergleichskette
{n
}
{ \in }{\N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mathl{v \vDash \neg p}{} für alle anderen Welten. Dann gilt
\mathdisp {w_0 \vDash \Diamond p \wedge \neg \Diamond ( p \wedge \neg \Diamond p )} { , }
da außerhalb der Kette stets
\mathl{\neg p}{} gilt und innerhalb der Kette stets
\mathl{\Diamond p}{} gilt.
\inputbemerkung
{}
{
Ein Modell des
\definitionsverweis {Löb-Axioms}{}{}
ist insbesondere frei von Schleifen, d.h. es ist reflexivitätsfrei, es gilt also nie
\mathl{w R w}{.} Eine solche Schleife würde ja direkt eine unendliche Kette produzieren. Der gerichtete Graph
\mathdisp {w_n, n \in \N} { , }
mit der durch
\mathl{w_nRw_m}{,} falls
\mavergleichskette
{\vergleichskette
{n
}
{ < }{m
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gegebenen Relation und der Belegung
\mathl{w_n \vDash p}{} für alle
\mavergleichskette
{\vergleichskette
{n
}
{ \in }{ \N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
zeigt, dass das
\definitionsverweis {Löb-Axiom}{}{}
\zusatzklammer {in der Form \mathlk{\Diamond p \rightarrow \Diamond (p \wedge \neg \Diamond p}{}} {} {}
bei einer unendlichen transitiven Kette ohne Schleifen nicht gelten muss.
}
\inputbeispiel{}
{
Wir betrachten für
\mavergleichskette
{\vergleichskette
{n
}
{ \in }{\N_+
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die
\definitionsverweis {modallogische Ausdrucksmenge}{}{,}
die durch
\mavergleichskettedisp
{\vergleichskette
{ \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
\mathl{\alpha_1 \wedge \ldots \wedge \alpha_n}{} mindestens $n$ Punkte. Daher ist
\mavergleichskettedisp
{\vergleichskette
{ \Gamma
}
{ =} { { \left\{ \alpha_n \mid n \in \N_+ \right\} }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
nicht durch einen endlichen gerichteten Graphen erfüllbar. Die Ausdrucksmenge ist aber problemlos durch einen unendlichen gerichteten Graphen erfüllbar: Es seien
\mathbed {W_n} {}
{n \in \N_+} {}
{} {} {} {,}
die unendlich vielen Welten, in $W_n$ gilt
\mathl{p_1 \wedge \ldots \wedge p_{n-1} \wedge \neg p_n}{}
\zusatzklammer {die Wahrheitsbelegung ist ansonsten unerheblich} {} {}
und jede Welt sei von jeder Welt aus erreichbar.
}