$ 13. Die Unabhängigkeit und Vollständigkeit des Systems. 31

Denn was die erste Regel betrifft, so ist klar, daß durch Einsetzen
eines Ausdrucks an Stelle einer Variablen der Wertevorrat für” die
Variablen jedenfalls nicht erweitert werden kann. Und wenn wir mit
Hilfe der zweiten Regel aus zwei Formeln X und HU die Formel 3
ableiten, so überträgt sich die Eigenschaft, immer den Wert 0 zu liefermn;
von jenen beiden Formeln auf die abgeleitete Formel; denn da die
Formel X immer den Wert 0 ergibt, so hat % immer den Wert 1, also
hat X denselben Wert wie B, und hiernach hat B ebenso wie AB
immer den Wert 0.

Wir sehen somit, daß tatsächlich mit Hilfe unseres Kalküls nur
solche Formeln erhalten werden, die bei der arithmetischen Deutung
immer den Wert 0 liefern. Indem wir dies feststellen, sind ‚wir aber
schon am Ende unseres Nachweises. Denn offenbar können zwei Formeln,
die dadurch aus X und X hervorgehen, daß man für X beide’Male
dieselbe Aussagenverknüpfung einsetzt, nicht beide die KEigenschaft
besitzen, immer gleich 0 zu sein; vielmehr wenn die eine immer den
Wert 0 besitzt, so hat die andere immer den Wert 1.

8 13. Die Unabhängigkeit und Vollständigkeit des Systems.

An die Frage der Widerspruchsfreiheit, die wir für das Axiomen-
system bejahend beantworten konnten, schließt sich die weitere Frage
an, ob die Axiome alle unabhängig voneinander sind oder ob man nicht
das eine oder das andere dieser Axiome entbehren kann!.

Die Antwort lautet, daß das Axiomensystem tatsächlich der Forde-
rung der Unabhängigkeit genügt.

Wir zeigen zunächst, daß die Formel a) XvX v X nicht aus den
übrigen Axiomen abgeleitet werden kann, und zwar auch dann nicht,
wenn man die Formel X v X (oder auch X v X) als Axiome hinzu-
nimmt, so daß also die Formel a) in dem axiomatischen System nicht
durch die einfachere XX ersetzt werden kann.

Der Beweis geschieht wieder mit Hilfe einer arithmetischen Inter-
pretation. Wir nehmen als Werte für ‚die Variablen X , Y.Z-. e
Restklassen 0,1,2 modulo 4. Das Zeichen ‚,v‘“ soll wieder die ge-
wöhnliche Multiplikation darstellen, und X erklären wir durch die Fest-
setzungen: 0 bedeutet 1, 1 bedeutet 0, 2 bedeutet 2.

Man kann nun verifizieren, daß die Formeln Xv.X, b), c), d) bei
der gegebenen Deutung der Variablen {mmer die Restklasse 0 ergeben,
und diese Eigenschaft überträgt sich bei der' Anwendung der beiden
Regeln auf alle aus jenen 4 Formeln abgeleiteten Formeln, was man
auf gleiche Weise wie vorher beim Beweise der Widerspruchsfreiheit

1 Diese Frage der Unabhängigkeit des Axiomensystems ist ebenfalls in
der S. 23 zitierten Arbeit von P. Bernays, Axiomatische Untersuchung usw. ge-
löst worden.