Kurs:Einführung in die mathematische Logik (Osnabrück 2016)/Vorlesung 25/latex
\setcounter{section}{25}
\zwischenueberschrift{Weitere Axiomenschemata}
\inputdefinition
{}
{
Das
\definitionsverweis {modallogische Axiomenschema}{}{}
\mathdisp {\Box \alpha \rightarrow \alpha} { }
nennt man
\definitionswort {Reflexivitätsaxiom}{.}
} Durch das Reflexivitätsaxiom wird die eigene Welt bei Möglichkeitsüberlegungen mitberücksichtigt.
\inputdefinition
{}
{
Das
\definitionsverweis {modallogische Axiomenschema}{}{}
\mathdisp {\alpha \rightarrow \Box \alpha} { }
nennt man
\definitionswort {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.
\inputdefinition
{}
{
Das
\definitionsverweis {modallogische Axiomenschema}{}{}
\mathdisp {\alpha \leftrightarrow \Box \alpha} { }
nennt man
\definitionswort {Fatalismusaxiom}{.}
}
In diesem Fall gilt auch
\mathdisp {\alpha \leftrightarrow \Diamond \alpha} { }
und damit auch
\mathdisp {\Box \alpha \leftrightarrow \Diamond \alpha} { . }
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.
\inputdefinition
{}
{
Das
\definitionsverweis {modallogische Axiomenschema}{}{}
\mathdisp {\alpha \rightarrow \Box \Diamond \alpha} { }
nennt man
\definitionswort {Symmetrieaxiom}{.}
}
\inputdefinition
{}
{
Das
\definitionsverweis {modallogische Axiomenschema}{}{}
\mathdisp {\Box \alpha \rightarrow \Box \Box \alpha} { }
nennt man
\definitionswort {Transitivitätsaxiom}{.}
}
\inputdefinition
{}
{
Das
\definitionsverweis {modallogische Axiomenschema}{}{}
\mathdisp {\Diamond \alpha \rightarrow \Box \Diamond \alpha} { }
nennt man
\definitionswort {euklidisches Axiom}{}
\zusatzklammer {oder Axiom $5$} {} {.}
}
\inputfaktbeweis
{Modallogik/K/Symmetrisch und euklidisch/Transitiv/Fakt}
{Lemma}
{}
{
\faktsituation {In einem modallogischen
$K$-\definitionsverweis {System}{}{,}}
\faktvoraussetzung {in dem das
\definitionsverweis {Symmetrieaxiom}{}{}
und das
\definitionsverweis {euklidische Axiom}{}{}
gelten,}
\faktfolgerung {gilt auch das
\definitionsverweis {Transitivitätsaxiom}{}{.}}
\faktzusatz {}
\faktzusatz {}
}
{
Es sei $S$ das in Frage stehende System. Eine spezielle Instanz des Symmetrieaxioms liefert
\mathdisp {S \vdash \Box \alpha \rightarrow \Box \Diamond \Box \alpha} { . }
Eine Umformulierung des euklidischen Axioms ist
\mathdisp {S \vdash \Diamond \Box \alpha \rightarrow \Box \alpha} { . }
Mit
Lemma 24.5 (1)
folgt daraus
\mathdisp {S \vdash \Box \Diamond \Box \alpha \rightarrow \Box \Box \alpha} { }
und insgesamt mit dem Kettenschluss
\mathdisp {S \vdash \Box \alpha \rightarrow \Box \Box \alpha} { . }
\zwischenueberschrift{Paradoxe Axiome}
Einen modallogischen Ausdruck nennen wir \stichwort {paradox} {,} wenn er, wenn man alle darin auftretenden $\Box$ \zusatzklammer {und somit auch alle $\Diamond$} {} {} weglässt, einen aussagenlogischen Widerspruch ergibt. Ein modallogisches Axiomenschema heißt paradox, wenn es davon eine paradoxe Instanz gibt.
\inputdefinition
{}
{
Das
\definitionsverweis {modallogische Axiomenschema}{}{}
\mathdisp {\Box \alpha \leftrightarrow \neg \alpha} { }
nennt man
\definitionswort {Antiaxiom}{.}
}
Wenn das Antiaxiom gilt, so ist auch
\mathdisp {\Diamond \alpha \leftrightarrow \neg \Box \neg \alpha \leftrightarrow \neg \neg \neg \alpha \leftrightarrow \neg \alpha \leftrightarrow \Box \alpha} { , }
das Antiaxiom ist also ideologisch. In einer
$K$-\definitionsverweis {Modallogik}{}{}
führt das Antiaxiom zu einem Widerspruch, da ja dann zu einer aussagenlogischen Tautologie $\alpha$ wegen der Nezessisierungsregel auch $\Box \alpha$ und somit der Widerspruch $\neg \alpha$ gilt. Wenn man dagegen das Antiaxiom auf Aussagenvariablen beschränkt, also
\mathdisp {\Box p \leftrightarrow \neg p} { }
betrachtet, so ergibt sich ein sinnvolles $K$-System.
\inputdefinition
{}
{
Das
\definitionsverweis {modallogische Axiomenschema}{}{}
\mathdisp {\Box (\Box \alpha \rightarrow \alpha ) \rightarrow \Box \alpha} { }
nennt man
\definitionswort {Löb-Axiom}{.}
}
\inputbemerkung
{}
{
Für das
\definitionsverweis {Ableitungsprädikat}{}{}
\mavergleichskettedisp
{\vergleichskette
{ \alpha(y)
}
{ =} { \exists x ( \delta_\Gamma(x,y))
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
zu einer die Peano-Arithmetik umfassenden entscheidbaren Satzmenge $\Gamma$ gilt neben den in
Bemerkung 23.7
angeführten Eigenschaften auch der Satz von Löb, nämlich
\mathdisp {\alpha (GN ( \alpha (GN (s )) \rightarrow s ) ) \rightarrow \alpha (GN (s ) )} { . }
Wenn man
\mavergleichskettedisp
{\vergleichskette
{\Box s
}
{ =} { \alpha (GN(s))
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
setzt, so kann man dies als
\mathdisp {\Box ( \Box s \rightarrow s ) \rightarrow \Box s} { }
schreiben, es liegt also genau das
\definitionsverweis {Löb-Axiom}{}{}
vor
\zusatzklammer {daher der Name des Axioms} {} {.}
Unter der modallogischen \stichwort {Beweisbarkeitslogik} {} versteht man die
$K$-\definitionsverweis {Modallogik}{}{,}
die durch das Löb-Axiom gegeben ist
\zusatzklammer {das Transitivitätsaxiom lässt sich daraus ableiten, siehe
Lemma 25.18} {} {.}
Es handelt sich um eine paradoxe Modallogik, in der man die Unvollständigkeit nachbbilden kann.
}
Es sei
\mavergleichskette
{\vergleichskette
{ \bot
}
{ = }{ p \wedge \neg p
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
\zusatzklammer {gesprochen Falsum} {} {}
eine Abkürzung für einen Widerspruch. Im Kontext der Beweisbarkeitslogik bedeutet dann
\mathl{\neg \Box \bot}{} die Nichtableitbarkeit eines Widerspruchs, also die Widerspruchsfreiheit des Systems.
Aus dem Löb-Axiom
\zusatzklammer {also der $K$-Modallogik $L$, die durch das Löbaxiom gegeben ist} {} {}
lässt sich ableiten, dass diese Widerspruchsfreiheit ein Fixpunkt der Nichtableitbarkeit ist, d.h. es gilt
\mathdisp {L \vdash \neg \Box \neg \Box \bot \leftrightarrow \neg \Box \bot} { , }
siehe
Aufgabe 25.6.
Dies bedeutet insbesondere, dass weder
\mathkor {} {\Box \bot} {noch} {\neg \Box \bot} {}
aus $L$ ableitbar ist
\zusatzklammer {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
\zusatzklammer {die Hauptarbeit liegt aber darin, zu zeigen, dass das arithmetische Ableitungsprädikat das Löb-Axiom erfüllt} {} {.}
\zwischenueberschrift{Einige klassische modallogische Systeme}
\inputdefinition
{}
{
Das modallogische $K$-\definitionsverweis {System}{}{,} in dem das \definitionsverweis {Möglichkeitsaxiom}{}{} gilt, heißt \definitionswortpraemath {D}{ System }{.}
}
\inputdefinition
{}
{
Das modallogische $K$-\definitionsverweis {System}{}{,} in dem das \definitionsverweis {Reflexivitätsaxiom}{}{} gilt, heißt \definitionswortpraemath {T}{ System }{.}
}
\inputfaktbeweis
{K-Modallogik/T-System/Folgerungen/Fakt}
{Lemma}
{}
{
\faktsituation {Im modallogischen
$T$-\definitionsverweis {System}{}{}
gelten die folgenden Aussagen.}
\faktfolgerung {Es ist
\mathdisp {T \vdash \alpha \rightarrow \Diamond \alpha} { . }
Insbesondere ist
\mathdisp {T \vdash \Box \alpha \rightarrow \Diamond \alpha} { }
und damit ist ein $T$-System auch ein
$D$-\definitionsverweis {System}{}{.}}
\faktzusatz {}
\faktzusatz {}
}
{
Die Kontraposition des Reflexivitätsaxioms ergibt direkt
\mathdisp {T \vdash \neg \alpha \rightarrow \neg \Box \alpha} { , }
also
\mathdisp {T \vdash \neg \alpha \rightarrow \Diamond \neg \alpha} { . }
Da dies für alle $\alpha$ gilt, gilt nach
Lemma 24.5 (5)
auch
\mathdisp {T \vdash \alpha \rightarrow \Diamond \alpha} { . }
Der Zusatz folgt aus
\mathdisp {T \vdash \Box \alpha \rightarrow \alpha \text{ und } T \vdash \alpha \rightarrow \Diamond \alpha} { . }
\inputdefinition
{}
{
Das modallogische $K$-\definitionsverweis {System}{}{,} in dem das \definitionsverweis {Reflexivitätsaxiom}{}{} und das \definitionsverweis {Symmetrieaxiom}{}{} gilt, heißt \definitionswortpraemath {B}{ System }{.}
}
\inputdefinition
{}
{
Das modallogische $K$-\definitionsverweis {System}{}{,} in dem das \definitionsverweis {Reflexivitätsaxiom}{}{} und das \definitionsverweis {Transitivitätsaxiom}{}{} gilt, heißt \definitionswortpraemath {S4}{ System }{.}
}
\inputdefinition
{}
{
Das modallogische $K$-\definitionsverweis {System}{}{,} in dem das \definitionsverweis {Reflexivitätsaxiom}{}{,} das \definitionsverweis {Symmetrieaxiom}{}{} und das \definitionsverweis {Transitivitätsaxiom}{}{} gilt, heißt \definitionswortpraemath {S5}{ System }{.}
}
\inputfaktbeweis
{K-Modallogik/S5/Charakterisierungen/Fakt}
{Lemma}
{}
{
\faktsituation {Für ein modallogisches
$K$-\definitionsverweis {System}{}{}
$S$}
\faktuebergang {sind folgende Aussagen äquivalent.}
\faktfolgerung {\aufzaehlungdrei{Es gilt das
\definitionsverweis {Reflexivitätsaxiom}{}{}
und das
\definitionsverweis {euklidische Axiom}{}{}
}{Es gilt das
\definitionsverweis {Möglichkeitsaxiom}{}{,}
das
\definitionsverweis {Symmetrieaxiom}{}{}
und das
\definitionsverweis {Transitivitätsaxiom}{}{}
}{Es handelt sich um das
$S5$-\definitionsverweis {System}{}{.}
}}
\faktzusatz {}
\faktzusatz {}
}
{
Aus (1) folgt (2). Es sei $\Gamma_1$ 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
\mathdisp {\Gamma_1 \vdash \alpha \rightarrow \Diamond \alpha} { }
und mit dem euklidischen Axiom gilt
\mathdisp {\Gamma_1 \vdash \Diamond \alpha \rightarrow \Box \Diamond \alpha} { , }
was mit dem Kettenschluss
\mathdisp {\Gamma_1 \vdash \alpha \rightarrow \Box \Diamond \alpha} { , }
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). Es sei $\Gamma_2$ die Vereinigung aus dem Möglichkeitsaxiom, dem Symmetrieaxiom und dem Transitivitätsaxiom. Das Symmetrieaxiom ergibt
\mathdisp {\Gamma_2 \vdash \alpha \rightarrow \Box \Diamond \alpha} { , }
das Möglichkeitsaxiom liefert
\mathdisp {\Gamma_2 \vdash \Box \Diamond \alpha \rightarrow \Diamond \Diamond \alpha} { }
und das Transitivitätsaxiom liefert
\mathdisp {\Gamma_2 \vdash \Diamond \Diamond \alpha \rightarrow \Diamond \alpha} { . }
Der Kettenschluss darauf angewendet liefert
\mathdisp {\Gamma_2 \vdash \alpha \rightarrow \Diamond \alpha} { , }
also das Reflexivitätsaxiom.
Aus (3) folgt (1). Aus dem Transitivitätsaxiom
\mathdisp {S_5 \vdash \Box \alpha \rightarrow \Box \Box \alpha} { }
ergibt sich mit
Lemma 24.5 (2)
\mathdisp {S_5 \vdash \Diamond \Box \alpha \rightarrow \Diamond \Box \Box \alpha} { . }
Aufgrund des Symmetrieaxioms gilt
\mathdisp {S_5 \vdash \Diamond \Box \beta \rightarrow \beta} { . }
Angewendet auf
\mavergleichskette
{\vergleichskette
{ \beta
}
{ = }{ \Box \alpha
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ergibt dies
\mathdisp {S_5 \vdash \Diamond \Box \alpha \rightarrow \Box \alpha} { . }
Dies ist gleichwertig zum euklidischen Axiom.
\inputfaktbeweis
{K-Modallogik/Beweisbarkeitslogik/Transitiv/Fakt}
{Lemma}
{}
{
\faktsituation {In einem modallogischen
$K$-\definitionsverweis {System}{}{,}}
\faktvoraussetzung {in dem das
\definitionsverweis {Löb-Axiom}{}{}
gilt,}
\faktfolgerung {gilt auch das
\definitionsverweis {Transitivitätsaxiom}{}{.}}
\faktzusatz {}
\faktzusatz {}
}
{
Wir wenden das Löb-Axiom auf den Ausdruck
\mathl{\Box \alpha \wedge \alpha}{} an und erhalten
\zusatzklammer {$L$ steht für dieses modallogische System} {} {}
\mathdisp {L \vdash \Box( \Box (\Box \alpha \wedge \alpha ) \rightarrow (\Box \alpha \wedge \alpha ) ) \rightarrow \Box( \Box \alpha \wedge \alpha )} { . }
Wegen
Lemma 24.5 (3)
ist
\mathdisp {\vdash \Box ( \Box \alpha \wedge \alpha ) \rightarrow \Box \Box \alpha} { }
und
\mathdisp {\vdash \Box ( \Box \alpha \wedge \alpha ) \rightarrow \Box \alpha} { . }
Wegen der zuletzt angeführten Ableitung erhält man
\mathdisp {\vdash \alpha \rightarrow ( \Box ( \Box \alpha \wedge \alpha ) \rightarrow (\Box \alpha \wedge \alpha))} { }
und daraus mit
Lemma 24.5 (1)
auch
\mathdisp {\vdash \Box \alpha \rightarrow \Box ( ( \Box ( \Box \alpha \wedge \alpha ) \rightarrow (\Box \alpha \wedge \alpha)))} { . }
Ein zweifacher Kettenschluss liefert
\mathdisp {L \vdash \Box \alpha \rightarrow \Box \Box \alpha} { . }
\zwischenueberschrift{Gerichtete Graphen}
Für die Modelltheorie der Modallogik benötigen wir gerichtete Graphen. Dies ist mathematisch betrachtet einfach eine zweistellige Relation auf einer Menge.
\inputdefinition
{}
{
Ein
\definitionswort {gerichteter Graph}{}
ist eine Menge $M$ versehen mit einer fixierten
\definitionsverweis {Relation}{}{}
\mavergleichskette
{\vergleichskette
{R
}
{ \subseteq }{ M \times M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}
Die Menge der Punkte
\mavergleichskette
{\vergleichskette
{x
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
nennt man auch die Knoten des Graphen und man sagt, dass ein Pfeil von $x$ nach $y$ geht, wenn
\mavergleichskette
{\vergleichskette
{(x,y)
}
{ \in }{R
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist. In dieser Weise werden gerichtete Graphen veranschaulicht. Ein Pfeil von einem Knoten zu sich selbst heißt \stichwort {Schleife} {.}
Im Kontext von Ordnungsrelationen und Äquivalenzrelationen haben wir schon die Eigenschaften reflexiv, symmetrisch, transitiv kennengelernt. Einen symmetrischen gerichteten Graphen nennt man auch einen \stichwort {ungerichteten Graphen} {.} In diesem Fall nennt man einen verbindenden Pfeil eine Kante. Wir besprechen einige weitere Begrifflichkeiten und Eigenschaften.
\inputdefinition
{}
{
Es sei
\mathl{(M,R)}{} ein
\definitionsverweis {gerichteter Graph}{}{.}
Zu einer Teilmenge
\mavergleichskette
{\vergleichskette
{T
}
{ \subseteq }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
nennt man
\mavergleichskettedisp
{\vergleichskette
{ \operatorname{Vorg} { \left( T \right) }
}
{ =} { { \left\{ x \in M \mid \text{ es gibt } y \in T \text{ mit } xRy \right\} }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
die
\definitionswort {Vorgängermenge}{}
zu $T$.
}
\inputdefinition
{}
{
Es sei
\mathl{(M,R)}{} ein
\definitionsverweis {gerichteter Graph}{}{.}
Zu einer Teilmenge
\mavergleichskette
{\vergleichskette
{T
}
{ \subseteq }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
nennt man
\mavergleichskettedisp
{\vergleichskette
{ \operatorname{Nachf} { \left( T \right) }
}
{ =} { { \left\{ z \in M \mid \text{ es gibt } y \in T \text{ mit } yRz \right\} }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
die
\definitionswort {Nachfolgermenge}{}
zu $T$.
}
Ein Knoten ohne Nachfolger, also ohne abgehenden Pfeil \zusatzklammer {also auch keine Schleife} {} {,} heißt \stichwort {Sackgasse} {.}
\inputdefinition
{}
{
Eine
\definitionsverweis {Relation}{}{}
auf einer Menge $M$ heißt
\definitionswort {euklidisch}{,}
wenn zu
\mavergleichskette
{\vergleichskette
{x,y,z
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mathl{xRy}{} und
\mathl{xRz}{} stets
\mathl{yRz}{} gilt.
}