next up previous contents search
Next: 2.8 Dualitätstheoreme Up: 2. Aussagenlogik Previous: 2.6 Ableitbarkeit

2.7 Widerspruchsfreiheit, Vollständigkeit und Nichtableitbarkeit

Unterabschnitte

2.7.1 Widerspruchsfreiheit

Widerspruchsfreiheit im Sinne des Wortes besteht dann, wenn in der gegebenen Menge von Aussagen ,,kein Widerspruch steckt``, d.h. aus ihr kein Widerspruch bewiesen bzw. gefolgert werden kann. Für den Aussagenkalkül wird dies durch HILBERTs Definition der klassischen Widerspruchsfreiheit (bzgl. des Ableitens $\ab$) gefaßt. Man kann schärfer die semantische Widerspruchsfreiheit mit der Forderung definieren, daß alles was beweisbar ist, auch wahr ist oder schwächer, daß nicht alles beweisbar sein darf (syntaktische Widerspruchsfreiheit).

Definition 2.7.1 (Widerspruchsfreiheit)

1.
(GÖDEL)
$X \subseteq \ausd$ heißt semantisch widerspruchsfrei genau dann, wenn $\ab\left(X\right)\subseteq \ag$
2.
(HILBERT)
X heißt klassisch widerspruchsfrei genau dann, wenn es keinen Ausdruck $H \in \ausd$ mit $H \in \ab\left(X\right)$ und $\neg H \in \ab\left(X\right)$ gibt.
3.
(POST)
X heißt syntaktisch widerspruchsfrei genau dann, wenn $\ab\left(X\right) \not= \ausd$.

Satz 2.7.2
 

1.
Wenn X semantisch widerspruchsfrei, so ist X klassisch widerspruchsfrei.
2.
 Wenn X klassisch widerspruchsfrei, so X syntaktisch widerspruchsfrei.
3.
Die Umkehrungen gelten nicht.

Beweis
der einzelnen Aussagen des Satzes

1.
weil niemals H und $\neg H$ zugleich allgemeingültig
2.
p, $\neg p$ sind nicht beide ableitbar, also $\ab\left(X\right) \not= \ausd$.
3.
$X_1 = \left\{\neg\left(p\rightarrow p\right)\right\} \not\subseteq \ag$. X1 nicht semantisch widerspruchsfrei.

$\ab\left(X_1\right) = \left\{\neg \left(H \rightarrow H\right) \vert H \in \ausd\right\}$klassisch widerspruchsfrei.

$X_2 = \left\{p \rightarrow p, \neg\left(p\rightarrow p\right)\right\}$ nicht klassisch widerspruchsfrei

Behauptung: $p \notin \ab\left(X_2\right)$. d.h. X2 syntaktisch widerspruchsfrei.

Beweis später (siehe unten), nicht ableitbar.

\qed

Satz 2.7.3 (Endlichkeitssatz für Widerspruchsfreiheit)
Die semantische/klassische/syntaktische Widerspruchsfreiheit hat finiten Charakter, d.h. eine Menge X ist genau dann semantisch bzw. klassisch bzw. syntaktisch widerspruchsfrei, wenn jede endliche Teilmenge $X^\ast \subseteq X$ diese Eigenschaft hat.

Beweis
Wir zeigen zuerst: Wenn X die Eigenschaft hat, dann auch jede endliche Teilmenge $X^\ast \subseteq X$.

semantisch:

\begin{displaymath}\mbox{ Wegen }X^\ast\subseteq X\mbox{ ist }\ab\left(X^\ast\right)
\subseteq \ab\left(X\right) \subseteq \ag
\end{displaymath}

klassisch:

Wenn $X^\ast$ nicht klassisch widerspruchsfrei ist, dann gibt es ein $H \in \ausd$ mit $H,\neg H\in\ab(X^\ast)\subseteq\ab(X)$, also ist X nicht klassisch widerspruchsfrei.

syntaktisch:

\begin{displaymath}\mbox{Wegen }X^\ast\subseteq X\mbox{ ist }\ab\left(X^\ast\right)
\subseteq \ab\left(X\right)\subset\ausd
\end{displaymath}

Jetzt setzen wir voraus, daß jede endliche Teilmenge $X^\ast \subseteq X$die Eigenschaft hat und zeigen, daß auch X die Eigenschaft hat.

