Kurs:Einführung in die mathematische Logik (Osnabrück 2016)/Vorlesung 27/latex
\setcounter{section}{27}
\zwischenueberschrift{Maximal widerspruchsfreie modallogische Ausdrucksmengen}
Wir wollen die Vollständigkeit der modallogischen Modelle zeigen, d.h. die Beziehung, dass wenn aus einer modallogischen Ausdrucksmenge $\Gamma$ die Gültigkeit von $\alpha$ folgt, dass dann $\alpha$ bereits aus $\Gamma$ modallogisch ableitbar ist. Die Ausdrucksmenge umfasst dabei stets das System $K$ 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
$K$-\definitionsverweis {Modallogik}{}{}
$\Gamma$ gelten das modallogische
\definitionsverweis {Distributionsaxiom}{}{,}
die aussagenlogischen Tautologien und weitere, für $\Gamma$ spezifische Ausdrücke. Ferner ist $\Gamma$ abgeschlossenen unter dem Modus ponens und der Nezessisierungsregel. In einem modallogischen Modell
\mathl{(M,R,\mu)}{,} das $\Gamma$ erfüllt, gilt $\Gamma$ in jedem Weltpunkt
\mathl{w \in M}{,} also
\mathdisp {(M,R,\mu,w) \vDash \Gamma} { . }
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
\betonung{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 $L$ eine Teilmenge
\mathl{W \subseteq L}{,} die die
$K$-\definitionsverweis {Modallogik}{}{}
umfasst und die unter Modus ponens abgeschlossen ist und keinen
\zusatzklammer {aussagenlogischen} {} {}
Widerspruch enthält. Maximal widerspruchsfrei bedeutet wieder, dass aus jeder echten Erweiterung ein Widerspruch aussagenlogisch ableitbar ist. Zu jeder Welt
\mathl{w \in M}{} in einem beliebigen
\definitionsverweis {modallogischen Modell}{}{}
\mathl{(M,R,\mu)}{} von $K$ ist die Gültigkeitsmenge
\mathl{(M,R,\mu,w)^\vDash}{} eine solche Teilmenge.
\inputfaktbeweis
{Modallogik/K/System/Widerspruchsfrei/Auffüllung/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei $\Gamma$ eine modallogische Ausdrucksmenge, die aussagenlogisch widerspruchsfrei sei.}
\faktfolgerung {Dann gibt es eine maximal widerspruchsfreie Ausdrucksmenge
\mavergleichskette
{\vergleichskette
{\Gamma
}
{ \subseteq }{\tilde{\Gamma}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}}
\faktzusatz {}
\faktzusatz {}
}
{
Dies ist eine rein aussagenlogische Aussage, die im Prinzip aus
Lemma 5.17
folgt. Allerdings ist hier durch die Anwesenheit von $\Box$ 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 $I$ ist auch die modallogische Sprache überhaupt abzählbar. Wir betrachten eine Abzählung
\mathbed {\alpha_n} {}
{n \in \N_+} {}
{} {} {} {,}
der modallogischen Ausdrücken und definieren
\mavergleichskettedisp
{\vergleichskette
{ \Gamma_{n+1}
}
{ =} { \Gamma_n \cup \{ \alpha_{n+1} \}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
falls dies widerspruchsfrei ist, und ansonsten durch
\mavergleichskettedisp
{\vergleichskette
{ \Gamma_{n+1}
}
{ =} { \Gamma_n
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Die Vereinigung $\tilde{\Gamma}$ ist dann maximal widerspruchsfrei.
\zwischenueberschrift{Das universelle modallogische Modell}
In einer jeden Welt in einem modallogischen Modell
\mathl{(M,R,\nu)}{} ist die Gültigkeitsmenge maximal widerspruchsfrei. Für zwei Welten
\mathl{w,v \in M}{} gilt dabei
\mathdisp {\text{Wenn } wRv, \text{ dann } { \left( v \vDash \alpha \Rightarrow w \vDash \Diamond \alpha \right) }} { . }
Die rechte Seite kann man also als eine notwendige Bedingung dafür ansehen, dass $v$ von $w$ aus erreichbar ist. Im universellen modallogischen Modell definiert man die Erreichbarkeitsrelation durch diese notwendige Bedingung.
\inputkonstruktion{}
{
Es sei
\mathbed {p_i} {}
{i \in I} {}
{} {} {} {,}
eine Menge von
\definitionsverweis {Aussagenvariablen}{}{}
und $L$ die zugehörige
\definitionsverweis {modallogische Sprache}{}{.}
Es sei $U$ die Menge aller $K$ umfassenden,
\zusatzklammer {aussagenlogisch} {} {}
maximal widerspruchsfreien Teilmengen
\mavergleichskettedisp
{\vergleichskette
{W
}
{ \subseteq} {L
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Auf $U$ definieren wir eine Erreichbarkeitsrelation $R$ durch
\mathdisp {WRV \text { genau dann, wenn für jedes } \alpha \in L \text { mit } \alpha \in V \text{ die Beziehung } \Diamond \alpha \in W \text{ gilt}} { . }
Wir nennen $U$ versehen mit dieser Relation und der durch
\mathl{W \vdash p}{,} wenn
\mavergleichskette
{\vergleichskette
{p
}
{ \in }{W
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
festgelegten Belegung $\nu$ das \stichwort {universelle modallogische Modell} {.}
}
Wir identifizieren also Welten mit der Menge der in ihnen gültigen modallogischen Aussagen.
Wenn $R$ eine Erreichbarkeitsrelation sein soll, so muss diese Beziehung gelten. Die rechte Seite ist dabei eine Implikation, keine Äquivalenz; es wird nicht gefordert, dass aus
\mathl{\Diamond \alpha \in W}{} auch
\mathl{\alpha \in V}{} folgt.
\inputkonstruktion{}
{
Es sei
\mathbed {p_i} {}
{i \in I} {}
{} {} {} {,}
eine Menge von
\definitionsverweis {Aussagenvariablen}{}{}
und $L$ die zugehörige
\definitionsverweis {modallogische Sprache}{}{.}
Es sei
\mavergleichskette
{\vergleichskette
{\Gamma
}
{ \subseteq }{L
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine
$K$-\definitionsverweis {modallogische}{}{}
Ausdrucksmenge. Es sei $U_\Gamma$ die Menge aller $\Gamma$ umfassenden,
\zusatzklammer {aussagenlogisch} {} {}
maximal widerspruchsfreien Teilmengen
\mavergleichskettedisp
{\vergleichskette
{W
}
{ \subseteq} {L
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Auf $U_\Gamma$ definieren wir eine Erreichbarkeitsrelation $R$ durch
\mathdisp {WRV \text { genau dann, wenn für jedes } \alpha \in L \text { mit } \alpha \in V \text{ die Beziehung } \Diamond \alpha \in W \text{ gilt}} { . }
Wir nennen $U_\Gamma$ versehen mit dieser Relation und der durch
\mathl{W \vdash p}{,} wenn
\mavergleichskette
{\vergleichskette
{p
}
{ \in }{W
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
festgelegten Belegung $\nu$ das $\Gamma$-\stichwort {universelle modallogische Modell} {.}
}
Die Relation und die Belegung im $\Gamma$-universellen modallogischen Modell stimmen mit dem universellen Modell überein, es hndelt sich also um einen Teilgraphen. Es ist unser Ziel zu zeigen, dass im $\Gamma$-universellen modallogischen Modell
\mathl{(U,R,\mu,W)}{} genau die Ausdrücke aus $W$ gelten.
\inputfaktbeweis
{Modallogik/Ableitung/Notwendigkeitsversion/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei $\Gamma$ ein
$K$-\definitionsverweis {modallogisches System}{}{}
und $\alpha$ ein modallogischer Ausdruck.}
\faktfolgerung {Dann folgt aus
\mathdisp {\Gamma \vdash \alpha} { }
die Beziehung
\mathdisp {\Box \Gamma \vdash \Box \alpha} { , }
wobei
\mavergleichskettedisp
{\vergleichskette
{\Box \Gamma
}
{ =} { { \left\{ \Box \beta \mid \beta \in \Gamma \right\} }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}}
\faktzusatz {}
\faktzusatz {}
}
{
Die Ableitbarkeit bedeutet, dass es Ausdrücke
\mavergleichskette
{\vergleichskette
{ \beta_1 , \ldots , \beta_n
}
{ \in }{ \Gamma
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mathdisp {\vdash \beta_1 \wedge \ldots \wedge \beta_n \rightarrow \alpha} { }
gibt. Nach
Lemma 24.5 (1)
ist
\mathdisp {\vdash \Box(\beta_1 \wedge \ldots \wedge \beta_n ) \rightarrow \Box \alpha} { . }
Aus
Lemma 24.5 (4)
folgt durch Induktion sofort
\mathdisp {\vdash \Box \beta_1 \wedge \ldots \wedge \Box \beta_n \rightarrow \Box( \beta_1 \wedge \ldots \wedge \beta_n )} { }
und somit mit dem Kettenschluss
\mathdisp {\vdash \Box \beta_1 \wedge \ldots \wedge \Box \beta_n \rightarrow \Box \alpha} { . }
Dies bedeutet
\mathdisp {\Box \beta_1 , \ldots , \Box \beta_n \vdash \Box \alpha} { . }
\inputfaktbeweis
{Modallogik/Möglichkeitsaussage/Weltrealisierung/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei
\mathbed {p_i} {}
{i \in I} {}
{} {} {} {,}
eine Menge von
\definitionsverweis {Aussagenvariablen}{}{}
und $L$ die zugehörige
\definitionsverweis {modallogische Sprache}{}{.}}
\faktvoraussetzung {Es sei
\mavergleichskette
{\vergleichskette
{\Gamma
}
{ \subseteq }{L
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein
$K$-\definitionsverweis {modallogisches System}{}{,}
es sei
\mavergleichskette
{\vergleichskette
{W
}
{ \subseteq }{L
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine maximal widerspruchsfreie $\Gamma$-Teilmenge und es sei
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ \in }{L
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein modallogischer Ausdruck mit
\mavergleichskette
{\vergleichskette
{ \Diamond \alpha
}
{ \in }{ W
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}}
\faktfolgerung {Dann gibt es eine maximal widerspruchsfreie $\Gamma$-Teilmenge
\mavergleichskette
{\vergleichskette
{V
}
{ \subseteq }{L
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mavergleichskette
{\vergleichskette
{\alpha
}
{ \in }{V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und mit
\mathl{WRV}{} im Sinne des
$\Gamma$-\definitionsverweis {universellen modallogischen Modells}{}{.}}
\faktzusatz {}
\faktzusatz {}
}
{
Wir betrachten die Menge
\mavergleichskettedisp
{\vergleichskette
{ V'
}
{ =} { { \left\{ \beta \mid \Box \beta \in W \right\} } \cup \{ \alpha \}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
die $\Gamma$ umfasst, da $\Gamma$ unter der Nezessisierungsregel abgeschlossen ist. Wir behaupten, dass diese Menge widerspruchsfrei ist. Andernfalls würde es endliche viele
\mathl{\beta_1 , \ldots , \beta_n}{} mit
\mavergleichskette
{\vergleichskette
{ \Box \beta_i
}
{ \in }{ W
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
geben mit
\mathdisp {\vdash \beta_1 \wedge \ldots \wedge \beta_n \rightarrow (\alpha \rightarrow (p \wedge \neg p))} { . }
Dies schreiben wir als
\mathdisp {\vdash \beta_1 \wedge \ldots \wedge \beta_n \rightarrow ( \neg( p \wedge \neg p) \rightarrow \neg \alpha)} { . }
Nach
Lemma 27.4
ist dann auch
\mathdisp {\vdash \Box \beta_1 \wedge \ldots \wedge \Box \beta_n \rightarrow \Box ( \neg (p \wedge \neg p) \rightarrow \neg \alpha)} { . }
Wegen des $K$-Axioms ist
\mathdisp {\vdash \Box ( \neg (p \wedge \neg p) \rightarrow \neg \alpha) \rightarrow ( \Box \neg (p \wedge \neg p) \rightarrow \Box \neg \alpha)} { }
und somit
\mathdisp {\vdash \Box \beta_1 \wedge \ldots \wedge \Box \beta_n \rightarrow (\Box (p \vee \neg p) \rightarrow \Box \neg \alpha )} { . }
Da der Vordersatz zu $W$ gehört, und $W$ abgeschlossen unter Implikationen ist, ist auch
\mathdisp {\Box (p \vee \neg p) \rightarrow \Box \neg \alpha \in W} { . }
Da
\mathl{p \vee \neg p}{} eine Tautologie ist und wegen der Nezessisierungsregel
\zusatzklammer {die ja für Tautologien gilt} {} {}
ergibt sich
\mavergleichskettedisp
{\vergleichskette
{ \Box \neg \alpha
}
{ \in} { W
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
was ein Widerspruch zu
\mavergleichskette
{\vergleichskette
{ \Diamond \alpha
}
{ \in }{ W
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
angesichts der Widerspruchsfreiheit von $W$ ist.
Somit ist $V'$ widerspruchsfrei. Sei
\mavergleichskette
{\vergleichskette
{V'
}
{ \subseteq }{V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine maximal widerspruchsfreie Teilmenge von $L$, die es nach
Lemma 27.1
gibt. Es sei
\mavergleichskette
{\vergleichskette
{ \beta
}
{ \in }{ V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Dann ist
\mavergleichskette
{\vergleichskette
{ \Diamond \beta
}
{ \in }{ W
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Andernfalls wäre nämlich wegen der Maximalität
\zusatzklammer {von $W$} {} {}
\mavergleichskette
{\vergleichskette
{\Box \neg \beta
}
{ \in }{W
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
doch dann wäre
\mavergleichskette
{\vergleichskette
{ \neg \beta
}
{ \in }{ V'
}
{ \subseteq }{V
}
{ }{
}
{ }{
}
}
{}{}{.}
Es gilt also
\mathl{WRV}{.}
\inputfaktbeweis
{Modallogik/System/Universelles Modell/Semantische Äquivalenz/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei $\Gamma$ ein
$K$-\definitionsverweis {modallogisches System}{}{.}
Dann gilt im
$\Gamma$-\definitionsverweis {universellen modallogischen Modell}{}{}
für jede Welt und jeden
\definitionsverweis {modallogischen Ausdruck}{}{}
$\alpha$}
\faktfolgerung {die Beziehung
\mathdisp {W \vDash \alpha \text{ genau dann, wenn } \alpha \in W} { . }
}
\faktzusatz {}
\faktzusatz {}
}
{
Wir führen Induktion über den Aufbau der modallogischen Sprache, und zwar gleichzeitig für alle Welten. Für
\definitionsverweis {Aussagenvariablen}{}{}
gilt die Behauptung unmittelbar aufgrund der festgelegten Belegung. Die Äquivalenz ist auch unter aussagenlogischen Konstruktionen abgeschlossen, da die $W$ unter $K$-Ableitungen abgeschlossen sind. Es bleibt noch zu zeigen, dass sich die Äquivalenz bei modallogischen Operationen erhält, wobei wir mit dem Möglichkeitsoperator $\Diamond$ arbeiten. Es sei also
\mathl{\Diamond \alpha}{} gegeben, wobei die Äquivalenz für $\alpha$ und für alle Welten gelte. Wenn
\mathl{W \vDash \Diamond \alpha}{} gilt, so gibt es eine Welt
\mavergleichskette
{\vergleichskette
{V
}
{ \in }{ U_\Gamma
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mathl{WRV}{} und
\mathl{V \vDash \alpha}{.} Aufgrund der Induktionsvoraussetzung gilt
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ \in }{ V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Wegen der Definition der Erreichbarkeitsrelation bedeutet dies insbesondere
\mavergleichskette
{\vergleichskette
{ \Diamond \alpha
}
{ \in }{ W
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Es sei umgekehrt
\mavergleichskette
{\vergleichskette
{ \Diamond \alpha
}
{ \in }{ W
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Dann folgt aus
Lemma 27.5
die Existenz einer von $W$ aus erreichbaren $\Gamma$-Welt $V$ mit
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ \in }{V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
also nach Induktionsvoraussetzung
\mathl{V \vDash \alpha}{} und somit
\mathl{W \vDash \Diamond \alpha}{.}
\zwischenueberschrift{Die Vollständigkeit der Modallogik}
\inputfaktbeweis
{K-Modallogik/Vollständigkeit/Fakt}
{Satz}
{}
{
\faktsituation {Es sei $\Gamma$ ein
$K$-\definitionsverweis {modallogisches System}{}{}
und sei $\alpha$ ein modallogischer Ausdruck.}
\faktfolgerung {Dann ist
\mathdisp {\Gamma \vdash \alpha} { }
genau dann, wenn
\mathdisp {\Gamma \vDash \alpha} { . }
}
\faktzusatz {}
\faktzusatz {}
}
{
Die Hinrichtung ergibt sich aus
Lemma 26.9.
Für die Rückrichtung nehmen wir
\mathdisp {\Gamma \not \vdash \alpha} { }
an. Dann ist
\mavergleichskettedisp
{\vergleichskette
{ \Gamma'
}
{ =} { \Gamma \cup \{ \neg \alpha \}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
\zusatzklammer {aussagenlogisch} {} {}
nicht widersprüchlich und wir müssen zeigen, dass $\Gamma'$ durch ein $\Gamma$-modallogisches Modell erfüllbar ist. Wir betrachten dazu das
$\Gamma$-\definitionsverweis {universelle modallogische Modell}{}{}
$(U_\Gamma,R,\nu)$, in dem $\Gamma$
\zusatzklammer {in jedem Weltpunkt} {} {}
gilt. Nach
Lemma 27.1
gibt es eine maximal widerspruchsfreie $\Gamma'$-Ausdrucksmenge $\tilde{\Gamma}$, die wir als Welt
\mavergleichskette
{\vergleichskette
{W
}
{ = }{ \tilde{\Gamma}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
in $U_\Gamma$ betrachten können. Nach
Lemma 27.6
gilt
\mathl{W \vDash \tilde{\Gamma}}{,} was insbesondere die Gültigkeit von
\mathl{\Gamma \cup \{ \neg \alpha\}}{} in $W$ zeigt.
\inputbemerkung
{}
{
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.
}