semantisch:

Für $\ab(X)\subseteq\ag$ genügt es zu zeigen, daß $X \subseteq \ag$ ist. Sei $H \in X$, dann ist $\{H\}\subseteq X$, also $\ab\left(\{H\}\right)
\subseteq\ag$, folglich $H \in \ag$ (wegen $H\in\ab\left(\{H\}\right)$), also ist $X \subseteq \ag$, was zu zeigen war.

klassisch:
indirekt
Nehmen wir an, daß ein $H \in \ausd$ mit

\begin{displaymath}H,\neg H\in \ab\left(X\right)
\end{displaymath}

existiert, d.h. X ist nicht klassisch widerspruchsfrei.

Nach dem Endlichkeitssatz für das Ableiten existieren endliche $X_1^\ast, X_2^\ast \subseteq X$ mit

\begin{eqnarray*}H\in \ab\left(X_1^\ast\right) &\mbox{und}& \neg H\in \ab\left(X_2^\ast\right)
\end{eqnarray*}


Dann ist $X_1^\ast\cup X_2^\ast$ endliche Teilmenge von X und

\begin{displaymath}H, \neg H \in \ab\left(X_1^\ast \cup X_2^\ast\right).
\end{displaymath}

im Widerspruch dazu, daß jede endliche Teilmenge von X klassisch widerspruchsfrei ist.

syntaktisch:
indirekt
Nehmen wir an, daß X nicht syntaktisch widerspruchsfrei ist: $\ab\left(X\right)=\ausd$.

Dann ist $p \in \ausd=\ab\left(X\right)$, es gibt also eine endliche Teilmenge $X^\ast \subseteq X$ mit

\begin{displaymath}p \in \ab\left(X^\ast\right),
\end{displaymath}

folglich ist $\ab\left(X^\ast\right)=\ausd$, also ist $X^\ast$ nicht syntaktisch widerspruchsfrei. $\Contradict $
\qed

2.7.2 Vollständigkeit

Die Vollständigkeit einer Menge besagt die Umkehrung der Widerspruchsfreiheit, d.h.

semantisch:
alles was wahr ist, ist beweisbar.
klassisch:
von zwei Aussagen A und nicht A ist stets eine beweisbar.
syntaktisch:
wenn eine nicht beweisbare Aussage als Axiom genommen wird, so ist die Widerspruchsfreiheit verletzt, d.h. alles wird beweisbar.

Definition 2.7.4 (Vollständigkeit)

1.
$X \subseteq \ausd$ heißt semantisch vollständig genau dann, wenn $\ab\left(X\right)\supseteq \ag$
2.
$X \subseteq \ausd$ heißt klassisch vollständig genau dann, wenn für jedes $H \in \ausd$ gilt $H \in \ab\left(X\right)$ oder $\neg H \in \ab\left(X\right)$.
3.
$X \subseteq \ausd$ heißt syntaktisch vollständig genau dann, wenn für jedes $H \in \ausd$ gilt: Wenn $H \notin \ab\left(X\right)$, so $\ab\left(X \cup \left\{H\right\}\right) = \ausd$

Satz 2.7.5

1.
$\axa$ ist semantisch widerspruchsfrei und semantisch vollständig.
2.
Es gibt im AK keine klassisch vollständige und klassisch widerspruchsfreie Menge X.

Beweis der zweiten Behauptung
Wir zeigen:

Wenn $X \subseteq \ausd$ klassisch vollständig ist, so ist X nicht klassisch widerspruchsfrei

Sei X klassisch vollständig, dann ist

\begin{eqnarray*}p \in \ab\left(X\right) & \mbox{oder} & \neg p \in \ab\left(X\right)
\end{eqnarray*}


Fall 1:
$p\in\ab\left(X\right)$
Es ist $\ab(X)=\ausd$, da in p jeder Ausdruck eingesetzt werden darf, also ist X nicht syntaktisch widerspruchsfrei, also nach Satz [*] nicht klassisch widerspruchsfrei.
Fall 2:
$\neg p \in \ab\left(X\right)$
Es ist

\begin{displaymath}\neg p\left(p/_{\displaystyle\neg p}\right)=\neg\neg p\in\ab(X)
\end{displaymath}

also $\neg p,\neg\neg p\in\ab(X)$, d.h. X ist ebenfalls nicht klassisch widerspruchsfrei.
\qed

Satz 2.7.6

1.
Wenn X semantisch vollständig, so ist X syntaktisch vollständig.
2.
Umkehrung gilt nicht

Beweis der ersten Behauptung
Es sei X semantisch vollständig, d.h. $\ag\subseteq\ab(X)$ und $H\notin
\ab(X)$. Folglich ist $H \notin \ag$, also

\begin{displaymath}\ab\left(\ag\cup\left\{H\right\}\right) =\ausd.
\end{displaymath}

Also

\begin{displaymath}\ab\left(X\cup\left\{H\right\}\right)=\ab\left(\ab\left(X\cup...
...ht\}\right)\right)\supseteq\ab\left(\ag\cup\{H\}\right)=\ausd
\end{displaymath}

d.h. X ist syntaktisch vollständig. \qed

Beweis der zweiten Behauptung
Betrachten: $X = \left\{\neg p\right\}$.

$\ab\left(X\right) = \left\{\neg H\vert H \in \ausd\right\} \subset \ausd, X$ syntaktisch widerspruchsfrei.

Nach LINDENBAUM existiert eine Menge Y mit

1.
$Y \supseteq X = \left\{\neg p\right\}$
2.
Y ist syntaktisch widerspruchsfrei und syntaktisch vollständig
3.
$\ab\left(Y\right) = Y$

Y ist nicht semantisch vollständig, d.h. $\ag \not\subseteq \ab\left(Y\right)$

sonst wäre $\axa \subseteq \ab\left(Y\right)$ und $\neg p \in Y \setminus \axa \subseteq Y$ d.h. $\ab\left(\axa \cup\left\{\neg p\right\}\right) = \ausd
\subseteq Y$

d.h. Y - nicht syntaktisch widerspruchsfrei $\Contradict $. \qed

2.7.3 Nichtableitbarkeit

Im Zusammenhang mit Satz [*] sind wir auf das Problem gestoßen

Wie beweist man $p\notin\ab\left(\{p\rightarrow p,\neg(p\rightarrow p)
\} \right)$ ?

allgemein:

Wie zeigt man $H\notin
\ab(X)$ ?

Für den Spezialfall $X=\axa$ ist das leicht, denn wegen $\ab(\axa)=\ag$handelt es sich dann um die Frage $H \notin \ag$, das können wir entscheiden.

Wenn wir statt des Ableitens das Folgern betrachten, d.h. die Frage $H\notin\fl(X)$? betrachten, so ist klar, wie sie zu beantworten ist: Wir müssen ein Modell von X finden, das H falsch macht, dann ist $H\notin\fl(X)$.

Diese Methode können wir zum Beweis von $H\notin
\ab(X)$ nutzbar machen, wenn es uns gelingt, das Ableiten semantisch (durch das Folgern) zu charakterisieren.

Wir ersetzen die klassische logische Matrix $\left[\left\{\W,\F\right\},\left\{\W\right\},\non,\et,\vel,\seq,\aeq\right]$durch eine Matrix $\mu = \left[M, M^\ast, \Phi_1, \Phi_2, \ldots, \Phi_5\right]$und definieren

Satz 2.7.7
$\abe\left(\ag_\mu\right) = \ag_\mu$ für jede logische Matrix $\mu$Beweis
Man zeigt durch Induktion über H:
Wenn $H = H_1\left(p/_{\displaystyle H^\ast}\right)$ und $ H_1 \in \ag_\mu$, so $H \in \ag_\mu$. \qed


Bemerkung
Für $\aba$ gibt es keinen äquivalenten Satz, betrachten wir als Beispiel die Matrix $\mu_0 = [\left\{\W, \F\right\},\left\{\W\right\},\non,\et,\vel,
\Phi_4, \aeq]$


next up previous contents search
Next: 2.8 Dualitätstheoreme Up: 2. Aussagenlogik Previous: 2.6 Ableitbarkeit
© 1995-2000 Prof. Peter H. Starke (starke@informatik.hu-berlin.de) und Stephan Roch (roch@...)

Zuletzt geändert am: 2000-07-06